JavaScript – Mike Johnson

React.JS

React and Angular are popping up a lot in job interviews these days. I decided to try React, since it is rumored to be the simpler of the two. So I created the old Chinese stone game Go in a Codepen. Normally I post code and talk about it in this case, but I think I will just let the Codepen speak for itself. Here, I report my experiences.

There is a lot of learning material out there, but the best resources start out right away with productive examples that get you working quickly. This tutorial video from Traversy Video does a very good job. I used this React demo from Facebook to model my architecture after.

The least trivial part of the game was the capture algorithm. The game engine must figure out if a newly placed stone results in another stone being surrounded. To figure this out, I implemented a recursive breadcrumb algorithm. The method searches recursively in four directions, resulting in a wide descending tree, but marks visited spots on the matrix to prevent infinite recursion. If at any point an empty space (liberty, in game terms) is found, the call stack starts bubbling up with that information. The recursive call will say whether or not a liberty was ever found. If it was, I run a second method to erase all visited points on the matrix, otherwise I run a different method to restore the marked spots back to original.

Here is my reaction (?) to React :

JavaScript is fun for web programming in limited amounts, but Object-Oriented frameworks like ES2015, Babel, etc. inevitably make it worse. this.method.bind(this)? Yucko.
Hidden inherited methods are traps waiting to happen. My IDE (Codepen) did not alert me to inherited methods, so this may be my own fault for not using a JetBrains tool or some such. Pick unique method names just in case.
I don’t really see the payoff. I understand the principle of data flow and limiting state on classes, but a real class-driven language does this in a more flexible way without need of a framework.

I know a little bit of CSS and HTML, so I was able to decorate it a bit, so that it kind of looks like an old wood board.

JavaScript Puzzles

I found my new grind. Goodbye Hearthstone. Goodbye World of Warcraft.

Hello, CodeFights.

Arcade Mode was a lot of fun for me today. In The Labyrinth of Nested Loops, I found this little gem :

We define the weakness of number x as the number of positive integers smaller than x that have more divisors than x.

It follows that the weaker the number, the greater overall weakness it has. For the given integer n, you need to answer two questions:

what is the weakness of the weakest numbers in the range [1, n]?

how many numbers in the range [1, n] have this weakness?

Return the answer as an array of two elements, where the first element is the answer to the first question, and the second element is the answer to the second question.

CodeFights

What fun!

This feels like I could brute-force it with a nested loop is and suffer the $O(n^2)$ performance. If I manage to solve it using only sequential loops on the other hand, it would be $O(n)$ no matter how many loops I used. I think I scored somewhere in between, maybe $O(n \log(n))$ depending on what you believe about the inner loops in the following sections.

The problem can be decomposed by first finding the number of divisors, then counting weakness counts (not a typo – counts of counts!), and finally finding the weakest among those.

Finding divisors can be done in many ways. I use variable-stride loops to increment every spot where a given number is a divisor.

    // Find the number of divisors 
    divisors = new Array(n+1)
    divisors.fill(0)
    for (var i=1; i<=n; i++)
        for (var j=i; j<=n; j+=i)
            divisors[j]++

Next, I want a count of all numbers that have a given number of divisors. This segment of code will end with a variable called divisorsCounts, where divisorsCounts[3] = 4 if there are exactly 4 numbers in range that have 3 divisors.

    // Count the counts
    divisorsCounts = new Array(n) // probably overkill
    divisorsCounts.fill(0)
    // Compute the weakness
    weakness = new Array(n+1)
    weakness.fill(0)
    greatestWeakness = 0

The array divisorsCounts does not need to be that large, but it’s only memory, right? Apparently something called the Divisor Function $\sigma_0(i)$ has an upper limit of $n/2$ . I’m no number theorist, but I buy it. A factor of two is not even worth typing Math.floor() for, so I’ll leave the code alone as it now looks clean.

    for (var me=1; me<=n; me++) {
        divisorsCounts[divisors[me]]++
        for (var j=divisorsCounts.length-1; j>divisors[me]; j--)
            weakness[me] += divisorsCounts[j]
    }

It is key here that I fill the divisorsCounts at the same time as I calculate weakness. At any given point in time I have only counted the divisors up to the number I am examining. For a given number m, weakness is the number of divisor counts greater than divisors[m]found in numbers smaller than m.

I can optimize these loops by shrinking divisorsCount. JavaScript creates sparse arrays by default, and their length is determined by the highest-indexed element. The inner nested loop will be shortened.

    // Count the counts
    divisorsCounts = []
    // Compute the weakness
    weakness = new Array(n+1)
    weakness.fill(0)
    greatestWeakness = 0
    
    for (var me=1; me<=n; me++) {
        divisorsCounts[divisors[me]] = 
            (divisorsCounts[divisors[me]] | 0) + 1
        for (var j=divisorsCounts.length-1; j>divisors[me]; j--)
            weakness[me] = (divisorsCounts[j] | 0) + weakness[me]
    }

The pipes handle undefined elements (note that x + undefined will never produce a number). With n=500, divisorsCount is only 25, so this may improve performance quite a bit.

Finally, I must track the greatestWeakness and how many times it is found.

Here it is in all of its beauty.

function weakNumbers(n) {
    // Find the number of divisors 
    divisors = new Array(n+1)
    divisors.fill(0)
    for (var i=1; i<=n; i++)
        for (var j=i; j<=n; j+=i)
            divisors[j]++
            
    // Count the counts
    divisorsCounts = []
    // Compute the weakness
    weakness = new Array(n+1)
    weakness.fill(0)
    greatestWeakness = 0
    greatestWeaknessCount = 0
    
    for (var me=1; me<=n; me++) {
        divisorsCounts[divisors[me]] = 
            (divisorsCounts[divisors[me]] | 0) + 1
        for (var j=divisorsCounts.length-1; j>divisors[me]; j--)
            weakness[me] = (divisorsCounts[j] | 0) + weakness[me]
        if (greatestWeakness < weakness[me]) {
            greatestWeakness = weakness[me]
            greatestWeaknessCount = 1
        } else if (greatestWeakness == weakness[me]) {
            greatestWeaknessCount++
        }
    }
    
    return [greatestWeakness, greatestWeaknessCount]
}

CodeFights is awesome! Come find me! Come fight me!

Functional JavaScript

Fun Fun Function is a wonderful video series for learning JavaScript and functional programming. I decided to try my own Map/Reduce filter in JS and uploaded it to my toybox. Some random notes of things I learned along the way:

JavaScript has four different variable scoping modifiers: let, var, const, and default (no modifier). let scopes to a block (like a loop), const also scopes to a block and prevents reassignment (though referenced objects may still be mutable), var scopes to a function, and the absence of modifiers indicates a global variable. As always, beware of hoisting which allows a variable to be scoped after it has already been used in code. Not all of these are available in all versions of JavaScript.
Running his examples using babel as an ES2015 transpiler is not trivial. To get it to run, I had to do:
- npm install –save-dev babel-cli
- npm install –save-dev babel-preset-es2015
- export PATH=”./node_modules/.bin:$PATH”
- babel –presets=es2015 medalOTM.js | node
JS map takes one parameter and returns one result. This is what you would expect of a mapping or relation.
JS reduce is more complex. It reduces the entire pipeline to a single object. This function takes a single callback function parameter and an optional initial value.
- The initial value can be thought of as the starting point for an object to be built up by the reduce callback over many iterations of the pipeline. Our value is just {}, an empty object.
- The callback builds up the object. It takes the object to be built up as the first parameter, and it returns a new value for that same object. The second parameter consists of the current pipeline element.
- The general idea is to use each pipeline element to build up the object.

Functional is fun! And JavaScript is deep!

Thanks to Kos on StackOverflow for helping me with my basic command-line syntax issues.

JavaScript Promise

I was mildly surprised to learn that the Promise class has been built-in to JavaScript. I was trying to fully grok the functional library Bacon when I ran into the JavaScript documentation for Promise. A Promise looks like this :

var p = new Promise( /* executor */ function(resolve, reject) { ... } );

A Promise can be in one of three states at all times : Pending, Fulfilled, or Rejected. This is actually not a new idea. Ever play with Java Scanner? Its hasNext() method returns a boolean indicating the presence of another token on the data stream. But one must understand that some streams, such as network packet streams, may postpone answering while waiting for a slow client. Thus, hasNext() returns true if another packet of data has been received, false if the client has disconnected, and simply blocks (does not return) if the network client is being quiet. This corresponds to Fulfilled, Rejected, and Pending. A Promise is much more explicit.

The Promise constructor calls function before anything else. function is expected to spawn asynchronous work but not call resolve or reject immediately. p is created only after function has returned. Once the asynchronous work completes, function will call resolve or reject, which notifies the Promise object of the new state.

Here is an example that fetches tweets from twitter using a Promise to handle the asynchronous call.

var http = require('http')

url = 'http://maps.googleapis.com/maps/api/geocode/json?address=New York, NY, U.S.A' 

//url = 'http://maps.googleapis.com/maps/api/geocode/json?address=Mungalatoid'

var p = new Promise((resolve, reject) => {
	console.log("Kicking off an HTTP request")
	// kicks off an asynchronous HTTP request
	http.get(url, (response) => {
		var data = ''
		console.log('HTTP response received')
		response.on('data', (buffer) => {data += buffer})
		response.on('end', () => {
			var twitterObject = JSON.parse(data)
			if (twitterObject.status == 'ZERO_RESULTS') {
				reject(data)
			} else {
				resolve(data) 
			}
		})
		response.on('error', () => {reject('HTTP Error')})
	})
	console.log("HTTP request has been made")
})

console.log("Evaluating Promise")
p.then(
	(resolvedValue) => {console.log("Promise resolved " + resolvedValue)}
).catch(
	(failureReason) => {console.log("Promise rejected " + failureReason)}
)

Try changing between the URLs to see what happens when Google cannot find a match for the place name. Notice that Evaluating Promise is printed before the http.get callback function is called.

Mind you, this whole thing is much simpler just using node’s fetch, which actually returns a promise given a URL.

Mike Johnson

Thoughts on Tag: JavaScript

Recent

Buzz

React.JS

JavaScript Puzzles

Functional JavaScript

JavaScript Promise

GOOD READS

Mike Johnson

BUZZ