hades

C#

using QuickGraph;
using QuickGraph.Algorithms.ShortestPath;

namespace aoc24;

public class Day18 : Solver {
  private int width = 71, height = 71, bytes = 1024;
  private HashSet<(int, int)> fallen_bytes;
  private List<(int, int)> fallen_bytes_in_order;
  private record class Edge((int, int) Source, (int, int) Target) : IEdge<(int, int)>;
  private DelegateVertexAndEdgeListGraph<(int, int), Edge> MakeGraph() => new(GetAllVertices(), GetOutEdges);

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

  private bool GetOutEdges((int, int) arg, out IEnumerable<Edge> result_enumerable) {
    List<Edge> result = [];
    foreach (var (dx, dy) in directions) {
      var (nx, ny) = (arg.Item1 + dx, arg.Item2 + dy);
      if (nx < 0 || ny < 0 || nx >= width || ny >= height) continue;
      if (fallen_bytes.Contains((nx, ny))) continue;
      result.Add(new(arg, (nx, ny)));
    }
    result_enumerable = result;
    return true;
  }

  private IEnumerable<(int, int)> GetAllVertices() {
    for (int i = 0; i < width; i++) {
      for (int j = 0; j < height; j++) {
        yield return (i, j);
      }
    }
  }

  public void Presolve(string input) {
    fallen_bytes_in_order = [..input.Trim().Split("\n")
      .Select(line => line.Split(","))
      .Select(pair => (int.Parse(pair[0]), int.Parse(pair[1])))];
    fallen_bytes = [.. fallen_bytes_in_order.Take(bytes)];
  }

  private double Solve() {
    var graph = MakeGraph();
    var search = new AStarShortestPathAlgorithm<(int, int), Edge>(graph, _ => 1, vtx => vtx.Item1 + vtx.Item2);
    search.SetRootVertex((0, 0));
    search.ExamineVertex += vertex => {
      if (vertex.Item1 == width - 1 && vertex.Item2 == width - 1) search.Abort();
    };
    search.Compute();
    return search.Distances[(width - 1, height - 1)];
  }

  public string SolveFirst() => Solve().ToString();

  public string SolveSecond() {
    foreach (var b in fallen_bytes_in_order[bytes..]) {
      fallen_bytes.Add(b);
      if (Solve() > width*height) return $"{b.Item1},{b.Item2}";
    }
    throw new Exception("solution not found");
  }
}

Great find, thanks for sharing!

C#

public class Day17 : Solver {
  private List<int> program;
  private long a, b, c;

  public void Presolve(string input) {
    var data = input.Trim().Split("\n");
    a = long.Parse(Regex.Match(data[0], @"\d+").Value);
    b = long.Parse(Regex.Match(data[1], @"\d+").Value);
    c = long.Parse(Regex.Match(data[2], @"\d+").Value);
    program = data[4].Split(" ")[1].Split(",").Select(int.Parse).ToList();
  }

  public string SolveFirst() => String.Join(',', Execute(a, b, c));

  private List<int> Execute(long a, long b, long c) {
    List<int> output = [];
    Func<long, long> combo = operand => operand switch {
      <= 3 => operand,
      4 => a,
      5 => b,
      6 => c,
      _ => throw new InvalidDataException(),
    };
    int ip = 0;
    while (ip < program.Count - 1) {
      switch (program[ip]) {
        case 0:
          a = a >> (int)combo(program[ip + 1]);
          break;
        case 1:
          b = b ^ program[ip + 1];
          break;
        case 2:
          b = combo(program[ip + 1]) % 8;
          break;
        case 3:
          if (a != 0) {
            ip = program[ip + 1];
            continue;
          }
          break;
        case 4:
          b = b ^ c;
          break;
        case 5:
          output.Add((int)(combo(program[ip + 1]) % 8));
          break;
        case 6:
          b = a >> (int)combo(program[ip + 1]);
          break;
        case 7:
          c = a >> (int)combo(program[ip + 1]);
          break;
      }
      ip += 2;
    }
    return output;
  }

  public string SolveSecond() {
    Dictionary<int, List<(int, int, int)>> mapping = [];
    for (int start_a = 0; start_a < 512; start_a++) {
      var output = Execute(start_a, b, c);
      mapping.TryAdd(output[0], []);
      mapping[output[0]].Add((start_a / 64, start_a / 8 % 8, start_a % 8));
    }
    List<List<(int, int, int)>> possible_codes = [.. program.Select(b => mapping[b])];
    possible_codes.Reverse();
    List<int>? solution = SolvePossibleCodes(possible_codes, null);
    solution?.Reverse();
    long result = 0;
    foreach (var code in solution!) {
      result = (result << 3) | code;
    }
    return result.ToString();
  }

  private List<int>? SolvePossibleCodes(List<List<(int, int, int)>> possible_codes, (int, int)? allowed_start) {
    if (possible_codes.Count == 0) return [];
    foreach (var (high, mid, low) in possible_codes[0]) {
      if (allowed_start is null || allowed_start.Value.Item1 == high && allowed_start.Value.Item2 == mid) {
        var tail = SolvePossibleCodes(possible_codes[1..], (mid, low));
        if (tail is null) continue;
        tail.Add(low);
        if (allowed_start is null) {
          tail.Add(mid);
          tail.Add(high);
        }
        return tail;
      }
    }
    return null;
  }
}

I love the division sign on the numpad.

C#

beautiful

public class Day15 : Solver
{
  private char[][] map;
  private int width, height;
  private string movements;

  public void Presolve(string input) {
    var blocks = input.Trim().Split("\n\n").ToList();
    map = blocks[0].Split("\n").Select(line => line.ToArray()).ToArray();
    width = map[0].Length;
    height = map.Length;
    movements = blocks[1];
  }

  public string SolveFirst() {
    var data = map.Select(row => row.ToArray()).ToArray();
    int robot_x = -1, robot_y = -1;
    for (int i = 0; i < width; i++) {
      for (int j = 0; j < height; j++) {
        if (data[j][i] == '@') {
          robot_x = i;
          robot_y = j;
          data[j][i] = '.';
          break;
        }
      }
    }
    foreach (var m in movements) {
      var (dx, dy) = m switch {
        '^' => (0, -1), '>' => (1, 0), 'v' => (0, 1), '<' => (-1, 0),
          _ => (0, 0)
      };
      if ((dx, dy) == (0, 0)) continue;
      var (x, y) = (robot_x + dx, robot_y + dy);
      if (data[y][x] == '#') continue;
      if (data[y][x] == '.') {
        (robot_x, robot_y) = (x, y);
        continue;
      }
      var (end_of_block_x, end_of_block_y) = (x + dx, y + dy);
      while (data[end_of_block_y][end_of_block_x] == 'O') {
        (end_of_block_x, end_of_block_y) = (end_of_block_x + dx, end_of_block_y + dy);
      }
      if (data[end_of_block_y][end_of_block_x] == '.') {
        data[end_of_block_y][end_of_block_x] = 'O';
        data[y][x] = '.';
        (robot_x, robot_y) = (x, y);
      }
    }
    long answer = 0;
    for (int i = 0; i < width; i++) {
      for (int j = 0; j < height; j++) {
        if (data[j][i] == 'O') {
          answer += i + 100 * j;
        }
      }
    }
    return answer.ToString();
  }

  public string SolveSecond() {
    var expanded_data = map.Select(row => row.SelectMany<char, char>(ch => ch switch {
          '#' => ['#', '#'], 'O' => ['[', ']'], '.' => ['.', '.'], '@' => ['@', '.'] }).ToArray()).ToArray();
    int robot_x = -1, robot_y = -1;
    for (int i = 0; i < width * 2; i++) {
      for (int j = 0; j < height; j++) {
        if (expanded_data[j][i] == '@') {
          robot_x = i;
          robot_y = j;
          expanded_data[j][i] = '.';
          break;
        }
      }
    }
    if (robot_x < 0) throw new InvalidDataException();
    foreach (var m in movements) {
      var (dx, dy) = m switch {
        '^' => (0, -1), '>' => (1, 0), 'v' => (0, 1), '<' => (-1, 0),
          _ => (0, 0)
      };
      if ((dx, dy) == (0, 0)) continue;
      var (x, y) = (robot_x + dx, robot_y + dy);
      if (expanded_data[y][x] == '#') continue;
      if (expanded_data[y][x] == '.') {
        (robot_x, robot_y) = (x, y);
        continue;
      }
      if (dy == 0) {
        var (end_of_block_x, end_of_block_y) = (x + dx * 2, y);
        while (expanded_data[end_of_block_y][end_of_block_x] == '[' ||
               expanded_data[end_of_block_y][end_of_block_x] == ']') {
          (end_of_block_x, end_of_block_y) = (end_of_block_x + dx, end_of_block_y);
        }
        if (expanded_data[end_of_block_y][end_of_block_x] == '.') {
          var (fill_start, fill_end) = dx > 0 ? (x + 1, end_of_block_x) : (end_of_block_x, x);
          for (int fill_x = fill_start; fill_x < fill_end; fill_x += 2) {
            expanded_data[y][fill_x] = '[';
            expanded_data[y][fill_x + 1] = ']';
          }
          expanded_data[y][x] = '.';
          (robot_x, robot_y) = (x, y);
        }
        continue;
      }
      List<(int, int)> boxes_to_move = [(x, y)];
      if (expanded_data[y][x] == ']') {
        boxes_to_move.Add((x - 1, y));
      } else {
        boxes_to_move.Add((x + 1, y));
      }
      List<(int, int)> boxes_move_ordered = [];
      bool impossible = false;
      while (boxes_to_move.Count > 0) {
        HashSet<(int, int)> next_boxes = [];
        foreach (var (box_x, box_y) in boxes_to_move) {
          boxes_move_ordered.Add((box_x, box_y));
          if (expanded_data[box_y + dy][box_x] == '.') continue;
          if (expanded_data[box_y + dy][box_x] == '#') {
            impossible = true;
            break;
          }
          next_boxes.Add((box_x, box_y + dy));
          if (expanded_data[box_y + dy][box_x] == ']') {
            next_boxes.Add((box_x - 1, box_y + dy));
          } else {
            next_boxes.Add((box_x + 1, box_y + dy));
          }
        }
        if (impossible) break;
        boxes_to_move = [..next_boxes];
      }
      if (impossible) continue;
      boxes_move_ordered.Reverse();
      foreach (var (box_x, box_y) in boxes_move_ordered) {
        expanded_data[box_y + dy][box_x] = expanded_data[box_y][box_x];
        expanded_data[box_y][box_x] = '.';
      }
      (robot_x, robot_y) = (x, y);
    }
    long answer = 0;
    for (int i = 0; i < width * 2; i++) {
      for (int j = 0; j < height; j++) {
        if (expanded_data[j][i] == '[') {
          answer += i + 100 * j;
        }
      }
    }
    return answer.ToString();
  }
}

C#

using System.Text.RegularExpressions;

namespace aoc24;

[ForDay(14)]
public partial class Day14 : Solver
{
  [GeneratedRegex(@"^p=(-?\d+),(-?\d+) v=(-?\d+),(-?\d+)$")]
  private static partial Regex LineRe();

  private List<(int X, int Y, int Vx, int Vy)> robots = [];

  private int width = 101, height = 103;

  public void Presolve(string input) {
    var data = input.Trim();
    foreach (var line in data.Split("\n")) {
      if (LineRe().Match(line) is not { Success: true } match ) {
        throw new InvalidDataException($"parse error: ${line}");
      }
      robots.Add((
        int.Parse(match.Groups[1].Value),
        int.Parse(match.Groups[2].Value),
        int.Parse(match.Groups[3].Value),
        int.Parse(match.Groups[4].Value)
        ));
    }
  }

  public string SolveFirst() {
    Dictionary<(bool, bool), int> quadrants = [];
    foreach (var robot in robots) {
      int x = (robot.X + 100 * (robot.Vx > 0 ? robot.Vx : robot.Vx + width)) % width;
      int y = (robot.Y + 100 * (robot.Vy > 0 ? robot.Vy : robot.Vy + height)) % height;
      if (x == width/2 || y == height/2) continue;
      var q = (x < width / 2, y < height / 2);
      quadrants[q] = quadrants.GetValueOrDefault(q, 0) + 1;
    }
    return quadrants.Values.Aggregate((a, b) => a * b).ToString();
  }

  private int CountAdjacentRobots(HashSet<(int, int)> all_robots, (int, int) this_robot) {
    var (x, y) = this_robot;
    int count = 0;
    for (int ax = x - 1; all_robots.Contains((ax, y)); ax--) count++;
    for (int ax = x + 1; all_robots.Contains((ax, y)); ax++) count++;
    for (int ay = y - 1; all_robots.Contains((x, ay)); ay--) count++;
    for (int ay = y + 1; all_robots.Contains((x, ay)); ay++) count++;
    return count;
  }

  public string SolveSecond() {
    for (int i = 0; i < int.MaxValue; ++i) {
      HashSet<(int, int)> end_positions = [];
      foreach (var robot in robots) {
        int x = (robot.X + i * (robot.Vx > 0 ? robot.Vx : robot.Vx + width)) % width;
        int y = (robot.Y + i * (robot.Vy > 0 ? robot.Vy : robot.Vy + height)) % height;
        end_positions.Add((x, y));
      }
      if (end_positions.Select(r => CountAdjacentRobots(end_positions, r)).Max() > 10) {
        return i.ToString();
      }
    }
    throw new ArgumentException();
  }
}

C#

using QuickGraph;
using QuickGraph.Algorithms.ShortestPath;

namespace aoc24;

[ForDay(16)]
public class Day16 : Solver {
  private string[] data;
  private int width, height;
  private int start_x, start_y;
  private int end_x, end_y;

  private readonly (int, int)[] directions = [(1, 0), (0, 1), (-1, 0), (0, -1)];
  private record class Edge((int, int, int) Source, (int, int, int) Target) : IEdge<(int, int, int)>;

  private DelegateVertexAndEdgeListGraph<(int, int, int), Edge> graph;
  private AStarShortestPathAlgorithm<(int, int, int), Edge> search;

  private long min_distance;
  private List<(int, int, int)> min_distance_targets;

  public void Presolve(string input) {
    data = input.Trim().Split("\n");
    width = data[0].Length;
    height = data.Length;
    for (int i = 0; i < width; i++) {
      for (int j = 0; j < height; j++) {
        if (data[j][i] == 'S') {
          start_x = i;
          start_y = j;
        } else if (data[j][i] == 'E') {
          end_x = i;
          end_y = j;
        }
      }
    }
    graph = MakeGraph();
    var start = (start_x, start_y, 0);
    search = new AStarShortestPathAlgorithm<(int, int, int), Edge>(
      graph,
      edge => edge.Source.Item3 == edge.Target.Item3 ? 1 : 1000,
      vertex => Math.Abs(vertex.Item1 - start_x) + Math.Abs(vertex.Item2 - start_y) + 1000 *
          Math.Min(vertex.Item3, 4 - vertex.Item3)
      );
    Dictionary<(int, int, int), long> distances = [];
    search.SetRootVertex(start);
    search.ExamineVertex += vertex => {
      if (vertex.Item1 == end_x && vertex.Item2 == end_y) {
        distances[vertex] = (long)search.Distances[vertex];
      }
    };
    search.Compute();
    min_distance = distances.Values.Min();
    min_distance_targets = distances.Keys.Where(v => distances[v] == min_distance).ToList();
  }

  private DelegateVertexAndEdgeListGraph<(int, int, int), Edge> MakeGraph() => new(GetAllVertices(), GetOutEdges);

  private bool GetOutEdges((int, int, int) arg, out IEnumerable<Edge> result_enumerable) {
    List<Edge> result = [];
    var (x, y, dir) = arg;
    result.Add(new Edge(arg, (x, y, (dir + 1) % 4)));
    result.Add(new Edge(arg, (x, y, (dir + 3) % 4)));
    var (tx, ty) = (x + directions[dir].Item1, y + directions[dir].Item2);
    if (data[ty][tx] != '#') result.Add(new Edge(arg, (tx, ty, dir)));
    result_enumerable = result;
    return true;
  }

  private IEnumerable<(int, int, int)> GetAllVertices() {
    for (int i = 0; i < width; i++) {
      for (int j = 0; j < height; j++) {
        if (data[j][i] == '#') continue;
        yield return (i, j, 0);
        yield return (i, j, 1);
        yield return (i, j, 2);
        yield return (i, j, 3);
      }
    }
  }

  private HashSet<(int, int, int)> GetMinimumPathNodesTo((int, int, int) vertex) {
    var (x, y, dir) = vertex;
    if (x == start_x && y == start_y && dir == 0) return [vertex];
    if (!search.Distances.TryGetValue(vertex, out var distance_to_me)) return [];
    List<(int, int, int)> candidates = [
          (x, y, (dir + 1) % 4),
          (x, y, (dir + 3) % 4),
          (x - directions[dir].Item1, y - directions[dir].Item2, dir),
      ];
    HashSet<(int, int, int)> result = [vertex];
    foreach (var (cx, cy, cdir) in candidates) {
      if (!search.Distances.TryGetValue((cx, cy, cdir), out var distance_to_candidate)) continue;
      if (distance_to_candidate > distance_to_me - (dir == cdir ? 1 : 1000)) continue;
      result = result.Union(GetMinimumPathNodesTo((cx, cy, cdir))).ToHashSet();
    }
    return result;
  }

  public string SolveFirst() => min_distance.ToString();

  public string SolveSecond() => min_distance_targets
    .SelectMany(v => GetMinimumPathNodesTo(v))
    .Select(vertex => (vertex.Item1, vertex.Item2))
    .ToHashSet()
    .Count
    .ToString();
}

prev_nodes[neighbor].append(node)

I think you're adding too many neighbours to the prev_nodes here potentially. At the time you explore the edge, you're not yet sure if the path to the edge's target via the current node will be the cheapest.

I was just discussing day 8, which is also weirdly/vaguely/poorly worded, so maybe you're on to something here.

Well done! I like how you're just looking for four integers instead of bothering with parsing the rest of the line.

Very nice!

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