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.

• Day 14, part 1
• Day 14, part 2

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!

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

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