NickyMeulemanNime
Metadata
  • Date

  • Last update

  • By

    • Nicky Meuleman
  • Tagged

  • Part of series

  • Older post

    Advent of Code 2023 Day 15

  • Newer post

    Advent of Code 2023 Day 17

Table of contents
  1. Day 16: The Floor Will Be Lava
  2. Parsing
  3. Part 1
    1. Helpers
    2. Code
  4. Part 2
    1. Code
  5. Final code

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}

Series navigation for: Advent of Code 2023

1. Advent of Code 2023 Day 1

Designed and developed by Nicky Meuleman

Built with Gatsby. Hosted on Netlify.