Advent of Code - 2025 - Day 11

var input = await File.ReadAllLinesAsync("input.txt");

var graph = new Dictionary<string, string[]>();
var start = "you";
const string end = "out";

foreach (var line in input)
{
    var parts = line.Split(": ");
    var node = parts[0];
    var edges = parts[1].Split(" ");
    graph[node] = edges;
}

var part1 = CountPaths(start, end, graph);

Console.WriteLine($"Part 1: {part1}");

start = "svr";
const string fft = "fft";
const string dac = "dac";

var startToFft = CountPaths(start, fft, graph);
var fftToDac = CountPaths(fft, dac, graph);
var dacToEnd = CountPaths(dac, end, graph);

var part2 = startToFft * fftToDac * dacToEnd;

Console.WriteLine($"Part 2: {part2}");

return;

static long CountPaths(string start, string end, Dictionary<string, string[]> graph)
{
    var memo = new Dictionary<string, long>();
    var stack = new Stack<string>();
    stack.Push(start);

    while (stack.Count > 0)
    {
        var current = stack.Peek();

        if (memo.ContainsKey(current))
        {
            stack.Pop();
            continue;
        }

        if (current == end)
        {
            memo[current] = 1;
            stack.Pop();
            continue;
        }

        if (!graph.TryGetValue(current, out var neighbors))
        {
            memo[current] = 0;
            stack.Pop();
            continue;
        }

        var allNeighborsProcessed = true;
        foreach (var neighbor in neighbors.Where(n => !memo.ContainsKey(n)))
        {
            stack.Push(neighbor);
            allNeighborsProcessed = false;
        }

        if (allNeighborsProcessed)
        {
            long count = 0;
            foreach (var neighbor in neighbors)
            {
                count += memo[neighbor];
            }
            memo[current] = count;
            stack.Pop();
        }
    }

    return memo.GetValueOrDefault(start, 0);
}