n-queens Part 1: Bitwise Bitzkrieg

It is rarely a good idea to tell a story from beginning to end. There are, of course, exceptions, as George Lucas has made it a point to demonstrate with Star Wars and Indiana Jones. Following his example, this story starts somewhere in the middle, with:

Q=function(n){
s=0,c=(1<<n)-1,
f=function(l,o,r,c){
var v=~(l|o|r)&c;
while(v>0){
var t=-v&v;
v=v^t;f((l|t)<<1,(o|t),(r|t)>>1,c)
}
o==c&&s++
};
f(0,0,0,c);
return s
}

The one hundred and fifty four characters above make up a bitwise backtracking solution to the algorithmic puzzle known as n-queens. They weren't written for legibility in this form, but in a *failed attempt to fit a blazing fast javascript solution to a spectacularly complex computer science problem into a tweet. Every semicolon in the code is essential. Every space between lines is discardable. It fits in a text message. 

Q=function(n){s=0,c=(1<<n)-1,f=function(l,o,r,c){var v=~(l|o|r)&c;while(v>0){var t=-v&v;v=v^t;f((l|t)<<1,(o|t),(r|t)>>1,c)}o==c&&s++};f(0,0,0,c);return s}

These lines of code are the product of an exhilarating four hour sprint during which my pair, John S. Dvorak and I wrapped our head around bitwise operators, attempting to design and write a solution to n-queens. What is n-queens?

  • Imagine a 'chess-like' board, of size n x n, where n is any positive integer
  • A solution is defined as a configuration n queens on the chessboard, placed such that they are unable to attack each other. 
  • An algorithm to solve n-queens for a board size n must determine how many solutions exist for a given n. 

It takes a moment for the computational intensity of the problem to sink in at first glance. The number of spots on a board is n squared. The number of possible configurations of n queens on an n x n sized board is n squared choose n. On an 8 x 8 board, that works out to 4,426,165,368 possibilities. In that problem space there are only 92 solutions. 

So how long does it take the algorithm John and I wrote to tackle that problem space and report back that there are 92 solutions? On our Mac workstations at Hack Reactor, less than a millisecond. What about a 10 x 10 board, with 17.3 trillion possibilities? How long do we take to return the 724 problems in this case? Also about a millisecond. It gets a little slower from there on out. To find the 2,680 solutions on a 11 x 11 board takes a whole 5 milliseconds. We were forgiving, at first. After all, 11 x 11 is a 1.27 quadrillion position problem space. 

As enchanted as we remain by our n-queens solution, and the things we can do with it, both John and I know that we could not have done this without at least a little help from circumstance. It all started with a Sieve of Atkin

To be continued.

A deep dive into data structures

A pessimist sees the difficulty in every opportunity;
an optimist sees the opportunity in every difficulty.
— Winston Churchill

Once in a while, a Hack Reactor sprint prompt will come along that stands out from the pack. You know when it happens, but you don't know why. Some part of the instructions carry - you will pardon my French -  a seductive je ne sais quoi that promises to take you all the way down a rabbit hole with a cognitive wonderland waiting on the other end. My first such experience was the "Nightmare Mode" section of the data structures sprints. 

The basic and extra credit requirements of the data structures sprints were by no means trivial to the many of us who were new to software engineering. They involved understanding and implementing stacks, queues, linked lists, trees and hash tables (yes, including collision handling), from scratch, in javascript. In the case of stacks and queues, we were not allowed to use arrays, for want of making things "too easy". After getting through this teaser on how computers fundamentally store our stuff, the "Nightmare Mode" problem caught my eye: design a data structure that, for a given hand of scrabble letters, will tell you every single valid word that you can make. 

This problem breaks down into two pieces:

  1. Calculating unique string permutations, so as to know every way in which we can combine our letters.
  2. Searching the dictionary (100,000 - 270,000 items), depending on which one strikes your fancy.

By this point, we were familiar with the concept of algorithmic time complexity, thanks to workshops by Hack Reactor faculty, and a student presentation by a fellow Hack Reactant, Selby Walker, graphically comparing different sorting algorithms

It was obvious that iteratively checking whether every combination of letters matched every word in the dictionary, stored in an array, would be inefficient. With the dictionary itself being 3 MB as a plaintext file, I didn't see how any of the structures we had implemented up to that point could help solve the problem. 

While my pair for this sprint, Nima Mehanian and I were studying lists earlier in the day, we came across Bloom filters, a fascinatingly eccentric data structure whose applications include identifying elements in Google's BigTable. Bloom filters work by running multiple hash functions on each input element, and applying a '1' or 'true' value to the resulting indices of every function, in a massive binary array. 

There is a lot of math behind them, to reduce the probability of (but not prevent), data collisions in the array. To help me get a better idea of whether a Bloom Filter was right for the job, I needed to crunch some numbers. To help do this, I whipped up a little "Bloom calculator" in javascript:

var bloomCalculator = {
len: undefined,
elements: undefined,
error: undefined,
filters: undefined,
optimize: function(elements, errorD) {
if (arguments) {
this.error = 1/errorD;
this.elements = elements;
}
this.len = - (this.elements * Math.log(this.error)) / (Math.pow(Math.LN2,2));
this.filters = (this.len / this.elements)*Math.LN2;
return [this.len.toLocaleString(), this.filters];
}
};

The Wikipedia page on Bloom filters has a great explanation of the relationship between the input size of your filter, the size of the binary array, the number of hashing functions it uses, and the resulting probability of a false positive lookup. The code above assumes that you have in mind the number of elements going into your array (elements), and the odds of an error you are willing to tolerate. In our case, with a dictionary size of 270,000, I was willing to tolerate an error probability of 1 in 1,000,000. After declaring the code above in the Chrome console, I ran:

bloomCalculator.optimize(270000,1000000)

//returning:
["7,763,897.286", 19.931568569324174]

This meant that to store my dictionary in an ideal bloom filter, I would need a binary array over 7 million elements in length, with 20 independent hashing functions. Even though this array could theoretically be smaller in size than the 3MB plaintext ASCII dictionary (7,763,897 bits = 970,487 bytes = 948 kilobytes), the engineering seemed to o complex to solve the problem. As excited as I was to have discovered Bloom filters, Hack Reactor's Marcus Phillips told me there was a better way, leaving me to find it.

As it turned out, the 'better way' turned out to be deterministic acyclic finite state automation - a topic for another day.

An introduction to Hack Reactor

Imagine that you are taking a course in escapology, taught by the great Harry Houdini himself. The field is alien to you, so you feel both comforted and intimidated to work with the master of art. Today, you are going to learn to unshackle yourself from lead weights. Most teachers would start off with several hours of lectures, followed by some guided practice on the many approaches to using various lock picking tools. Not Harry Houdini. He gives you a 15 minute introduction to the problem, his brilliance allowing him to concisely convey just enough information to give you a shot at escaping the trap. He then straps the waits to your feet, and has you jump into a lake, sinking straight to the bottom.

For some reason, you don't panic, even though you have never, ever, dealt with any situation remotely like this. Before you know it, in a matter of moments, the panic is replaced by resolve. You remember what Houdini taught you, break free of your chains so fast that you don't know where you found the strength or skill to do so, and you rush to the surface, catching a breath of fresh air. You've barely caught your first breath before you are overcome with an implacable wave of excitement and accomplishment. Your teacher, the master escapologist, is waiting for you, and leaves you no time to absorb the implications of what you were able to learn in so little time - It's time to move on to the next lesson.  

In a literal sense, this never happened. Metaphorically speaking, some of us go through this every day. Just substitute references to escapology with javascript, the acts of jumping into, and escaping from the "deep end" with sprints. You now know I feel learning with the elite engineers of Hack Reactor - the Harry Houdinis of javascript. They throw us in the deep end with access to the best tools, and in the blink of an eye imbue knowledge and skills that take us another step closer to mastering software engineering. 

Whether we are redesigning the Google home page pixel for pixel, rewriting the Underscore.js library from scratch, or rebuilding archive.org in Node.js, each sprint takes us from 0 to 60 in 48 hours. As we get started, we ask questions like "Node? What's Node?". Two days later, we're trolling for NPM modules like socket.io and express to expand the capabilities of or server side code, or just make it more readable and easy to write.