Advent of Code 2023 - Day 21

var input = File.ReadAllLines("input.txt");
// The grid is a square of 131x131 tiles. S is in the exact center at (65, 65).
// The edge rows and columns are all open, and S has a straight path to all of them.
// It takes 65 steps to reach the first set of edges, then 131 more to reach every next set.
// When we reach the first edges, the points form a diamond.
// Then we run to the next edges, and to the ones after that, making the diamond grow.
// For each of those 3 runs, we will store the number of steps taken (x) and the number of open tiles at that step (y).
// 3 pairs are enough to interpolate the growth function - y = f(x),
// so I went searching for an online Lagrange interpolation calculator,
// because that is all I can remember about numerical methods from college. :)
// I found this, and it helped: https://www.dcode.fr/lagrange-interpolating-polynomial
// It's a quadratic formula! (it's a square grid, and with every step we form a perfect diamond, so it makes sense)
// So we can just calculate the formula for X = 26501365, and we get the answer.

const long totalSteps = 26501365L;

var sequenceCounts = new List<(int X, int Y)>();
var startPosition = input.Length / 2; // 65
var start = new Position(startPosition, startPosition);
var visited = new HashSet<Position> { start };
var steps = 0;

for (var run = 0; run < 3; run++)
{
    for (; steps < run * 131 + 65; steps++) // First run is 65 steps, the rest are 131 each.
    {
        var nextOpen = new HashSet<Position>();
        foreach (var position in visited)
        {
            foreach (var dir in new[] { Direction.Up, Direction.Down, Direction.Left, Direction.Right })
            {
                var dest = position.Move(dir);
                if (input[Modulo(dest.Row)][Modulo(dest.Col)] != '#')
                {
                    nextOpen.Add(dest);
                }
            }
        }

        visited = nextOpen;

        if (steps == 63)
        {
            Console.WriteLine($"Part 1: {visited.Count}");
        }
    }
    sequenceCounts.Add((steps, visited.Count));
}

// Lagrange interpolation
double result = 0;

for (var i = 0; i < 3; i++)
{
    // Compute individual terms of formula
    double term = sequenceCounts[i].Y;

    for (var j = 0; j < 3; j++)
    {
        if (j != i)
        {
            term = term * (totalSteps - sequenceCounts[j].X) / (sequenceCounts[i].X - sequenceCounts[j].X);
        }
    }

    // Add current term to result
    result += term;
}

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

return;

static int Modulo(int number)
{
    return ((number % 131) + 131) % 131;
}

internal record Direction(int Row, int Col)
{
    public static Direction Up = new(-1, 0);
    public static Direction Down = new(1, 0);
    public static Direction Left = new(0, -1);
    public static Direction Right = new(0, 1);
}

internal record Position(int Row, int Col)
{
    public Position Move(Direction dir)
    {
        return new Position(Row + dir.Row, Col + dir.Col);
    }
}