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)}`];
}

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