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

  • CameronDevOPM
    1·
    1 day ago

    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}");
    }
}