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