Advent of Code 2016 - Day 15

Day 15: Timing is Everything

Useful Links

‹›

• 2016 Main Page
• My solution code

Concepts and Packages Demonstrated

regexdataclassesenumerate

Problem Intro

We’re faced with a kinetic sculpture that has a series of rotating discs. Each disc has a number of positions, and a single slot. For a capsule to pass through a disc, the slot must be at position 0. The discs rotate at a rate of one position per second.

The discs are stacked, and it takes one second for the capsule to travel between them. This means if we press the button at time t, the capsule reaches the first disc at t+1, the second at t+2, and so on.

Our input looks like this:

Disc #1 has 5 positions; at time=0, it is at position 4.
Disc #2 has 2 positions; at time=0, it is at position 1.

Part 1

What is the first time you can press the button to get a capsule?

We need to find the first integer time t where we can press the button, and the capsule will fall through all the discs. This means that for each disc i (starting from 1), at time t+i, the disc must be at position 0.

My approach is to:

1. Parse the input to get the number of positions and starting position for each disc. I’ll use a regular expression for this.
2. Create a Disc dataclass to represent each disc. This class will have a method to calculate its position at any given time t. The formula for the position of a disc at time t is (initial_position + t) % number_of_positions.
3. Iterate through time t starting from 0. For each t, I’ll check if the capsule would pass through all discs.
4. For each disc i in the stack, the capsule reaches it at time t+i. So, we need to check if disc[i].get_position_at_time(t + i + 1) is 0. Note the +1 is because the discs are 1-indexed in the problem, but 0-indexed in my code.
5. The first t for which this condition is true for all discs is our answer.

Here’s the Disc dataclass and the parsing logic:

import re
from dataclasses import dataclass

disc_params_match = re.compile(r"Disc #(\d+) has (\d+) positions; at time=(\d+), it is at position (\d+).")

@dataclass
class Disc:
    """ Disc Dataclass 
    Knows how to return its own position at any given time in seconds. """
    disc_num: int
    positions_count: int
    start_time: int
    position: int
        
    def get_position_at_time(self, t) -> int:
        return (self.position + t) % self.positions_count

And here’s the main loop:

def main():
    # ... parsing code ...

    discs: list[Disc] = []
    for line in data:
        if match := disc_params_match.search(line):
            disc_num, disc_positions, disc_time, disc_position = map(int, match.groups())
            discs.append(Disc(disc_num, disc_positions, disc_time, disc_position))

    t = 0
    # loop until we find a drop time t, where all discs are aligned
    while True:
        all_discs_aligned = True
        for i, disc in enumerate(discs, 1): # we reach the 1st disc at time t=t+1, 2nd at t=t+2, etc
            time_at_this_disc = t+i
            
            # We need all discs to be at position 0
            if disc.get_position_at_time(time_at_this_disc) != 0:
                all_discs_aligned = False
                break
            
        if all_discs_aligned:
            logging.info(f"All discs aligned at t={t}")
            break
        
        t += 1

This is a brute-force approach, but given the nature of the problem, it’s simple and effective.

Part 2

We’ve added another disc. What is the first time you can press the button to get a capsule?

The new disc has 11 positions and starts at position 0. I just need to add this to my list of discs and run the same simulation again.

    # In my actual code, I just added the new disc to the input file.
    # But programmatically, it would look like this:
    discs.append(Disc(disc_num=7, positions_count=11, start_time=0, position=0))

The same logic from Part 1 will then find the new time t.

Results

Here’s the output from my solution:

All discs aligned at t=122313
Execution time: 0.1000 seconds

And for part 2:

All discs aligned at t=3208583
Execution time: 1.0000 seconds

The solution is reasonably fast, so the brute-force approach is acceptable.

‹›