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
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; }
}
}
Python
Nobody posted a solution in python for today???
Here is my solver with a little extra to print the Part 2 path. you can totally remove/comment out the printing out of the part 2 path, but it is neat to look at!
Execution time: ~25 milliseconds + an unnecessary ~7 ms to print part 2 path
This is the one where you don’t have it print out the Part 2 path and smaller: [ Paste ]
here is also a faster version that uses binary search instead. but its only a few milliseconds faster.
Execution time: ~21 milliseconds + an unnecessary ~7 ms to print part 2 path
C
Flood fill for part 1. Little tired so for part 2 I just retry the flood fill every step. Slow by C standards (2s) but I’ll let it brew and come back to it later.
Code
#include "common.h"
#define SAMPLE 0
#define GZ (SAMPLE ? 9 : 73)
#define NCORR (SAMPLE ? 12 : 1024)
#define CORR -1
int g[GZ][GZ];
static void
flood(void)
{
int x,y, dirty=1, lo;
for (y=1; y<GZ-1; y++)
for (x=1; x<GZ-1; x++)
if (g[y][x] > 1)
g[y][x] = 0;
while (dirty) {
dirty = 0;
for (y=1; y<GZ-1; y++)
for (x=1; x<GZ-1; x++) {
if (g[y][x] == CORR) continue;
lo = INT_MAX;
if (g[y-1][x] > 0) lo = MIN(lo, g[y-1][x]);
if (g[y+1][x] > 0) lo = MIN(lo, g[y+1][x]);
if (g[y][x-1] > 0) lo = MIN(lo, g[y][x-1]);
if (g[y][x+1] > 0) lo = MIN(lo, g[y][x+1]);
if (lo != INT_MAX && (!g[y][x] || g[y][x]>lo+1))
{ dirty=1; g[y][x] = lo+1; }
}
}
}
int
main(int argc, char **argv)
{
int p1=0, x,y, i;
if (argc > 1)
DISCARD(freopen(argv[1], "r", stdin));
for (i=0; i<GZ; i++)
g[0][i] = g[GZ-1][i] =
g[i][0] = g[i][GZ-1] = CORR;
g[1][1] = 1;
for (i=0; scanf(" %d,%d", &x, &y) == 2; i++) {
assert(x >= 0); assert(x < GZ-2);
assert(y >= 0); assert(y < GZ-2);
g[y+1][x+1] = CORR;
flood();
if (i==NCORR-1)
p1 = g[GZ-2][GZ-2]-1;
if (g[GZ-2][GZ-2] <= 0) {
printf("18: %d %d,%d\n", p1, x,y);
return 0;
}
}
assert(!"no solution");
return -1;
}
Part 2 can be faster if you iteratively remove blocks until there is a path. This is because it is faster to fail to find a path and the flood fill algorithm does not need to fill as many spots because the map would be filled up with more blocks! this drops the part 2 solve to a few milliseconds. others have taken a binary search option which is faster.
Thanks, that’s exactly the sort of insight that I was too tired to have at that point 😅
The other thing I had to change was to make it recursive rather than iterating over the full grid - the latter is fast for large update, but very wasteful for local updates, like removing the points. Virtually instant now!
Code
#include "common.h"
#define SAMPLE 0
#define PTZ 3600
#define GZ (SAMPLE ? 9 : 73)
#define P1STEP (SAMPLE ? 12 : 1024)
#define CORR -1
static int g[GZ][GZ];
static void
flood(int x, int y)
{
int lo=INT_MAX;
if (x <= 0 || x >= GZ-1 ||
y <= 0 || y >= GZ-1 || g[y][x] == CORR)
return;
if (g[y-1][x] > 0) lo = MIN(lo, g[y-1][x] +1);
if (g[y+1][x] > 0) lo = MIN(lo, g[y+1][x] +1);
if (g[y][x-1] > 0) lo = MIN(lo, g[y][x-1] +1);
if (g[y][x+1] > 0) lo = MIN(lo, g[y][x+1] +1);
if (lo != INT_MAX && (!g[y][x] || g[y][x] > lo)) {
g[y][x] = lo;
flood(x, y-1);
flood(x, y+1);
flood(x-1, y);
flood(x+1, y);
}
}
int
main(int argc, char **argv)
{
static int xs[PTZ], ys[PTZ];
static char p2[32];
int p1=0, npt=0, i;
if (argc > 1)
DISCARD(freopen(argv[1], "r", stdin));
for (i=0; i<GZ; i++)
g[0][i] = g[GZ-1][i] =
g[i][0] = g[i][GZ-1] = CORR;
for (npt=0; npt<PTZ && scanf(" %d,%d", xs+npt, ys+npt)==2; npt++) {
assert(xs[npt] >= 0); assert(xs[npt] < GZ-2);
assert(ys[npt] >= 0); assert(ys[npt] < GZ-2);
}
assert(npt < PTZ);
for (i=0; i<npt; i++)
g[ys[i]+1][xs[i]+1] = CORR;
g[1][1] = 1;
flood(2, 1);
flood(1, 2);
for (i=npt-1; i >= P1STEP; i--) {
g[ys[i]+1][xs[i]+1] = 0;
flood(xs[i]+1, ys[i]+1);
if (!p2[0] && g[GZ-2][GZ-2] > 0)
snprintf(p2, sizeof(p2), "%d,%d", xs[i],ys[i]);
}
p1 = g[GZ-2][GZ-2]-1;
printf("18: %d %s\n", p1, p2);
return 0;
}
Wooo! instant is so good, I knew you could do it! When I see my python script getting close to 20 ms, I usually expect my fellow optimized language peers to be doing it faster. Pretty surprised to see so many varying solutions that ended up being a little slower just because people didnt realize the potential of speed from failing to find a path.
The first part has a guaranteed path! if you think about a binary search, when there is a path then the block is higher up the list, so we ignore the lower blocks in the list. move to the next “midpoint” to test and just fill and remove blocks as we go to each mid point. So I took the first part as the lower point and moved to a mid point above that.
at least that is how I saw it, when I first looked, but binary search is a little harder to think of than just a simple for loop from the end of the list back. Yet I still got it done! Even included a dead end filler that takes 7 ms to show the final path for Part 2, it was not needed but was a neat inclusion!
Haskell
Not really happy with performance, binary search would speed this up a bunch, takes about 1.3 seconds.
Update: Binary search got it to 960 ms.
Code
import Data.Maybe
import qualified Data.Set as S
type Coord = (Int, Int)
parse :: String -> [Coord]
parse = map (read . ('(' :) . (++ ")")) . takeWhile (not . null) . lines
shortest :: Coord -> [Coord] -> Maybe Int
shortest (x0, y0) corrupted' = go $ S.singleton (x0 - 1, y0 - 1)
where
corrupted = S.fromList corrupted'
inside (x, y)
| x < 0 = False
| y < 0 = False
| x0 <= x = False
| y0 <= y = False
| otherwise = True
grow cs = S.filter inside $ S.unions $ cs :
[ S.mapMonotonic (\(x, y) -> (x + dx, y + dy)) cs
| (dx, dy) <- [(-1, 0), (0, -1), (0, 1), (1, 0)]
]
go visited
| (0, 0) `S.member` visited = Just 0
| otherwise = case grow visited S.\\ corrupted of
visited'
| S.size visited == S.size visited' -> Nothing
| otherwise -> succ <$> go visited'
main :: IO ()
main = do
rs <- parse <$> getContents
let size = (71, 71)
print $ fromJust $ shortest size $ take 1024 rs
putStrLn $ init $ tail $ show $ last $ zipWith const (reverse rs) $
takeWhile (isNothing . shortest size) $ iterate init rs
Faster (binary search)
import Data.Maybe
import qualified Data.Set as S
type Coord = (Int, Int)
parse :: String -> [Coord]
parse = map (read . ('(' :) . (++ ")")) . takeWhile (not . null) . lines
shortest :: Coord -> [Coord] -> Maybe Int
shortest (x0, y0) corrupted' = go $ S.singleton (x0 - 1, y0 - 1)
where
corrupted = S.fromList corrupted'
inside (x, y)
| x < 0 = False
| y < 0 = False
| x0 <= x = False
| y0 <= y = False
| otherwise = True
grow cs = S.filter inside $ S.unions $ cs :
[ S.mapMonotonic (\(x, y) -> (x + dx, y + dy)) cs
| (dx, dy) <- [(-1, 0), (0, -1), (0, 1), (1, 0)]
]
go visited
| (0, 0) `S.member` visited = Just 0
| otherwise = case grow visited S.\\ corrupted of
visited'
| S.size visited == S.size visited' -> Nothing
| otherwise -> succ <$> go visited'
solve2 :: Coord -> [Coord] -> Coord
solve2 r0 corrupted = go 0 $ length corrupted
where
go a z
| succ a == z = corrupted !! a
| otherwise =
let x = (a + z) `div` 2
in case shortest r0 $ take x corrupted of
Nothing -> go a x
Just _ -> go x z
main :: IO ()
main = do
rs <- parse <$> getContents
let size = (71, 71)
print $ fromJust $ shortest size $ take 1024 rs
putStrLn $ init $ tail $ show $ solve2 size rs
