Advent of Code (Day 12)


Check out out day 12 here.

Here we had programs link to other programs, which linked to other programs and back. For example:


0 <-> 2
1 <-> 1
2 <-> 0, 3, 4
3 <-> 2, 4
4 <-> 2, 3, 6
5 <-> 6
6 <-> 4, 5

0 links to 2, which links to 0, 3, 4, which each link to others. You can see the id on the left, and the linking id(s) on the right. The first part has to see how many programs were linked to 0, either directly or indirectly.

I thought a little recursion would do the trick and my algorithm looked like this.

This can be seen in the group_ids method.

Challenge One


mapping = {}

input = File.read('input.txt').split("\n")
input.map do |program|
  input, output = program.split(' <-> ')
  output = output.split(', ')
  mapping[input] = output
end

group = []

def group_ids(mapping, id, group)
  return if group.include? id

  group << id
  mapping[id].each do |output|
    group_ids(mapping, output, group)
  end
end

ids = group_ids(mapping, '0', group)

puts ids.size

Challenge Two

Here, we had to see how many unique groups there are in the set of ids 0 to 1999. I kind of cheated and just mapped 0 to 1999 to each of their respective groups and called .uniq to remove redundant groups. I’m sure there’s a better way to optimize, perhaps marking each number with a group id and seeing how many ids there are?


groups = (0..1999).to_a.map do |item|
  group = []
  group_ids(mapping, item.to_s, group)
  group.sort
end.uniq.size

puts groups