swizec.com

#### Senior Mindset Book

Get promoted, earn a bigger salary, work for top companies

# Advent of Code Days 17 & 18 – Spinlocks and Interpreters

Days 17 and 18 both defeated me. Star 1 was easy, Star 2 was not. Both were pretty quick to solve for the first star, though, so let's look at that.

## Day 17 – Spinlock

For Advent of Code Day 17, we had to implement a spinlock. Spinlocks are a way to implement busy waiting 👇

In software engineering, a spinlock is a lock which causes a thread trying to acquire it to simply wait in a loop ("spin") while repeatedly checking if the lock is available. Since the thread remains active but is not performing a useful task, the use of such a lock is a kind of busy waiting.

There's no video for Day 17 because I was doing it in bed and yes, I did fall asleep while waiting for Star 2 to finish computing. It never did; my algorithm was too slow.

Unlike a real spinlock, the puzzle spinlock is trying to eat up infinite memory as well as infinite time.

For example, if the spinlock were to step 3 times per insert, the circular buffer would begin to evolve like this (using parentheses to mark the current position after each iteration of the algorithm):

(0), the initial state before any insertions.

0 (1): the spinlock steps forward three times (0, 0, 0), and then inserts the first value, 1, after it. 1 becomes the current position.

0 (2) 1: the spinlock steps forward three times (0, 1, 0), and then inserts the second value, 2, after it. 2 becomes the current position.

0 2 (3) 1: the spinlock steps forward three times (1, 0, 2), and then inserts the third value, 3, after it. 3 becomes the current position.

The question was "What is the value right after 2017 gets inserted into the buffer?".

To find out, I built a recursive implementation of the spinlock algorithm above in Haskell. Because Haskell is fun.

```.css-1yb0ye3{font-family:monospace;color:#728fcb;background-color:#faf8f5;font-size:0.9em;padding-left:0;padding-right:0;}.css-1yb0ye3 .comment,.css-1yb0ye3 .prolog,.css-1yb0ye3 .doctype,.css-1yb0ye3 .cdata,.css-1yb0ye3 .punctuation{color:#b6ad9a;}.css-1yb0ye3 .namespace{opacity:0.7;}.css-1yb0ye3 .tag,.css-1yb0ye3 .operator,.css-1yb0ye3 .number{color:#063289;}.css-1yb0ye3 .property,.css-1yb0ye3 .function{color:#b29762;}.css-1yb0ye3 .tag-id,.css-1yb0ye3 .selector,.css-1yb0ye3 .atrule-id{color:#2d2006;}.css-1yb0ye3 .attr-name{color:#896724;}.css-1yb0ye3 .boolean,.css-1yb0ye3 .string,.css-1yb0ye3 .entity,.css-1yb0ye3 .url,.css-1yb0ye3 .attr-value,.css-1yb0ye3 .keyword,.css-1yb0ye3 .control,.css-1yb0ye3 .directive,.css-1yb0ye3 .unit,.css-1yb0ye3 .statement,.css-1yb0ye3 .regex,.css-1yb0ye3 .at-rule{color:#728fcb;}.css-1yb0ye3 .placeholder,.css-1yb0ye3 .variable{color:#93abdc;}.css-1yb0ye3 .deleted{text-decoration-line:line-through;}.css-1yb0ye3 .inserted{text-decoration-line:underline;}.css-1yb0ye3 .italic{font-style:italic;}.css-1yb0ye3 .important,.css-1yb0ye3 .bold{font-weight:700;}.css-1yb0ye3 .important{color:#896724;}.css-1yb0ye3 .highlight{background:hsla(0, 0%, 70%, .5);}.css-o6ar0x{font-family:monospace;color:#728fcb;background-color:#faf8f5;font-size:0.9em;padding-left:0;padding-right:0;font-family:monospace;color:#728fcb;background-color:#faf8f5;font-size:0.9em;padding-left:0;padding-right:0;}.css-o6ar0x .comment,.css-o6ar0x .prolog,.css-o6ar0x .doctype,.css-o6ar0x .cdata,.css-o6ar0x .punctuation{color:#b6ad9a;}.css-o6ar0x .namespace{opacity:0.7;}.css-o6ar0x .tag,.css-o6ar0x .operator,.css-o6ar0x .number{color:#063289;}.css-o6ar0x .property,.css-o6ar0x .function{color:#b29762;}.css-o6ar0x .tag-id,.css-o6ar0x .selector,.css-o6ar0x .atrule-id{color:#2d2006;}.css-o6ar0x .attr-name{color:#896724;}.css-o6ar0x .boolean,.css-o6ar0x .string,.css-o6ar0x .entity,.css-o6ar0x .url,.css-o6ar0x .attr-value,.css-o6ar0x .keyword,.css-o6ar0x .control,.css-o6ar0x .directive,.css-o6ar0x .unit,.css-o6ar0x .statement,.css-o6ar0x .regex,.css-o6ar0x .at-rule{color:#728fcb;}.css-o6ar0x .placeholder,.css-o6ar0x .variable{color:#93abdc;}.css-o6ar0x .deleted{text-decoration-line:line-through;}.css-o6ar0x .inserted{text-decoration-line:underline;}.css-o6ar0x .italic{font-style:italic;}.css-o6ar0x .important,.css-o6ar0x .bold{font-weight:700;}.css-o6ar0x .important{color:#896724;}.css-o6ar0x .highlight{background:hsla(0, 0%, 70%, .5);}.css-o6ar0x .comment,.css-o6ar0x .prolog,.css-o6ar0x .doctype,.css-o6ar0x .cdata,.css-o6ar0x .punctuation{color:#b6ad9a;}.css-o6ar0x .namespace{opacity:0.7;}.css-o6ar0x .tag,.css-o6ar0x .operator,.css-o6ar0x .number{color:#063289;}.css-o6ar0x .property,.css-o6ar0x .function{color:#b29762;}.css-o6ar0x .tag-id,.css-o6ar0x .selector,.css-o6ar0x .atrule-id{color:#2d2006;}.css-o6ar0x .attr-name{color:#896724;}.css-o6ar0x .boolean,.css-o6ar0x .string,.css-o6ar0x .entity,.css-o6ar0x .url,.css-o6ar0x .attr-value,.css-o6ar0x .keyword,.css-o6ar0x .control,.css-o6ar0x .directive,.css-o6ar0x .unit,.css-o6ar0x .statement,.css-o6ar0x .regex,.css-o6ar0x .at-rule{color:#728fcb;}.css-o6ar0x .placeholder,.css-o6ar0x .variable{color:#93abdc;}.css-o6ar0x .deleted{text-decoration-line:line-through;}.css-o6ar0x .inserted{text-decoration-line:underline;}.css-o6ar0x .italic{font-style:italic;}.css-o6ar0x .important,.css-o6ar0x .bold{font-weight:700;}.css-o6ar0x .important{color:#896724;}.css-o6ar0x .highlight{background:hsla(0, 0%, 70%, .5);}```spinlock::[Int] -> Int -> Int -> Int -> Int -> (Int, [Int])
spinlock buffer steps pos i iterations
| i < iterations = spinlock (left ++ [i] ++ right) steps nextPos (i+1) iterations
| otherwise = (nextPos, buffer)
where spinPos = mod (pos+steps) (length buffer)
(left, right) = splitAt (spinPos+1) buffer
nextPos = spinPos+1
``````

The `spinlock` method takes 5 arguments, which I'm sure is sacrilege in Haskell, and returns a tuple: An integer and a list of integers.

Arguments look like this:

• `buffer` is the current state of our circular buffer
• `steps` tells us how many steps we do on each spin
• `pos` gives us the current position in our buffer
• `i` says how many times we've iterated
• `iterations` tells us how many times to iterate in total

The algorithm itself was simple to implement, but fraught with off-by-one errors.

If we have to keep going – `i < iterations` – then recurse with an edited buffer, updated position and `i+1`. Otherwise, return the result. A tuple with the next position and final buffer.

We get the position after spinning, `spinPos`, as a remainder between current position `pos` and `steps`, and the buffer length. Split the buffer into `left` and `right` at position after the spin, and say the next position is going to be there too.

This worked great for the `2017` iterations from Star 1.

``````star1::Int -> Int
star1 steps = buffer!!pos
where (pos, buffer) = spinlock [0] steps 0 1 2017
``````

A little slow maybe, but it worked.

For Star 2, they wanted us to find the value after `0` when 50,000,000 iterations are performed. This did not go so well.

``````star2::Int -> Int
star2 steps = buffer!!(zeroAt+1)
where (pos, buffer) = spinlock [0] steps 0 1 50000000
zeroAt = Data.Maybe.fromJust \$ elemIndex 0 buffer
``````

The idea is simple: Iterate 50 million times, look for the `0`, return the value after it.

But the spinlock never finishes. Haskell's lazy evaluation gets in the way, and I couldn't figure out how to make it stop.

With lazy evaluation, we keep all iterations of the spinlock in memory until we print the final result. That's a problem.

shrug

## Day 18 – A programming language interpreter

On Day 18 of our Advent of Code, we had to build an interpreter for a simple programming language. There are 7 commands that take 1 or 2 arguments. Arguments can be registers or values.

`snd X` plays a sound with a frequency equal to the value of X.

`set X Y` sets register X to the value of Y.

`add X Y` increases register X by the value of Y.

`mul X Y` sets register X to the result of multiplying the value contained in register X by the value of Y.

`mod X Y` sets register X to the remainder of dividing the value contained in register X by the value of Y (that is, it sets X to the result of X modulo Y).

`rcv X` recovers the frequency of the last sound played, but only when the value of X is not zero. (If it is zero, the command does nothing.)

`jgz X Y` jumps with an offset of the value of Y, but only if the value of X is greater than zero. (An offset of 2 skips the next instruction, an offset of -1 jumps to the previous instruction, and so on.)

Our goal is to find the first non-zero value that `rcv` finds.

I built this one in JavaScript because why not. 😇

We start with a bunch of `registers`, which are a JavaScript `Map`.

``````function initRegisters() {
const registers = new Map(
"abcdefghijklmnopqrstuvwxyz".split("").map((l) => [l, 0])
);
registers.set("sound", null);
registers.set("pointer", 0);

return registers;
}
``````

This creates a register for each letter of the alphabet plus a `sound` register and a `pointer`. `sound` will be where `snd` puts its values and `rcv` reads them from, `pointer` is going to point to the current line of code we're executing.

The interpreter itself comes as just 39 lines of code. It's a simple language after all. Although I do think it's got enough instructions to be Turing-complete, but it lacks the memory. 25 registers won't cut it for Turing completeness.

You could, of course, expand it to have infinite registers 🤔

Anyway, the interpreter 👇

``````function execute(registers, command) {
const [com, val1, val2] = command.trim().split(" ");

function getVal(val) {
if (registers.has(val)) {
return registers.get(val);
} else {
return Number(val);
}
}

let jumped = false,
kill = false;

const commands = {
snd: (a) => registers.set("sound", getVal(a)),
set: (a, b) => registers.set(a, getVal(b)),
add: (a, b) => registers.set(a, getVal(a) + getVal(b)),
mul: (a, b) => registers.set(a, getVal(a) * getVal(b)),
mod: (a, b) => registers.set(a, getVal(a) % getVal(b)),
rcv: (a) => (
console.log("SOUND:", getVal("sound")),
(kill = true),
registers.set(a, getVal("sound"))
),
jgz: (a, b) =>
getVal(a) > 0
? ((jumped = true),
registers.set("pointer", getVal("pointer") + getVal(b)))
: null,
};

commands[com](val1, val2);

if (!jumped) {
registers.set("pointer", getVal("pointer") + 1);
}

return [kill, registers];
}
``````

We split the line of code into a `command` and two values, `val1` and `val2`.

Then we define a function for reading values, `getVal`. If the value given is a known register, we read from it; otherwise, we return the value itself.

After that, we need two flags: `jump` tells us if we executed a jump command, and `kill` tells us if we have to stop executing.

A dictionary mapping all possible commands to a function that executes them helps us run the commands. Each function manipulates the `registers` and potentially flips the `jump` and `kill` flags.

When the current line of code is executed, we advance our `pointer` by `+1` if we didn't jump. The interpreter returns the `kill` flag and the new `registers`.

The registers are actually changed in place, and there's no need to return, but I think this approach makes our implementation clearer.

With the interpreter in hand, we then have to add some looping to find the answer to AoC 18 Star 1.

``````function star1() {
let registers = initRegisters(),
kill = false;
const program = input.split("\n").filter((command) => command.length > 0);

// find sound value at first non-zero rcv
while (
registers.get("pointer") >= 0 &&
registers.get("pointer") < program.length &&
!kill
) {
[kill, registers] = execute(registers, program[registers.get("pointer")]);
}
}
``````

Create registers, split program into lines, `execute` until a `while` condition is met. Either we jumped out of the program, or a line set the `kill` flag.

Works like a charm 👌

Star 2 is where it gets tricky. Those `snd` and `rcv` commands weren't actually about sound; they were `send` and `receive` commands, and you're meant to run two copies of this code in parallel.

They communicate with `snd` and `rcv`.

We have to expand our `sound` register into a message queue and add some logic for how it's shared between the two programs. Additionally, the puzzle wants us to pause execution of each program while it waits for the queue to get values.

Sounds hard. So I went to bed.

Published on December 18th, 2017 in Haskell, Technical

Semantically similar articles hand-picked by GPT-4

### Senior Mindset Book

Get promoted, earn a bigger salary, work for top companies

Have a burning question that you think I can answer? Hit me up on twitter and I'll do my best.

Who am I and who do I help? I'm Swizec Teller and I turn coders into engineers with "Raw and honest from the heart!" writing. No bullshit. Real insights into the career and skills of a modern software engineer.

Want to become a true senior engineer? Take ownership, have autonomy, and be a force multiplier on your team. The Senior Engineer Mindset ebook can help 👉 swizec.com/senior-mindset. These are the shifts in mindset that unlocked my career.

Curious about Serverless and the modern backend? Check out Serverless Handbook, for frontend engineers 👉 ServerlessHandbook.dev

Want to Stop copy pasting D3 examples and create data visualizations of your own? Learn how to build scalable dataviz React components your whole team can understand with React for Data Visualization

Want to get my best emails on JavaScript, React, Serverless, Fullstack Web, or Indie Hacking? Check out swizec.com/collections

Did someone amazing share this letter with you? Wonderful! You can sign up for my weekly letters for software engineers on their path to greatness, here: swizec.com/blog

Want to brush up on your modern JavaScript syntax? Check out my interactive cheatsheet: es6cheatsheet.com

By the way, just in case no one has told you it yet today: I love and appreciate you for who you are ❤️

Created by Swizec with ❤️