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!

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

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

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

Java

Custom bubble sort ftw!

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

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()
    }
}