Day 11: Plutonian Pebbles

from collections import Counter

with open('input/11.txt', 'r') as f:
    stones = list(map(int, f.readline().split()))

stone_count = Counter(stones)

def transform_stone(n):
    s = str(n)
    if n == 0:
        yield 1
    elif len(s) % 2 == 0:
        half = len(s) // 2
        yield int(s[:half])
        yield int(s[half:])
    else:
        yield n * 2024

def blink(stone_count : Counter):
    new_stones = Counter()
    for s, count in stone_count.items():
        for t in transform_stone(s):
            new_stones[t] += count
    return new_stones

s = stone_count
for i in range(75):
    s = blink(s)
    if i + 1 == 25:
        print("Part 1:", s.total())
    if i + 1 == 75:
        print("Part 2:", s.total())

Originally I split the input into an array and looped through it, building a second array from the results of the rules for each stone. It worked fine for 25 steps... but when I tried it in Part 2 I was startled to see the whole thing explode with a RangeError: Invalid array length error. So that data type was a non-starter.

At that point I switched to direct string manipulation, because at least there's no firm upper bound on length for strings. I knew this was playing with fire but wanted to see how far it could get me. I looped through the string one char at a time, looking for " " delimiters between words (in this case a "word" is a number, but string-encoded). When each word was identified, I'd apply the relevant rule and replace the word with its result in the main string. I had to keep close track of my index because this changed the length of the string and my pointer position within it while I was in the middle of looping through it. At the end I'd just count up the occurrences of " " in the string to see how many stones I had.

This approach was noticeably slower than my array-based solution, for solving Part 1. But it did have the advantage of not throwing RangeErrors so I let it run for a while. I added some duration logging so I could track its progress through each "blink" (step):

Step 1 completed in 00:00:00.
Step 2 completed in 00:00:00.
Step 3 completed in 00:00:00.
Step 4 completed in 00:00:00.
Step 5 completed in 00:00:00.
Step 6 completed in 00:00:00.
Step 7 completed in 00:00:00.
Step 8 completed in 00:00:00.
Step 9 completed in 00:00:00.
Step 10 completed in 00:00:00.
Step 11 completed in 00:00:00.
Step 12 completed in 00:00:00.
Step 13 completed in 00:00:00.
Step 14 completed in 00:00:00.
Step 15 completed in 00:00:00.
Step 16 completed in 00:00:00.
Step 17 completed in 00:00:00.
Step 18 completed in 00:00:00.
Step 19 completed in 00:00:00.
Step 20 completed in 00:00:00.
Step 21 completed in 00:00:00.
Step 22 completed in 00:00:01.
Step 23 completed in 00:00:02.
Step 24 completed in 00:00:05.
Step 25 completed in 00:00:12.
Step 26 completed in 00:00:26.
Step 27 completed in 00:01:00.
Step 28 completed in 00:02:17.
Step 29 completed in 00:05:18.
Step 30 completed in 00:13:21.

At this point I had enough data to see the hockey stick— it would take literally billions of years to reach step 75. That's when I hopped onto Tildes and got the hint I needed.

I think what I had gotten hung up on was this sentence in the puzzle text: "No matter how the stones change, their order is preserved, and they stay on their perfectly straight line." That suggested that the exact order was important so I'd been avoiding discarding that information. In reality, it's only looking for the number of stones, not their relative positions. Good exercise in thinking outside the box! My final code was able to complete both parts in just 10ms. Edit: 76ms, still pretty good imho.

type InputData = number[];
type StoneCatalog = Record<number, number>;

function formatInput(input: string): InputData {
  return input
    .trim()
    .split(' ')
    .map(num => Number(num));
}

// void function; update catalog object in-place
const countStone = (stoneString: keyof StoneCatalog, numberToCount: number, stoneCatalog: StoneCatalog): void => {
  if (Object.prototype.hasOwnProperty.call(stoneCatalog, stoneString)) {
    stoneCatalog[stoneString] += numberToCount;
  } else {
    stoneCatalog[stoneString] = numberToCount;
  }
};

export function run(input: string): string[] {
  const data = formatInput(input);

  const countStonesAfter25Blinks = (stones: InputData): number => {
    const numberOfBlinks = 25;
    let clonedStones = [...stones];
    for (let blinkNum = 0; blinkNum < numberOfBlinks; blinkNum++) {
      const newStones: number[] = [];
      for (const stone of clonedStones) {
        if (stone === 0) {
          newStones.push(1);
          continue;
        }
        const stoneString = `${stone}`;
        if (stoneString.length % 2 === 0) {
          const midpoint = stoneString.length / 2;
          const split = [Number(stoneString.slice(0, midpoint)), Number(stoneString.slice(midpoint))];
          newStones.push(...split);
          continue;
        }
        newStones.push(stone * 2024);
      }
      clonedStones = newStones;
    }
    return clonedStones.length;
  };

  const countStonesAfter75Blinks = (stones: InputData): number => {
    const numberOfBlinks = 75;
    let result = 0;
    let stoneCatalog: StoneCatalog = {};
    for (const stone of stones) {
      countStone(stone, 1, stoneCatalog);
    }
    for (let blinkNum = 0; blinkNum < numberOfBlinks; blinkNum++) {
      const newCatalog: StoneCatalog = {};
      for (const stoneString in stoneCatalog) {
        if (stoneString === '0') {
          countStone(1, stoneCatalog[stoneString], newCatalog);
          continue;
        }
        if (stoneString.length % 2 === 0) {
          const midpoint = stoneString.length / 2;
          countStone(Number(stoneString.slice(0, midpoint)), stoneCatalog[stoneString], newCatalog);
          countStone(Number(stoneString.slice(midpoint)), stoneCatalog[stoneString], newCatalog);
          continue;
        }
        countStone(Number(stoneString) * 2024, stoneCatalog[stoneString], newCatalog);
      }
      stoneCatalog = newCatalog;
    }
    for (const stone in stoneCatalog) {
      result += stoneCatalog[stone];
    }
    return result;
  };

  return [`${countStonesAfter25Blinks(data)}`, `${countStonesAfter75Blinks(data)}`];
}

defmodule AdventOfCode.Solution.Year2024.Day11 do
  use AdventOfCode.Solution.SharedParse

  import Integer, only: [is_even: 1]

  @impl true
  def parse(input), do: String.split(input)

  def part1(stones), do: solve(stones, 25)
  def part2(stones), do: solve(stones, 75)

  defp solve(stones, blinks) do
    stones
    |> collect()
    |> Stream.iterate(&blink/1)
    |> Enum.at(blinks)
    |> Enum.map(fn {_stone, n} -> n end)
    |> Enum.sum()
  end

  defp blink(stones, acc \\ [])

  defp blink([], acc), do: collect(acc)

  defp blink([stone | stones], acc) do
    acc =
      case stone do
        {"0", n} ->
          [{"1", n} | acc]

        {stone, n} when is_even(byte_size(stone)) ->
          {a, b} = split(stone)
          [{b, n}, {a, n} | acc]

        {stone, n} ->
          stone = stone |> String.to_integer() |> Kernel.*(2024) |> Integer.to_string()
          [{stone, n} | acc]
      end

    blink(stones, acc)
  end

  defp split(str) do
    half = str |> byte_size() |> div(2)
    a = str |> binary_part(0, half) |> trim_zeros()
    b = str |> binary_part(half, half) |> trim_zeros()
    {a, b}
  end

  defp trim_zeros(str) do
    case String.trim_leading(str, "0") do
      "" -> "0"
      trimmed -> trimmed
    end
  end

  defp collect([{_stone, _n} | _] = stones) do
    stones
    |> Enum.group_by(fn {stone, _n} -> stone end, fn {_stone, n} -> n end)
    |> Enum.map(fn {stone, ns} -> {stone, Enum.sum(ns)} end)
  end

  defp collect([_stone | _] = stones) do
    stones
    |> Enum.frequencies()
    |> Map.to_list()
  end
end

Name             ips        average  deviation         median         99th %
Parse      288130.82     0.00347 ms   ±229.80%     0.00342 ms     0.00471 ms
Part 1        774.97        1.29 ms     ±6.84%        1.28 ms        1.46 ms
Part 2          7.89      126.79 ms     ±1.35%      126.76 ms      134.28 ms

Comparison: 
Parse      288130.82
Part 1        774.97 - 371.80x slower +1.29 ms
Part 2          7.89 - 36531.34x slower +126.78 ms

Class {
	#name : 'Day11Solver',
	#superclass : 'AoCSolver',
	#instVars : [
		'stones',
		'cache'
	],
	#category : 'AoCDay11',
	#package : 'AoCDay11'
}

Day11Solver >> blink: blinkCount timesStone: stone [
	| s firstHalf secondHalf |
	blinkCount = 0 ifTrue: [ ^ 1 ].
	stone = 0 ifTrue: [ ^ self cachedBlink: blinkCount - 1 timesStone: 1 ].
	s := stone asString.
	s size even ifTrue: [
		firstHalf := (s first: s size // 2) asInteger.
		secondHalf := (s allButFirst: s size // 2) asInteger.
		^ (self cachedBlink: blinkCount - 1 timesStone: firstHalf)
		  + (self cachedBlink: blinkCount - 1 timesStone: secondHalf) ].
	^ self cachedBlink: blinkCount - 1 timesStone: stone * 2024
]

Day11Solver >> cachedBlink: blinkCount timesStone: stone [
	| key |
	key := { blinkCount . stone }.
	(cache includesKey: key)
		ifTrue: [ ^ cache at: key ]
		ifFalse: [ ^ cache at: key put: (self blink: blinkCount timesStone: stone). ]
]

Day11Solver >> parseRawData [
	cache := Dictionary new.
	stones := (rawData splitOn: ' ') collect: #asInteger.
]

Day11Solver >> solvePart1 [
	^ (stones collect: [ :stone | self cachedBlink: 25 timesStone: stone ]) sum
]

Day11Solver >> solvePart2 [
	^ (stones collect: [ :stone | self cachedBlink: 75 timesStone: stone ]) sum
]

I should have solved this properly from the start, but the experience so far this year has been that the first part can be solved naively. Somehow I always get that the wrong way around, thinking I need a proper Part 1 when I don't, and not thinking properly about part 2 when I need to. I hate how I go into 'hacking' mode immediately instead of taking a minute to think things through.

I initially just used a linked list to iterate on the 'blinks', but after solving part 2 properly, part 1 became a lot simpler as well.

pub fn part1(input: &PuzzleInput) -> String {
    blink_many(&input.stones, 25).to_string()
}

pub fn blink_many(input: &[u64], count: usize) -> usize {
    let states = Counter::from(input.iter().cloned());

    let counts = (0..count).fold(states, |states, _| {
        state_iteration(&states, |input, _| blink(*input), ())
    });

    counts.count_sum()
}

pub gen fn blink(stone: u64) -> u64 {
    if stone == 0 {
        yield 1;
        return;
    }

    let num_digits = stone.ilog10() + 1;

    if num_digits % 2 == 0 {
        yield stone / 10u64.pow(num_digits / 2);
        yield stone % 10u64.pow(num_digits / 2);
        return;
    }

    yield stone * 2024;
}

pub fn part2(input: &PuzzleInput) -> String {
    blink_many(&input.stones, 75).to_string()
}

/// Iterates a state function once.
///
/// The idea is to have a HashMap containing the current states. Then a
/// transition function (which may take an input value) is applied to each
/// state, and the resulting state(s) are collected in a new HashMap.
///
/// The HashMap keeps track of how often a given state has occurred. This can be
/// used to, for example, count how often a state is visited in a finite state
/// machine after n iterations.
///
/// For example, given a non-deterministic finite state machine, you can count
/// how often you end up in the `accept` state after iterating the machine for
/// n steps. This was useful for AoC 2023, day 12 in order to count the number of
/// valid strings.
///
pub fn state_iteration<S, FN, IS, IN>(
    states: &Counter<S>,
    mut transition: FN,
    input: IN,
) -> Counter<S>
where
    S: Eq + Hash,
    FN: FnMut(&S, &IN) -> IS,
    IS: IntoIterator<Item = S>,
{
    let mut new_states = Counter::new();

    for (state, count) in states.iter() {
        for new_state in transition(state, &input) {
            new_states.add_many(new_state, *count);
        }
    }

    new_states
}

day_11    fastest       │ slowest       │ median        │ mean          │ samples │ iters
├─ part1  133.5 µs      │ 170.3 µs      │ 136.3 µs      │ 137 µs        │ 100     │ 100
╰─ part2  5.305 ms      │ 5.812 ms      │ 5.418 ms      │ 5.465 ms      │ 100     │ 100

/* Advent of Code 2024
 * Day 11: Plutonian Pebbles
 */

#import "Basic";
#import "File";
#import "Hash_Table";
#import "String";

add_stones :: (stones: *Table(int, int), stone: int, amount: int) {
    old_amount, success := table_find(stones, stone);
    if success {
        table_set(stones, stone, old_amount + amount);
    } else {
        table_add(stones, stone, amount);
    }
}

get_stone_count :: (stones: *Table(int, int)) -> int {
    stone_count := 0;
    for stones {
        stone_count += it;
    }

    return stone_count;
}

main :: () {
    input, success := read_entire_file("inputs/day_11.txt");
    assert(success);

    stones: Table(int, int);
    defer deinit(*stones);

    for split(input, " ") {
        table_add(*stones, string_to_int(it), 1);
    }

    for 1..75 {
        // We have to track the new stones separately to avoid processing
        // the same stones multiple times in the same blink.
        new_stones: Table(int, int);
        defer deinit(*new_stones);

        for stones {
            if it_index == 0 {
                add_stones(*new_stones, 1, it);
            } else {
                stone := it_index;
                digit_count := 1;

                while stone >= 10 {
                    stone /= 10;
                    digit_count += 1;
                }

                if digit_count % 2 == 0 {
                    divisor := 1;
                    for 1..digit_count / 2 {
                        divisor *= 10;
                    }

                    add_stones(*new_stones, it_index / divisor, it);
                    add_stones(*new_stones, it_index % divisor, it);
                } else {
                    add_stones(*new_stones, it_index * 2024, it);
                }
            }

            table_set(*stones, it_index, 0);
        }

        for new_stones {
            add_stones(*stones, it_index, it);
        }

        // We have to wait to remove stones until everything for this blink has
        // been processed.
        for stones {
            if it == 0 {
                remove it;
            }
        }

        if it == 25 {
            print("Part 1: %\n", get_stone_count(*stones));
        }
    }

    print("Part 2: %\n", get_stone_count(*stones));
}

#! /usr/bin/env racket
#lang racket

(module+ test
  (require rackunit))

(define (input->stones in-port)
  (let ([stone-strs (string-split (read-line in-port) " ")])
    (map string->number stone-strs)))

;; Helper procedure to apply the rules for a single stone value
(define (apply-rules stone)
  (cond
    ;; If the stone is engraved with the number 0, it is replaced by a stone engraved with the number 1.
    [(zero? stone) (list 1)]
    ;; If the stone is engraved with a number that has an even number of digits, it is replaced by two stones.
    ;; The left half of the digits are engraved on the new left stone, and the right half of the digits are
    ;; engraved on the new right stone. (The new numbers don't keep extra leading zeroes: 1000 would become
    ;; stones 10 and 0.)
    [(even? (string-length (number->string stone)))
     (let* ([stone-str (number->string stone)]
            [middle (quotient (string-length stone-str) 2)]
            [left-str (substring stone-str 0 middle)]
            [right-str (substring stone-str middle)]
            [left (string->number left-str)]
            [right (string->number right-str)])
       (list left right))]
    ;; If none of the other rules apply, the stone is replaced by a new stone; the old stone's number
    ;; multiplied by 2024 is engraved on the new stone.
    [else (list (* stone 2024))]))

;; I'm sure there's a trick to this...
(define (blink-orig stones [count 1])
  (if (zero? count)
      stones
      (blink-orig (for/fold ([new-stones '()])
                            ([stone (in-list stones)])
                    (append (apply-rules stone) new-stones))
                  (sub1 count))))

;; Ah...
;; This version of the procedure loses the ordering but is much faster for lots of iterations.
(define (blink-efficient stones [count 1])
  ;; Iteratively create a hash table and put the stones in it.
  ;; Each key is a value on a stone and each value is the number of
  ;; that value.
  ;; I don't know how to do this not iteratively.
  (define ht (make-hash))
  (for ([stone (in-list stones)])
    (hash-update! ht stone add1 0))
  ;; We also create a hash table to dynamically store our results, this way we don't have to redo calculations!
  (define calculated (make-hash))
  ;; Use a helper since we want don't want to re-create ht every time.
  (let helper ([stones ht] [count count])
    (define new-stones (make-hash))
    (cond
      [(zero? count) stones]
      ;; Also don't really know how to do this without side effects.
      [else
       ;; First, iterate through stones and update ht.
       (for ([stone-pair (in-list (hash->list stones))])
         (let* ([stone (car stone-pair)]
                [count (cdr stone-pair)]
                [blinked-stones (hash-ref calculated stone (lambda () (apply-rules stone)))])
           (hash-set! calculated stone blinked-stones)
           (for ([stone (in-list blinked-stones)])
             (hash-update! new-stones stone (lambda (n) (+ n count)) 0))))
       ;; Then recurse
       (helper new-stones (sub1 count))])))

(module+ test
  ;; Part 1
  (check-equal? (length (blink-orig (input->stones (open-input-string "0 1 10 99 999")) 1)) 7 "Test blink 1:")
  (let* ([input (open-input-string "125 17")]
         [stones (input->stones input)])
    (check-equal? (length (blink-orig stones 1)) 3 "Test blink 1: 2")
    (check-equal? (length (blink-orig stones 2)) 4 "Test blink 1: 3")
    (check-equal? (length (blink-orig stones 3)) 5 "Test blink 1: 4"))
  ;; Part 2
  (check-equal? (for/sum ([x (in-list (hash-values (blink-efficient (input->stones (open-input-string "0 1 10 99 999")) 1)))])
                  x) 7 "Test blink 2: 1")
  (let* ([input (open-input-string "125 17")]
         [stones (input->stones input)])
    (check-equal? (for/sum ([x (in-list (hash-values (blink-efficient stones 1)))])
                    x) 3 "Test blink 2: 2")
    (check-equal? (for/sum ([x (in-list (hash-values (blink-efficient stones 2)))])
                    x) 4 "Test blink 2: 3")
    (check-equal? (for/sum ([x (in-list (hash-values (blink-efficient stones 3)))])
                    x) 5 "Test blink 2: 4")))

(define (day11/run-part01 stones)
  (length (blink-orig stones 25)))
(define (day11/run-part02 stones [count 75])
  (for/sum ([x (in-list (hash-values (blink-efficient stones count)))])
    x))

(module+ test
  (let* ([in-port (open-input-string "125 17")]
         [stones (input->stones in-port)])
    (check-equal? (day11/run-part01 stones) 55312 "Test part 1 (blink-orig)")
    (check-equal? (day11/run-part02 stones 25) 55312 "Test part 2 (blink-efficient)")))

;; Run against my input and print the results
(module+ main
  (let* ([in-port (open-input-file "inputs/day11.in")]
         [stones (input->stones in-port)]
         [part1 (day11/run-part01 stones)]
         [part2 (day11/run-part02 stones)])
    (printf "Part 1: ~a, Part 2: ~a\n" part1 part2)))