undefined

     
Data  ← ≡◇(⊜⋕⊸≠@,)°/$"_\n_" "5,4\n4,2\n4,5\n3,0\n2,1\n6,3\n2,4\n1,5\n0,6\n3,3\n2,6\n5,1\n1,2\n5,5\n2,5\n6,5\n1,4\n0,4\n6,4\n1,1\n6,1\n1,0\n0,5\n1,6\n2,0"
End   ← 6_6
Count ← 12

D₄      ← [1_0 ¯1_0 0_1 0_¯1]
Valid   ← ▽¬⊸∊:▽⊸(≡/××⊃(≤⊢End|≥0))+D₄¤
BestLen ← ⍣(-1⧻⊢path(Valid|≍End)0_0↙:Data|∞)
Chop!   ← ◌⍢(⨬(⊙◌+1|⊙⊙◌:):⟜^0⌊÷2+,,|>)

&p BestLen Count
&p/$"_,_"⊏:Data-1Chop!(=∞BestLen)Count ⧻Data


  

 undefined

    
import 'dart:math';
import 'package:collection/collection.dart';
import 'package:more/more.dart';

var d4 = <Point<num>>[Point(0, 1), Point(0, -1), Point(1, 0), Point(-1, 0)];

solve(List<String> lines, int count, Point end, bool inPart1) {
  var blocks = (lines
      .map((e) => e.split(',').map(int.parse).toList())
      .map((p) => Point<num>(p[0], p[1]))).toList();
  var blocksSofar = blocks.take(count).toSet();
  var start = Point(0, 0);
  Map<Point, num> fNext(Point here) => {
        for (var d in d4
            .map((d) => d + here)
            .where((e) =>
                e.x.between(start.x, end.x) &&
                e.y.between(start.y, end.y) &&
                !blocksSofar.contains(e))
            .toList())
          d: 1
      };

  int fHeur(Point here) => 1;
  bool fAtEnd(Point here) => here == end;
  var cost = aStarSearch<Point>(start, fNext, fHeur, fAtEnd);

  if (inPart1) return cost.first;
  var lo = count, hi = blocks.length;
  while (lo <= hi) {
    var mid = (lo + hi) ~/ 2;
    blocksSofar = blocks.take(mid).toSet();
    cost = aStarSearch<Point>(start, fNext, fHeur, fAtEnd);
    (cost.first > 0) ? lo = mid + 1 : hi = mid - 1;
  }
  var p = blocks[lo - 1];
  return '${p.x},${p.y}';
}

part1(lines, count, end) => solve(lines, count, end, true);
part2(lines, count, end) => solve(lines, count, end, false);

  

 undefined

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

namespace Day18;

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

        var sampleInput = ReceiveInput("sample.txt");
        var sampleBounds = new Point(7,7);
        
        var programInput = ReceiveInput("input.txt");
        var programBounds = new Point(71, 71);

        Console.WriteLine($"Part 1 sample: {Part1(sampleInput, 12, sampleBounds)}");
        Console.WriteLine($"Part 1 input: {Part1(programInput, 1024, programBounds)}");

        Console.WriteLine($"Part 2 sample: {Part2(sampleInput, 12, sampleBounds)}");
        Console.WriteLine($"Part 2 input: {Part2(programInput, 1024, programBounds)}");

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

    static int Part1(ImmutableArray<Point> input, int num, Point bounds) => FindBestPath(
        new Point(0, 0),
        new Point(bounds.Row - 1, bounds.Col - 1),
        input.Take(num).ToImmutableHashSet(),
        bounds);

    static object Part2(ImmutableArray<Point> input, int num, Point bounds)
    {
        var start = num;
        var end = input.Length;
        
        while (start != end)
        {
            var check = (start + end) / 2;
            if (Part1(input, check, bounds) < 0) end = check;
            else start = check + 1;
        }

        var lastPoint = input[start - 1];
        return $"{lastPoint.Col},{lastPoint.Row}";
    }

    record struct State(Point Location, int Steps);

    static int FindBestPath(Point start, Point end, ISet<Point> corruptedBytes, Point bounds)
    {
        var seenStates = new Dictionary<Point, int>();

        var queue = new Queue<State>();
        queue.Enqueue(new State(start, 0));
        while (queue.TryDequeue(out var state))
        {
            if (state.Location == end) return state.Steps;
            
            if (seenStates.TryGetValue(state.Location, out var bestSteps))
            {
                if (state.Steps >= bestSteps) continue;
            }
            
            seenStates[state.Location] = state.Steps;
            queue.EnqueueRange(state.Location.GetCardinalMoves()
                .Where(p => p.IsInBounds(bounds) && !corruptedBytes.Contains(p))
                .Select(p => new State(p, state.Steps + 1)));
        }

        return -1;
    }

    static ImmutableArray<Point> ReceiveInput(string file) => File.ReadAllLines(file)
        .Select(l => l.Split(','))
        .Select(p => new Point(int.Parse(p[1]), int.Parse(p[0])))
        .ToImmutableArray();
}

  

 undefined

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