Posted in:

Today’s Advent of Code puzzle gave us details of some “particles”, each with a 3D position, velocity and acceleration vector. From these initial values we could calculate their new positions and velocities after each “tick.”

The problem we had to solve though involved finding values “in the long run”. So for part 1, which particle stayed closest to the origin (0,0,0) in the long run? And for part 2, if we eliminate any particles that collide, how many remain in the long run?

A simple way to approach this sort of problem is to enumerate a sequence until it has a stable value. If the value has been stable for a certain number of repetitions, we assume that it will not change in the future. Obviously for today’s puzzle there might be some way to prove that the sequence has settled on its final value, but I leave that to the expert mathematicians.

The first step was to parse the input, and here I just needed to pick out the 9 numbers on each line of my input:

const particles = input.map(p => p.match(/-?\d+/g).map(d => Number(d)))
                       .map((x,n) => ({ p: x.slice(0,3), v: x.slice(3,6), a: x.slice(6,9),n }))

To calculate the new positions of each particle after a tick, we needed some helper functions. I created addv to add two 3D vectors together, dist to calculate the Manhattan distance from (0,0,0) and tick to update the position and velocity of all particles in an array.

const addv = (v1,v2) => [v1[0] + v2[0], v1[1] + v2[1], v1[2] + v2[2]]
const dist = v => Math.abs(v[0]) + Math.abs(v[1]) + Math.abs(v[2])
const tick = ps => { for(let p of ps) { p.v = addv(p.v,p.a); p.p = addv(p.p,p.v); } return ps; }

We need to create a sequence of particle states, repeatedly applying the tick function. To do this I created an unfold utility method, that takes a starting value and then returns the sequence of repeatedly applying a function to that value:

function* unfold(start, fn) {
    yield start;
    for(;;) {
        start = fn(start)
        yield start
    }
}

I also needed a general purpose function that could find the first element in a sequence that is “repeated” more than n times. My firstRepeated function lets you specify the sequence to enumerate (potentially infinite), the number of repeats you want, and an optional selector to select the value by which adjacent elements should be compared.

function firstRepeated(seq, repeats, selector) {
    let current;
    let currentEl;
    let count = 0;
    for(let el of seq) {
        let testVal = (selector ? selector(el) : el)
        if (testVal === current) {
            count++;
            if (count >= repeats) return [current,currentEl]
        }
        else {
            current = testVal
            currentEl = el
            count = 1;
        }
    }
    throw new Error("Repeated element not found")
}

function firstRepeatedValue(seq, repeats, selector) {
    return firstRepeated(seq, repeats, selector)[0]
}

Here’s an example of one of the Jasmine tests I created to check that it correctly finds the repeated value with a selector function. In this example, we find three consecutive strings of length three:

it ("can find with selector", function() {
    let actual = firstRepeatedValue(["bear","apple","pear","dog","cat","ant","tiger"], 3, s => s.length)
    expect(actual).toEqual(3)
})

A final general purpose function I needed for part 2 was to remove any elements from a sequence that appear more than once.

For this I created the nonRepeated utility function, which uses a map to track what elements have been seen, and again provides a selector function to select the key that should be used to determine equality.

function nonRepeated(seq, selector) {
    let map = new Map() 
    for (let el of seq) {
        let key = selector ? selector(el) : el;
        if (!map.has(key)) {
            map.set(key, el)
        }
        else {
            map.set(key, undefined) // don't delete to eliminate three at same pos
        }
    }
    return where(map.values(),n => n !== undefined)
}

Again I wrote some Jasmine tests to ensure this function works as expected. Here’s an example test where strings of the same length are considered to be duplicates:

it ("supports selector", function() {
    let actual = [...nonRepeated(["cat","dog","horse","cow","bear"], s => s.length)]
    expect(actual).toEqual(["horse","bear"])
})

So that was a fair bit of work to create these helpers (unfold, firstRepeatedValue and nonRepeated), but they have the advantage of being completely generic. They are not in any way tied to the specifics of today’s puzzle and hopefully will prove useful again in the future. And as it happens, I also took advantage of minBy, another utility function I’d created for a previous puzzle.

Now we can solve both parts of today’s challenge, with the only difficulty being deciding how many iterations would be needed before I considered the sequence to be stabilised. I started off with high numbers like 10000, but it turned out that much lower numbers got me to the correct answer (obviously this depends on your puzzle input):

if (part === 1) {
    return firstRepeatedValue(unfold(particles, tick), 300, ps => minBy(ps, p => dist(p.p)).n)
}
else {
    return firstRepeatedValue(unfold(particles, ps => [...nonRepeated(tick(ps),p=>p.p.toString())]), 100, ps => ps.length)
}

The full code for today’s solution can as always be found in my GitHub repository.