Day 14: Parabolic Reflector Dish
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)
- Code block support is not fully rolled out yet but likely will be in the middle of the event. Try to share solutions as both code blocks and using something such as https://topaz.github.io/paste/ , pastebin, or github (code blocks to future proof it for when 0.19 comes out and since code blocks currently function in some apps and some instances as well if they are running a 0.19 beta)
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
🔒 Thread is locked until there’s at least 100 2 star entries on the global leaderboard
Edit: 🔓 Unlocked
Rust
The trick for part 2 is obviously to check when the pattern repeats itself and then jump ahead to 1000000000.
My code allocates an entire new grid for every tilt, some in-place procedure would probably be more efficient in terms of memory, but this seems good enough.
Scala3
type Grid = List[List[Char]] def tiltUp(a: Grid): Grid = @tailrec def go(c: List[Char], acc: List[Char]): List[Char] = def shifted(c: List[Char]) = val (h, t) = c.splitAt(c.count(_ == 'O')) h.map(_ => 'O') ++ t.map(_ => '.') ++ acc val d = c.indexOf('#') if d == -1 then shifted(c) else go(c.slice(d + 1, c.size), '#'::shifted(c.slice(0, d))) a.map(go(_, List()).reverse) def weight(a: Grid): Long = a.map(d => d.zipWithIndex.filter((c, _) => c == 'O').map(1 + _._2).sum).sum def rotateNeg90(a: Grid): Grid = a.reverse.transpose def runCycle = Seq.fill(4)(tiltUp andThen rotateNeg90).reduceLeft(_ andThen _) def stateAt(target: Long, a: Grid): Grid = @tailrec def go(cycle: Int, state: Grid, seen: Map[Grid, Int]): Grid = seen.get(state) match case Some(i) => if (target - cycle) % (cycle - i) == 0 then state else go(cycle + 1, runCycle(state), seen) case None => go(cycle + 1, runCycle(state), seen + (state -> cycle)) go(0, a, Map()) def toColMajorGrid(a: List[String]): Grid = rotateNeg90(a.map(_.toList)) def task1(a: List[String]): Long = weight(tiltUp(toColMajorGrid(a))) def task2(a: List[String]): Long = weight(stateAt(1_000_000_000, toColMajorGrid(a)))
Haskell
A little slow (1.106s on my machine), but list operations made this really easy to write. I expect somebody more familiar with Haskell than me will be able to come up with a more elegant solution.
Nevertheless, 59th on the global leaderboard today! Woo!
Solution
import Data.List import qualified Data.Map.Strict as Map import Data.Semigroup rotateL, rotateR, tiltW :: Endo [[Char]] rotateL = Endo $ reverse . transpose rotateR = Endo $ map reverse . transpose tiltW = Endo $ map tiltRow where tiltRow xs = let (a, b) = break (== '#') xs (os, ds) = partition (== 'O') a rest = case b of ('#' : b') -> '#' : tiltRow b' [] -> [] in os ++ ds ++ rest load rows = sum $ map rowLoad rows where rowLoad = sum . map (length rows -) . elemIndices 'O' lookupCycle xs i = let (o, p) = findCycle 0 Map.empty xs in xs !! if i < o then i else (i - o) `rem` p + o where findCycle i seen (x : xs) = case seen Map.!? x of Just j -> (j, i - j) Nothing -> findCycle (i + 1) (Map.insert x i seen) xs main = do input <- lines <$> readFile "input14" print . load . appEndo (tiltW <> rotateL) $ input print $ load $ lookupCycle (iterate (appEndo $ stimes 4 (rotateR <> tiltW)) $ appEndo rotateL input) 1000000000
42.028 line-seconds
What’s a line-second? Never heard/seen this term before.
There was a post about it a few days ago: https://lemmy.sdf.org/post/9116867
Haskell
Managed to do part1 in one line using ByteString operations:
import Control.Monad import qualified Data.ByteString.Char8 as BS part1 :: IO Int part1 = sum . ( BS.transpose . BS.split '\n' >=> fmap succ . BS.elemIndices 'O' . BS.reverse . BS.intercalate "#" . fmap (BS.reverse . BS.sort) . BS.split '#' ) <$> BS.readFile "inp"
Part 2
{-# LANGUAGE NumericUnderscores #-} import qualified Data.ByteString.Char8 as BS import qualified Data.Map as M import Relude type Problem = [ByteString] -- We apply rotation so that north is to the right, this makes -- all computations easier since we can just sort the rows. parse :: ByteString -> Problem parse = rotate . BS.split '\n' count :: Problem -> [[Int]] count = fmap (fmap succ . BS.elemIndices 'O') rotate, move, rotMov, doCycle :: Problem -> Problem rotate = fmap BS.reverse . BS.transpose move = fmap (BS.intercalate "#" . fmap BS.sort . BS.split '#') rotMov = rotate . move doCycle = rotMov . rotMov . rotMov . rotMov doNcycles :: Int -> Problem -> Problem doNcycles n = foldl' (.) id (replicate n doCycle) findCycle :: Problem -> (Int, Int) findCycle = go 0 M.empty where go :: Int -> M.Map Problem Int -> Problem -> (Int, Int) go n m p = let p' = doCycle p in case M.lookup p' m of Just n' -> (n', n + 1) Nothing -> go (n + 1) (M.insert p' n m) p' part1, part2 :: ByteString -> Int part1 = sum . join . count . move . parse part2 input = let n = 1_000_000_000 p = parse input (s, r) = findCycle p numRots = s + ((n - s) `mod` (r - s - 1)) in sum . join . count $ doNcycles numRots p
Dart
Big lump of code. I built a general slide function which ended up being tricksy in order to visit rocks in the correct order, but it works.
int hash(List> rocks) => (rocks.map((e) => e.join('')).join('\n')).hashCode; /// Slide rocks in the given (vert, horz) direction. List> slide(List> rocks, (int, int) dir) { // Work out in which order to check rocks for most efficient movement. var rrange = 0.to(rocks.length); var crange = 0.to(rocks.first.length); var starts = [ for (var r in (dir.$1 == 1) ? rrange.reversed : rrange) for (var c in ((dir.$2 == 1) ? crange.reversed : crange) .where((c) => rocks[r][c] == 'O')) (r, c) ]; for (var (r, c) in starts) { var dest = (r, c); var next = (dest.$1 + dir.$1, dest.$2 + dir.$2); while (next.$1.between(0, rocks.length - 1) && next.$2.between(0, rocks.first.length - 1) && rocks[next.$1][next.$2] == '.') { dest = next; next = (dest.$1 + dir.$1, dest.$2 + dir.$2); } if (dest != (r, c)) { rocks[r][c] = '.'; rocks[dest.$1][dest.$2] = 'O'; } } return rocks; } List> oneCycle(List> rocks) => [(-1, 0), (0, -1), (1, 0), (0, 1)].fold(rocks, (s, t) => slide(s, t)); spin(List> rocks, {int target = 1}) { var cycle = 1; var seen = {}; while (cycle != target) { rocks = oneCycle(rocks); var h = hash(rocks); if (seen.containsKey(h)) { var diff = cycle - seen[h]!; var count = (target - cycle) ~/ diff; cycle += count * diff; seen = {}; } else { seen[h] = cycle; cycle += 1; } } return weighting(rocks); } parse(List lines) => lines.map((e) => e.split('').toList()).toList(); weighting(List> rocks) => 0 .to(rocks.length) .map((r) => rocks[r].count((e) => e == 'O') * (rocks.length - r)) .sum; part1(List lines) => weighting(slide(parse(lines), (-1, 0))); part2(List lines) => spin(parse(lines), target: 1000000000);
C
Chose not to do transposing/flipping or fancy indexing so it’s rather verbose, but it’s also clear and (I think) fast. I also tried to limit the number of search steps by keeping two cursors in the current row/col, rather than shooting a ray every time.
Part 2 immediately reminded me of that Tetris puzzle from day 22 last year so I knew how to find and apply the solution. State hashes are stored in an array and (inefficiently) scanned until a loop is found.
One direction of the shift function:
/* * Walk two cursors i and j through each column x. The i cursor * looks for the first . where an O can go. The j cursor looks * ahead for O's. When j finds a # we start again beyond it. */ for (x=0; x
Python
import numpy as np from .solver import Solver def _tilt(row: list[int], reverse: bool = False) -> list[int]: res = row[::-1] if reverse else row[:] rock_x = 0 for x, item in enumerate(res): if item == 1: rock_x = x + 1 if item == 2: if rock_x < x: res[rock_x] = 2 res[x] = 0 rock_x += 1 return res[::-1] if reverse else res class Day14(Solver): data: np.ndarray def __init__(self): super().__init__(14) def presolve(self, input: str): lines = input.splitlines() self.data = np.zeros((len(lines), len(lines[0])), dtype=np.int8) for x, line in enumerate(lines): for y, char in enumerate(line): if char == '#': self.data[x, y] = 1 elif char == 'O': self.data[x, y] = 2 def solve_first_star(self) -> int: for y in range(self.data.shape[1]): self.data[:, y] = _tilt(self.data[:, y].tolist()) return sum((self.data.shape[0] - x) * (self.data[x] == 2).sum() for x in range(self.data.shape[0])) def solve_second_star(self) -> int: seen = {} order = [] for i in range(1_000_000_000): order += [self.data.copy()] s = self.data.tobytes() if s in seen: loop_size = i - seen[s] remainder = (1_000_000_000 - i) % loop_size self.data = order[seen[s] + remainder] break seen[s] = i for y in range(self.data.shape[1]): self.data[:, y] = _tilt(self.data[:, y].tolist()) for x in range(self.data.shape[0]): self.data[x, :] = _tilt(self.data[x, :].tolist()) for y in range(self.data.shape[1]): self.data[:, y] = _tilt(self.data[:, y].tolist(), reverse=True) for x in range(self.data.shape[0]): self.data[x, :] = _tilt(self.data[x, :].tolist(), reverse=True) return sum((self.data.shape[0] - x) * (self.data[x] == 2).sum() for x in range(self.data.shape[0]))
33.938 line-seconds (ranks 3rd hardest after days 8 and 12 so far).
If you use numpy you could just take advantage of np.rot90 function to do the tilting for you:)
Oh yeah, great idea, thanks!
Nim
Part 1: I made the only procedure - to roll rocks to the right. First, I rotate input 90 degrees clockwise. Then roll rocks in each row. To roll a row of rocks - I scan from right to left, until I find a rock and try to find the most right available position for it. Not the best approach, but not the worst either.
Part 2: To do a cycle I use the same principle as part 1:(rotate clockwise + roll rocks right) x 4 = 1 cycle
. A trillion cycles would obviously take too long. Instead, I cycle the input and add every configuration to a hashTable and once we reach a full copy of one of previous cycles - it means we’re in a loop. And then finding out in what configuration rocks will be after trillion steps is easy with use of a modulo.Total Runtime: 60ms relatively slow today =(
Puzzle rating: 7/10
Code: day_14/solution.nimJava
Custom bubble sort ftw!
C#
Obviously, you can’t calculate 1 billion iterations, so the states must repeat after a while. My solution got to 154 different states and then started looping from state 92 to state 154 (63 steps). From there we can find the index in the state cache that the final state would be, and calculate the supported load from that.
https://code.dinn.ca/stevedinn/AdventOfCode/src/branch/main/2023/day14/Program.cs
Nim
Getting caught up slowly after spending way too long on day 12. I’ll be busy this weekend though, so I’ll probably fall further behind.
Part 2 looked daunting at first, as I knew brute-forcing 1 billion iterations wouldn’t be practical. I did some premature optimization anyway, pre-calculating north/south and east/west runs in which the round rocks would be able to travel.
At first I figured maybe the rocks would eventually reach a stable configuration, so I added a check to detect if the current iteration matches the previous one. It never triggered, so I dumped some of the grid states and it became obvious that there was a cycle occurring. I probably should have guessed this in advance. The spin cycle is effectively a pseudorandom number generator, and all PRNGs eventually cycle. Good PRNGs have a very long cycle length, but this one isn’t very good.
I added a hash table, mapping the state of each iteration to the next one. Once a value is added that already exists in the table as a key, there’s a complete cycle. At that point it’s just a matter of walking the cycle to determine it’s length, and calculating from there.
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]
The first part was simple enough. Adding in the 3 remaining tilt methods for star 2 was also simple enough, and worked just how I figured it would. Tried the brute force solution first, but realized it was going to take a ridiculous amount of time and went back to figure out an algorithm. It was simple enough to guess that it would hit a point where it just repeats infinitely, but actually coding out the math to extrapolate that took way more time than I want to admit. Not sure why I struggled with it so much, but after some pen and paper mathing, I essentially got there. Ended up having to subract
1
from this calculation, and either I’m just missing something or am way too tired, because I don’t know why it’s one less than what I thought it would be, but it works so who am I to complain.https://github.com/capitalpb/advent_of_code_2023/blob/main/src/solvers/day14.rs
use crate::Solver; #[derive(Debug)] struct PlatformMap { tiles: Vec>, } impl PlatformMap { fn from(input: &str) -> PlatformMap { PlatformMap { tiles: input.lines().map(|line| line.chars().collect()).collect(), } } fn load(&self) -> usize { self.tiles .iter() .enumerate() .map(|(row, tiles)| { tiles.iter().filter(|tile| *tile == &'O').count() * (self.tiles.len() - row) }) .sum() } fn tilt_north(&mut self) { for row in 1..self.tiles.len() { for col in 0..self.tiles[0].len() { if self.tiles[row][col] != 'O' { continue; } let mut new_row = row; for check_row in (0..row).rev() { if self.tiles[check_row][col] == '.' { new_row = check_row; } else { break; } } self.tiles[row][col] = '.'; self.tiles[new_row][col] = 'O'; } } } fn tilt_west(&mut self) { for col in 1..self.tiles[0].len() { for row in 0..self.tiles.len() { if self.tiles[row][col] != 'O' { continue; } let mut new_col = col; for check_col in (0..col).rev() { if self.tiles[row][check_col] == '.' { new_col = check_col; } else { break; } } self.tiles[row][col] = '.'; self.tiles[row][new_col] = 'O'; } } } fn tilt_south(&mut self) { for row in (0..(self.tiles.len() - 1)).rev() { for col in 0..self.tiles[0].len() { if self.tiles[row][col] != 'O' { continue; } let mut new_row = row; for check_row in (row + 1)..self.tiles.len() { if self.tiles[check_row][col] == '.' { new_row = check_row; } else { break; } } self.tiles[row][col] = '.'; self.tiles[new_row][col] = 'O'; } } } fn tilt_east(&mut self) { for col in (0..(self.tiles[0].len() - 1)).rev() { for row in 0..self.tiles.len() { if self.tiles[row][col] != 'O' { continue; } let mut new_col = col; for check_col in (col + 1)..self.tiles[0].len() { if self.tiles[row][check_col] == '.' { new_col = check_col; } else { break; } } self.tiles[row][col] = '.'; self.tiles[row][new_col] = 'O'; } } } } pub struct Day14; impl Solver for Day14 { fn star_one(&self, input: &str) -> String { let mut platform_map = PlatformMap::from(input); platform_map.tilt_north(); platform_map.load().to_string() } fn star_two(&self, input: &str) -> String { let mut platform_map = PlatformMap::from(input); let mut map_history: Vec>> = vec![]; for index in 0..1_000_000_000 { platform_map.tilt_north(); platform_map.tilt_west(); platform_map.tilt_south(); platform_map.tilt_east(); if let Some(repeat_start) = map_history .iter() .position(|tiles| tiles == &platform_map.tiles) { let repeat_length = index - repeat_start; let delta = (1_000_000_000 - repeat_start) % repeat_length; let solution_index = repeat_start + delta - 1; return PlatformMap { tiles: map_history[solution_index].clone(), } .load() .to_string(); } map_history.push(platform_map.tiles.clone()); } platform_map.load().to_string() } }