this post was submitted on 16 Dec 2024
8 points (83.3% liked)

Advent Of Code

920 readers
57 users here now

An unofficial home for the advent of code community on programming.dev!

Advent of Code is an annual Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like.

AoC 2024

Solution Threads

M T W T F S S
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 18 20 21 22
23 24 25

Rules/Guidelines

Relevant Communities

Relevant Links

Credits

Icon base by Lorc under CC BY 3.0 with modifications to add a gradient

console.log('Hello World')

founded 1 year ago
MODERATORS
[email protected]
[email protected]
[email protected]
8
๐ŸฆŒ - 2024 DAY 16 SOLUTIONS -๐ŸฆŒ (programming.dev)
submitted 2 days ago by [email protected] to c/[email protected]
24 comments fedilink hide all child comments
 

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

you are viewing a single comment's thread
view the rest of the comments
[โ€“] [email protected] 1 points 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}");
    }
}