I'm confused reading the buildQuine() method. It reads to me that when you call it from the top level with top = true, A0 will be set to 0, and then when we get to the 0 to 8 loop, the 'A' register will be 0 * 8 + 0 for the first iteration, and then recurse with top = false, but with a0 still ending up 0, causing infinite recursion.

Am I missing something?

I got it to work with a check that avoids the recursion if the last state's A register value is the same as the new state's value.

This is giving me Punch Out vibes. Little Mac vs King Hippo.

I guess I'll never know what the kids are saying ever again because there's no way I'm installing either of those apps.

C#

Ended up modifying part 1 to do part 2 and return both answers at once.

using System.Collections.Immutable;
using System.Diagnostics;
using Common;

namespace Day16;

static class Program
{
    static void Main()
    {
        var start = Stopwatch.GetTimestamp();

        var smallInput = Input.Parse("smallsample.txt");
        var sampleInput = Input.Parse("sample.txt");
        var programInput = Input.Parse("input.txt");

        Console.WriteLine($"Part 1 small: {Solve(smallInput)}");
        Console.WriteLine($"Part 1 sample: {Solve(sampleInput)}");
        Console.WriteLine($"Part 1 input: {Solve(programInput)}");

        Console.WriteLine($"That took about {Stopwatch.GetElapsedTime(start)}");
    }

    static (int part1, int part2) Solve(Input i)
    {
        State? endState = null;
        Dictionary<(Point, int), int> lowestScores = new();

        var queue = new Queue<State>();
        queue.Enqueue(new State(i.Start, 1, 0, ImmutableHashSet<Point>.Empty));
        while (queue.TryDequeue(out var state))
        {
            if (ElementAt(i.Map, state.Location) is '#')
            {
                continue;
            }

            if (lowestScores.TryGetValue((state.Location, state.DirectionIndex), out var lowestScoreSoFar))
            {
                if (state.Score > lowestScoreSoFar) continue;
            }

            lowestScores[(state.Location, state.DirectionIndex)] = state.Score;

            var nextStatePoints = state.Points.Add(state.Location);

            if (state.Location == i.End)
            {
                if ((endState is null) || (state.Score < endState.Score))
                    endState = state with { Points = nextStatePoints };
                else if (state.Score == endState.Score)
                    endState = state with { Points = nextStatePoints.Union(endState.Points) };
                continue;
            }

            // Walk forward
            queue.Enqueue(state with
            {
                Location = state.Location.Move(CardinalDirections[state.DirectionIndex]),
                Score = state.Score + 1,
                Points = nextStatePoints,
            });

            // Turn clockwise
            queue.Enqueue(state with
            {
                DirectionIndex = (state.DirectionIndex + 1) % CardinalDirections.Length,
                Score = state.Score + 1000,
                Points = nextStatePoints,
            });

            // Turn counter clockwise
            queue.Enqueue(state with
            {
                DirectionIndex = (state.DirectionIndex + CardinalDirections.Length - 1) % CardinalDirections.Length,
                Score = state.Score + 1000,
                Points = nextStatePoints, 
            });
        }

        if (endState is null) throw new Exception("No end state found!");
        return (endState.Score, endState.Points.Count);
    }

    public static void DumpMap(Input i, ISet<Point>? points, Point current)
    {
        for (int row = 0; row < i.Bounds.Row; row++)
        {
            for (int col = 0; col < i.Bounds.Col; col++)
            {
                var p = new Point(row, col);
                Console.Write(
                    (p == current) ? 'X' :
                    (points?.Contains(p) ?? false) ? 'O' :
                    ElementAt(i.Map, p));
            }

            Console.WriteLine();
        }

        Console.WriteLine();
    }

    public static char ElementAt(string[] map, Point location) => map[location.Row][location.Col];

    public record State(Point Location, int DirectionIndex, int Score, ImmutableHashSet<Point> Points);

    public static readonly Direction[] CardinalDirections =
        [Direction.Up, Direction.Right, Direction.Down, Direction.Left];
}

public class Input
{
    public string[] Map { get; init; } = [];
    public Point Start { get; init; } = new(-1, -1);
    public Point End { get; init; } = new(-1, -1);
    public Point Bounds => new(this.Map.Length, this.Map[0].Length);

    public static Input Parse(string file)
    {
        var map = File.ReadAllLines(file);
        Point start = new(-1, -1), end = new(-1, -1);
        foreach (var p in map
            .SelectMany((line, i) => new []
            {
                 new Point(i, line.IndexOf('S')),
                 new Point(i, line.IndexOf('E')),
            })
            .Where(p => p.Col >= 0)
            .Take(2))
        {
            if (map[p.Row][p.Col] is 'S') start = p;
            else end = p;
        }

        return new Input()
        {
            Map = map,
            Start = start,
            End = end,
        };
    }
}

It's a simple record type I use for (x,y) coordinate problems:

record struct Point(int X, int Y);

It's defined in a separate project containing things I use in multiple problems.

Maybe I could have done it that way, but this was the first thing I thought of, and it worked :)

C#

Thank goodness for high school algebra!

using System.Diagnostics;
using Common;

namespace Day13;

static class Program
{
    static void Main()
    {
        var start = Stopwatch.GetTimestamp();

        var sampleInput = Input.ParseInput("sample.txt");
        var programInput = Input.ParseInput("input.txt");

        Console.WriteLine($"Part 1 sample: {Part1(sampleInput)}");
        Console.WriteLine($"Part 1 input: {Part1(programInput)}");

        Console.WriteLine($"Part 2 sample: {Part2(sampleInput)}");
        Console.WriteLine($"Part 2 input: {Part2(programInput)}");

        Console.WriteLine($"That took about {Stopwatch.GetElapsedTime(start)}");
    }

    static object Part1(Input i) => i.Machines
        .Select(m => CalculateCoins(m, 100))
        .Where(c => c > 0)
        .Sum();

    static object Part2(Input i) => i.Machines
        .Select(m => m with { Prize = new XYValues(
            m.Prize.X + 10000000000000,
            m.Prize.Y + 10000000000000) })
        .Select(m => CalculateCoins(m, long.MaxValue))
        .Where(c => c > 0)
        .Sum();

    static long CalculateCoins(Machine m, long limit)
    {
        var bBottom = (m.A.X * m.B.Y) - (m.A.Y * m.B.X);
        if (bBottom == 0) return -1;

        var bTop = (m.Prize.Y * m.A.X) - (m.Prize.X * m.A.Y);
        var b = bTop / bBottom;
        if ((b <= 0) || (b > limit)) return -1;
        
        var a = (m.Prize.X - (b * m.B.X)) / m.A.X;
        if ((a <= 0) || (a > limit)) return -1;

        var calcPrizeX = (a * m.A.X) + (b * m.B.X);
        var calcPrizeY = (a * m.A.Y) + (b * m.B.Y);
        if ((m.Prize.X != calcPrizeX) || (m.Prize.Y != calcPrizeY)) return -1;

        return (3 * a) + b;
    }
}

public record struct Machine(XYValues A, XYValues B, XYValues Prize);
public record struct XYValues(long X, long Y);

public class Input
{
    private Input()
    {
    }

    public List<Machine> Machines { get; init; }

    public static Input ParseInput(string file)
    {
        var machines = new List<Machine>();

        var lines = File.ReadAllLines(file);
        for(int l=0; l<lines.Length; l+=4)
        {
            machines.Add(new Machine(
                ParseXYValues(lines[l + 0]),
                ParseXYValues(lines[l + 1]),
                ParseXYValues(lines[l + 2])));
        }

        return new Input()
        {
            Machines = machines,
        };
    }

    private static readonly char[] XYDelimiters = ['X', 'Y', '=', '+', ',', ' '];

    private static XYValues ParseXYValues(string s)
    {
        var parts = s
            .Substring(s.IndexOf(':') + 1)
            .SplitAndTrim(XYDelimiters)
            .Select(long.Parse)
            .ToArray();
        
        return new XYValues(parts[0], parts[1]);
    }
}

C#

There is probably a more efficient way of finding the sides, but this way was what came to me.

using System.Diagnostics;
using Common;

namespace Day12;

static class Program
{
    static void Main()
    {
        var start = Stopwatch.GetTimestamp();

        var sampleInput = Input.ParseInput("sample.txt");
        var programInput = Input.ParseInput("input.txt");

        var (samplePart1, samplePart2) = Solve(sampleInput);
        Console.WriteLine($"Part 1 sample: {samplePart1}");
        Console.WriteLine($"Part 1 input: {samplePart2}");

        var (inputPart1, inputPart2) = Solve(programInput);
        Console.WriteLine($"Part 2 sample: {inputPart1}");
        Console.WriteLine($"Part 2 input: {inputPart2}");

        Console.WriteLine($"That took about {Stopwatch.GetElapsedTime(start)}");
    }

    static (int part1, int part2) Solve(Input i)
    {
        var retail = 0;
        var bulk = 0;
        var allPlotPoints = new Dictionary<char, HashSet<Point>>();
        foreach (var p in Grid.EnumerateAllPoints(i.Bounds))
        {
            var plant = i.ElementAt(p);

            if (!allPlotPoints.TryGetValue(plant, out var previousPlotPoints))
            {
                previousPlotPoints = new();
                allPlotPoints[plant] = previousPlotPoints;
            }
            else if (previousPlotPoints.Contains(p)) continue;

            var plotPoints = new HashSet<Point>();
            var perimeter = SearchPlot(i, plotPoints, plant, p);
            var area = plotPoints.Count;
            var sides = CountSides(plotPoints);
            retail += area * perimeter;
            bulk += area * sides;

            previousPlotPoints.AddRange(plotPoints);
        }

        return (retail, bulk);
    }

    static int CountSides(HashSet<Point> plot)
    {
        var sides = 0;

        // Track the points we've visited searching for sides
        HashSet<Point> visitedDownRight = new(),
            visitedDownLeft = new(),
            visitedRightDown = new(),
            visitedRightUp = new();

        // Sort the points in the plot from upper-left to lower-right, so we can
        // go through them in reading order
        foreach (var p in plot.OrderBy(p => (p.Row * 10000) + p.Col))
        {
            // Move right while looking up
            sides += GetSideLength(p, plot, visitedRightUp, Direction.Right, Direction.Up) > 0 ? 1 : 0;
            
            // Move right while looking down
            sides += GetSideLength(p, plot, visitedRightDown, Direction.Right, Direction.Down) > 0 ? 1 : 0;
            
            // Move down while looking right
            sides += GetSideLength(p, plot, visitedDownRight, Direction.Down, Direction.Right) > 0 ? 1 : 0;
            
            // Move down while looking left
            sides += GetSideLength(p, plot, visitedDownLeft, Direction.Down, Direction.Left) > 0 ? 1 : 0;
        }

        return sides;
    }

    static int GetSideLength(Point p, HashSet<Point> plotPoints, HashSet<Point> visited, Direction move, Direction look)
    {
        if (!plotPoints.Contains(p)) return 0;
        if (!visited.Add(p)) return 0;
        if (plotPoints.Contains(p.Move(look))) return 0;
        return 1 + GetSideLength(p.Move(move), plotPoints, visited, move, look);
    }

    static int SearchPlot(Input i, HashSet<Point> plotPoints, char plant, Point p)
    {
        if (!plotPoints.Add(p)) return 0;
        return p
            .GetCardinalMoves()
            .Select(move =>
            {
                if (!i.IsInBounds(move) || (i.ElementAt(move) != plant)) return 1;
                return SearchPlot(i, plotPoints, plant, move);
            })
            .Sum();
    }
}

public class Input
{
    public required string[] Map { get; init; }
    
    public Point Bounds => new Point(this.Map.Length, this.Map[0].Length);
    public char ElementAt(Point p) => this.Map[p.Row][p.Col];
    public bool IsInBounds(Point p) => p.IsInBounds(this.Map.Length, this.Map[0].Length);
    
    public static Input ParseInput(string file) => new Input()
    {
        Map = File.ReadAllLines(file),
    };
}

I had a very similar take on this problem, but I was not caching the results of a blink for a single stone, like youre doing with subtree_pointers. I tried adding that to my solution, but it didn't make an appreciable difference. I think that caching the lengths is really the only thing that matters.

C#

    static object Solve(Input i, int numBlinks)
    {
        // This is a cache of the tuples of (stoneValue, blinks) to
        // the calculated count of their child stones.
        var lengthCache = new Dictionary<(long, int), long>();
        return i.InitialStones
            .Sum(stone => CalculateUltimateLength(stone, numBlinks, lengthCache));
    }

    static long CalculateUltimateLength(
        long stone,
        int numBlinks,
        IDictionary<(long, int), long> lengthCache)
    {
        if (numBlinks == 0) return 1;
        
        if (lengthCache.TryGetValue((stone, numBlinks), out var length)) return length;

        length = Blink(stone)
            .Sum(next => CalculateUltimateLength(next, numBlinks - 1, lengthCache));
        lengthCache[(stone, numBlinks)] = length;
        return length;
    }

    static long[] Blink(long stone)
    {
        if (stone == 0) return [1];

        var stoneText = stone.ToString();
        if (stoneText.Length % 2 == 0)
        {
            var halfLength = stoneText.Length / 2;
            return
            [
                long.Parse(stoneText.Substring(0, halfLength)),
                long.Parse(stoneText.Substring(halfLength)),
            ];
        }

        return [stone * 2024];
    }

I totally brute forced this one, and it only took about 2 seconds to run, so I call that a win.

• Keep track of all points visited on part 1.
• loop over them, placing an extra rock at that position each time through.
• run part 1
• if you ever end up at any position you had already visited while facing the same direction, then you're in a loop.
• Otherwise, stop if you go off the map.

Straightforward depth first search. I found that the only difference for part 2 was to remove the current location from the HashSet of visited locations when the recurive call finished so that it could be visited again in other unique paths.

C#

using System.Diagnostics;
using Common;

namespace Day10;

static class Program
{
    static void Main()
    {
        var start = Stopwatch.GetTimestamp();

        var sampleInput = Input.ParseInput("sample.txt");
        var programInput = Input.ParseInput("input.txt");

        Console.WriteLine($"Part 1 sample: {Part1(sampleInput)}");
        Console.WriteLine($"Part 1 input: {Part1(programInput)}");

        Console.WriteLine($"Part 2 sample: {Part2(sampleInput)}");
        Console.WriteLine($"Part 2 input: {Part2(programInput)}");

        Console.WriteLine($"That took about {Stopwatch.GetElapsedTime(start)}");
    }

    static object Part1(Input i) => GetTrailheads(i)
        .Sum(th => CountTheNines(th, i, new HashSet<Point>(), false));

    static object Part2(Input i) => GetTrailheads(i)
        .Sum(th => CountTheNines(th, i, new HashSet<Point>(), true));

    static int CountTheNines(Point loc, Input i, ISet<Point> visited, bool allPaths)
    {
        if (!visited.Add(loc)) return 0;
        
        var result =
            (ElevationAt(loc, i) == 9) ? 1 :
            loc.GetCardinalMoves()
                .Where(move => move.IsInBounds(i.Bounds.Row, i.Bounds.Col))
                .Where(move => (ElevationAt(move, i) - ElevationAt(loc, i)) == 1)
                .Where(move => !visited.Contains(move))
                .Sum(move => CountTheNines(move, i, visited, allPaths));
        
        if(allPaths) visited.Remove(loc);
        
        return result;
    }

    static IEnumerable<Point> GetTrailheads(Input i) => Grid.EnumerateAllPoints(i.Bounds)
        .Where(loc => ElevationAt(loc, i) == 0);

    static int ElevationAt(Point p, Input i) => i.Map[p.Row][p.Col];
}

public class Input
{
    public required Point Bounds { get; init; }
    public required int[][] Map { get; init; }
    
    public static Input ParseInput(string file)
    {
        using var reader = new StreamReader(file);
        var map = reader.EnumerateLines()
            .Select(l => l.Select(c => (int)(c - '0')).ToArray())
            .ToArray();
        var bounds = new Point(map.Length, map.Max(l => l.Length));
        return new Input()
        {
            Map = map,
            Bounds = bounds,
        };
    }
}

I wish the web interface let you sort the sub categories both ways. I have a series of subcategories of Year/month that I'm using as a journal and the longer I keep writing, the further have to scroll down :/