DEV Community

Nicky Meuleman
Nicky Meuleman

Posted on • Originally published at nickymeuleman.netlify.app

Advent of Code 2023 Day 16

#adventofcode #rust

Day 16: The Floor Will Be Lava

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

TL;DR: my solution in Rust

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:

.|...\....
|.-.\.....
.....|-...
........|.
..........
.........\
..../.\\..
.-.-/..|..
.|....-|.\
..//.|....
Enter fullscreen mode Exit fullscreen mode
  • . 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()
}
Enter fullscreen mode Exit fullscreen mode

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,
}
Enter fullscreen mode Exit fullscreen mode

The position of a beam is stored as a Coord:

struct Coord {
    x: usize,
    y: usize,
}
Enter fullscreen mode Exit fullscreen mode

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

enum Direction {
    Up,
    Down,
    Left,
    Right,
}
Enter fullscreen mode Exit fullscreen mode

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)
}
Enter fullscreen mode Exit fullscreen mode

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()
}
Enter fullscreen mode Exit fullscreen mode

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)
    }
}
Enter fullscreen mode Exit fullscreen mode

Code 

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)
}
Enter fullscreen mode Exit fullscreen mode

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 

    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()
Enter fullscreen mode Exit fullscreen mode

Final code 

use std::collections::{HashSet, VecDeque};

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Hash)]
enum Direction {
    Up,
    Down,
    Left,
    Right,
}

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Hash)]
struct Coord {
    x: usize,
    y: usize,
}

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Hash)]
struct Beam {
    pos: Coord,
    dir: Direction,
}

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

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Hash)]
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()
}

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()
}

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

pub fn part_2(input: &str) -> usize {
    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()
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)

Read next

trish_07 profile image

Rust TUI Chat Application - Mastering Terminal User Interfaces

Trish -

crabnebuladev profile image

Interview with Prabhu Kiran Konda, Creator of Snail AI!

CrabNebula -

evgenyigumnov profile image

Need Advice on Improving My Codebase: Increased Readability and Error Management

Evgeny Igumnov -

crabnebuladev profile image

Interview with Klauss Andrei, Creator of FocusPocus.io!

CrabNebula -