Day 18: Ram Run
Megathread guidelines
- Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
- You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL
FAQ
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
1 point
C#
I did flood fill because i normally just do Dijkstra for this kind of stuff. watching the map print as it flooded was cool, had to disable it for part two though as it was too slow. Just let it run while I made a cup of tea instead of doing a binary search.
spoiler
namespace AoC2024.Day_18;
public class Day18 {
public const string CLEAR = ".";
public const string BLOCKED = "#";
public const string TRAVELED = "O";
public void Go()
{
var testGrid = GenerateGrid(71, 71);
PrintGrid(testGrid);
var coords = GetInputCoordinates(File.ReadAllText("\\AdventOfCode2024\\AoC\\src\\Day_18\\input.txt"));
testGrid = ApplyCoords(testGrid, coords.Take(1024).ToList(), BLOCKED);
PrintGrid(testGrid);
FloodFillGrid(testGrid, new Coordinate(0,0), new (70,70));
}
public void GoPart2()
{
var testGrid = GenerateGrid(71, 71);
PrintGrid(testGrid);
var coords = GetInputCoordinates(File.ReadAllText("\\AdventOfCode2024\\AoC\\src\\Day_18\\input.txt"));
for (int i = 1; i <= coords.Count; i++)
{
testGrid = ApplyCoords(testGrid, coords.Take(i).ToList(), BLOCKED);
PrintGrid(testGrid);
var result = FloodFillGrid(testGrid, new Coordinate(0,0), new (70,70));
if (result.Item2 == int.MaxValue)
{
var badCoord = coords[i - 1];
Console.WriteLine($"!!!!Coord Number: {i} with a value of ({badCoord.Column},{badCoord.Row}) IS A BLOCKER!!!!");
break;
}
else if (i%100 == 0)
{
var goodCoord = coords[i - 1];
Console.WriteLine($"Coord Number: {i} with a value of ({goodCoord.Column},{goodCoord.Row}) allows an exit in {result.Item2} steps");
}
}
}
public List<List<string>> GenerateGrid(int width, int height)
{
var grid = new List<List<string>>();
for (int i = 0; i < height; i++)
{
var row = new List<string>();
for (int j = 0; j < width; j++)
{
row.Add(CLEAR);
}
grid.Add(row);
}
return grid;
}
public void PrintGrid(List<List<string>> grid)
{
// foreach (var row in grid)
// {
// foreach (var value in row)
// {
// Console.Write($" {value} ");
// }
// Console.WriteLine();
// }
}
public List<List<string>> ApplyCoords(List<List<string>> grid, List<Coordinate> coordinates, string value)
{
foreach (var coord in coordinates)
{
grid[coord.Row][coord.Column] = value;
}
return grid;
}
public List<Coordinate> GetInputCoordinates(string input)
{
var coords = new List<Coordinate>();
foreach (var pair in input.Split(Environment.NewLine, StringSplitOptions.RemoveEmptyEntries))
{
var values = pair.Split(',', StringSplitOptions.RemoveEmptyEntries);
coords.Add(new Coordinate(values[1], values[0]));
}
return coords;
}
public (List<List<string>>, int) FloodFillGrid(List<List<string>> grid, Coordinate start, Coordinate target)
{
var newGrid = grid.Select(list => new List<string>(list)).ToList();
var previousGrid = grid;
newGrid[start.Row][start.Column] = TRAVELED;
int stepCounter = 0;
while (newGrid[target.Row][target.Column] != TRAVELED)
{
bool valueUpdatedInLoop = false;
previousGrid = newGrid;
newGrid = newGrid.Select(list => new List<string>(list)).ToList().ToList();
for (var row = 0; row < grid.Count; row++)
{
for (var column = 0; column < grid[row].Count; column++)
{
if (previousGrid[row][column] == CLEAR && IsAdjacentEqual(previousGrid, new Coordinate(row,column), TRAVELED))
{
newGrid[row][column] = TRAVELED;
valueUpdatedInLoop = true;
}
}
}
stepCounter++;
if (!valueUpdatedInLoop)
{
return (newGrid,int.MaxValue);
}
//Console.WriteLine($"Step counter: {stepCounter}");
PrintGrid(newGrid);
}
return (newGrid,stepCounter);
}
private bool IsAdjacentEqual(List<List<string>> grid, Coordinate location, string value)
{
if (location.Row < grid.Count-1 && grid[location.Row+1][location.Column] == value)
{
return true;
}
if (location.Column < grid[0].Count-1 && grid[location.Row][location.Column+1] == value)
{
return true;
}
if (location.Row > 0 && grid[location.Row-1][location.Column] == value)
{
return true;
}
if (location.Column > 0 && grid[location.Row][location.Column-1] == value)
{
return true;
}
return false;
}
public struct Coordinate
{
public Coordinate(int row, int column)
{
Row = row;
Column = column;
}
public Coordinate(string row, string column)
{
Row = int.Parse(row);
Column = int.Parse(column);
}
public int Row { get; set; }
public int Column { get; set; }
}
}
2 points
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");
}
}
2 points
Javascript
Reused my logic from Day 16. For part two I manually changed the bytes (i on line 271) to narrow in on a solution faster, but this solution should solve it eventually.
https://blocks.programming.dev/Zikeji/c8fdef54f78c4fb6a79cf1dc5551ff4d
2 points
Haskell
I did an easy optimization for part 2, but it’s not too slow without.
Solution
import Control.Monad
import Data.Ix
import Data.List
import Data.Map qualified as Map
import Data.Maybe
import Data.Set (Set)
import Data.Set qualified as Set
readInput :: String -> [(Int, Int)]
readInput = map readCoords . lines
where
readCoords l = let (a, _ : b) = break (== ',') l in (read a, read b)
findRoute :: (Int, Int) -> Set (Int, Int) -> Maybe [(Int, Int)]
findRoute goal blocked = go Set.empty (Map.singleton (0, 0) [])
where
go seen paths
| Map.null paths = Nothing
| otherwise =
(paths Map.!? goal)
`mplus` let seen' = Set.union seen (Map.keysSet paths)
paths' =
(`Map.withoutKeys` seen')
. foldl' (flip $ uncurry Map.insert) Map.empty
. concatMap (\(p, path) -> (,p : path) <$> step p)
$ Map.assocs paths
in go seen' paths'
step (x, y) = do
(dx, dy) <- [(0, -1), (0, 1), (-1, 0), (1, 0)]
let p' = (x + dx, y + dy)
guard $ inRange ((0, 0), goal) p'
guard $ p' `Set.notMember` blocked
return p'
dropAndFindRoutes goal skip bytes =
let drops = drop skip $ zip bytes $ drop 1 $ scanl' (flip Set.insert) Set.empty bytes
in zip (map fst drops) $ scanl' go (findRoute goal (snd $ head drops)) $ tail drops
where
go route (p, blocked) = do
r <- route
if p `elem` r then findRoute goal blocked else route
main = do
input <- readInput <$> readFile "input18"
let routes = dropAndFindRoutes (70, 70) 1024 input
print $ length <$> (snd . head) routes
print $ fst <$> find (isNothing . snd) routes
2 points
*
Dart
I knew keeping my search code from day 16 would come in handy, I just didn’t expect it to be so soon.
For Part 2 it finds that same path (laziness on my part), then does a simple binary chop to home in on the last valid path. (was then searches for the first block that will erm block that path, and re-runs the search after that block has dropped, repeating until blocked. Simple but okay. )
90 lines, half of which is my copied search method. Runs in a couple of seconds which isn’t great, but isn’t bad. Binary chop dropped it to 200ms.
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);
That search method
/// Returns cost to destination, plus list of routes to destination.
/// Does Dijkstra/A* search depending on whether heuristic returns 1 or
/// something better.
(num, List<List<T>>) aStarSearch<T>(T start, Map<T, num> Function(T) fNext,
int Function(T) fHeur, bool Function(T) fAtEnd,
{multiplePaths = false}) {
var cameFrom = SetMultimap<T, T>.fromEntries([MapEntry(start, start)]);
var ends = <T>{};
var front = PriorityQueue<T>((a, b) => fHeur(a).compareTo(fHeur(b)))
..add(start);
var cost = <T, num>{start: 0};
while (front.isNotEmpty) {
var here = front.removeFirst();
if (fAtEnd(here)) {
ends.add(here);
continue;
}
var ns = fNext(here);
for (var n in ns.keys) {
var nCost = cost[here]! + ns[n]!;
if (!cost.containsKey(n) || nCost < cost[n]!) {
cost[n] = nCost;
front.add(n);
cameFrom.removeAll(n);
cameFrom[n].add(here);
}
if (multiplePaths && cost[n] == nCost) cameFrom[n].add(here);
}
}
Iterable<List<T>> routes(T h) sync* {
if (h == start) {
yield [h];
return;
}
for (var p in cameFrom[h]) {
yield* routes(p).map((e) => e + [h]);
}
}
if (ends.isEmpty) return (-1, []);
var minCost = ends.map((e) => cost[e]!).min;
ends = ends.where((e) => cost[e]! == minCost).toSet();
return (minCost, ends.fold([], (s, t) => s..addAll(routes(t).toList())));
}
