Day 16: The Floor Will Be Lava
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
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
Python
53.059 line-seconds (ranks third hardest after days 8 and 12 so far).
from .solver import Solver def _trace_beam(data, initial_beam_head): wx = len(data[0]) wy = len(data) beam_heads = [initial_beam_head] seen_beam_heads = set() while beam_heads: next_beam_heads = [] for x, y, dx, dy in beam_heads: seen_beam_heads.add((x, y, dx, dy)) nx, ny = (x + dx), (y + dy) if nx < 0 or nx >= wx or ny < 0 or ny >= wy: continue obj = data[ny][nx] if obj == '|' and dx != 0: next_beam_heads.append((nx, ny, 0, 1)) next_beam_heads.append((nx, ny, 0, -1)) elif obj == '-' and dy != 0: next_beam_heads.append((nx, ny, 1, 0)) next_beam_heads.append((nx, ny, -1, 0)) elif obj == '/': next_beam_heads.append((nx, ny, -dy, -dx)) elif obj == '\\': next_beam_heads.append((nx, ny, dy, dx)) else: next_beam_heads.append((nx, ny, dx, dy)) beam_heads = [x for x in next_beam_heads if x not in seen_beam_heads] energized = {(x, y) for x, y, _, _ in seen_beam_heads} return len(energized) - 1 class Day16(Solver): def __init__(self): super().__init__(16) def presolve(self, input: str): data = input.splitlines() self.possible_energized_cells = ( [_trace_beam(data, (-1, y, 1, 0)) for y in range(len(data))] + [_trace_beam(data, (x, -1, 0, 1)) for x in range(len(data[0]))] + [_trace_beam(data, (len(data[0]), y, -1, 0)) for y in range(len(data))] + [_trace_beam(data, (x, len(data), 0, -1)) for x in range(len(data[0]))]) def solve_first_star(self) -> int: return self.possible_energized_cells[0] def solve_second_star(self) -> int: return max(self.possible_energized_cells)
Nim
I’m caught up!
This one was pretty straighforward. Iterate through the beam path, recursively creating new beams when you hit splitters. The only gotcha is that you need a way to detect infinite loops that can be created by splitters. I opted to record energized non-special tiles as
-
or|
, depending on which way the beam was traveling, and then abort any path that retreads those tiles in the same way. I meant to also use+
for where the beams cross, but I forgot and it turned out not to be necessary.Part 2 was pretty trivial once the code for part 1 was written.
Hi there! Looks like you linked to a Lemmy community using a URL instead of its name, which doesn’t work well for people on different instances. Try fixing it like this: [email protected]
Haskell
A pretty by-the-book “walk all paths” algorithm. This could be made a lot faster with some caching.
Solution
import Control.Monad import Data.Array.Unboxed (UArray) import qualified Data.Array.Unboxed as A import Data.Foldable import Data.Set (Set) import qualified Data.Set as Set type Pos = (Int, Int) readInput :: String -> UArray Pos Char readInput s = let rows = lines s in A.listArray ((1, 1), (length rows, length $ head rows)) $ concat rows energized :: (Pos, Pos) -> UArray Pos Char -> Set Pos energized start grid = go Set.empty $ Set.singleton start where go seen beams | Set.null beams = Set.map fst seen | otherwise = let seen' = seen `Set.union` beams beams' = Set.fromList $ do ((y, x), (dy, dx)) <- toList beams d'@(dy', dx') <- case grid A.! (y, x) of '/' -> [(-dx, -dy)] '\\' -> [(dx, dy)] '|' | dx /= 0 -> [(-1, 0), (1, 0)] '-' | dy /= 0 -> [(0, -1), (0, 1)] _ -> [(dy, dx)] let p' = (y + dy', x + dx') beam' = (p', d') guard $ A.inRange (A.bounds grid) p' guard $ beam' `Set.notMember` seen' return beam' in go seen' beams' part1 = Set.size . energized ((1, 1), (0, 1)) part2 input = maximum counts where (_, (h, w)) = A.bounds input starts = concat $ [[((y, 1), (0, 1)), ((y, w), (0, -1))] | y <- [1 .. h]] ++ [[((1, x), (1, 0)), ((h, x), (-1, 0))] | x <- [1 .. w]] counts = map (\s -> Set.size $ energized s input) starts main = do input <- readInput <$> readFile "input16" print $ part1 input print $ part2 input
A whopping 130.050 line-seconds!
Scala3
This could be much more efficient (and quite a bit shorter), but I wanted to try out the scala-graph library (https://www.scala-graph.org)
import day10._ import day10.Dir._ import scalax.collection.edges.DiEdge import scalax.collection.immutable.Graph import scalax.collection.edges.DiEdgeImplicits import scalax.collection.generic.AnyEdge import scalax.collection.generic.Edge case class Node(ps: Set[Pos]) def getNode(p: Pos, d: Dir) = Node(Set(p, walk(p, d))) def connect(p: Pos, d1: Dir, d2: Dir) = List(getNode(p, d1) ~> getNode(p, d2), getNode(p, d2) ~> getNode(p, d1)) def parseGrid(a: List[List[Char]]) = def parseCell(s: Char, pos: Pos) = s match case '.' => connect(pos, Left, Right) ++ connect(pos, Up, Down) case '/' => connect(pos, Left, Up) ++ connect(pos, Right, Down) case '\\' => connect(pos, Left, Down) ++ connect(pos, Right, Up) case '-' => connect(pos, Left, Right) ++ List( getNode(pos, Up) ~> getNode(pos, Left), getNode(pos, Up) ~> getNode(pos, Right), getNode(pos, Down) ~> getNode(pos, Left), getNode(pos, Down) ~> getNode(pos, Right), ) case '|' => connect(pos, Up, Down) ++ List( getNode(pos, Left) ~> getNode(pos, Up), getNode(pos, Left) ~> getNode(pos, Down), getNode(pos, Right) ~> getNode(pos, Up), getNode(pos, Right) ~> getNode(pos, Down), ) case _ => List().ensuring(false) val edges = a.zipWithIndex.flatMap((r, y) => r.zipWithIndex.map((v, x) => v -> Pos(x, y))).map(parseCell).reduceLeft((a, b) => a ++ b) Graph() ++ edges def illuminationFrom(p: Pos, d: Dir, g: Graph[Node, DiEdge[Node]], inBounds: Pos => Boolean): Long = val es = getNode(p, d.opposite) ~> getNode(p, d) val g2 = g + es val n = g2.get(getNode(p, d)) n.outerNodeTraverser.flatMap(_.ps).toSet.filter(inBounds).size def inBounds(a: List[String])(p: Pos) = p.x >= 0 && p.x < a(0).size && p.y >= 0 && p.y < a.size def task1(a: List[String]): Long = illuminationFrom(Pos(-1, 0), Right, parseGrid(a.map(_.toList)), inBounds(a)) def task2(a: List[String]): Long = val inits = (for y <- a.indices yield Seq((Pos(-1, y), Right), (Pos(a(y).size, y), Left))) ++ (for x <- a(0).indices yield Seq((Pos(x, -1), Down), (Pos(x, a.size), Up))) val g = parseGrid(a.map(_.toList)) inits.flatten.map((p, d) => illuminationFrom(p, d, g, inBounds(a))).max
Rust
I simply check each starting position individually for Part 2, I don’t know if there are more clever solutions. Initially that approach ran in 180ms which is a lot more than any of the previous puzzles needed, so I tried if I could optimize it.
Initially I was using two hash sets, one for counting unique energized fields, and one for detecting cycles which also included the direction in the hash. Going from the default rust hasher to FxHash sped it up to 100ms. Seeing that, I thought that this point could be further improved upon, and ended up replacing both hash sets with boolean arrays, since their size is neatly bounded by the input field size. Now it runs in merely 30ms, meaning a 6x speedup just by getting rid of the hashing.
C
Just tracing the ray. When it splits, recurse one way and continue the other. Didn’t bother with a direction lookup table this time, just a few ifs. The ray ends when it goes out of bounds or a ray in that direction has been previously traced on a given cell (this is tracked with a separate table).
It would’ve been straightforward if I hadn’t gotten the ‘previously visited’ check wrong 😞. I was checking against the direction coming in of the tile but marking the direction going out.
Ray function:
static void ray(int x, int y, int dir) { int c; while (x>=0 && y>=0 && x
Haskell
A bit of a mess, I probably shouldn’t have used RWS …
import Control.Monad.RWS import Control.Parallel.Strategies import Data.Array import qualified Data.ByteString.Char8 as BS import Data.Foldable (Foldable (maximum)) import Data.Set import Relude data Cell = Empty | VertSplitter | HorizSplitter | Slash | Backslash deriving (Show, Eq) type Pos = (Int, Int) type Grid = Array Pos Cell data Direction = N | S | E | W deriving (Show, Eq, Ord) data BeamHead = BeamHead { pos :: Pos, dir :: Direction } deriving (Show, Eq, Ord) type Simulation = RWS Grid (Set Pos) (Set BeamHead) next :: BeamHead -> BeamHead next (BeamHead p d) = BeamHead (next' d p) d where next' :: Direction -> Pos -> Pos next' direction = case direction of N -> first pred S -> first succ E -> second succ W -> second pred advance :: BeamHead -> Simulation [BeamHead] advance bh@(BeamHead position direction) = do grid <- ask seen <- get if inRange (bounds grid) position && bh `notMember` seen then do tell $ singleton position modify $ insert bh pure . fmap next $ case (grid ! position, direction) of (Empty, _) -> [bh] (VertSplitter, N) -> [bh] (VertSplitter, S) -> [bh] (HorizSplitter, E) -> [bh] (HorizSplitter, W) -> [bh] (VertSplitter, _) -> [bh {dir = N}, bh {dir = S}] (HorizSplitter, _) -> [bh {dir = E}, bh {dir = W}] (Slash, N) -> [bh {dir = E}] (Slash, S) -> [bh {dir = W}] (Slash, E) -> [bh {dir = N}] (Slash, W) -> [bh {dir = S}] (Backslash, N) -> [bh {dir = W}] (Backslash, S) -> [bh {dir = E}] (Backslash, E) -> [bh {dir = S}] (Backslash, W) -> [bh {dir = N}] else pure [] simulate :: [BeamHead] -> Simulation () simulate heads = do heads' <- foldMapM advance heads unless (Relude.null heads') $ simulate heads' runSimulation :: BeamHead -> Grid -> Int runSimulation origin g = size . snd . evalRWS (simulate [origin]) g $ mempty part1, part2 :: Grid -> Int part1 = runSimulation $ BeamHead (0, 0) E part2 g = maximum $ parMap rpar (`runSimulation` g) possibleInitials where ((y0, x0), (y1, x1)) = bounds g possibleInitials = join [ [BeamHead (y0, x) S | x <- [x0 .. x1]], [BeamHead (y1, x) N | x <- [x0 .. x1]], [BeamHead (y, x0) E | y <- [y0 .. y1]], [BeamHead (y, x1) W | y <- [y0 .. y1]] ] parse :: ByteString -> Maybe Grid parse input = do let ls = BS.lines input h = length ls w <- BS.length <$> viaNonEmpty head ls mat <- traverse toCell . BS.unpack $ BS.concat ls pure $ listArray ((0, 0), (h - 1, w - 1)) mat where toCell '.' = Just Empty toCell '|' = Just VertSplitter toCell '-' = Just HorizSplitter toCell '/' = Just Slash toCell '\\' = Just Backslash toCell _ = Nothing
C#
Breadth-first search, then take the max of the values of searches starting from all the edge tiles.
https://code.dinn.ca/stevedinn/AdventOfCode/src/branch/main/2023/day16/Program.csRust
use std::fs; use std::path::PathBuf; use clap::Parser; use rayon::prelude::*; #[derive(Parser)] #[command(author, version, about, long_about = None)] struct Cli { input_file: PathBuf, } #[derive(Copy, Clone)] enum TileState { None, Energized(BeamState), } #[derive(Default, Copy, Clone)] struct BeamState { up: bool, down: bool, left: bool, right: bool, } fn main() { // Parse CLI arguments let cli = Cli::parse(); // Read file let input_text = fs::read_to_string(&cli.input_file) .expect(format!("File \"{}\" not found", cli.input_file.display()).as_str()); let tiles: Vec> = input_text.lines().map(|l| l.chars().collect()).collect(); // Part 1 let part_1 = test_beam(&tiles, (0, 0), (0, 1)); println!("Part 1: {}", part_1); // Part 2 let part_2: usize = (0..4) .into_par_iter() .map(|dir| { (0..tiles.len()) .into_par_iter() .map(move |x| (dir.clone(), x)) }) .flatten() .map(|(dir, x)| match dir { 0 => ((0, x), (1, 0)), 1 => ((x, tiles[0].len() - 1), (0, -1)), 2 => ((tiles.len() - 1, x), (-1, 0)), 3 => ((x, 0), (0, 1)), _ => unreachable!(), }) .map(|(loc, dir)| test_beam(&tiles, loc, dir)) .max() .unwrap(); println!("Part 2: {}", part_2); } fn test_beam( tiles: &Vec>, start_location: (usize, usize), start_direction: (i64, i64), ) -> usize { let mut energized: Vec> = vec![vec![TileState::None; tiles[0].len()]; tiles.len()]; continue_beam( &mut energized, &tiles, start_location, start_direction, true, 0, ); energized .iter() .map(|r| { r.iter() .filter(|t| matches!(t, TileState::Energized(_))) .count() }) .sum() } fn continue_beam( energized: &mut Vec>, tiles: &Vec>, beam_location: (usize, usize), beam_direction: (i64, i64), start_hack: bool, depth: usize, ) { assert_ne!(beam_direction, (0, 0)); // Set current tile to energized with the direction let current_state = energized[beam_location.0][beam_location.1]; if !start_hack { energized[beam_location.0][beam_location.1] = match current_state { TileState::None => TileState::Energized(match beam_direction { (0, 1) => BeamState { right: true, ..BeamState::default() }, (0, -1) => BeamState { left: true, ..BeamState::default() }, (1, 0) => BeamState { down: true, ..BeamState::default() }, (-1, 0) => BeamState { up: true, ..BeamState::default() }, _ => unreachable!(), }), TileState::Energized(state) => TileState::Energized(match beam_direction { (0, 1) => { if state.right { return; } BeamState { right: true, ..state } } (0, -1) => { if state.left { return; } BeamState { left: true, ..state } } (1, 0) => { if state.down { return; } BeamState { down: true, ..state } } (-1, 0) => { if state.up { return; } BeamState { up: true, ..state } } _ => unreachable!(), }), }; } // energized[beam_location.0][beam_location.1] = TileState::Energized(BeamState { up: , down: , left: , right: }); let next_beam_location = { let loc = ( (beam_location.0 as i64 + beam_direction.0), (beam_location.1 as i64 + beam_direction.1), ); if start_hack { beam_location } else if loc.0 < 0 || loc.0 >= tiles.len() as i64 || loc.1 < 0 || loc.1 >= tiles[0].len() as i64 { return; } else { (loc.0 as usize, loc.1 as usize) } }; let next_beam_tile = tiles[next_beam_location.0][next_beam_location.1]; let next_beam_directions: Vec<(i64, i64)> = match next_beam_tile { '.' => vec![beam_direction], '/' => match beam_direction { (0, 1) => vec![(-1, 0)], (0, -1) => vec![(1, 0)], (1, 0) => vec![(0, -1)], (-1, 0) => vec![(0, 1)], _ => unreachable!(), }, '\\' => match beam_direction { (0, 1) => vec![(1, 0)], (0, -1) => vec![(-1, 0)], (1, 0) => vec![(0, 1)], (-1, 0) => vec![(0, -1)], _ => unreachable!(), }, '|' => match beam_direction { (0, 1) => vec![(1, 0), (-1, 0)], (0, -1) => vec![(1, 0), (-1, 0)], (1, 0) => vec![(1, 0)], (-1, 0) => vec![(-1, 0)], _ => unreachable!(), }, '-' => match beam_direction { (0, 1) => vec![(0, 1)], (0, -1) => vec![(0, -1)], (1, 0) => vec![(0, 1), (0, -1)], (-1, 0) => vec![(0, 1), (0, -1)], _ => unreachable!(), }, _ => unreachable!(), }; for dir in next_beam_directions { continue_beam(energized, tiles, next_beam_location, dir, false, depth + 1); } }
26.28 line-seconds
Dart
I’m cheating a bit by posting this as it does take 11s for the full part 2 solution, but having tracked down and eliminated the excessively long path for part 1, I can’t be bothered to do it again for part 2.I’m an idiot. Avoiding recursively adding the same points to the
seen
set dropped total runtime to a hair under 0.5s, so line-seconds are around 35.Map, Set>> seen = {}; Map fire(List> grid, Point here, Point dir) { seen = {}; return _fire(grid, here, dir); } Map, Set>> _fire( List> grid, Point here, Point dir) { while (true) { here += dir; if (!here.x.between(0, grid.first.length - 1) || !here.y.between(0, grid.length - 1)) { return seen; } if (seen[here]?.contains(dir) ?? false) return seen; seen[here] = (seen[here] ?? >{})..add(dir); Point split() { _fire(grid, here, Point(-dir.y, -dir.x)); return Point(dir.y, dir.x); } dir = switch (grid[here.y][here.x]) { '/' => Point(-dir.y, -dir.x), r'\' => Point(dir.y, dir.x), '|' => (dir.x.abs() == 1) ? split() : dir, '-' => (dir.y.abs() == 1) ? split() : dir, _ => dir, }; } } parse(List lines) => lines.map((e) => e.split('').toList()).toList(); part1(List lines) => fire(parse(lines), Point(-1, 0), Point(1, 0)).length; part2(List lines) { var grid = parse(lines); var ret = 0.to(grid.length).fold( 0, (s, t) => [ s, fire(grid, Point(-1, t), Point(1, 0)).length, fire(grid, Point(grid.first.length, t), Point(-1, 0)).length ].max); return 0.to(grid.first.length).fold( ret, (s, t) => [ s, fire(grid, Point(t, -1), Point(0, 1)).length, fire(grid, Point(t, grid.length), Point(0, -1)).length ].max); }
Golang
Avoided recursion by having an array of “pending paths”. Whenever I hit a splitter, I follow one of the paths straight away, and push the starting point and direction of the other path to the array.
First time I ran it, hit an infinite loop. Handled it by skipping “|” and “-” if they have been visited already.
Part 2 is the same code as part 1 but I just check all the possible starting points.
Code
package main import ( "bufio" "fmt" "os" ) type Direction int const ( UP Direction = 0 DOWN Direction = 1 LEFT Direction = 2 RIGHT Direction = 3 ) type LightPoint struct { row int col int dir Direction } func solve(A [][]rune, start LightPoint) int { m := len(A) n := len(A[0]) visited := make([]bool, m*n) points := []LightPoint{} points = append(points, start) for len(points) > 0 { current := points[0] points = points[1:] i := current.row j := current.col dir := current.dir for { if i < 0 || i >= m || j < 0 || j >= n { break } if visited[i*n+j] && (A[i][j] == '-' || A[i][j] == '|') { break } visited[i*n+j] = true if A[i][j] == '.' || (A[i][j] == '-' && (dir == LEFT || dir == RIGHT)) || (A[i][j] == '|' && (dir == UP || dir == DOWN)) { switch dir { case UP: i-- case DOWN: i++ case LEFT: j-- case RIGHT: j++ } continue } if A[i][j] == '\\' { switch dir { case UP: dir = LEFT j-- case DOWN: dir = RIGHT j++ case LEFT: dir = UP i-- case RIGHT: dir = DOWN i++ } continue } if A[i][j] == '/' { switch dir { case UP: dir = RIGHT j++ case DOWN: dir = LEFT j-- case LEFT: dir = DOWN i++ case RIGHT: dir = UP i-- } continue } if A[i][j] == '-' && (dir == UP || dir == DOWN) { points = append(points, LightPoint{row: i, col: j + 1, dir: RIGHT}) dir = LEFT j-- continue } if A[i][j] == '|' && (dir == LEFT || dir == RIGHT) { points = append(points, LightPoint{row: i + 1, col: j, dir: DOWN}) dir = UP i-- } } } energized := 0 for _, v := range visited { if v { energized++ } } return energized } func part1(A [][]rune) { start := LightPoint{row: 0, col: 0, dir: RIGHT} energized := solve(A, start) fmt.Println(energized) } func part2(A [][]rune) { m := len(A) n := len(A[0]) max := -1 for i := 0; i < m; i++ { start := LightPoint{row: i, col: 0, dir: RIGHT} energized := solve(A, start) if energized > max { max = energized } start = LightPoint{row: 0, col: n - 1, dir: LEFT} energized = solve(A, start) if energized > max { max = energized } } for j := 0; j < n; j++ { start := LightPoint{row: 0, col: j, dir: DOWN} energized := solve(A, start) if energized > max { max = energized } start = LightPoint{row: m - 1, col: j, dir: UP} energized = solve(A, start) if energized > max { max = energized } } fmt.Println(max) } func main() { // file, _ := os.Open("sample.txt") file, _ := os.Open("input.txt") defer file.Close() scanner := bufio.NewScanner(file) var lines []string for scanner.Scan() { lines = append(lines, scanner.Text()) } var A [][]rune for _, line := range lines { A = append(A, []rune(line)) } // part1(A) part2(A) }