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

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

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

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

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

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

Java

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.

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

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