Posted in:

I didn’t have a lot of time for todays’ Advent of Code challenge, but I was able to get my two stars, so here’s a quick breakdown of how I solved it.

We were given an which could be thought of as a list of locations and reachable destinations. Here location 0 can reach locations 5, 8 and 10:

0 <-> 5, 8, 10

If we then had another line saying that:

5 <-> 0, 7, 9

That means that from 0 you can also reach 7 and 9. So locations 0, 5, 7, 8, 9 and 10 are effectively in a “group” – they can all be reached from one another.

I parsed each line with a regex like this:

const parse = s => {
    let [,from,dest] = /(\d+) <-> ((\d+)(, \d+)*)/.exec(s);
    return {from,to:dest.split(', ')}
}

For part 1 I needed to find how many locations (called ‘programs’ in this puzzle) are reachable from location 0. I did this by starting at 0, maintaining an ES6 Set of places I’d already visited, and then recursively following all the destinations until I’d seen them all.

const getGroup = (start,programs) => {
    let s = new Set()
    visit(s, programs[start].to, programs)
    return s;
}

const visit = (visited,destinations,programs) => {
    for(let d of destinations) {
        if (!visited.has(d)) {
            visited.add(d)
            visit(visited,programs[Number(d)].to,programs)
        }
    }
}

That left me with a set containing every destination reachable from 0, meaning the answer was just its size.

For part 2, I had to find out how many unique groups (locations from which you can reach all the other locations in the group) there were. I solved this by maintaining a set of locations that were part of any group. So I calculated the group containing 0, and put all locations in that group into the set. Then I found the next location that wasn’t in the set of already visited locations, calculated its group, and so on.

let groups = 0;
let inAnyGroup = new Set();
for(let g = 0; g < programs.length; g++) {
    if(!inAnyGroup.has(g.toString())) {
        groups++;
        let group = getGroup(g,programs);
        for(let m of group) {
            inAnyGroup.add(m)
        }
    }
}
return groups;

As I said, I didn’t have a lot of time today to optimize my solution, but it performs pretty quickly and shows off how the Set object can be very useful for tracking unique values. I’m sure there were plenty of other approaches that could have been taken today so do let me know in the comments how you tackled it. As usual you can find my full solution code on GitHub.