Caleb Weeks

Posted on

# Advent of Code #8 (in Crystal)

So... today's puzzle was a bit of a mixed bag. Part 1 had a fairly straightforward solution, but part 2 required some careful inspection of the input.

A certain amount of reasoning would get you to a place where determining the cycles of each path and taking the least common multiple may have something to do with it. But there is no guarantee that any of these cycles start at the same time, or that the paths don't cross.

But here's the catch: all the inputs are guaranteed to have cycles that start at the same time right at the start and none of the paths overlap. This means that the answer IS just the LCM of all the cycles. For many people, including myself, this answer seems dissatisfactory, because you would only know that by analyzing the input.

I actually stumbled on this solution by accident when one of the guys at work had calculated the LCM and I suggested to him to just try to see if it was the right answer. I then tried it with my input, but only after getting the right answer did I realize that I didn't know why that was the right answer.

It's been a weird year so far for Advent of Code. Day one had a couple twists, and the second part of day 5 also had nicely arranged inputs to make an analytical approach possible (though I ended up just brute forcing it).

We'll see how it goes from here! I'm expecting day 9 to start ramping up the difficulty. Here's how I solved day 8:

``````input = File.read("input").strip

alias Node = Hash(String, Tuple(String, String))

instruction_str, nodes = input.split("\n\n")

nodes = nodes.split("\n").reduce(Node.new) do |nodes, line|
node, left, right = line.scan(/\w+/).map(&.[0])
nodes.merge({node => {left, right}})
end

part1 = begin
instructions = instruction_str
.gsub({L: 0, R: 1})
.each_char
.map(&.to_i)
.cycle
steps = 0
current_node = "AAA"
while current_node != "ZZZ"
steps += 1
current_node = nodes[current_node][instructions.next.as(Int32)]
end
steps
end

puts part1

part2 = begin
instructions = instruction_str
.gsub({L: 0, R: 1})
.each_char
.map(&.to_i)
.cycle
steps = 0
starting_nodes = nodes.select { |node, _| node.ends_with?('A') }.keys
current_nodes = starting_nodes
cycles = Array.new(current_nodes.size, 0_i64)
cycle_counts = Array.new(current_nodes.size, 0)
while cycle_counts.map { |x| x < 2 }.all?
steps += 1
step = instructions.next.as(Int32)
current_nodes = current_nodes.map_with_index do |node, i|
cycle_counts[i] += 1 if node.ends_with?('Z')
cycles[i] = steps - cycles[i] - 1 if node.ends_with?('Z')
nodes[node][step]
end
end
cycles.reduce { |lcm, cycle| lcm.lcm(cycle) }
end

puts part2
``````