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
You are viewing a single thread.
View all comments 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}");
}
}
