hades

This. There's just so much game in that game.

Definitely threw off my meat LLM.

It's interesting that you're not checking if the solution to x is a whole number. I guess the data doesn't contain any counterexamples.

C#

public partial class Day13 : Solver
{
  private record struct Button(int X, int Y);
  private record struct Machine(int X, int Y, Button A, Button B);
  private List<Machine> machines = [];

  [GeneratedRegex(@"^Button (A|B): X\+(\d+), Y\+(\d+)$")]
  private static partial Regex ButtonSpec();

  [GeneratedRegex(@"^Prize: X=(\d+), Y=(\d+)$")]
  private static partial Regex PrizeSpec();

  public void Presolve(string input) {
    var machine_specs = input.Trim().Split("\n\n").ToList();
    foreach (var spec in machine_specs) {
      var lines = spec.Split("\n").ToList();
      if (ButtonSpec().Match(lines[0]) is not { Success: true } button_a_match
        || ButtonSpec().Match(lines[1]) is not { Success: true } button_b_match
        || PrizeSpec().Match(lines[2]) is not { Success:true} prize_match) {
        throw new InvalidDataException($"parse error: ${lines}");
      }
      machines.Add(new Machine(
        int.Parse(prize_match.Groups[1].Value),
        int.Parse(prize_match.Groups[2].Value),
        new Button(int.Parse(button_a_match.Groups[2].Value), int.Parse(button_a_match.Groups[3].Value)),
        new Button(int.Parse(button_b_match.Groups[2].Value), int.Parse(button_b_match.Groups[3].Value))
        ));
    }
  }

  private string Solve(bool unit_conversion) {
    BigInteger total_cost = 0;
    foreach (var machine in machines) {
      long prize_x = machine.X + (unit_conversion ? 10000000000000 : 0);
      long prize_y = machine.Y + (unit_conversion ? 10000000000000 : 0);
      BigInteger det = machine.A.X * machine.B.Y - machine.B.X * machine.A.Y;
      if (det == 0) continue;
      BigInteger det_a = prize_x * machine.B.Y - machine.B.X * prize_y;
      BigInteger det_b = prize_y * machine.A.X - machine.A.Y * prize_x;
      var (a, a_rem) = BigInteger.DivRem(det_a, det);
      var (b, b_rem) = BigInteger.DivRem(det_b, det);
      if (a_rem != 0 || b_rem != 0) continue;
      total_cost += a * 3 + b;
    }
    return total_cost.ToString();
  }

  public string SolveFirst() => Solve(false);
  public string SolveSecond() => Solve(true);
}

What is the Point type? I'm surprised that you can't just lexicographically sort instead of plot.OrderBy(p => (p.Row * 10000) + p.Col).

I think that caching the lengths is really the only thing that matters.

Yep, it is just a dynamic programming problem really.

C#

public class Day12 : Solver
{
  private string[] data;
  private int width, height;
  private Dictionary<int, long> perimeters = [];
  private Dictionary<int, long> areas = [];
  private Dictionary<int, long> sides = [];
  private int region_count;

  public void Presolve(string input) {
    data = input.Trim().Split("\n").ToArray();
    height = data.Length;
    width = data[0].Length;
    var graph_cc = MakeGraph(false);
    var cc = new ConnectedComponentsAlgorithm<Point, PointEdge>(graph_cc);
    cc.Compute();
    var graph_all = MakeGraph(true);
    Dictionary<(int Component, int Y), List<int>> x_sides = [];
    Dictionary<(int Component, int X), List<int>> y_sides = [];
    var search = new UndirectedBreadthFirstSearchAlgorithm<Point, PointEdge>(graph_all);
    search.SetRootVertex((0, 0));
    search.FinishVertex += vertex => {
      if (IsWithinBounds(vertex.Item1, vertex.Item2)) {
        int component = cc.Components[vertex];
        areas.TryAdd(component, 0L);
        areas[component] += 1;
      }
    };
    search.ExamineEdge += edge => {
      var (si, ti) = (IsWithinBounds(edge.Source), IsWithinBounds(edge.Target));
      bool border = si != ti || cc.Components[edge.Source] != cc.Components[edge.Target];
      if (si && border) {
        int component = cc.Components[edge.Source];
        perimeters.TryAdd(component, 0L);
        perimeters[component] += 1;
        if (edge.Source.Item1 == edge.Target.Item1) {
          int y = Math.Min(edge.Source.Item2, edge.Target.Item2);
          x_sides.TryAdd((component, y), []);
          x_sides[(component, y)].Add(edge.Source.Item2 > edge.Target.Item2 ? edge.Source.Item1 : -edge.Source.Item1 - 5);
        } else {
          int x = Math.Min(edge.Source.Item1, edge.Target.Item1);
          y_sides.TryAdd((component, x), []);
          y_sides[(component, x)].Add(edge.Source.Item1 > edge.Target.Item1 ? edge.Source.Item2 : -edge.Source.Item2 - 5);
        }
      }
    };
    search.Compute();
    region_count = cc.ComponentCount;
    foreach (var side_projection in x_sides) {
      side_projection.Value.Sort();
      sides.TryAdd(side_projection.Key.Component, 0);
      int last_x = int.MinValue;
      foreach (var x in side_projection.Value) {
        if (x != (last_x + 1)) sides[side_projection.Key.Component] += 1;
        last_x = x;
      }
    }
    foreach (var side_projection in y_sides) {
      side_projection.Value.Sort();
      sides.TryAdd(side_projection.Key.Component, 0);
      int last_y = int.MinValue;
      foreach (var y in side_projection.Value) {
        if (y != (last_y + 1)) sides[side_projection.Key.Component] += 1;
        last_y = y;
      }
    }
    foreach (var component in Enumerable.Range(0, region_count)) {
      if (!areas.ContainsKey(component)) continue;
    }
  }

  public string SolveFirst() =>
    Enumerable.Range(0, region_count)
      .Where(component => areas.ContainsKey(component))
      .Select(component => areas[component] * perimeters[component]).Sum().ToString();

  public string SolveSecond() =>
    Enumerable.Range(0, region_count)
      .Where(component => areas.ContainsKey(component))
      .Select(component => areas[component] * sides[component]).Sum().ToString();

  private record struct PointEdge(Point Source, Point Target): IEdge<Point>;

  private IUndirectedGraph<Point, PointEdge> MakeGraph(bool with_edges_between_plots)=>
    new DelegateUndirectedGraph<Point, PointEdge>(GetVertices(), with_edges_between_plots? GetAllEdges : GetEdgesWithoutBorders, false);

  private bool IsWithinBounds(int x, int y) => x >= 0 && x < width && y >= 0 && y < height;
  private bool IsWithinBounds(Point p) => IsWithinBounds(p.Item1, p.Item2);

  private readonly (int, int)[] directions = [(-1, 0), (0, -1), (1, 0), (0, 1)];

  private bool GetEdgesWithoutBorders(Point arg, out IEnumerable<PointEdge> result) {
    List<PointEdge> result_list = [];
    var (x, y) = arg;
    bool inside = IsWithinBounds(x, y);
    foreach (var (dx, dy) in directions) {
      var (ox, oy) = (x + dx, y + dy);
      if (!inside || !IsWithinBounds(ox, oy)) continue;
      if (data[y][x] == data[oy][ox]) result_list.Add(new(arg, (ox, oy)));
    }
    result = result_list;
    return true;
  }

  private bool GetAllEdges(Point arg, out IEnumerable<PointEdge> result) {
    List<PointEdge> result_list = [];
    var (x, y) = arg;
    foreach (var (dx, dy) in directions) {
      var (ox, oy) = (x + dx, y + dy);
      if (ox >= -1 && ox <= width && oy >= -1 && oy <= height) result_list.Add(new(arg, (ox, oy)));
    }
    result = result_list;
    return true;
  }

  private IEnumerable<(int, int)> GetVertices() => Enumerable.Range(-1, width + 2).SelectMany(x => Enumerable.Range(-1, height + 2).Select(y => (x, y)));
}

C#

public class Day11 : Solver
{
  private long[] data;

  private class TreeNode(TreeNode? left, TreeNode? right, long value) {
    public TreeNode? Left = left;
    public TreeNode? Right = right;
    public long Value = value;
  }

  private Dictionary<(long, int), long> generation_length_cache = [];
  private Dictionary<long, TreeNode> subtree_pointers = [];

  public void Presolve(string input) {
    data = input.Trim().Split(" ").Select(long.Parse).ToArray();
    List<TreeNode> roots = data.Select(value => new TreeNode(null, null, value)).ToList();
    List<TreeNode> last_level = roots;
    subtree_pointers = roots.GroupBy(root => root.Value)
      .ToDictionary(grouping => grouping.Key, grouping => grouping.First());
    for (int i = 0; i < 75; i++) {
      List<TreeNode> next_level = [];
      foreach (var node in last_level) {
        long[] children = Transform(node.Value).ToArray();
        node.Left = new TreeNode(null, null, children[0]);
        if (subtree_pointers.TryAdd(node.Left.Value, node.Left)) {
          next_level.Add(node.Left);
        }
        if (children.Length <= 1) continue;
        node.Right = new TreeNode(null, null, children[1]);
        if (subtree_pointers.TryAdd(node.Right.Value, node.Right)) {
          next_level.Add(node.Right);
        }
      }
      last_level = next_level;
    }
  }

  public string SolveFirst() => data.Select(value => GetGenerationLength(value, 25)).Sum().ToString();
  public string SolveSecond() => data.Select(value => GetGenerationLength(value, 75)).Sum().ToString();

  private long GetGenerationLength(long value, int generation) {
    if (generation == 0) { return 1; }
    if (generation_length_cache.TryGetValue((value, generation), out var result)) return result;
    TreeNode cur = subtree_pointers[value];
    long sum = GetGenerationLength(cur.Left.Value, generation - 1);
    if (cur.Right is not null) {
      sum += GetGenerationLength(cur.Right.Value, generation - 1);
    }
    generation_length_cache[(value, generation)] = sum;
    return sum;
  }

  private IEnumerable<long> Transform(long arg) {
    if (arg == 0) return [1];
    if (arg.ToString() is { Length: var l } str && (l % 2) == 0) {
      return [int.Parse(str[..(l / 2)]), int.Parse(str[(l / 2)..])];
    }
    return [arg * 2024];
  }
}

C#

using QuickGraph;
using QuickGraph.Algorithms.Search;
using Point = (int, int);

public class Day10 : Solver
{
  private int[][] data;
  private int width, height;
  private List<int> destinations_counts = [], paths_counts = [];
  private record PointEdge(Point Source, Point Target): IEdge<Point>;

  private DelegateVertexAndEdgeListGraph<Point, PointEdge> MakeGraph() => new(AllPoints(), GetNeighbours);

  private static readonly List<Point> directions = [(1, 0), (-1, 0), (0, 1), (0, -1)];

  private bool GetNeighbours(Point from, out IEnumerable<PointEdge> result) {
    List<PointEdge> neighbours = [];
    int next_value = data[from.Item2][from.Item1] + 1;
    foreach (var (dx, dy) in directions) {
      int x = from.Item1 + dx, y = from.Item2 + dy;
      if (x < 0 || y < 0 || x >= width || y >= height) continue;
      if (data[y][x] != next_value) continue;
      neighbours.Add(new(from, (x, y)));
    }
    result = neighbours;
    return true;
  }

  private IEnumerable<Point> AllPoints() => Enumerable.Range(0, width).SelectMany(x => Enumerable.Range(0, height).Select(y => (x, y)));

  public void Presolve(string input) {
    data = input.Trim().Split("\n").Select(s => s.Select(ch => ch - '0').ToArray()).ToArray();
    width = data[0].Length;
    height = data.Length;
    var graph = MakeGraph();
    for (int i = 0; i < width; i++) {
      for (int j = 0; j < height; j++) {
        if (data[j][i] != 0) continue;
        var search = new BreadthFirstSearchAlgorithm<Point, PointEdge>(graph);
        Point start = (i, j);
        Dictionary<Point, int> paths_into = [];
        paths_into[start] = 1;
        var destinations = 0;
        var paths = 0;
        search.ExamineEdge += edge => {
          paths_into.TryAdd(edge.Target, 0);
          paths_into[edge.Target] += paths_into[edge.Source];
        };
        search.FinishVertex += vertex => {
          if (data[vertex.Item2][vertex.Item1] == 9) {
            paths += paths_into[vertex];
            destinations += 1;
          }
        };
        search.SetRootVertex(start);
        search.Compute();
        destinations_counts.Add(destinations);
        paths_counts.Add(paths);
      }
    }
  }

  public string SolveFirst() => destinations_counts.Sum().ToString();
  public string SolveSecond() => paths_counts.Sum().ToString();
}

This part looks suspicious:

    for f in range(len(free) - 2):
        disk_map[free[f]] = disk_map.pop(max(disk_map.keys()))

You're always moving exactly len(free) - 2 blocks, but that doesn't sound to be correct in all cases. If you consider the following input: 191, you only need to move one block, and not seven.

I'm also doing 2016 concurrently with this year!

C#

public class Day09 : Solver
{
  private string data;

  public void Presolve(string input) {
    data = input.Trim();
  }

  public string SolveFirst() {
    var arr = new List<int>();
    bool file = true;
    int file_id = 0;
    foreach (var ch in data) {
      if (file) {
        Enumerable.Range(0, ch - '0').ToList().ForEach(_ => arr.Add(file_id));
        file_id++;
      } else {
        Enumerable.Range(0, ch - '0').ToList().ForEach(_ => arr.Add(-1));
      }
      file = !file;
    }
    int from_ptr = arr.Count - 1;
    int to_ptr = 0;
    while (from_ptr > to_ptr) {
      if (arr[to_ptr] != -1) {
        to_ptr++;
        continue;
      }
      if (arr[from_ptr] == -1) {
        from_ptr--;
        continue;
      }
      arr[to_ptr] = arr[from_ptr];
      arr[from_ptr] = -1;
      to_ptr++;
      from_ptr--;
    }
    return Enumerable.Range(0, arr.Count)
      .Select(block_id => arr[block_id] > 0 ? ((long)arr[block_id]) * block_id : 0)
      .Sum().ToString();
  }

  public string SolveSecond() {
    var files = new List<(int Start, int Size, int Id)>();
    bool is_file = true;
    int file_id = 0;
    int block_id = 0;
    foreach (var ch in data) {
      if (is_file) {
        files.Add((block_id, ch - '0', file_id));
        file_id++;
      }
      is_file = !is_file;
      block_id += (ch - '0');
    }
    while (true) {
      bool moved = false;
      for (int from_ptr = files.Count - 1; from_ptr >= 1; from_ptr--) {
        var file = files[from_ptr];
        if (file.Id >= file_id) continue;
        file_id = file.Id;
        for (int to_ptr = 0; to_ptr < from_ptr; to_ptr++) {
          if (files[to_ptr + 1].Start - files[to_ptr].Start - files[to_ptr].Size >= file.Size) {
            files.RemoveAt(from_ptr);
            files.Insert(to_ptr + 1, file with { Start = files[to_ptr].Start + files[to_ptr].Size });
            moved = true;
            break;
          }
        }
        if (moved) break;
      }
      if (!moved) break;
    }
    return files.Select(file => ((long)file.Id) * file.Size * (2 * ((long)file.Start) + file.Size - 1) / 2)
      .Sum().ToString();
  }
}