Skip to content

Instantly share code, notes, and snippets.

@ephbaum

ephbaum/README.md

Last active December 16, 2023 18:11
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ephbaum/324301c029582c01ab6a1143baf979ba to your computer and use it in GitHub Desktop.
Save ephbaum/324301c029582c01ab6a1143baf979ba to your computer and use it in GitHub Desktop.
Download ZIP
Advent of Code - Day 16
Raw
README.md

Advent of Code Day 16: The Floor Will Be Lava

Puzzle Description

In this puzzle, we're tasked with simulating the behavior of a beam of light as it moves through a contraption in a cave. The contraption is a grid containing mirrors (/ and \), splitters (| and -), and empty space (.). The beam of light enters the grid from the top-left corner and moves according to these rules:

  • Continues in the same direction in empty space (.).
  • Reflects 90 degrees when hitting a mirror (/ or \).
  • Passes through the pointy end of a splitter (| or -) as if it were empty space.
  • Splits into two beams at the flat side of a splitter (| or -), with each new beam going in the directions the splitter's pointy ends point.

The objective is to calculate how many tiles become energized, i.e., tiles that the beam passes through, reflects in, or splits in.

Proposed Solution

Plan

  1. Grid Representation: Create a 2D array to represent the grid. Each cell in the array corresponds to a tile in the grid.

  2. Beam Initialization: Set the initial position and direction of the beam.

  3. Beam Simulation:

    • Iterate through the grid based on the beam's direction.
    • Change the beam's direction according to the type of tile encountered.
    • If the beam hits the flat side of a splitter, create two new beams each going in one of the directions indicated by the splitter's pointy ends.
    • Mark tiles as energized whenever they are passed through, reflected in, or a beam splits in them.

  4. Terminate Simulation: End the simulation when the beam exits the grid.

  5. Count Energized Tiles: Calculate the total number of tiles that have been energized.

Implementation

  • The implementation will involve creating functions for each step of the plan, particularly for handling different tile types and beam directions.
  • The simulation will track all beams, including any split beams, and update the grid accordingly.
  • Finally, a function will count and return the total number of energized tiles.

This plan outlines a methodical approach to solving the puzzle, focusing on accurately simulating the beam's behavior and tracking the state of each tile in the grid.

Example and Solution

Example

Given the following grid as the puzzle input:

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

The beam of light starts in the top-left corner, moving right. The grid contains mirrors (/ and \), splitters (| and -), and empty spaces (.).

Beam Path

Here's how the beam of light moves through the contraption:

  1. Enters from the top-left, moving right.
  2. Reflects upwards at the first mirror (/).
  3. Continues upward, then reflects right at the next mirror (\).
  4. Hits a splitter (-) and continues in the same direction.
  5. Encounters various elements, reflecting and splitting as per the rules.

The path of the beam is complex due to the reflections and splittings. Each tile that the beam passes through, reflects in, or splits in becomes energized.

Energized Tiles

After simulating the beam's path, we find the energized tiles marked as #:

######....
.#...#....
.#...#####
.#...##...
.#...##...
.#...##...
.#..####..
########..
.#######..
.#...#.#..

Solution

In this example, the number of tiles that become energized is 46. This is calculated by counting all the # symbols in the energized grid.

This example demonstrates the application of the rules and the simulation process, leading to the final count of energized tiles.

Had some trouble on this one

I wound up looking at and adapting some other solutions as none of my own worked quite right as I was going through this one.

I thought BFS might be the right path but a colleague suggested they'd used DFS and I found that I couldn't quite implement either of solution as I would like. I ended doing part one with recursion and then just brute forced the second part... but after looking at some other folks' solutions I think I can see a path forward but, at this point, I just decided to move on as I just don't have time to dwell on this one today

I may return to this to try to get my own solution working as I'd like

Raw
index.js
/**
* This script is not yet working, still needs adaptation
*/
const fs = require('fs');
function main() {
const args = process.argv;
if (args.length < 3) {
console.log(`Usage: node ${args[1]} <filename>`);
return;
}
const filename = args[2];
const document = fs.readFileSync(filename, 'utf8');
part1(document);
part2(document);
}
function parseGrid(document) {
const grid = {};
const lines = document.split('\n');
let bounds = [0, 0];
lines.forEach((line, x) => {
line.split('').forEach((c, y) => {
grid[`${x},${y}`] = c;
bounds = [x, y];
});
});
return { grid, bounds };
}
function resolveLocation(grid, location, vector, bounds) {
const nextX = location[0] + vector[0];
const nextY = location[1] + vector[1];
if (nextX < 0 || nextY < 0 || nextX > bounds[0] || nextY > bounds[1]) {
return null;
}
return [nextX, nextY];
}
function getNextVectors(grid, location, vector) {
const cell = grid[`${location[0]},${location[1]}`];
switch (cell) {
case '.':
return [vector];
case '\\':
return vector[0] === 0 ? [[vector[1], vector[0]]] : [[-vector[1], -vector[0]]];
case '/':
return vector[0] === 0 ? [[-vector[1], -vector[0]]] : [[vector[1], vector[0]]];
case '-':
return vector[0] === 0 ? [vector, [-vector[1], -vector[0]]] : [vector];
case '|':
return vector[1] === 0 ? [vector, [-vector[0], -vector[1]]] : [vector];
default:
return [];
}
}
function traverse(grid, entry, bounds) {
const visitedLocations = new Set();
const visitQueue = [entry];
const loopDetector = new Set();
while (visitQueue.length > 0) {
const [location, vector] = visitQueue.pop();
const locStr = `${location[0]},${location[1]},${vector[0]},${vector[1]}`;
if (loopDetector.has(locStr)) continue;
loopDetector.add(locStr);
visitedLocations.add(`${location[0]},${location[1]}`);
const nextVectors = getNextVectors(grid, location, vector);
nextVectors.forEach(nextVector => {
const nextLocation = resolveLocation(grid, location, nextVector, bounds);
if (nextLocation) {
visitQueue.push([nextLocation, nextVector]);
}
});
}
return visitedLocations.size;
}
function part1(document) {
const { grid, bounds } = parseGrid(document);
const count = traverse(grid, [[0, 0], [0, 1]], bounds);
console.log(`Part 1: ${count}`);
}
function part2(document) {
const { grid, bounds } = parseGrid(document);
let maxVisited = 0;
for (let y = 0; y <= bounds[1]; y++) {
maxVisited = Math.max(maxVisited, traverse(grid, [[0, y], [1, 0]], bounds));
maxVisited = Math.max(maxVisited, traverse(grid, [[bounds[0], y], [-1, 0]], bounds));
}
for (let x = 0; x <= bounds[0]; x++) {
maxVisited = Math.max(maxVisited, traverse(grid, [[x, 0], [0, 1]], bounds));
maxVisited = Math.max(maxVisited, traverse(grid, [[x, bounds[1]], [0, -1]], bounds));
}
console.log(`Part 2: ${maxVisited}`);
}
main();
Raw
layout.txt
\.................-....-.-.|....................|......./.|.\................|...........|....--..............
............-...................|.............|..-.......-/..............-....\...............................
|.......//...........................................|...............-......../.....\....................\....
....|......-.-.............-......\.....\......../..................../.......................................
..\..\../................../.............-............|....-.........................|......|...............|.
-..|........................./.................\.........\./.............\..|..-...-.............\............
.\......||-..................../................-................./....|........................|.............
..............\./...........-.........../-................-.........\...\........../-.......|.................
....-..........-.-.....\......................../.......-..........-/.....................||................|.
./..........|/............................\./............................./....../........\...-|............\-
........\.............................-...../............---...........|...............|......\\..............
........//....|.\......./...\.............|..............\............./...........-.|..-.............|.......
...................\...........-/..-......\...|........-.|................\-.......|........\.................
|.|....../|............\./..-........\..............................-.....................|....../............
............-....................-..............-..-................|.//.............-.............-..........
..........-.......-......|-................./........../...\........-.......................-..\.......\......
................../....|............-....../................./.....................|.................-........
...\..............--..|.....||.....\.............\../................................................-.-...../
.........-......|....-.................-.......\-................./..|...................|\.....\.....|.|-....
......................-......................-............/....................\...../...\..../...............
...../......-...............\...-....|......../.........\................................|.........../........
........../.......\..............-...............\........-|....-......-.............|...........|........./..
./...............\....../....../..../...................................................|.....|.|../......./..
....|\........\-...../...................-.............\.\..................................././..........\...
....................................-..../......................-..///......-...|.|..........................|
.........-\.....-...........|........./..........-..\.....\./...................-........................-....
....../.......././......--.....|.\..-...-....\..........................-....-...-..|.|.....|.......\-./......
...-....................-................|.............-../........|../........-.............|\...............
...../...........-......../................|................|.....\.....-.............../...|....../\.........
./...\.....\..-./.........................|................................-....................-.............
.............\|.../....\\.....\..|...........\.....................|......|.|.....|.....-............\.\......
........................|......-..........-.../......-........|...../.\|...-................................|.
.......\...-...\..........|.....\...................\.........|..........-/.........\...................../...
.-|.......|............./..|./....-.../...\............-......../..............-.......//...-...........||.\..
..|..\./..-........\..|....-..\.........../..............................|..\..................../..|...../-..
.|.........-.\...........................\..../......./....||............\..........|............-.\|.........
....................\..../|............................\.../..|........./...../............||........\....../.
....................../.....|...................|......|.................|..|.......|................|........
.....................\.........-..../.........../../..-......\.................|.../....................../...
........\.-................/........\...../....../.|.\...|/../..........................................-.....
....................................|......./...../............-................-/..|.-....................\..
..|.........................-....................../...|.....|.............../.........../.....|\.............
.......................................|.\.|.......................-.......|..............\............-./....
..........//................\..|./................-.................-..../../|................................
.|......................................./............/..-.......-.|.........................\|..|............
............................/.-..................-./..../..............|-.........-|..........................
.................-...|................\.........|\...............................\...........\...//...........
........\..|.|--.............|.......\.................|......|\./.........................\.|................
.-|.............|\|.....\|././...|..\.............\..\...................\...........\...../..................
..../..............-..|...|.........-.........\.....-...........-.....|...\.-....-../.................\.......
........\.|........\\.........-...............-.......-..................................../..........|.......
...............-...................\/...............\..-\...........|.-........-.\-.....\....\..../......-....
.../-......./..............|.......|..//......-....................../.|....\......|..\.........../-\.........
.-....|./....-.../....../.....-..............\..-..\..-............\................|...|..........-.......|..
|......../...................\..../....\......./..|.................\...............\.........\../.|......../.
../............/........|..|.......................................\../\...............\............/.......\.
........-.-...\........../.......-....-............./.............-......./................\..........-.......
.../-................/......|/........-......|..........|..-..............|/..........................-.......
......./............../...................|../...../................./../..........\../.....\....\............
..............-..|../-........................|...\.../...-/..........\.......\......\.................-....-.
......................................-/.\........................../......-..\..\........\...............|..\
.............-.........../-|........-........\....-.....\....../..\........................\......|.......\...
.././....................|\.../\.........\.|.............../..../...|......./.\...|.......\.........|.........
......................./........./-./...........................|/...\........-.../.................||........
..............|./........\..............\.............................|/................../............|.-..|.
.........................-......../........./.....|....-..-.-..............-.-......../.......\...\./.........
.-............../../....\//......../...|......|......\..................-......\.....-....\|.........|........
..............-.....................\.................\.|...-............................|......\.............
\\.....|...........\............|............................../............................................\.
.-........../|...\..............-...............................\...........\.....|......\..........\.........
.\............\.|....-........./....../../.....-..\........|...............-..................|............-.|
.....\......-.........-.........|....../..-....|.....\..../....|........-.....................................
..........\-..-..../\.....................\.........-...........|..../-.......................\....-..........
...../............./..|..................../............../../.........|...............-../...................
.....|...../.....|......-.............................|...........-......................./............/......
.....................||./.-.................-.........\.\..................-..............\...--.........\....
.|......-......-.\.......-......\....\..\..|.........../......./.....................-..........|.............
.....\.....\............................--..................|..-........\....\...\.|.\.-...........\...\......
./...........\.......\/......|........./..|................\-................/....\...................\.\.....
..|...............................-.........-.|/......|.....|........\........................................
.......|............-............../............-......../..-...\|-...-..../...........-..........-..-/.......
............................-..\.......................................-.........................\..........-.
........................\.........|................||...-....\......\.....\.................\...\\....../.....
....\../.....-.......-.................-|...................-../.|-............|........-|......./../...\.....
..................................................\.......|......./..\./......../....|....-|.-................
....../.........|.......|...|.......\.../|...............-.......-\..\......././..................|..\.|...../
............|.....\...........-.............................../.....-.................-.../............/.../..
...../.......\............................|.....\....\................/..................\......../...........
..................-....\.........\|................/|......../.-................|...\......................--.
......-..-.....................................-\.........|.../.....................|..|.-.....\...|....\....-
......-......-.................-......|..................................................|....................
..\...............|......../........-......./.............../...........-..........|/.....///\.....-..........
.........../..|.............../..........\|.........................\...|.....\||....\...|.|/.....-....../....
...../...../.....-............................................|........|............|.........................
......-../\................../..............\............\.................../|...........|.............\.....
...........-..........................-....\..\..|.-..............................................\........|..
/.--..//....\...............................-............|..././..............................................
/...............|.........../..../......................\.....|............|...........|...................-..
..-................\../|......../...................../...........\..|.|\../..................................
....|...../.....-......\.........................-.....//...............|.........-.......|...-....--.........
....|..\.-..../....................|..........\............./...........\.../.................................
............................\...................................../.......................|...........\.......
.........../.....-.....................\..\.-..|............-...............\.........................-.......
......-.......-\.\......\..-.-........./...........\..........|........................\.....-.....\..........
..............-....../.-............./........../..............\-....-.../...../.-............\......./.-.....
......|...................................................||..../...|\.....................-.../...\........|.
......|.//........................-...../...........-..\...|......|..................../........../...........
.....................................................|.........//...........|\.....\....................|.../.
............-..||...........|....../....................\...\................................../.......|......
..\....\......./-\.\...........-\................|.........../................||.../.....-...........\........
Raw
main.py
f = open("layout.txt","r")
lines = f.read().splitlines()
f.close()
map = {}
ycoord = 0
for y in lines:
arr = list(y)
xcoord = 0
for x in arr:
map[(xcoord,ycoord)] = x
xcoord += 1
ycoord += 1
energized = map.copy()
stack = [((0,0),(1,0))]
count = 0
while count != 100000:
count += 1
val = ()
try:
val = stack.pop()
except:
break
curr = val[0]
dir = val[1]
exit = True
for x in curr:
if x < 0 or x > 109:
exit = False
if exit:
energized[curr] = "#"
if map[curr] == '.':
curr = (curr[0] + dir[0], curr[1] + dir[1])
stack.append((curr,dir))
elif map[curr] == '|':
if dir[1] != 1:
dir1 = (0,-1)
curr1 = (curr[0] + dir1[0], curr[1] + dir1[1])
stack.append((curr1,dir1))
if dir[1] != -1:
dir2 = (0,1)
curr2 = (curr[0] + dir2[0], curr[1] + dir2[1])
stack.append((curr2,dir2))
map[curr] = '#'
elif map[curr] == '-':
if dir[0] != 1:
dir1 = (-1,0)
curr1 = (curr[0] + dir1[0], curr[1] + dir1[1])
stack.append((curr1,dir1))
if dir[0] != -1:
dir2 = (1,0)
curr2 = (curr[0] + dir2[0], curr[1] + dir2[1])
stack.append((curr2,dir2))
map[curr] = '#'
elif map[curr] == '/':
if dir == (1,0):
dir = (0,-1)
curr = (curr[0] + dir[0], curr[1] + dir[1])
stack.append((curr,dir))
elif dir == (-1,0):
dir = (0,1)
curr = (curr[0] + dir[0], curr[1] + dir[1])
stack.append((curr,dir))
elif dir == (0,1):
dir = (-1,0)
curr = (curr[0] + dir[0], curr[1] + dir[1])
stack.append((curr,dir))
else:
dir = (1,0)
curr = (curr[0] + dir[0], curr[1] + dir[1])
stack.append((curr,dir))
elif map[curr] == '\\':
if dir == (1,0):
dir = (0,1)
curr = (curr[0] + dir[0], curr[1] + dir[1])
stack.append((curr,dir))
elif dir == (-1,0):
dir = (0,-1)
curr = (curr[0] + dir[0], curr[1] + dir[1])
stack.append((curr,dir))
elif dir == (0,1):
dir = (1,0)
curr = (curr[0] + dir[0], curr[1] + dir[1])
stack.append((curr,dir))
else:
dir = (-1,0)
curr = (curr[0] + dir[0], curr[1] + dir[1])
stack.append((curr,dir))
vals = list(energized.values())
total = 0
for x in vals:
if x == '#':
total += 1
print(total)
Raw
main.rs
use std::collections::{HashMap, HashSet};
fn main() {
let args: Vec<String> = std::env::args().collect();
if args.len() < 2 {
println!("Missing file name. Call: {} <filename>", args[0]);
return;
}
let filename = &args[1];
let document =
std::fs::read_to_string(filename).expect("Something went wrong reading the file");
part1(document.to_string());
part2(document.to_string());
}
type Point = (usize, usize);
type Vector = (isize, isize);
struct Grid {
map: HashMap<Point, char>,
bounds: (usize, usize),
}
impl From<String> for Grid {
fn from(string: String) -> Self {
let mut map = HashMap::with_capacity(string.len());
let mut bounds = (0, 0);
for (x, line) in string.lines().enumerate() {
for (y, c) in line.chars().enumerate() {
map.insert((x, y), c);
bounds = (x, y);
}
}
Grid { map, bounds }
}
}
impl Grid {
fn resolve_location(&self, location: &Point, vector: &Vector) -> Option<Point> {
let next_x = location.0.checked_add_signed(vector.0)?;
let next_y = location.1.checked_add_signed(vector.1)?;
if next_x > self.bounds.0 || next_y > self.bounds.1 {
None
} else {
Some((next_x, next_y))
}
}
fn get_next_vectors(&self, location: &Point, vector: &Vector) -> Vec<Vector> {
match self.map.get(location) {
Some('.') => vec![*vector],
Some('\\') => match vector {
(0, 1) => vec![(1, 0)],
(0, -1) => vec![(-1, 0)],
(1, 0) => vec![(0, 1)],
(-1, 0) => vec![(0, -1)],
_ => unreachable!(),
},
Some('/') => match vector {
(0, 1) => vec![(-1, 0)],
(0, -1) => vec![(1, 0)],
(1, 0) => vec![(0, -1)],
(-1, 0) => vec![(0, 1)],
_ => unreachable!(),
},
Some('-') => match vector {
(0, 1) | (0, -1) => vec![*vector],
(1, 0) | (-1, 0) => vec![(0, 1), (0, -1)],
_ => unreachable!(),
},
Some('|') => match vector {
(1, 0) | (-1, 0) => vec![*vector],
(0, 1) | (0, -1) => vec![(1, 0), (-1, 0)],
_ => unreachable!(),
},
_ => unreachable!(),
}
}
fn traverse(&self, entry: (Point, Vector)) -> u64 {
let mut visited_locations: HashSet<Point> = HashSet::new();
let mut visit_queue: Vec<(Point, Vector)> = vec![];
let mut loop_detector: HashSet<(Point, Vector)> = HashSet::new();
visit_queue.push(entry);
while let Some((location, vector)) = visit_queue.pop() {
if !loop_detector.insert((location, vector)) {
continue;
}
visited_locations.insert(location);
let next_vectors = self.get_next_vectors(&location, &vector);
for next_vector in next_vectors {
if let Some(next_location) = self.resolve_location(&location, &next_vector) {
visit_queue.push((next_location, next_vector));
}
}
}
visited_locations.len() as u64
}
}
fn part1(document: String) {
let map = Grid::from(document);
let count = map.traverse(((0, 0), (0, 1)));
println!("Part 1: {}", count);
}
fn part2(document: String) {
let map = Grid::from(document);
let mut max_visited = 0;
for y in 0..=map.bounds.1 {
max_visited = max_visited.max(map.traverse(((0, y), (1, 0))));
max_visited = max_visited.max(map.traverse(((map.bounds.0, y), (-1, 0))));
}
for x in 0..=map.bounds.0 {
max_visited = max_visited.max(map.traverse(((x, 0), (0, 1))));
max_visited = max_visited.max(map.traverse(((x, map.bounds.1), (0, -1))));
}
println!("Part 2: {}", max_visited);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment