What You Need to Know for Solving the Advent of Code Puzzles Blazingly Fast with JavaScript
Solving the year 2016 day 11 puzzle in half a minute
The purpose of this article is to show you some programming techniques in JavaScript (useful for other languages) that you will need when executing brute-force algorithms. Without using these techniques, your computer may run out of memory and/or your processor will be stressed for several minutes (even hours).
I said “techniques”, not “libraries”.
You will be able to test this subject, in just a few seconds, in your browser console.
Advent of Code
For years, I’ve heard about the Advent of Code programming puzzles, but until two weeks ago I hadn’t addressed it. Now I’m addicted.
I’ve started from the very first puzzle — year 2015 day 1 — using only plain JavaScript, no libraries (excepting when the puzzle involves creating md5 hashes).
Even without using the techniques that I am going to show you today, I got fast execution times. Most solutions took around 25ms — note that the Deno startup time is around 20ms, and it had to read the input file.
By the way, I am publishing my solutions on Github. I tried to make the code very readable, self-explained.
The year 2016 day 11 puzzle
The year 2015 was completed and I’ve started the year 2016. Everything was fine till I reached day 11. My first trying, using recursive functions, crashed by stack overflow almost immediately. Then I discharged using recursive programming and refactored the code using loops: after 2 minutes the computer ran out of memory — running it at the browser, the JS heap size goes beyond 700 MB.
Googling about this specific puzzle, I realized that some people in Github had given up on it — they had solutions from day 1 to day 10 only. Also, I found this funny blog, Advent of Code Day 11–Admitting Defeat, where the author states this:
I did eventually permit myself to look at the shared solutions on Reddit to see what I could learn from other people’s answers, but so far the main thing I learned is that they are a lot cleverer than me!
In another blog, the author decided to gave up because his solution was still running after hours and his kid wanted the computer for playing video game:
My solution works fine for the small example, but for the actual input, it takes forever. Seems that with every component you add in the input, the amount of iterations skyrocket (I am not even going to calculate how many).
So, if the Advent of Code wants a good fight, I am all in!
NOTE 1
AOC considers that each day has one puzzle, made of two parts. This article considers that each day has two puzzles (the first and the second) — plus the example.
Pure brute-force algorithm/code
I decided to use only generic optimizations of the brute-force code, because, being generic, could be used for solving other puzzles.
Making specific optimizations (aborting some paths based on my guesses) is error-prone and demands time to study the specificities of this puzzle. It would be done only if necessary. And it wasn’t!
The algorithm is the same
We use the same algorithm to solve the example, the first and the second puzzles.
But we must use an improved implementation of the algorithm, because the computing increases dramatically.
This puzzle has a feature that makes it harder than all previous ones: DYNAMISM.
For example, in the year 2015 day 24 puzzle (balancing the weight of packages), you face a lot of combinations (states) and just pick the best. A well written recursive function or loop structure automatically avoids trying the same combination again.
In our current puzzle, there is a dramatic difference:
We must keep track of the already processed nodes (states) to not repeat them again. Or else, the program works like someone lost in a maze, passing on the same places over and over again.
Now you would argue that writing a simple list to store the already processed nodes is pretty simple! Writing this list is pretty simple. But running this list (checking its items) ranges from superfast to nightmare/impossible, according to its size.
The algorithm in pseudocode
// pseudocode for the puzzle //
var nodesToProcessNow = [ ]
var nodesToProcessLater = [ ]
const nodesAlreadyProcessed = [ ]
var targetWasFound = false
function main() {
let numberOfSteps = -1
const startingNode = createNode("using the input data")
nodesToProcessLater.push(startingNode)
while(! targetWasFound) { // outer loop
numberOfsteps += 1
nodesToProcessNow = nodesToProcessLater
nodesToProcessLater = [ ]
while(targetWasFound) { // inner loop
const node = nodesToProcessNow.shift()
if (node == undefined) { break } // empty list
processNode(node)
}
}
console.log("answer:", numberOfSteps)
}
function createNode(...) { ... }
function cloneNode(node) { ... }
function processNode(node) {
if (node reaches target conditions) { targetAsFound = true; return }
nodesAlreadyProcessed.push(node)
for each possible child of node {
const newnode = cloneNode(node) // CLONING IS A MUST!!!
// -> change here some data of the newnode <-
if (friesMicrochip(newnode)) { continue }
if (nodesAlreadyProcessed.includes(newnode)) { continue }
nodesToProcessLater.push(newnode)
}
}
function friesMicrochip(node) {
// makes the necessary checks
}
main()This code/algorithm processes nodes by layers, starts with the home node, then gets all nodes that are one step far away from the home node; then processes all nodes that are 2 steps far away from the home node, and so on.
This pseudocode is simple, short and correctly implements the algorithm… but it is incomplete. It shows the flow of the nodes, but not the data structure of a node.
The structure of the node
The puzzle doesn’t ask us about the best path (first move up carrying A and B, second move down carrying C…). So, we don’t need to store the paths, we are not going to make any data structure for the paths.
What we need is an efficient data structure for the node. We could think of using a traditional formal OOP object:
function Node() { // the numbers mean the floors
this.elevator = 3
this.generatorA = 0
this.microchipA = 1
...
}Seems nice. But, for intensive computing, arrays are more suitable because we can iterate them (for each item in list). Imagine if we had 50 generators and 50 microchips, writing specific checks for each combination…
function checkNode(node) {
if (node.generatorA == 3 && node.microchipA == 3 &&
! node.generatorB == 3 || node.microchipB == 2 ...
return true
}
// just DON'T!OK, let’s try arrays. My first attempt, inspired by the diagrams of the AOC website, was this:
const node = [ // a list that contains onelist for each floor
[ "", "", "", "", "" ],
[ "", "", "", "LG", "" ],
[ "", "HG", "", "", "" ],
[ "E", "", "HM", "", "LM" ]
]I didn’t like it!
We know that the outer list will always contain 4 lists, no less, no more. We know that each inner list will always contain 5 items (only small strings), no less, no more.
We know… but JavaScript *doesn’t know*. Maybe he reserves room if we want to expand a list, maybe he has to track the type of values of each item.
JavaScript is smart, fast and powerful. But we should not abuse it.
What I really mean is 1,073,741,824 nodes.
The total nodes/combinations/states for the example is 1024 (4 x 4 x 4 x 4 x 4). JavaScript happily handles that amount, no matter the data structure that you use.
But for the second puzzle, you face, keeping the same 4 floors, the elevator plus 7 chemicals (each chemical means a generator and a microchip). The total is 4 x 4 x 4 x … OK. It is four raised to the fifteenth power: more than one billion nodes.
Now you know why your computer ran out of memory or was so slow.
Remember that we need to store each processed node, so we don’t get trapped in a maze repeating the same paths.
That node structure made with nested lists of strings is definitely NOT good for storing one billion nodes.
NOTE 2
I will be using diagrams and some code samples related to the puzzle example (elevator plus 2 pairs of chemicals) that, being small, are nice for concept demonstration.
But we will be addressing the solution for the second puzzle (elevator plus 7 pairs of chemicals).
The first optimization — no, it is a single dimension list
Let’s check again that diagram from the AOC website. It has two catches!
- If we just convert the diagram to a nested list structure (like we did before): the first inner list matches the last floor of the building. And the last inner list matches the first floor of the building ;)
2. We don’t need the first column (green color), that marks the floor number. It is just a damn label! Now, if you erase the damn label, you realize that for each other column, just one cell is used. One cell, no more, no less. So…
For our eyes, the diagram above is the best representation of the data. But our computer prefers something more discreet:
// E HG HM LG LM
const node = [ 1, 2, 1, 3, 1 ] // each number means the number of the floorOK. This is halfway to paradise!
- Instead of nested arrays, now we have a single array!
2. Instead of strings, we have numbers! And we all know that computers love numbers. Strings are more complicated to store in memory and process than numbers.
But, I am still NOT happy. I don’t like the idea of my computer storing one billion of dynamic arrays and searching them 50 million times for solving the second puzzle.
Fifity million searches on nodesAlreadyProcessed
As the second puzzle(*) takes a bit to run (30s), I decided to print partial feedbacks, so the user knows that the program is running fine.
(*) We’ve skipped the first puzzle directly to the fun — second puzzle.
The picture above shows the program processing more than 30 queues, with 150,000 nodes in average per queue. Now if we consider that each processed node generates 10 child nodes (we must check if this child node was already processed or not), this means 30 x 150,000 x 10 (45 million) searches — just for what the picture shows. We can round it to 50 million searches.
50 million is not a small number, but we can handle it searching a small list. The problem is that the list grows to more than one billion nodes.
The first problem is storing big data. The second problem is searching it fast.
The second optimization — no, it is a string
I don’t know how you feel about this. And I don’t know how JavaScript feels about this. But I prefer to store and process 1 billion strings than one billion lists. Maybe it just my prejudice. Maybe JavaScript sees one billion strings and says, “Let’s make room!”. Maybe JavaScript sees one billion lists and says “OH NO! One billion of dynamic arrays. Help me god!”.
// OLD node data structure
// E HG HM LG LM
const node = [ 1, 2, 1, 3, 1 ] // each number means the number of the floor
// NEW node data structure
// E HG HM LG LM
const node = "12131" // each digit means the number of the floorAs the number of the floor is always 1 digit (there is no tenth floor), a string is perfect to store data: each character matches one data field!
Third optimization —no, it is an integer
Looking at that string. What it reminds you? It looks a lot like a binary number, right? Well, if it had only “0”s and “1”s, we could
treat it as binary number and convert it to a decimal number, which is extremely better to store and process than a string!
I liked that!
And I will do it. It cannot be a binary number but can be a base 4 number.
A base 4 number is made by 4 characters: 0, 1, 2 and 3.
“But the puzzle building numbers its floors from 1 to 4!” — you tell me. Yes. But they are just damn labels ;)
// OLD node data structure
// E HG HM LG LM
const node = [ 1, 2, 1, 3, 1 ] // each number means the number of the floor
// NEW node data structure
// E HG HM LG LM
const node = "12131" // each digit means the number of the floor
// we decrase each value by 1, so the floors now range from 0 to 3
const node = "01020" // each digit means the number of the floor
// FINAL node data structure
const node = parseInt("01020", 4) // number 72 is the value of the nodeLet’s make it absolutely clear. The number 72 means:
- the elevator is on floor 0
- the generator H is on floor 1
- the microchip H is on floor 0
- the generator L is on floor 2
- the microchip L is on floor 0
In case you don’t believe me, please try this:
(72).toString(4) // -> "1020"
// ops, we are missing the starting zero:
(72).toString(4).padStart(5, "0") // -> "01020"Seems magical!
// Scheme of the node as string:
// node[0] : floor of elevator
// node[1] : floor of generator A
// node[2] : floor of microchip A
// node[3] : floor of generator B
// node[4] : floor of microchip B
// Converion of base 4 string-number
// to unsigned integer (decimal):
"00000" : 0 // lowest number
"00001" : 1
"00002" : 2
"00003" : 3
"00010" : 4
"00011" : 5
"00012" : 6
"00013" : 7
"00020" : 8
"00021" : 9
"00022" : 10
...
"01020" : 72
...
"33331" : 1021
"33332" : 1022
"33333" : 1023 // highest numberWe will come back to the table above.
Just don’t forget: the first floor is zero, not one!
WARNING
Those conversions are very cool but don’t work with big numbers, for the second puzzle I had to split the number/string in two, make two conversions and reassemble them:
function decimalFromNode(node) { // for 15 characters!
const a = parseInt(node.substr(0, 7), 4)
const b = parseInt(node.substr(7, 8), 4)
return a * (256 * 256) + b
}
function nodeFromDecimal(decimal) { // for 15 characters!
const block = 256 * 256
const intA = Math.floor(decimal / block)
const intB = decimal % block
const strA = intA.toString(4).padStart(7, "0")
const strB = intB.toString(4).padStart(8, "0")
return strA + strB
}The fourth optimization — no heap monkey business
OK. We’ve managed to reach a very efficient data structure for the node: a simple unsigned integer. I don’t think we can optimize it further. Let’s find something else to work on.
Our code/algorithm have 3 big data sets:
- nodesToProcessNow (250,000 nodes at maximum)
- nodesToProcessLater (250,000 nodes at maximum)
- nodesAlreadyProcessed (1,073,741,824 nodes at maximum)
Although handling a few thousand nodes is now very efficient and easy, a billion nodes might become a problem.
For a JavaScript developer, the problem is not the big size of the data.
For a JavaScript developer, the problem is not that lists and dictionaries grow and shrink.
For a JavaScript developer, the problem is growing and shrinking big lists/dictionaries. Because, behind the scenes, JavaScript is forced to do a lot of expensive reallocations in the heap memory.
What we have to do is to start with lists big enough to hold all future data: never grow them, never shrink them.
// BAD:
const nodes = [ ]
...
nodes.push(node)
...
while (nodes > 0) {
const node = nodes.shift()
...
}
// GOOD:
const nodes = new Array(250000)
var nodesCount = 0
...
nodes[nodesCount] = newnode
nodesCount += 1
...
for (let i = 0; i < nodesCount; i++) {
const node = nodes[i]
...
}We create a variable that stores the next empty position of the list.
When we want to empty the list, we just set its position pointer/counter to zero. We don’t have to spend time erasing the list. Besides that, the more we empty a list or any other object, the more we are seducing JavaScript to make heap memory reallocations (expensive or not)!
From the algorithm point of view, the lists are still queues to be filled and emptied — nothing has changed! Internally, they are data pools. No conflict at all!
nodesToProcessNow and nodesToProcessLater are OK now.
They are easy to use because we get one node after other till the queue become “empty” — they are pools now.
And we just “push” a node to the next available space.
We DON’T search any target node inside them!
The fifth optimization — it is a node and it is an index
On the other hand, nodesAlreadyProcessed is NOT OK:
// BAD (too big list is expensive to iterate):
const nodesAlreadyProcessed = new Array(1073741824) // list of nodes (integers)
var nodesAlreadyProcessedCount = 0
function wasAlreadyProcessed(target) {
for (let i = 0; i < nodesAlreadyProcessedCount; i++) {
if(nodesAlreadyProcessed[i] == target) { return true }
}
return false
}It is very inefficient to search for a node in a list of billion nodes. Imagine going one by one the items of the list until we find (or not) the target node. Now, repeat it 50 million times — as we have guessed before. NO WAY! Not in my computer!
Of course, in the beginning we only get a few slots to search — nodesAlreadyProcessedCount is there protecting us to check empty slots.
The ideal data structure for nodesAlreadyProcessed is this:
// GOOD (fast, no iteration):
const nodesAlreadyProcessed = new Array(1073741824)
nodesAlreadyProcessed.fill(false) // list of booleans!
function wasAlreadyProcessed(index) {
return nodesAlreadyProcessed[index]
}
// NOTE: DON'T go changing nodestoProcessNow and nodesProcessLaterNote the differences.
Before:
- big list of nodes (integers), filled without any special order
- easy to write — just take the next available slot
- hard to read a target — had to iterate the big list
Now:
- big list of booleans, filled in very special order
- easy to write — just access the list by index
- easy to read a target— just access the list by index
The only problem is where does the node index lives?
- If we include the node index in its data structure, we destroy the very nice ultra simplified data that we had: just the integer.
- If the node index lives outside it, inside a big list, we have to iterate this big list to get the index: it doesn’t help at all, it only adds trouble.
- We use magic again ;)
By using magic again, I mean that we don’t need to do anything else. We already have all the node indices that we need!
Take a look at that conversion table again:
// node conversion
// from base 4 number-string to decimal
"00000" : 0 // lowest number
"00001" : 1
"00002" : 2
"00003" : 3
"00010" : 4
"00011" : 5
"00012" : 6
"00013" : 7
"00020" : 8
"00021" : 9
"00022" : 10
...
"33333" : 1023 // highest numberThe same unsigned integer that we use to represent the node data is perfectly fine to be its index in a (big enough) static size array!
function wasAlreadyProcessed(node) { // node is an unsigned integer
return nodesAlreadyProcessed[node]
}The sixth optimization — bit vs byte
A boolean value just need one bit (‘0’ for false or ‘1’ for true) to be stored. But when you write var x = true, the computer uses a whole byte (32 bits or 64 bits) for this boolean. What a waste!!! The computer cannot give the not used space of the byte for another variable, it would be too messy.
The computer cannot use that remaining bits. But we can ;)
The trick is NOT ordering the computer to store a boolean.
The trick is telling the computer to store an integer. And that integer converted to binary means a long string of ‘0’s and ‘1’s — that we can read as falses and trues.
nodesAlreadyProcessed is using 1,073,741,824 bytes to store 1,073,741,824 booleans. But it could use 32 or 64 times fewer bytes — a huge economy of memory!
const allPossibleStates = Math.pow(4, 15) // 1,073,741,824
const length = allPossibleStates / 8 // 134,217,728
const alreadyProcessedNodes = new Uint8Array(length) // *TYPED ARRAY*JavaScript allow us to use typed arrays, that are arrays without dynamic behavior — exactly what we need.
I am using Uint8Array, which means the data for each index/position of the array is a sequence of 8 bits (the good old school byte!). Although it is not 32 or 64 bits, JavaScript internally places one close to another without leaving unused, wasted space.
Consider that we have a very long array of bits that starts at the left with zero:
byte 0 : byte 1 : byte 2
00000000 : 00000000 : 00000000
^ ^ ^
A B C
A: myIndex 0, byte 0, bit 0
B: myIndex 7, byte 0, bit 7
C: myIndex 8, byte 1, bit 0I’ve just realized that although the sequence of bits above makes sense, and works fine in the program, it breaks the concept that the least value bit comes at the right of the byte, not at the left.
I don’t want to cause confusion, so I will stop this section here, leaving you with a nice video about bitwise operations.
Anyway, you can always check the source code of my solutions …
Let’s run the code (1)
I’ve made four special versions of the year 2016 day 11 puzzles , for running in the console of the browser (copy/paste and press enter).
The first three versions are not (very) optimized and serve to compare the use of a dictionary or not for alreadyProcessedNodes.
- array style solution for the *first* puzzle running in the browser (JS heap size 35 MB) takes 0.76s to succeed
- dictionary style solution for the *first* puzzle running in the browser (JS heap size is 78 MB) takes 1.25s to succeed
- dictionary style solution for the *second* puzzle running in the browser (JS heap size grows beyond 681 MB) CRASHES after 1 minute
What can we learn from those 3 programs, considering speed and use of heap memory?
For the first puzzle (the easy one), using a dictionary achieved in inferior but acceptable results.
For the second puzzle (the hard one) using a dictionary was a disaster.
Let’s run the code (2)
This is the optimized solution for the *second* puzzle running in the browser (JS heap size is 3.6 MB) takes 29.6s to succeed
Note the heap size: incredibly low, considering the job!
Final considerations
I hope you didn’t find this article difficult to understand. His topics are easy if you are familiar with them. In case you are not familiar. I suggest you try them one by one while you improve your programs. It is very rewarding to see your machines/programs becoming more and more performant.
Happy puzzles!
In Plain English
Thank you for being a part of our community! Before you go:
- Be sure to clap and follow the writer! 👏
- You can find even more content at PlainEnglish.io 🚀
- Sign up for our free weekly newsletter. 🗞️
- Follow us on Twitter(X), LinkedIn, YouTube, and Discord.