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; }
}
}
3 points
*
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
3 points
Haskell
solution
import Control.Arrow
import Control.Monad
import Control.Monad.RWS
import Control.Monad.Trans.Maybe
import Data.Array (inRange)
import Data.Char
import Data.Set qualified as S
import Text.ParserCombinators.ReadP hiding (get)
parse = fst . last . readP_to_S (endBy ((,) <$> num <*> (char ',' *> num)) $ char '\n')
where
num = read <$> munch1 isDigit
bounds = ((0, 0), (70, 70))
bfs :: MaybeT (RWS (S.Set (Int, Int)) () (S.Set (Int, Int), [(Int, (Int, Int))])) Int
bfs = do
(seen, (c, x) : xs) <- get
modify . second $ const xs
isCorrupt <- asks (S.member x)
when (not (x `S.member` seen) && not isCorrupt && inRange bounds x) $
modify (S.insert x *** (++ ((succ c,) <$> neighbors x)))
if x == snd bounds
then return c
else bfs
neighbors (x, y) = [(succ x, y), (pred x, y), (x, succ y), (x, pred y)]
findPath = fst . flip (evalRWS (runMaybeT bfs)) (mempty, [(0, (0, 0))]) . S.fromList
part1 = findPath . take 1024
search corrupt = go 0 (length corrupt)
where
go l r = case (findPath $ take (pred m) corrupt, findPath $ take m corrupt) of
(Just _, Just _) -> go m r
(Just _, Nothing) -> Just $ pred m
(Nothing, Nothing) -> go l m
where
m = (l + r) `div` 2
part2 = liftM2 fmap (!!) search
main = getContents >>= print . (part1 &&& part2) . parse
2 points
2 points
*
Uiua
I didn’t think I could do this in Uiua this morning, but I gave it some thought while walking the dog and managed to wrangle the data into shape tonight. I factored out the binary chop as that seems like another useful tool to have up my sleeve.
EDIT: goddammit, Kai literally snuck a new RC release out just after I posted this, with a breaking change to how path works. Updated version below.
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
