Advent of Code 2025 Day 7: Beam Tracking with C++

December 7th

The Advent of Code 2025 Day 7 puzzle required tracking beams through a grid. The author’s part one solution failed for part two, requiring a recursive approach with memoization to handle 1.5 trillion beam paths.

Why This Matters

The initial approach for part one used a greedy algorithm that worked for small-scale beam propagation but collapsed under the complexity of part two’s exponential path growth. The problem exposed a common engineering challenge: optimizing for scalability requires rethinking data structures (e.g., switching from sets to memoized recursion) and avoiding assumptions about problem symmetry.

Key Insights

• “8-hour App Engine outage, 2012”: Not applicable here, but highlights the cost of scalability missteps.
• “Recursive memoization over iterative tracking for grid problems”: The trackBeam function uses a map to cache results, avoiding redundant calculations.
• “C++17 used by Advent of Code contributors”: The code leverages standard containers like std::map and std::set for efficient lookups.

Working Example

#include <cassert>
#include <fstream>
#include <iostream>
#include <set>
#include <map>
#include <sstream>
std::vector<std::string> loadInput(const std::string &filename) {
    std::vector<std::string> result;
    std::ifstream file(filename);
    std::string line;
    while (std::getline(file, line)) {
        result.push_back(line);
    }
    return result;
}
void partOne() {
    const auto lines = loadInput("/Users/rob/projects/robvanderleek/adventofcode/2025/07/input.txt");
    std::set<int> beams;
    long result = 0;
    for (const auto &line : lines) {
        for (int i = 0; i < line.length(); ++i) {
            char c = line[i];
            if (c == 'S') {
                beams.insert(i);
            } else if (c == '^' && beams.count(i)) {
                result++;
                beams.erase(i);
                beams.insert(i - 1);
                beams.insert(i + 1);
            }
        }
    }
    std::cout << result << std::endl;
    assert(result == 1507);
}
long trackBeam(std::vector<std::string> lines, int i, int j, std::map<std::pair<int, int>, long> &p) {
    if (i == lines.size() - 1) {
        return 1;
    }
    if (lines[i][j] == '^') {
        if (p.count({i, j})) {
            return p.at({i, j});
        }
        long traces = trackBeam(lines, i + 1, j - 1, p) + trackBeam(lines, i + 1, j + 1, p);
        p[{i, j}] = traces;
        return traces;
    }
    return trackBeam(lines, i + 1, j, p);
}
void partTwo() {
    const auto lines = loadInput("/Users/rob/projects/robvanderleek/adventofcode/2025/07/input.txt");
    std::map<std::pair<int, int>, long> p;
    long result = 0;
    for (int j = 0; j < lines[0].length(); ++j) {
        char c = lines[0][j];
        if (c == 'S') {
            result = trackBeam(lines, 0, j, p);
            break;
        }
    }
    std::cout << result << std::endl;
    assert(result == 1537373473728);
}
int main() {
    partOne();
    partTwo();
    return 0;
}

Practical Applications

• Use Case: Grid-based pathfinding in puzzle-solving or robotics.
• Pitfall: Assuming a single solution approach works for all problem variants; part one’s greedy method failed for part two’s combinatorial explosion.

References:

• https://dev.to/robvanderleek/advent-of-code-2025-december-7th-3j94

---