Day 7: Laboratories

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

  • Pyro@programming.dev
    3·
    3 days ago

    Python

    Not too difficult, especially since there are no edge cases (particles leaving the grid, adjacent splitters).

    My initial solution mutated the input for the simulation which I cleaned up after by creating an array that would record the number of particle paths at every column location + some other optimizations. I chose to implement both parts in the same function because they share the majority of the logic.

    click to view code 
    def solve(data: str):
    grid = data.splitlines()
    m, n = len(grid), len(grid[0])

    # find the first particle
    particle_paths = [0] * n  # count of particle paths that will reach this column
    for j in range(n):
        if grid[0][j] == 'S':
            particle_paths[j] = 1
            break
    
    # count the number of splits for part 1
    splits = 0

    # simulate the particle moving down the grid
    #   optimization 1: we can start from the 3rd row (index 2) because that's where the first splitter is
    #   optimization 2: we can skip alternating rows because every other row is empty
    for i in range(2, m, 2):
        # particle paths per column after this row is processed
        next_particle_paths = [0] * n

        for j in range(n):
            if particle_paths[j] == 0:
                # skip if there are no particle paths coming from above in this column
                continue
            
            if grid[i][j] == '.':
                # no splitter here, the number of paths in this column remains the same
                # make sure to use += to account for neighboring splitters dumping additional paths into this column
                next_particle_paths[j] += particle_paths[j]
            else:
                # splitter activated here, any particle arriving here can end up in the left or right column
                # this can be simulated by adding the number of paths to the columns on either side
                splits += 1
                next_particle_paths[j-1] += particle_paths[j]
                next_particle_paths[j+1] += particle_paths[j]
        
        # update vars for next iteration
        particle_paths = next_particle_paths

    # return both 
    #   the number of splits AND 
    #   the count of timelines a particle would create
    return splits, sum(particle_paths)

sample = """.......S.......
...............
.......^.......
...............
......^.^......
...............
.....^.^.^.....
...............
....^.^...^....
...............
...^.^...^.^...
...............
..^...^.....^..
...............
.^.^.^.^.^...^.
..............."""
assert solve(sample) == (21, 40)