Solution for Advent of Code 2016 - Day 15: Timing is Everything

Link to the puzzle text

Part 1

In this puzzle we have to find the ideal time to start a ball through rotating discs. Each disc has multiple closed positions, one open position and rotate one position per second. We need to find the start time. so each disc is on the open position while the ball is falling through.

We can model this problem as finding a start time t, such that (initial_position + t + #disc) % #positions) = 0  for all discs 1 to n. This is the same as t % positions = (t + #disc) % positions for all discs. Problems in this form can be solved via the Chinese remainder theorem. I used an implementation from Rosetta code, so the programming work here was mostly parsing the input.

Part 2

For part 2, we have an additional disc we need to pass. We can simply add additional values before we call our Chinese remainder solver and get the new result.

Link to my solutions