Advent of Code 2023 Day 16

Day 16: The Floor Will Be Lava

https://adventofcode.com/2023/day/16

The light is focussed somewhere.

It goes into a big cavern with a bunch of mirrors and splitters in it.

Today’s input is a map of the cavern.

An example input looks like this:

input.txt

.|...\....
|.-.\.....
.....|-...
........|.
..........
.........\
..../.\\..
.-.-/..|..
.|....-|.\
..//.|....

. empty space
’\’ left mirror
’/’ right mirror
’-’ horizontal splitter
’|’ vertical splitter

If a beam hits an empty space, it keeps going like nothing happened (Because it didn’t you see? Nothing. It happened.)

If a beam hits a mirror, it is reflected 90 degrees according to the angle of the mirror it hit.

If a beam hits a splitter on the pointy end, it passes through like nothing happened.

If a beam hits a splitter on the flat end, it gets split and exits through the 2 pointy ends.

Beams do not interact, they pass right through eachother.

Parsing

I represent the cave as a 2D list of Tile:

enum Tile {
    Empty,
    SplitHoriz,
    SplitVert,
    MirrorForward,
    MirrorBack,
}

fn parse(s: &str) -> Vec<Vec<Tile>> {
    s.lines()
        .map(|line| {
            line.chars()
                .map(|c| match c {
                    '\\' => Tile::MirrorBack,
                    '/' => Tile::MirrorForward,
                    '.' => Tile::Empty,
                    '-' => Tile::SplitHoriz,
                    '|' => Tile::SplitVert,
                    _ => panic!("at the disco"),
                })
                .collect()
        })
        .collect()
}

Part 1

The beam enters the cave from the top left, going right.

The question asks how many tiles are energized (1 or more beams pass through it).

Helpers

A Beam struct represents a beam of light:

struct Beam {
    pos: Coord,
    dir: Direction,
}

The position of a beam is stored as a Coord:

struct Coord {
    x: usize,
    y: usize,
}

And the direction a beam is currently travelling in as Direction:

enum Direction {
    Up,
    Down,
    Left,
    Right,
}

Some skeleton-code I want to work towards:

pub fn part_1(input: &str) -> usize {
    let grid = parse(input);
    let start = Beam {
        pos: Coord { x: 0, y: 0 },
        dir: Direction::Right,
    };
    energized(start, &grid)
}

The main logic is in the energized helper.

It keeps track of a set of energized coordinates. At the end, it returns how large that set is.

It starts by pushing a starting Beam onto a queue.

Then it pops a beam off that queue until it’s empty. For each beam, it determines the next positions and directions, and adds those to the queue.

To prevent infinite loops (the beams might get trapped in the cave, going around forever), I keep track of every instance of Beam I saw so far. If I pop a beam off the stack I have already seen, I know I’m in a loop and can ignore that beam.

For every beam I pop off the queue, I determine the next direction(s) it will travel in: Either 1 direction if it reflects or keeps going, or 2 directions if the beam gets split.

For each direction, I try to move the beam in that direction. If it didn’t go off the sides of the map, I add a beam with that new direction and updated position to the queue.

fn energized(start: Beam, grid: &[Vec<Tile>]) -> usize {
    let rows = grid.len();
    let cols = grid[0].len();

    let mut q = VecDeque::new();
    let mut energized = HashSet::new();
    let mut seen = HashSet::new();
    q.push_back(start);

    while let Some(mut beam) = q.pop_front() {
        if seen.contains(&beam) {
            continue;
        }
        energized.insert(beam.pos);
        seen.insert(beam);

        let dirs = match (grid[beam.pos.y][beam.pos.x], beam.dir) {
            (Tile::Empty, _)
            | (Tile::SplitHoriz, Direction::Left)
            | (Tile::SplitHoriz, Direction::Right)
            | (Tile::SplitVert, Direction::Up)
            | (Tile::SplitVert, Direction::Down) => vec![beam.dir],
            (Tile::SplitHoriz, _) => {
                vec![Direction::Left, Direction::Right]
            }
            (Tile::SplitVert, _) => {
                vec![Direction::Up, Direction::Down]
            }
            (Tile::MirrorForward, Direction::Up) | (Tile::MirrorBack, Direction::Down) => {
                vec![Direction::Right]
            }
            (Tile::MirrorForward, Direction::Down) | (Tile::MirrorBack, Direction::Up) => {
                vec![Direction::Left]
            }
            (Tile::MirrorForward, Direction::Left) | (Tile::MirrorBack, Direction::Right) => {
                vec![Direction::Down]
            }
            (Tile::MirrorForward, Direction::Right) | (Tile::MirrorBack, Direction::Left) => {
                vec![Direction::Up]
            }
        };
        for dir in dirs {
            beam.dir = dir;
            if let Some(beam) = beam.forward(rows, cols) {
                q.push_back(beam);
            }
        }
    }
    energized.len()
}

The forward helper that only returns a beam if it didn’t go off the edges of the map:

impl Beam {
    fn forward(mut self, rows: usize, cols: usize) -> Option<Self> {
        match self.dir {
            Direction::Up if self.pos.y > 0 => self.pos.y -= 1,
            Direction::Down if self.pos.y < rows - 1 => self.pos.y += 1,
            Direction::Left if self.pos.x > 0 => self.pos.x -= 1,
            Direction::Right if self.pos.x < cols - 1 => self.pos.x += 1,
            _ => return None,
        }
        Some(self)
    }
}

Code

day_16.rs

pub fn part_1(input: &str) -> usize {
    let grid = parse(input);
    let start = Beam {
        pos: Coord { x: 0, y: 0 },
        dir: Direction::Right,
    };
    energized(start, &grid)
}

Part 2

The beam can enter the cave from any position along the edges (heading directly away from that edge).

The question asks for the maximum amount of tiles that can be energized.

I brute forced this. I looped through every possible starting configuration, calculated the amount of energized tiles, and took the maximum.

Code

day_16.rs

let grid = parse(input);
    let from_left = (0..grid.len()).map(|row| Beam {
        dir: Direction::Right,
        pos: Coord { x: 0, y: row },
    });
    let from_right = (0..grid.len()).map(|row| Beam {
        dir: Direction::Left,
        pos: Coord {
            x: grid[0].len() - 1,
            y: row,
        },
    });
    let from_up = (0..grid[0].len()).map(|col| Beam {
        dir: Direction::Down,
        pos: Coord { x: col, y: 0 },
    });
    let from_down = (0..grid[0].len()).map(|col| Beam {
        dir: Direction::Up,
        pos: Coord {
            x: col,
            y: grid.len() - 1,
        },
    });

    from_left
        .chain(from_right)
        .chain(from_up)
        .chain(from_down)
        .map(|start| energized(start, &grid))
        .max()
        .unwrap()

Final code

day_16.rs

1use std::collections::{HashSet, VecDeque};
2
3#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Hash)]
4enum Direction {
5    Up,
6    Down,
7    Left,
8    Right,
9}
10
11#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Hash)]
12struct Coord {
13    x: usize,
14    y: usize,
15}
16
17#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Hash)]
18struct Beam {
19    pos: Coord,
20    dir: Direction,
21}
22
23impl Beam {
24    fn forward(mut self, rows: usize, cols: usize) -> Option<Self> {
25        match self.dir {
26            Direction::Up if self.pos.y > 0 => self.pos.y -= 1,
27            Direction::Down if self.pos.y < rows - 1 => self.pos.y += 1,
28            Direction::Left if self.pos.x > 0 => self.pos.x -= 1,
29            Direction::Right if self.pos.x < cols - 1 => self.pos.x += 1,
30            _ => return None,
31        }
32        Some(self)
33    }
34}
35
36#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Hash)]
37enum Tile {
38    Empty,
39    SplitHoriz,
40    SplitVert,
41    MirrorForward,
42    MirrorBack,
43}
44
45fn parse(s: &str) -> Vec<Vec<Tile>> {
46    s.lines()
47        .map(|line| {
48            line.chars()
49                .map(|c| match c {
50                    '\\' => Tile::MirrorBack,
51                    '/' => Tile::MirrorForward,
52                    '.' => Tile::Empty,
53                    '-' => Tile::SplitHoriz,
54                    '|' => Tile::SplitVert,
55                    _ => panic!("at the disco"),
56                })
57                .collect()
58        })
59        .collect()
60}
61
62fn energized(start: Beam, grid: &[Vec<Tile>]) -> usize {
63    let rows = grid.len();
64    let cols = grid[0].len();
65
66    let mut q = VecDeque::new();
67    let mut energized = HashSet::new();
68    let mut seen = HashSet::new();
69    q.push_back(start);
70
71    while let Some(mut beam) = q.pop_front() {
72        if seen.contains(&beam) {
73            continue;
74        }
75        energized.insert(beam.pos);
76        seen.insert(beam);
77
78        let dirs = match (grid[beam.pos.y][beam.pos.x], beam.dir) {
79            (Tile::Empty, _)
80            | (Tile::SplitHoriz, Direction::Left)
81            | (Tile::SplitHoriz, Direction::Right)
82            | (Tile::SplitVert, Direction::Up)
83            | (Tile::SplitVert, Direction::Down) => vec![beam.dir],
84            (Tile::SplitHoriz, _) => {
85                vec![Direction::Left, Direction::Right]
86            }
87            (Tile::SplitVert, _) => {
88                vec![Direction::Up, Direction::Down]
89            }
90            (Tile::MirrorForward, Direction::Up) | (Tile::MirrorBack, Direction::Down) => {
91                vec![Direction::Right]
92            }
93            (Tile::MirrorForward, Direction::Down) | (Tile::MirrorBack, Direction::Up) => {
94                vec![Direction::Left]
95            }
96            (Tile::MirrorForward, Direction::Left) | (Tile::MirrorBack, Direction::Right) => {
97                vec![Direction::Down]
98            }
99            (Tile::MirrorForward, Direction::Right) | (Tile::MirrorBack, Direction::Left) => {
100                vec![Direction::Up]
101            }
102        };
103        for dir in dirs {
104            beam.dir = dir;
105            if let Some(beam) = beam.forward(rows, cols) {
106                q.push_back(beam);
107            }
108        }
109    }
110    energized.len()
111}
112
113pub fn part_1(input: &str) -> usize {
114    let grid = parse(input);
115    let start = Beam {
116        pos: Coord { x: 0, y: 0 },
117        dir: Direction::Right,
118    };
119    energized(start, &grid)
120}
121
122pub fn part_2(input: &str) -> usize {
123    let grid = parse(input);
124    let from_left = (0..grid.len()).map(|row| Beam {
125        dir: Direction::Right,
126        pos: Coord { x: 0, y: row },
127    });
128    let from_right = (0..grid.len()).map(|row| Beam {
129        dir: Direction::Left,
130        pos: Coord {
131            x: grid[0].len() - 1,
132            y: row,
133        },
134    });
135    let from_up = (0..grid[0].len()).map(|col| Beam {
136        dir: Direction::Down,
137        pos: Coord { x: col, y: 0 },
138    });
139    let from_down = (0..grid[0].len()).map(|col| Beam {
140        dir: Direction::Up,
141        pos: Coord {
142            x: col,
143            y: grid.len() - 1,
144        },
145    });
146
147    from_left
148        .chain(from_right)
149        .chain(from_up)
150        .chain(from_down)
151        .map(|start| energized(start, &grid))
152        .max()
153        .unwrap()
154}

Date

Last update

By

Tagged

Part of series

Older post

Newer post

Advent of Code 2023 Day 16

Day 16: The Floor Will Be Lava

Parsing

Part 1

Helpers

Code

Part 2

Code

Final code