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)