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


🔒 Thread is locked until there’s at least 100 2 star entries on the global leaderboard

Edit: 🔓 Unlocked

  • Gobbel2000@feddit.de
    link
    fedilink
    arrow-up
    6
    ·
    11 months ago

    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.

  • cvttsd2si@programming.dev
    link
    fedilink
    arrow-up
    5
    ·
    edit-2
    11 months ago

    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)))
    
  • Leo Uino@lemmy.sdf.org
    link
    fedilink
    arrow-up
    5
    ·
    11 months ago

    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

  • hades@lemm.ee
    link
    fedilink
    arrow-up
    4
    ·
    edit-2
    3 months ago

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

  • mykl@lemmy.world
    link
    fedilink
    arrow-up
    4
    ·
    edit-2
    11 months ago

    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);
    
  • LeixB@lemmy.world
    link
    fedilink
    arrow-up
    4
    ·
    11 months ago

    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
    
  • sjmulder@lemmy.sdf.org
    link
    fedilink
    arrow-up
    4
    ·
    edit-2
    11 months ago

    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
  • janAkali@lemmy.one
    link
    fedilink
    English
    arrow-up
    3
    ·
    edit-2
    11 months ago

    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.nim

  • capitalpb@programming.dev
    link
    fedilink
    English
    arrow-up
    1
    ·
    11 months ago

    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()
        }
    }
    
  • cacheson@kbin.social
    link
    fedilink
    arrow-up
    1
    ·
    11 months ago

    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.