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();
  }
}

I don’t know what recursive rays are :)

But is it guaranteed that the guard will ever come from the left? As far as I can tell, you are just retracing the path from the part one.

C#

public class Day08 : Solver
{
  private ImmutableArray<string> data;
  private int width, height;

  public void Presolve(string input) {
    data = input.Trim().Split("\n").ToImmutableArray();
    width = data[0].Length;
    height = data.Length;
  }

  public string SolveFirst() {
    Dictionary<char, List<(int, int)>> antennae = [];
    HashSet<(int, int)> antinodes = [];
    for (int i = 0; i < width; i++) {
      for (int j = 0; j < height; j++) {
        if ('.' == data[j][i]) continue;
        antennae.TryAdd(data[j][i], []);
        foreach (var (oi, oj) in antennae[data[j][i]]) {
          int di = i - oi;
          int dj = j - oj;
          int ai = i + di;
          int aj = j + dj;
          if (ai >= 0 && aj >= 0 && ai < width && aj < height) {
            antinodes.Add((ai, aj));
          }
          ai = oi - di;
          aj = oj - dj;
          if (ai >= 0 && aj >= 0 && ai < width && aj < height) {
            antinodes.Add((ai, aj));
          }
        }
        antennae[data[j][i]].Add((i, j));
      }
    }
    return antinodes.Count.ToString();
  }

  public string SolveSecond() {
    Dictionary<char, List<(int, int)>> antennae = [];
    HashSet<(int, int)> antinodes = [];
    for (int i = 0; i < width; i++) {
      for (int j = 0; j < height; j++) {
        if ('.' == data[j][i]) continue;
        antennae.TryAdd(data[j][i], []);
        foreach (var (oi, oj) in antennae[data[j][i]]) {
          int di = i - oi;
          int dj = j - oj;
          for (int ai = i, aj = j;
               ai >= 0 && aj >= 0 && ai < width && aj < height; 
               ai += di, aj +=dj) {
            antinodes.Add((ai, aj));
          }
          for (int ai = oi, aj = oj;
               ai >= 0 && aj >= 0 && ai < width && aj < height; 
               ai -= di, aj -=dj) {
            antinodes.Add((ai, aj));
          }
        }
        antennae[data[j][i]].Add((i, j));
      }
    }
    return antinodes.Count.ToString();
  }
}

Check if turning right would lead back onto the recorded path in the same direction we walked it before

You’re checking this by casting one “ray” in the direction you’re turning. This will not always detect a cycle, it will only detect it, if your traversed path has already crossed one of the points of that “ray”. For example in this case:

.%..
...#
#...
.^#.

where % is the place where we put an obstacle.

Unrelated to the algorithm, I’ve noticed that you’re using type hints (which is great), but do you actually run a type checker? Because I don’t think tuple[int] is the correct type for values like (0, 1).

Wow, what a nice explanation, thank you!

I, for one, having never heard of Uiua, initially assumed it was one of those obtuse languages like Malbolge. Bit then I found its website, and it’s actually quite sensible!

looks slightly better than the code I have at work

you meant depth first, right? since you’re using recursion

C#

public class Day07 : Solver
{
  private ImmutableList<(long, ImmutableList<long>)> equations;

  public void Presolve(string input) {
    equations = input.Trim().Split("\n")
      .Select(line => line.Split(": "))
      .Select(split => (long.Parse(split[0]), split[1].Split(" ").Select(long.Parse).ToImmutableList()))
      .ToImmutableList();
  }

  private bool TrySolveWithConcat(long lhs, long head, ImmutableList<long> tail) {
    var lhs_string = lhs.ToString();
    var head_string = head.ToString();
    return lhs_string.Length > head_string.Length &&
      lhs_string.EndsWith(head_string) &&
      SolveEquation(long.Parse(lhs_string.Substring(0, lhs_string.Length - head_string.Length)), tail, true);
  }

  private bool SolveEquation(long lhs, ImmutableList<long> rhs, bool with_concat = false) {
    if (rhs.Count == 1) return lhs == rhs[0];
    long head = rhs[rhs.Count - 1];
    var tail = rhs.GetRange(0, rhs.Count - 1);
    return (SolveEquation(lhs - head, tail, with_concat))
      || (lhs % head == 0) && SolveEquation(lhs / head, tail, with_concat)
      || with_concat && TrySolveWithConcat(lhs, head, tail);
  }

  public string SolveFirst() => equations
    .Where(eq => SolveEquation(eq.Item1, eq.Item2))
    .Select(eq => eq.Item1)
    .Sum().ToString();
  public string SolveSecond() => equations
    .Where(eq => SolveEquation(eq.Item1, eq.Item2, true))
    .Select(eq => eq.Item1)
    .Sum().ToString();
}

Those unicode code points won’t use themselves.