Day 16: Reindeer Maze
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
Rust
Not sure if I should dump my full solution, its quite long. If its too long I’ll delete it. Way over-engineered, and performs like it as well, quite slow.
Quite proud of my hack for pt2. I walk back along the path, which is nothing special. But because of the turn costs, whenever a turn joins a straight, it makes the straight discontinuous:
###### 11043 ######
10041 10042 ######
###### 11041 ######
So I check the before and after cells, and make sure the previous is already marked as a short path, and check the after cell, to make sure its 2 steps apart, and ignore the middle. Dunno if anyone else has done the same thing, I’ve mostly managed to avoid spoilers today.
code
#[cfg(test)]
mod tests {
use crate::day_16::tests::State::{CELL, END, SHORTPATH, START, WALL};
use std::cmp::PartialEq;
fn get_cell(board: &[Vec<MazeCell>], row: isize, col: isize) -> &MazeCell {
&board[row as usize][col as usize]
}
fn set_cell(board: &mut [Vec<MazeCell>], value: &MazeStep) {
let cell = &mut board[value.i as usize][value.j as usize];
cell.dir = value.dir;
cell.cost = value.cost;
cell.state = value.state.clone();
}
fn find_cell(board: &mut [Vec<MazeCell>], state: State) -> (isize, isize) {
for i in 0..board.len() {
for j in 0..board[i].len() {
if get_cell(board, i as isize, j as isize).state == state {
return (i as isize, j as isize);
}
}
}
unreachable!();
}
static DIRECTIONS: [(isize, isize); 4] = [(0, 1), (1, 0), (0, -1), (-1, 0)];
#[derive(PartialEq, Debug, Clone)]
enum State {
CELL,
WALL,
START,
END,
SHORTPATH,
}
struct MazeCell {
dir: i8,
cost: isize,
state: State,
}
struct MazeStep {
i: isize,
j: isize,
dir: i8,
cost: isize,
state: State,
}
fn walk_maze(board: &mut [Vec<MazeCell>]) -> isize {
let start = find_cell(board, START);
let mut moves = vec![MazeStep {
i: start.0,
j: start.1,
cost: 0,
dir: 0,
state: START,
}];
let mut best = isize::MAX;
loop {
if moves.is_empty() {
break;
}
let cell = moves.pop().unwrap();
let current_cost = get_cell(board, cell.i, cell.j);
if current_cost.state == END {
if cell.cost < best {
best = cell.cost;
}
continue;
}
if current_cost.state == WALL {
continue;
}
if current_cost.cost < cell.cost {
continue;
}
set_cell(board, &cell);
for (i, dir) in DIRECTIONS.iter().enumerate() {
let cost = match (i as i8) - cell.dir {
0 => cell.cost + 1,
-2 | 2 => continue,
_ => cell.cost + 1001,
};
moves.push(MazeStep {
i: cell.i + dir.0,
j: cell.j + dir.1,
dir: i as i8,
cost,
state: State::CELL,
});
}
}
best
}
fn unwalk_path(board: &mut [Vec<MazeCell>], total_cost: isize) -> usize {
let end = find_cell(board, END);
let mut cells = vec![MazeStep {
i: end.0,
j: end.1,
dir: 0,
cost: total_cost,
state: State::END,
}];
set_cell(board, &cells[0]);
while let Some(mut cell) = cells.pop() {
for dir in DIRECTIONS {
let next_cell = get_cell(board, cell.i + dir.0, cell.j + dir.1);
if next_cell.cost == 0 {
continue;
}
if next_cell.state == WALL {
continue;
}
if next_cell.state == CELL
&& (next_cell.cost == &cell.cost - 1001 || next_cell.cost == &cell.cost - 1)
{
cells.push(MazeStep {
i: cell.i + dir.0,
j: cell.j + dir.1,
dir: 0,
cost: next_cell.cost,
state: CELL,
});
} else {
let prev_cell = get_cell(board, cell.i - dir.0, cell.j - dir.1);
if prev_cell.state == SHORTPATH && prev_cell.cost - 2 == next_cell.cost {
cells.push(MazeStep {
i: cell.i + dir.0,
j: cell.j + dir.1,
dir: 0,
cost: next_cell.cost,
state: CELL,
});
}
}
}
cell.state = SHORTPATH;
set_cell(board, &cell);
}
let mut count = 0;
for row in board {
for cell in row {
if cell.state == SHORTPATH {
count += 1;
}
if cell.state == END {
count += 1;
}
if cell.state == START {
count += 1;
}
}
}
count
}
#[test]
fn day15_part2_test() {
let input = std::fs::read_to_string("src/input/day_16.txt").unwrap();
let mut board = input
.split('\n')
.map(|line| {
line.chars()
.map(|c| match c {
'#' => MazeCell {
dir: 0,
cost: isize::MAX,
state: WALL,
},
'S' => MazeCell {
dir: 0,
cost: isize::MAX,
state: START,
},
'E' => MazeCell {
dir: 0,
cost: isize::MAX,
state: END,
},
'.' => MazeCell {
dir: 0,
cost: isize::MAX,
state: CELL,
},
_ => unreachable!(),
})
.collect::<Vec<MazeCell>>()
})
.collect::<Vec<Vec<MazeCell>>>();
let cost = walk_maze(&mut board);
let count = unwalk_path(&mut board, cost);
println!("{count}");
}
}
1 point
*
Javascript
So my friend tells me my solution is close to Dijkstra but honestly I just tried what made sense until it worked. I originally wanted to just bruteforce it and get every single possible path explored but uh… Yeah that wasn’t gonna work, I terminated that one after 1B operations.
I created a class to store the state of the current path being explored, and basically just clone it, sending it in each direction (forward, 90 degrees, -90 degrees), then queue it up if it didn’t fail. Using a priority queue (array based) to store them, I inverted it for the second answer to reduce the memory footprint (though ultimately once I fixed the issue with the algorithm, which turned out to just be a less than or equal to that should have been a less than, I didn’t really need this).
Part two “only” took 45 seconds to run on my Thinkpad P14 Gen1.
My code was too powerful for Lemmy (or verbose): https://blocks.programming.dev/Zikeji/ae06ca1ca88649c99581eefce97a708e
5 points
C
Yay more grids! Seemed like prime Dijkstra or A* material but I went with an iterative approach instead!
I keep an array cost[y][x][dir], which is seeded at 1 for the starting location and direction. Then I keep going over the array, seeing if any valid move (step or turn) would yield to a lower best-known-cost for this state. It ends when a pass does not yield changes.
This leaves us with the best-known-costs for every reachable state in the array, including the end cell (bit we have to take the min() of the four directions).
Part 2 was interesting: I just happend to have written a dead end pruning function for part 1 and part 2 is, really, dead-end pruning for the cost map: remove any suboptimal step, keep doing so, and you end up with only the optimal steps. ‘Suboptimal’ here is a move that yields a higher total cost than the best-known-cost for that state.
It’s fast enough too on my 2015 i5:
day16 0:00.05 1656 Kb 0+242 faults
Code
#include "common.h"
#define GZ 145
enum {NN, EE, SS, WW};
static const int dx[]={0,1,0,-1}, dy[]={-1,0,1,0};
static char g[GZ][GZ]; /* with 1 tile border */
static int cost[GZ][GZ][4]; /* per direction, starts at 1, 0=no info */
static int traversible(char c) { return c=='.' || c=='S' || c=='E'; }
static int
minat(int x, int y)
{
int acc=0, d;
for (d=0; d<4; d++)
if (cost[y][x][d] && (!acc || cost[y][x][d] < acc))
acc = cost[y][x][d];
return acc;
}
static int
count_exits(int x, int y)
{
int acc=0, i;
assert(x>0); assert(x<GZ-1);
assert(y>0); assert(y<GZ-1);
for (i=0; i<4; i++)
acc += traversible(g[y+dy[i]][x+dx[i]]);
return acc;
}
/* remove all dead ends */
static void
prune_dead(void)
{
int dirty=1, x,y;
while (dirty) {
dirty = 0;
for (y=1; y<GZ-1; y++)
for (x=1; x<GZ-1; x++)
if (g[y][x]=='.' && count_exits(x,y) < 2)
{ dirty = 1; g[y][x] = '#'; }
}
}
/* remove all dead ends from cost[], leaves only optimal paths */
static void
prune_subopt(void)
{
int dirty=1, x,y,d;
while (dirty) {
dirty = 0;
for (y=1; y<GZ-1; y++)
for (x=1; x<GZ-1; x++)
for (d=0; d<4; d++) {
if (!cost[y][x][d])
continue;
if (g[y][x]=='E') {
if (cost[y][x][d] != minat(x,y))
{ dirty = 1; cost[y][x][d] = 0; }
continue;
}
if (cost[y][x][d]+1 > cost[y+dy[d]][x+dx[d]][d] &&
cost[y][x][d]+1000 > cost[y][x][(d+1)%4] &&
cost[y][x][d]+1000 > cost[y][x][(d+3)%4])
{ dirty = 1; cost[y][x][d] = 0; }
}
}
}
static void
propagate_costs(void)
{
int dirty=1, cost1, x,y,d;
while (dirty) {
dirty = 0;
for (y=1; y<GZ-1; y++)
for (x=1; x<GZ-1; x++)
for (d=0; d<4; d++) {
if (!traversible(g[y][x]))
continue;
/* from back */
if ((cost1 = cost[y-dy[d]][x-dx[d]][d]) &&
(cost1+1 < cost[y][x][d] || !cost[y][x][d]))
{ dirty = 1; cost[y][x][d] = cost1+1; }
/* from right */
if ((cost1 = cost[y][x][(d+1)%4]) &&
(cost1+1000 < cost[y][x][d] || !cost[y][x][d]))
{ dirty = 1; cost[y][x][d] = cost1+1000; }
/* from left */
if ((cost1 = cost[y][x][(d+3)%4]) &&
(cost1+1000 < cost[y][x][d] || !cost[y][x][d]))
{ dirty = 1; cost[y][x][d] = cost1+1000; }
}
}
}
int
main(int argc, char **argv)
{
int p1=0,p2=0, sx=0,sy=0, ex=0,ey=0, x,y;
char *p;
if (argc > 1)
DISCARD(freopen(argv[1], "r", stdin));
for (y=1; fgets(g[y]+1, GZ-1, stdin); y++) {
if ((p = strchr(g[y]+1, 'S'))) { sy=y; sx=p-g[y]; }
if ((p = strchr(g[y]+1, 'E'))) { ey=y; ex=p-g[y]; }
assert(y+1 < GZ-1);
}
cost[sy][sx][EE] = 1;
prune_dead();
propagate_costs();
prune_subopt();
p1 = minat(ex, ey) -1; /* costs[] values start at 1! */
for (y=1; y<GZ-1; y++)
for (x=1; x<GZ-1; x++)
p2 += minat(x,y) > 0;
printf("16: %d %d\n", p1, p2);
return 0;
}
3 points
3 points
*
C#
Ended up modifying part 1 to do part 2 and return both answers at once.
using System.Collections.Immutable;
using System.Diagnostics;
using Common;
namespace Day16;
static class Program
{
static void Main()
{
var start = Stopwatch.GetTimestamp();
var smallInput = Input.Parse("smallsample.txt");
var sampleInput = Input.Parse("sample.txt");
var programInput = Input.Parse("input.txt");
Console.WriteLine($"Part 1 small: {Solve(smallInput)}");
Console.WriteLine($"Part 1 sample: {Solve(sampleInput)}");
Console.WriteLine($"Part 1 input: {Solve(programInput)}");
Console.WriteLine($"That took about {Stopwatch.GetElapsedTime(start)}");
}
static (int part1, int part2) Solve(Input i)
{
State? endState = null;
Dictionary<(Point, int), int> lowestScores = new();
var queue = new Queue<State>();
queue.Enqueue(new State(i.Start, 1, 0, ImmutableHashSet<Point>.Empty));
while (queue.TryDequeue(out var state))
{
if (ElementAt(i.Map, state.Location) is '#')
{
continue;
}
if (lowestScores.TryGetValue((state.Location, state.DirectionIndex), out var lowestScoreSoFar))
{
if (state.Score > lowestScoreSoFar) continue;
}
lowestScores[(state.Location, state.DirectionIndex)] = state.Score;
var nextStatePoints = state.Points.Add(state.Location);
if (state.Location == i.End)
{
if ((endState is null) || (state.Score < endState.Score))
endState = state with { Points = nextStatePoints };
else if (state.Score == endState.Score)
endState = state with { Points = nextStatePoints.Union(endState.Points) };
continue;
}
// Walk forward
queue.Enqueue(state with
{
Location = state.Location.Move(CardinalDirections[state.DirectionIndex]),
Score = state.Score + 1,
Points = nextStatePoints,
});
// Turn clockwise
queue.Enqueue(state with
{
DirectionIndex = (state.DirectionIndex + 1) % CardinalDirections.Length,
Score = state.Score + 1000,
Points = nextStatePoints,
});
// Turn counter clockwise
queue.Enqueue(state with
{
DirectionIndex = (state.DirectionIndex + CardinalDirections.Length - 1) % CardinalDirections.Length,
Score = state.Score + 1000,
Points = nextStatePoints,
});
}
if (endState is null) throw new Exception("No end state found!");
return (endState.Score, endState.Points.Count);
}
public static void DumpMap(Input i, ISet<Point>? points, Point current)
{
for (int row = 0; row < i.Bounds.Row; row++)
{
for (int col = 0; col < i.Bounds.Col; col++)
{
var p = new Point(row, col);
Console.Write(
(p == current) ? 'X' :
(points?.Contains(p) ?? false) ? 'O' :
ElementAt(i.Map, p));
}
Console.WriteLine();
}
Console.WriteLine();
}
public static char ElementAt(string[] map, Point location) => map[location.Row][location.Col];
public record State(Point Location, int DirectionIndex, int Score, ImmutableHashSet<Point> Points);
public static readonly Direction[] CardinalDirections =
[Direction.Up, Direction.Right, Direction.Down, Direction.Left];
}
public class Input
{
public string[] Map { get; init; } = [];
public Point Start { get; init; } = new(-1, -1);
public Point End { get; init; } = new(-1, -1);
public Point Bounds => new(this.Map.Length, this.Map[0].Length);
public static Input Parse(string file)
{
var map = File.ReadAllLines(file);
Point start = new(-1, -1), end = new(-1, -1);
foreach (var p in map
.SelectMany((line, i) => new []
{
new Point(i, line.IndexOf('S')),
new Point(i, line.IndexOf('E')),
})
.Where(p => p.Col >= 0)
.Take(2))
{
if (map[p.Row][p.Col] is 'S') start = p;
else end = p;
}
return new Input()
{
Map = map,
Start = start,
End = end,
};
}
}
3 points
Haskell
code
import Control.Arrow
import Control.Monad
import Control.Monad.RWS
import Control.Monad.Trans.Maybe
import Data.Array.Unboxed
import Data.List
import Data.Map qualified as M
import Data.Maybe
import Data.Set qualified as S
data Dir = N | S | W | E deriving (Show, Eq, Ord)
type Maze = UArray Pos Char
type Pos = (Int, Int)
type Node = (Pos, Dir)
type CostNode = (Int, Node)
type Problem = RWS Maze [(Node, [Node])] (M.Map Node Int, S.Set (CostNode, Maybe Node))
parse = toMaze . lines
toMaze :: [String] -> Maze
toMaze b = listArray ((0, 0), (n - 1, m - 1)) $ concat b
where
n = length b
m = length $ head b
next :: Int -> (Pos, Dir) -> Problem [CostNode]
next c (p, d) = do
m <- ask
let straigth = fmap ((1,) . (,d)) . filter ((/= '#') . (m !)) . return $ move d p
turn = (1000,) . (p,) <$> rot d
return $ first (+ c) <$> straigth ++ turn
move N = first (subtract 1)
move S = first (+ 1)
move W = second (subtract 1)
move E = second (+ 1)
rot d
| d `elem` [N, S] = [E, W]
| otherwise = [N, S]
dijkstra :: MaybeT Problem ()
dijkstra = do
m <- ask
visited <- gets fst
Just (((cost, vertex@(p, _)), father), queue) <- gets (S.minView . snd)
let (prevCost, visited') = M.insertLookupWithKey (\_ a _ -> a) vertex cost visited
case prevCost of
Nothing -> do
queue' <- lift $ foldr S.insert queue <$> (fmap (,Just vertex) <$> next cost vertex)
put (visited', queue')
tell [(vertex, maybeToList father)]
Just c -> do
if c == cost
then tell [(vertex, maybeToList father)]
else guard $ m ! p /= 'E'
put (visited, queue)
dijkstra
solve b = do
start <- getStart b
end <- getEnd b
let ((m, _), w) = execRWS (runMaybeT dijkstra) b (M.empty, S.singleton (start, Nothing))
parents = M.fromListWith (++) w
endDirs = (end,) <$> [N, S, E, W]
min = minimum $ mapMaybe (`M.lookup` m) endDirs
ends = filter ((== Just min) . (`M.lookup` m)) endDirs
part2 =
S.size . S.fromList . fmap fst . concat . takeWhile (not . null) $
iterate (>>= flip (M.findWithDefault []) parents) ends
return (min, part2)
getStart :: Maze -> Maybe CostNode
getStart = fmap ((0,) . (,E) . fst) . find ((== 'S') . snd) . assocs
getEnd :: Maze -> Maybe Pos
getEnd = fmap fst . find ((== 'E') . snd) . assocs
main = getContents >>= print . solve . parse
