AdventOfCode/AoC_2025/Day11.cs

using AdvenOfCode.Contracts;

namespace AoC_2025;

public class Day11 : IPuzzleSolver<long>
{
    private Dictionary<string, string[]> ParsePuzzleInput(string path)
    {
        var puzzleInput = File.ReadAllLines(path)
            .Where(line => !string.IsNullOrWhiteSpace(line))
            .Select(line => line.Split(':', StringSplitOptions.RemoveEmptyEntries | StringSplitOptions.TrimEntries))
            .Select(line => (line[0], line[1].Split(' ', StringSplitOptions.RemoveEmptyEntries)))
            .ToDictionary();
            
        return puzzleInput;
    }

    public long SolvePart1(string pathToPuzzleInput)
    {
        var connections = ParsePuzzleInput(pathToPuzzleInput);
        var pathsToOut = GetAmountPaths("you", "out", connections, []);
        return pathsToOut;
    }

    public long SolvePart2(string pathToPuzzleInput)
    {
        var connections = ParsePuzzleInput(pathToPuzzleInput);
        var pathsToOut = GetAmountPathsThrough("svr", "out", ["dac", "fft"], connections, []);
        return pathsToOut;
    }

    private long GetAmountPaths(string from, string to, Dictionary<string, string[]> paths, Dictionary<(string, string), long> memory)
    {
        if (from == to) return 1;
        if (memory.TryGetValue((from, to), out var res)) return res;
        if (!paths.TryGetValue(from, out var pathsToCheck)) return 0;
        
        var totalAmount = pathsToCheck.Sum(path => GetAmountPaths(path, to, paths, memory));

        memory[(from, to)] = totalAmount;
        return totalAmount;
    }
    
    private long GetAmountPathsThrough(string from, string to, HashSet<string> through, 
        Dictionary<string, string[]> paths, 
        Dictionary<(string, string), (long, HashSet<string>)> memory)
    {
        through.Remove(from);
        if (from == to) return through.Count == 0 ? 1 : 0;
        if (memory.TryGetValue((from, to), out var res) && res.Item2.SetEquals(through)) return res.Item1;
        if (!paths.TryGetValue(from, out var pathsToCheck)) return 0;
        
        var totalAmount = pathsToCheck.Sum(path => GetAmountPathsThrough(path, to, [..through], paths, memory));

        memory[(from, to)] = (totalAmount, through);
        return totalAmount;
    }
}