Advent Of Code - 2025 - Day 7

29 Apr, 2026

https://adventofcode.com/2025/day/7

How I solved?

I'm trying to follow the beej's guide approach. Understand. Plan. Code. Reflect.

What is my understanding of this problem?

A particle flows down - when it hits the splitter - it gets split in 2 paths.

For part 1, they have asked how many times the particle splits.

What I did? I have went through each row - if I see a . - i just replace it with | if the above neighbour is a |.

If I see a ^ splitter then in the bottom left and right below I update them to | as they split into 2. I increment split count. There could be an edge case where the below row left or right could contain ^ but that case didn't occur for me.

For part 2, they gave the twist - quantum thing - so particle goes either left or right - i need to find out the number of timelines the particle takes to reach the bottom.

I did the naive approach - recursive one - when particle reaches a splitter - for left and right respectively i do a recursive call with the updated data structure until that data structure reaches the end of the row for that particle.

It sorta like I explored all paths exhaustively. This worked for example but for input it was running for hours - so I gave up and checked what was a proper solution.

It turned out that DP was the correct fit and it was very easy. We just have to count row wise.

When we encounter a splitter we have just have to increment the counter in that place and when we encounter a dot we just have to carry forward.

Starting S gets the value of 1 as 1 timeline reaches there - the starting one.

The AI chat:

Here is the complete teardown and post-mortem of the problem, your architecture, and the path to the optimal solution.

1. The Problem & The Core Understanding

The puzzle presents a physics simulation of "tachyons" falling through a grid (the manifold). The rules are strict: particles fall straight down through empty space (.), and when they hit a splitter (^), they divide into two beams that shift diagonally left and right.

The Underlying Mechanics: While it looks like a physical maze, structurally, it is a Directed Acyclic Graph (DAG). Because particles can only move downward, the flow of time and state is strictly one-way. A particle on Row 10 can never bounce back up and alter Row 9. This means the entire system can be solved in a single top-to-bottom sweep.

Part 1 asks: "How many splitters get activated?" (A footprint problem).
Part 2 asks: "How many timelines reach the bottom?" (An exponential growth problem).

2. Spotting the Hidden DP Pattern

Dynamic Programming (DP) is often disguised behind flavor text. The transition from Part 1 to Part 2 had three massive red flags pointing directly to a DP state-tracker:

"How Many?" vs. "Which Path?": Part 2 doesn't ask for the route a timeline took; it only asks for the final integer count. When a problem discards the history of a journey and only wants the total, you must stop drawing paths and start tracking numbers.
The Exponential Threat: "Time itself splits." The puzzle explicitly states the entities multiply at every splitter. Simulating $2^{N}$ branching paths guarantees a CPU or memory crash. You must merge overlapping states to survive.
One-Way Movement: Because movement is purely downward, we never have to look backward. This guarantees that if two paths reach the same coordinate, their future is identical, allowing us to safely add them together ( $1 + 1 = 2$ ) and process them as a single entity moving forward.

3. Your Part 1 Solution

Your Approach: A nested loop that iterates through the grid row by row, checking the row above it, and physically drawing the beams by replacing strings with |.

What was excellent: You completely avoided recursion. You correctly identified that because particles only fall down, you could process the grid in a single pass (enumerate(input_data[1:], 1)). Furthermore, by physically drawing the | characters, you implicitly handled the overlapping path problem. If two beams hit the same empty space, your code just overwrote | with |, naturally merging them without duplicating effort.

What could be improved: Modifying a 2D list of strings in Python is visually intuitive but computationally heavy. Searching across every single column (for j, pos in enumerate(line)) wastes cycles checking empty space where no beams exist.

4. My Part 1 Solution

Instead of modifying the whole grid, we can just track the "active coordinates" of the beams as they fall. By using a Python set, we only process exactly where the beams are, and sets naturally prevent duplicates when two beams merge on the same space.

def solve_part1(filename="input.txt"):
    with open(filename) as f:
        grid = f.read().splitlines()
        
    # Find start and initialize a set of active columns
    start_c = grid[0].index('S')
    active_beams = {start_c} 
    split_count = 0
    
    # Process row by row
    for r in range(1, len(grid)):
        next_beams = set()
        for c in active_beams:
            if grid[r][c] == '.':
                next_beams.add(c) # Falls straight down
            elif grid[r][c] == '^':
                split_count += 1
                next_beams.add(c - 1) # Forks left
                next_beams.add(c + 1) # Forks right
                
        active_beams = next_beams # Move to the next row
        
    return split_count

5. Your Part 2 Solution

Your Approach: A recursive function that clones the entire grid (deepcopy) every time it hits a splitter, running a separate simulation for every branching timeline.

What was excellent: Your logical breakdown of the rules was flawless. You accurately mapped how the beam interacts with the splitters and correctly defined the stopping condition.

What broke: The architecture. You attempted to simulate an exponentially multiplying universe.

The Deepcopy Death: Copying a full grid into a new memory block at every splitter creates massive overhead.
Redundant Computation: If Timeline A and Timeline B both reached the same coordinate, your recursive tree treated them as entirely different universes, calculating the exact same downward journey twice.

6. My Part 2 Solution

Instead of simulating the paths, we track the mathematical state. We swap a grid of strings for a grid of integers, representing "how many timelines are currently sitting on this space."

def solve_part2(filename="input.txt"):
    with open(filename) as f:
        grid = f.read().splitlines()

    rows, cols = len(grid), len(grid[0])
    
    # dp[r][c] will store the integer count of timelines at that space
    dp = [[0] * cols for _ in range(rows)]
    dp0.index('S')] = 1 

    for r in range(rows - 1):
        for c in range(cols):
            if dp[r][c] > 0: # Only process spaces that actually have timelines
                next_cell = grid[r + 1][c]
                
                if next_cell == '.':
                    dp[r + 1][c] += dp[r][c] # Push the integer straight down
                    
                elif next_cell == '^':
                    if c > 0:
                        dp[r + 1][c - 1] += dp[r][c] # Push integer down-left
                    if c < cols - 1:
                        dp[r + 1][c + 1] += dp[r][c] # Push integer down-right

    return sum(dp[-1])

By pushing integers downward and using += to add merging timelines together, the CPU executes the problem in a single top-to-bottom pass, mathematically handling billions of timelines in roughly $O (R \times C)$ time.

Found and learned about Recursive approach as well. Tabular and Memoized DP.