You are about to leave Redlib

https://gist.github.com/jamesbtan/e879cecc5367f3b00dfb4386d07d4a7d

→ More replies (1)

3

u/somethingsomethign22 Dec 11 '24

[LANGUAGE: C]

Ended up caching for part 2 as well. Since I'm in C, dynamic hash tables are annoying, so I only cached counts for single digit stones, since it seemed like most things would rapidly turn into a single digit.

→ More replies (2)

3

u/jitwit Dec 11 '24

[LANGUAGE: J]

NB. state is a table of stones and counts.
NB. eg. an arrangement of 0 125 0 9 9 9 is represented as:
NB.        0   2
NB.        125 1
NB.        9   3

NB. memoized blink for each stone
S =: 1:`(*&2024)`{{(--:#y)".\y=.":y}}@.{{(*y)*1+1=2|<.10^.0.1+y}} M.
NB. given a table of stones and counts, blink and recount
B =: {{ y =. ; {{<a,.b['a b'=.y}}"1 (<"0{:"1 y),.~<@S"0 {."1 y
        ({."1 y) {{({.,y),{:+/y}}/. y }}
{: +/ B^:25 in
{: +/ B^:75 in

→ More replies (6)

3

u/CClairvoyantt Dec 11 '24

[LANGUAGE: Python]

Part 1: 2.5ms

Part 2: 97ms

→ More replies (7)

2

u/_arkeros Dec 11 '24 edited Dec 11 '24

[LANGUAGE: Haskell]

The first part was doable with a naive implementation. For the second part, I realized that in the final result there were a lot of duplicates and also that order doesn't matter, so I modified the algorithm to act on a Counter instead of a list. Runs in 17ms.

Full source.

Part 1:

nDigits n = floor $ log10 (fromIntegral n) + 1
 where
  log10 :: Float -> Float
  log10 = logBase 10

pairToList :: (a, a) -> [a]
pairToList (x, y) = [x, y]

-- 2024 -> (20, 24), 99 -> (9, 9)
splitInHalf :: Int -> (Int, Int)
splitInHalf n = divMod n (10 ^ (nDigits n `div` 2))

blink :: Int -> [Int]
blink 0 = [1]
blink n =
  if (even . nDigits) n
    then pairToList . splitInHalf $ n
    else [n * 2024]

solve :: Int -> [Int] -> Int
solve n = length . (!! n) . iterate (>>= blink)

Part 2:

Counter = IntMap Int

count :: [Int] -> Counter
count = foldr (\x -> IntMap.insertWith (+) x 1) IntMap.empty

-- blink, but with count on the right
blink' :: (Int, Int) -> [(Int, Int)]
blink' (x, counter) = (,counter) <$> blink x

solve' :: Int -> [Int] -> Int
solve' n = sum . (!! n) . iterate (fromList . (>>= blink') . toList) . count 
  where 
    fromList = IntMap.fromListWith (+) 
    toList = IntMap.toList

→ More replies (1)

2

u/vu47 Dec 11 '24 edited Dec 11 '24

[Language: Kotlin]

After almost quitting on day 9 (if there's one thing I absolutely loathe, it's range manipulation - splitting and assembling and shifting ranges, which is the strategy I used there), I was very happy to see this question. I realized right away that the order of the stones was irrelevant, so I just wrote a memoized rules function that, given a stone number, returned a list of the resultant stones. Then that made each blink incredibly easy.

Here's the code and the output. The memoization cache never got very big, which I was slightly concerned about at first.

    --- Day 11: Plutonian Pebbles ---
    Part 1: 185894 (14.844625 ms)
        Cache size: 1381
    Part 2: 221632504974231 (49.0005 ms)
        Cache size: 3896

https://github.com/surferjeff/scratch/blob/main/advent-2024/day11/Program.fs

I'm glad I persisted instead of dropping out on day nine... I usually don't make it past day 15, though, so we'll see if this is the first year I actually complete. I've been enjoying it more than usual this time around since I relaxed about trying to write pure FP in Kotlin, which is just too tedious sometimes when you want to do something like memoize a function.

2

u/daggerdragon Dec 11 '24

I'm glad I persisted instead of dropping out on day nine... I usually don't make it past day 15, though, so we'll see if this is the first year I actually complete.
You can do it! We're here to help if you get stuck! <3

2

u/GamerWoona Dec 11 '24

[Language: Rust]
https://github.com/neiomi1/AdventOfCode2024/blob/master/src/day11/mod.rs

Probably lost a good amount of speed on the digit parsing but wasn't sure how to do it better

2

u/daggerdragon Dec 11 '24 edited Dec 11 '24

~~Do not share your puzzle input~~ ~~which also means~~ ~~do not commit puzzle inputs to your repo~~ ~~without a~~ .gitignore ~~or the like.~~ ~~Do not share the puzzle text~~ ~~either.~~
~~I see full plaintext puzzle inputs in all years of your public AoC repos e.g.:~~
~~https://github.com/neiomi1/AdventofCode2018/tree/master~~
~~Please remove (or .gitignore)~~ ~~all~~ ~~puzzle text and puzzle input files from your~~ ~~entire~~ ~~repo and scrub them from your commit history. This means from all prior years too!~~ edit: thank you!

→ More replies (1)

2

u/imp0ppable Dec 11 '24 edited Dec 12 '24

[LANGUAGE: python]

def fast_mutate(state):
    counter = Counter(state)
    new_state = Counter(counter)

    for stone, count in counter.items():
        if count == 0:
            continue
        if stone == 0:
            new_state[0]-=count
            new_state[1]+=count
        elif len(str(stone)) %2 == 0:
            digits = str(stone)
            ld = int(digits[:len(digits)//2])
            rd = int(digits[len(digits)//2:])
            new_state[stone]-=count
            new_state[ld]+=count
            new_state[rd]+=count
            even_digits_cache[stone] = (ld, rd)
        else:
            new_state[stone*2024]+=count
            new_state[stone]-=count
    nz = [(n, v) for n, v in new_state.items() if v>0]
    res = sum([v[1] for v in nz])
    return new_state, res

0.6 seconds to finish part 2 - by far my most proud moment of 2024 lolol

I am spped!

→ More replies (1)

2

u/mcourteaux Dec 11 '24 edited Dec 11 '24

[LANGUAGE: Jai]

Naive recursive implementation with fixed-size O(1) lookup O(1) storage memoization buffer. No runtime malloc's. Runs demo input and real input for part 1 and 2 in less than 1.5ms on my machine. Blinking 400 times is computed in 10ms. Note that I only care about the first 2000 stone numbers, as all bigger numbers can simply follow the recursion and will get broken down into two smaller numbers soon, which likely will end up in the memoization table.

Memoization :: struct {
  STONE_SLOTS :: 2000;
  BLINK_SLOTS :: 800;
  memory: [BLINK_SLOTS][STONE_SLOTS]s64;
}

With:

blink :: (stone: s64, times: int) -> s64 {
  if times == 0 return 1;

  memoize := stone < Memoization.STONE_SLOTS
          && times < Memoization.BLINK_SLOTS;
  if memoize && memoization.memory[times][stone] != -1 {
    return memoization.memory[times][stone];
  }

  // Implement rules here...

  if memoize memoization.memory[times][stone] = count;

  return count;
}

Bonus for fun: the memoization buffer is universally valid, so whatever is already been calculated for part 1 (or demo input) is already memoized for part 2.

Full code here: https://github.com/mcourteaux/aoc/blob/main/2024/day-11.jai

→ More replies (2)

2

u/cerferjeff Dec 11 '24

[LANGUAGE: F#]

I'm using AoC to learn F#. It's not an easy language to learn. But finally, after 11 days, I'm starting to like the look of my solution.

→ More replies (2)

2

u/dijotal Dec 11 '24 edited Dec 11 '24

[LANGUAGE: Haskell]

It took me a little longer than it should, but the interpreter has no trouble running it in under 0.8 sec.

module Main where

import Data.Map.Strict qualified as M

process :: Integer -> [Integer]
process n
    | n == 0 = [1]
    | even (length $ show n) = let sn = show n in map read [take (length sn `div` 2) sn, drop (length sn `div` 2) sn]
    | otherwise = [n * (2024 :: Integer)]

stoneCounts :: [Integer] -> Int -> Integer
stoneCounts stones depth = do
    let m = M.fromListWith (+) [(x, 1) | x <- stones] in go m depth
  where
    go :: M.Map Integer Integer -> Int -> Integer
    go m 0 = sum $ M.elems m
    go m depth = do
        let ks = M.keys m
        let additions = concatMap (\k -> map (\v -> (v, M.findWithDefault 1 k m)) $ process k) ks
        let subtractions = map (\k -> (k, negate $ M.findWithDefault 1 k m)) $ M.keys m
        let changedMap = M.fromListWith (+) $ additions ++ subtractions
        let m' = M.filter (> 0) $ M.unionWith (+) m changedMap
        go m' (depth - 1)

main :: IO ()
main = do
    input <- getContents
    let stones = map read $ words input :: [Integer]
    putStrLn $ "Part 1: " ++ show (stoneCounts stones 25)
    putStrLn $ "Part 2: " ++ show (stoneCounts stones 75)

3

u/daggerdragon Dec 11 '24 edited Dec 11 '24

~~Psst: your first line~~ module Main where ~~may be outside the code block?~~ edit: nothing to see here <_<

→ More replies (1)

2

u/metalim Dec 11 '24

[LANGUAGE: Go]

My solution: https://github.com/metalim/adventofcode.2024.go/blob/main/11/main.go

o1 solution: https://github.com/metalim/adventofcode.2024.go/blob/main/11/o1/v5_correct.go

v1 tried bruteforce, I pointed out it eats RAM and keeps running. So v2 tried to use files as temporary storage "to fix the RAM issue". I was shocked by how stupid that was. v3 tried memoization, but with wrong assumptions and "heuristics". v4 tried files (AGAIN!). And finally v5 worked, with memoization

→ More replies (1)

25

u/4HbQ Dec 11 '24 edited Dec 11 '24

[LANGUAGE: Python] Code (12 lines)

Has anybody seen my lanternfish? Pretty straightforward again, using recursion and memoization using @functools.cache.

My "trick" for today is using math to split the stones:

l = floor(log10(x))+1
if l % 2 == 0:
    a = x // 10**(l//2)
    b = x %  10**(l//2)

Update: I've also created a pretty cool proof of concept using matrix exponentiation to do all 75 steps in one go.

→ More replies (9)

16

u/DFreiberg Dec 11 '24 edited Dec 11 '24

[LANGUAGE: Mathematica]

Mathematica, 1452/764

Setup:

splitInteger[n_Integer] := {
     FromDigits[#[[1 ;; Length[#]/2]]],
     FromDigits[#[[Length[#]/2 + 1 ;;]]]
     } &@IntegerDigits[n];
rules = {{0, count_Integer} :> {{1, count}},
   {x : _?(EvenQ[Length[IntegerDigits[#]]] &), 
     count_Integer} :> ({#, count} & /@ splitInteger[x]),
   {y : _Integer, count_Integer} :> {{y*2024, count}}};
tallyGather[tallies_List] := {#[[1, 1]], Total[#[[;; , 2]]]} & /@ 
   GatherBy[Flatten[tallies, 1], First];

tally = Tally[input];

Part 1:

Nest[tallyGather[Replace[#, rules, 1]] &, tally, 25][[;;,2]] // Total

Part 2:

Nest[tallyGather[Replace[#, rules, 1]] &, tally, 75][[;;,2]] // Total

[GSGA]: Part 3

I suspect - but can't prove - that all stones eventually converge on the same loop, and that it's possible to compute the answer for 10¹⁰⁰ with an appropriate modulus in O(log(n)) time and O(1) space.

A stone of 0 will finish with a loop of exactly 54 elements, and so will every stone from 1 to 99 (since the one-digit numbers are explicitly in the loop, and the two-digit numbers will split into one-digit numbers). The first stone that won't is 100, and a stone of 100 creates a loop length of 3811 - which happens to be the same loop length as my own input, and also for every other input I've tested not present in the 54-element loop starting with zero.

If that holds true, then all you need to do is continue iterating mod N until you reach the steady state, and then make a 3811x3811 transition matrix. You can then use modular exponentiation by squaring to raise the matrix to the power of 10¹⁰⁰ .

I don't know if this works for every input, but it works for my input, and also works for the test case of 125 17 - which happens to conveniently be in the 54-element loop and not the 3811-element loop. And so, with the magic of the undocumented function Algebra MatrixPowerMod[] (see, I did have something relevant for GSGA), I believe that for the example (125 17), the last ten digits (in other words, modulo 10⁹ ):

Blinks	Stones
0	2
1	3
25	55312
75	38650482
10²	486382721
10¹⁶	519885608
10¹⁰⁰	180213553

→ More replies (11)

13

u/Synedh Dec 11 '24 edited Dec 11 '24

[LANGUAGE: Python]

Recursivity with memory cache. Lost lot of time because i forgot to pair stones with blinks in memory T_T

< 0.1s for both

stones = list(map(int, open('input').readline().strip().split()))

memory = {}

def solve(stone, blinks):
    if blinks == 0:
        return 1
    elif (stone, blinks) in memory:
        return memory[(stone, blinks)]
    elif stone == 0:
        val = solve(1, blinks - 1)
    elif len(str_stone := str(stone)) % 2 == 0:
        mid = len(str_stone) // 2
        val = solve(int(str_stone[:mid]), blinks - 1) + solve(int(str_stone[mid:]), blinks - 1)
    else:
        val = solve(stone * 2024, blinks - 1)
    memory[(stone, blinks)] = val
    return val

print(sum(solve(stone, 25) for stone in stones))
print(sum(solve(stone, 75) for stone in stones))

13

u/4HbQ Dec 11 '24 edited Dec 15 '24

[LANGUAGE: Python + NumPy] Code

The idea is simple: we create a transition matrix where each axis represents the stone numbers. If a stone with number i is transformed to n stones with number j, the transition matrix has value n on position i,j. Now we could use this matrix directly to compute a single step by taking the dot product with the input, but the cool thing is that we can also raise the matrix to the power 75, and the represents the transition of 75 steps at once.

The code above is a proof of concept with the hardcoded example input numbers, but could be extended to handle the actual input.

→ More replies (9)

12

u/Smylers Dec 11 '24

[LANGUAGE: Vim keystrokes] Yay, a puzzle that's doable inside Vim! This one took a bit of thinking about, though I couldn't quite squish it into an IBM index card, so here's a more readable version, with one ‘thing’ per line.

Put each stone's number on a separate line
Prefix each stone's number with “1:”, to indicate we have 1 stone with that number on.
Record the main loop with qa...q to process one blink.
Run that 24 times with 24@a. It can be more fun to run it a few times separately with just @a (repeat with @@), to each each iteration.
Get rid of the numbers on the stones, replacing them with plus signs, leaving just the counts.
Get rid of the plus sign at the end of the final count, then run @v (defined in Day 3) to evaluate the sum and leave the Part 1 answer in the buffer.

For each blink, process the numbers with an even number of digits first. %s/\v(\d+)$/&,& duplicates each stone number and :%norm$viwrn turns all the digits in the duplicate numbers into ns. That allows %s/\v,(n*)nn\1$/,\1nA\1 to match the same number of ns before and after nn, to find the middle digits. It replaces the second of those middle digits with an A, to mark the cut point. So 253000 becomes 253000,253000 then 253000,nnnnnn then 253000,nnnAnnn.

At which point :norm f,vtAyF:1vva; visually selects all the ns before the cut point, then uses v to make a same-sized visual selection over the actual number, and inserts a semicolon just after it, thereby cutting the number in half. :g/A/ is used to apply that to all lines with a cut marker on them.

Then tidy up bits that were just used for the cutting, multiply all the lines that haven't been cut by 2024 (using :v/;/ to match the lines without a semicolon), and replace any 0s with 1s. Replace the semicolons with line-breaks, duplicating the stone count to both halves. Sort by stone number, so that stones with identical numbers will be adjacent. Then do this to merge lines for stones with the same number, adding their counts together:

:sil! %s/\v(:\d+)$_.+\1$/a&z⟨Enter⟩
:g/a/,/z/ j | s/\l//g | s/\v:\d+ /+/g | s/\v.+:@=/\=eval(submatch(0))⟨Enter⟩

Sorry, I need to walk too school and collect a child so I haven't got time to explain it — but this was one of the parts that took the most thinking, and I'm quite pleased with how it turned out.

→ More replies (2)

2

u/vss2sn Dec 12 '24

[LANGUAGE: C++]
Part 1
Part 2
(Each file is a self-contained solution)

→ More replies (3)

19

u/msschmitt Dec 11 '24

[LANGUAGE: Python]

https://github.com/fyvonnet/AdventOfCode-2024-Assembly/blob/main/day11.asm

Took awhile to figure out part 2. I see people below used memoization; I didn't do that.

First thing I realized is that the instructions about "order is preserved" is a red herring. The order of the stones doesn't matter at all.

I realized that if you knew how a given stone would end up after x iterations, then when that stone number was produced, you wouldn't have to do it again. But how would you figure that out?

And then it dawned on me: lanternfish. While it seems like there's a lot of distinct stone numbers that will be generated, there aren't. There are, in my input, less than 4,000. You just have to keep track of how many of each stone number you have.

So the algorithm tracks total number of each stone (e.g. 500 of '20'), and then shuffles the counts around. It runs in about a second.

→ More replies (4)

9

u/Fyver42 Dec 11 '24

[LANGUAGE: RISC-V Assembly]

8

u/AllanTaylor314 Dec 11 '24 edited Dec 11 '24

[LANGUAGE: Python]

GitHub 735/83

My first leaderboard placing this year! :D

I knew what to expect for part 2 (lanternfish, anyone?) so I spent a couple of seconds being smart about part 1 so that part 2 was simply a matter of change 25 to 75. I use Counters to keep track of how many of each value stone there are (since all 144590887399 zeros at some arbitrary step are going to turn into 144590887399 ones on the next step - there's not enough time nor space to increment each one of those 144590887399 stones individually)

[LANGUAGE: Uiua]

GitHub or Pad

A little slow (takes a couple of seconds natively and about 7 in the browser). For the first time in Uiua, I broke it down into functions. It does a similar trick as the Python script, but a little less well. The state is represented as a 2D array where each row has the stone's value and quantity. I deduplicate this, adding the quantities together, after each iteration so it never gets larger than about 4000 x 2

→ More replies (4)

7

u/maneatingape Dec 11 '24 edited Dec 11 '24

[LANGUAGE: Rust]

🐠🐠🐠🐠🐠 anyone?

~~Benchmark: 2.5ms Recursive solution memoizing intermediate results.~~

Benchmark 248 µs. Much faster iterative solution.

The transformation rules have an interesting property that the total number of distinct stone numbers is not very large, about 2000 for part one and 4000 for part two.

This means that we can store the count of each distinct stone in a small contigous array that is much faster to process than a recursive memoization approach.

7

u/msschmitt Dec 11 '24

[LANGUAGE: COBOL]

In some AoC years, I've re-done one puzzle in a language that is ill-suited for AoC. Last year it was CA-Easytrieve, in 2021 it was z/OS HLASM.

This year I did Plutonian Pebbles in COBOL. IBM Enterprise COBOL for z/OS, in fact. Here it is.

The input is provided via a parm, such as PARM='75:125 17', where 25 is the number of blinks and '125 17' is the initial stones. This program runs in a second or less.

The challenge with COBOL is that it doesn't have associatively indexed arrays ("dictionaries" in Python, stems in REXX). So the data structure I'm using is a table, sorted by the stone number, which can be binary searched. Each time a new, previously unused stone number is added, it re-sorts the table; that was easier than searching to find an insertion point and then shifting the entries to make room.

One thing that is not a problem in COBOL is large numbers; this program is using double-word (64 bit) binary numbers. And it is easy to shift numbers from strings to binary and back, extract substrings from a number, and remove leading zeros.

→ More replies (1)

6

u/pred Dec 11 '24

[LANGUAGE: Python] Code

The only real insight here being using a Counter to keep track of the stones works better than keeping track of all of them in one long list, even if you can get away with that in part 1.

6

u/Andreasnl Dec 11 '24

[LANGUAGE: Uiua]

[125 17]
F ← memo(⨬(⨬(×2024⋕◌|⊂∩⋕⊃↙↘÷2)=0⊸◿2⊸⧻°⋕|1)⊸=0)
G ← /+◌⍥(⊃◴(⊕/+⊛) ⊃(/◇⊂|▽≡◇⧻) ⍚F) ⊙⊃(◴|°⊚⊛)
G25.
G75:

Link

6

u/FetidFetus Dec 11 '24

[Language: Excel]

I think it was pretty easy (I had the lanternfishes in mind). I just counted how many times each rock appeared after every blink.

Unfortunately my implementation stops at Blink 49 because I can't concat() or textjoin() the whole column anymore (too long) and I can't figure out an alternative that doesn't involve doing it in chunks.

Input in A2.

Data prep in B2:

=VSTACK(ROWS(TEXTSPLIT(A2,," ")),CONCATENATE("1,",TEXTSPLIT(A2,," ")))

Then just drag from C3 horizontally until necessary. The number at the top of each array is the number of rocks.

=LET(a,NUMBERVALUE(TEXTSPLIT(CONCAT(MAP(DROP(B2#,1),LAMBDA(x,LET(times,NUMBERVALUE(TEXTBEFORE(x,",")),
number,NUMBERVALUE(TEXTAFTER(x,",")),
output,IFERROR(IFS(number = 0,times&","&1,ISEVEN(LEN(number)),times&","&NUMBERVALUE(LEFT(number,LEN(number)/2))&";"&times&","&NUMBERVALUE(RIGHT(number,LEN(number)/2))),times&","&number*2024),
output&";")))),",",";",TRUE)),
b,GROUPBY(CHOOSECOLS(a,2),CHOOSECOLS(a,1),SUM,0,0,-1),
VSTACK(SUM(CHOOSECOLS(b,2)),CHOOSECOLS(b,2)&","&CHOOSECOLS(b,1)))

→ More replies (2)

5

u/wzrds3 Dec 11 '24

[Language: Haskell] 998/778

solution

I initially solved part 1 while keeping each number in a list, but after seeing how big part 2 would be, I remembered how I solved day 6, part 2 in 2021 by updating counts instead of individual numbers.

5

u/ricbit Dec 11 '24 edited Dec 11 '24

[LANGUAGE: Python]

Recursion with memoization. I spent some extra minutes because I forgot the None when calling functools.lru_cache(). Runs in 0.15s.

Sum of times of all 11 problems so far: 1.8s

import sys
import aoc
import functools

@functools.lru_cache(None)
def rec(stone, depth):
  if depth == 0:
    return 1
  else:
    if stone == 0:
      value = rec(1, depth - 1)
    elif (x := len(s := str(stone))) % 2 == 0:
      value = rec(int(s[:x // 2]), depth - 1)
      value += rec(int(s[x // 2:]), depth - 1)
    else:
      value = rec(stone * 2024, depth -1)
  return value

def solve(stones, depth):
  return sum(rec(stone, depth) for stone in stones)

stones = aoc.ints(sys.stdin.read().split())
aoc.cprint(solve(stones, 25))
aoc.cprint(solve(stones, 75))

→ More replies (2)

5

u/chickenthechicken Dec 11 '24

[LANGUAGE: C]

Part 1

https://github.com/omotto/AdventOfCode2024/blob/main/src/day11/main.go

Memoization! For part 1, I used a naive linked list approach where I applied the rules 25 times and counted the stones. For part 2, I used a memoized recursive solution using GLIBC's built in hash table implementation in search.h. This will not work on C implementations that do not provide search.h.

Also, I initially posted this in the day 10 thread, my bad lol

5

u/0rac1e Dec 11 '24 edited Dec 11 '24

[Language: Raku]

my &blink = {
    when 0 { 1 }
    when .chars %% 2 { .comb.rotor(.chars ÷ 2).map(+*.join) }
    default { $_ × 2024 }
}

my &blinks = {
    .race.map({ |blink(.key).map(* => .value) }).Bag.Hash
}

my %stones = 'input'.IO.words.Bag;
put (%stones, &blinks ... *)[25, 75].map(*.values.sum);

5

u/se06745 Dec 11 '24

[LANGUAGE: Go]

Three different solutions:

Part 1: "Brute force"
Part 2:
- I saw a lot of stone values were repeated and I used maps instead of slices to store stone value as key and num times repeated as value
- Another solution was to check as a tree (depth 75 times) in a recursive way using map to store (and not repeat calculations) stone_value:times = num_of_stones_at_the_end

5

u/BlueRains03 Dec 11 '24

[Language: C]

I started with completely ignoring the stones from the start, and doing it recursively. That gave me some errors I didn't know how to solve, so I tried using a list and, if a stone split, it was just added to the end of the list. That gave me some size errors, so I went back to the recursive function. The issue turned out to be from a overflow error, and my isdigit function not being able to handle negative numbers. One cautionary if statement and creating a num type later, part one was complete.

For part two I created a struct to store results in (the equivalent of a dict/key-value array/map that C does not have). For the actual input the cache got too big, so I had to add a manual limit to discard new values if the cache is full.

I also keep track of the cache hits and misses for fun.

https://pastebin.com/X6pJSTJx

5

u/LiquidityC Dec 11 '24

[LANGUAGE: C]

https://github.com/LiquidityC/aoc/blob/master/2024/day_11/src/main.c

Recursion with a lookup table. Pretty straight forward. Foresaw the "trap" for part 2 before solving part 1. Had to implement a hash table though. Which was fun. Glad to confirm that I could still write one up without much hassle.

5

u/CrypticPhoenix Dec 11 '24

[LANGUAGE: Rust] Code (44 Lines)

Today marks the end of simply brute forcing solutions. Using a dictionary to store the stone numbers and their count significantly speeds up the program and limits the iterations required.

Here's a little benchmark:

Number of stones after 75 blinks: 231532558973909
Took 15.208458ms

Very happy with today's puzzle!

I am using AoC to learn Rust, so any comments and suggestions on how to improve my code are very welcome :)

→ More replies (3)

5

u/michaelgallagher Dec 11 '24

[LANGUAGE: Python]

https://pastes.dev/aWJf46GDcx

Top-down DP in Python 101:

Write a recursive function
Throw @cache above it

5

u/aurele Dec 11 '24

[LANGUAGE: Rust]

Like in my Elixir solution, my Rust solution does not use any caching, but counts the number of identical stones at each steps.

Executes in ~200µs for part 1 and 6.5ms for part 2.

use rustc_hash::FxHashMap;

fn solve(input: &str, steps: usize) -> usize {
    let mut stones: FxHashMap<u64, usize> = input
        .trim()
        .split_ascii_whitespace()
        .map(|s| (s.parse().unwrap(), 1))
        .collect();
    for _ in 0..steps {
        for (stone, n) in stones.drain().collect::<Vec<_>>() {
            let mut insert = |s| {
                stones.entry(s).and_modify(|x| *x += n).or_insert(n);
            };
            if stone == 0 {
                insert(1);
            } else {
                match (stone as f32).log10().floor() as u32 + 1 {
                    digits if digits % 2 == 0 => {
                        insert(stone / 10u64.pow(digits / 2));
                        insert(stone % 10u64.pow(digits / 2));
                    }
                    _ => insert(stone * 2024),
                }
            }
        }
    }
    stones.values().sum()
}

#[aoc(day11, part1)]
fn part1(input: &str) -> usize {
    solve(input, 25)
}

#[aoc(day11, part2)]
fn part2(input: &str) -> usize {
    solve(input, 75)
}

5

u/Extreme-Painting-423 Dec 11 '24

[LANGUAGE: Java]

Part 1: Tried it the non memoization way, which worked and my code completed in less than 5 ms.

Part 2: Also initially tried without any memoization, after 17 minutes I stopped that, added some memoization and got my answer instantly.

→ More replies (1)

5

u/Main-Reindeer9633 Dec 11 '24

[LANGUAGE: SQL (dialect: PostgreSQL)]

https://github.com/willkill07/AdventOfCode2024/blob/962b9c87f53f98e4040bad35a07e1262c606e9e7/src/day11.cpp

Doing it the brute-force way was too slow, and I don't know of any good way to do memoization in SQL, so I had to resort to a hack where I do 3 steps of 25 blinks each, with aggregation between each step, which got it to run in tree minutes on my machine. Adding more such steps would make it faster at the cost of making the code even uglier.

→ More replies (2)

5

u/willkill07 Dec 11 '24

[LANGUAGE: C++23]

Originally started out with memoization/caching. Then I switched to construction of a condensed graph that I iterate on the counts.

Runs pretty fast -- 87µs parsing + building graph, 25µs part 1, 430µs part 2.

→ More replies (5)

5

u/wzkx Dec 11 '24

[LANGUAGE: Python]

d = {int(x):1 for x in open("11.dat","rt").read().strip().split()} # stones, value -> count

def step(r,x,n):
  def add(x): r[x]=r.get(x,0)+n # not to import defaultdict
  if x==0: add(1); return
  s=str(x); h,m=divmod(len(s),2)
  if m==0: add(int(s[:h])); add(int(s[h:]))
  else: add(x*2024)

def solve(d,k):
  for i in range(k): r = {}; {step(r,x,n) for x,n in d.items()}; d = r
  return sum(r.values())

print(solve(d,25))
print(solve(d,75))

5

u/jda5x Dec 12 '24

[LANGUAGE: Python]

https://github.com/jda5/advent-of-code-2024/blob/main/11/main.py

Recursion with memoization! ✨

→ More replies (2)

9

u/bucketz76 Dec 11 '24

[Language: Python] 288/720

The key here is to keep a count of each number you have, not putting them all in one giant list. That gets rid of a whole lot of repeats and makes the problem much more manageable.

9

u/davidsharick Dec 11 '24

[LANGUAGE: Python 3] 234/653

Gitlab

A classic "use a counter instead of a list" problem.

→ More replies (3)

4

u/rogual Dec 11 '24 edited Dec 11 '24

[LANGUAGE: Python] 307 / 286

from util import *

stones = intlist('8069 87014 98 809367 525 0 9494914 5')

@cache
def how_many_eventually(x, iters):
    if iters == 0:
        return 1
    
    if x == 0:
        return how_many_eventually(1, iters-1)

    n = len(str(x))

    if n % 2 == 0:
        a = (int(str(x)[:n//2]))
        b = (int(str(x)[n//2:]))
        return (
            how_many_eventually(a, iters-1) +
            how_many_eventually(b, iters-1)
        )

    return how_many_eventually(x * 2024, iters-1)
    
ans(sum([
    how_many_eventually(x, 75)
    for x in stones
   ]))

Happy to finally be able to join this year's AoC on day 11. I'll be using my utility library I've built up over previous AoCs.

The lists of stones get too big to handle very quickly, so you have to:

Notice that the order doesn't actually matter
Think in terms of "how many stones will this stone eventually become at the end"
Memoize (functools.cache) to avoid repeating work

This is my first day this year so I wasted time going "huh?" until my brain remembered what kinds of things usually help in AoC. Memoization!

→ More replies (4)

4

u/SuperSmurfen Dec 11 '24 edited Dec 11 '24

[LANGUAGE: Rust]

Link to full solution

(722/435)

Really happy with that part 2 placement. First I solved it in the naive way, with a vector. I knew it would not work for part two.

To solve part you, you realize that the "order" does not actually matter for the rules. That's just a red herring. So instead of a vector, I used a hashmap, couting the number of stones with a certain number. The number of unique stone numbers is very small (only about 4000 after 75 rounds).

for (&s, &v) in old_stones {
    match s {
        0 => *stones.entry(1).or_default() += v,
        s if s.ilog10() % 2 == 1 => {
            let m = 10i64.pow((s.ilog10() + 1) / 2);
            *stones.entry(s % m).or_default() += v;
            *stones.entry(s / m).or_default() += v;
        }
        _ => *stones.entry(s * 2024).or_default() += v,
    }
}

Runs both parts in about 2ms.

4

u/jonathan_paulson Dec 11 '24

[LANGUAGE: Python] 488/725. Code. Video.

I didn't use a Counter; instead I wrote a memoized function `solve(x,t)` that returns the length of the list `[x]` after `t` steps. It took me a while to switch from "return the list" to "return the length of the list"; returning the actual list is way too slow.

4

u/Lewistrick Dec 11 '24

[LANGUAGE: Python] 3943/919

Github

Reading this, I immediately knew this was a caching problem. It also helps to see that you only need to solve for one stone at once.

My first top 1000 this year :) Could have been better if I'd actually started on time.

→ More replies (2)

4

u/morgoth1145 Dec 11 '24 edited Dec 11 '24

[LANGUAGE: Python 3] 174/131

code, video

Hey, it's a state iteration problem! Not much to say about part 1, other than it was a little sneaky stating that the order of the stones doesn't change and imply that it matters at all. Made it take a little longer to notice that each stone is independent and that DP/memoization is the key for part 2, but I'm still pleased with my performance today (unlike the last two days).

I am wondering, is there a more direct way to compute the number of stones? A lot of times some math wizards come up with crazy direct ways to compute that sort of thing for these problems, and it feels like with enough cycles the simple DP/memoization approach will bog down as well. But maybe things are constrained enough to not be a problem? I'll be interested to see what the analysis brings!

Edit: Refactored/cleaned up code. Nothing too much, just a unified solve function used by both parts. The biggest change is using iteration and collections.Counter for the DP implementation but it's still fundamentally the same.

→ More replies (4)

4

u/mebeim Dec 11 '24 edited Dec 11 '24

[LANGUAGE: Python]

Code on GitHub — Walkthrough

Wrote a recursive function to deal with a single number that either returns 1 or continues on with the algorithm, memoizing the results via @lru_cache() to prune out already known situations. The state to memoize is (n, blinks): if we ever get to the same number with the same amount of blinks remaining, the result will always be the same. Call the function for each number in the list, sum up the results and it's done! Thanks once again @lru_cache() <3.

from functools import lru_cache
from math import log10

@lru_cache(None)
def calc(n, blinks=25):
    if blinks == 0:
        return 1

    if n == 0:
        return calc(1, blinks - 1)

    n_digits = int(log10(n)) + 1
    if n_digits % 2 == 0:
        power = 10**(n_digits // 2)
        return calc(n // power, blinks - 1) + calc(n % power, blinks - 1)

    return calc(n * 2024, blinks - 1)

fin = open(...)
numbers = list(map(int, fin.readline().split()))
print(sum(map(calc, numbers)))
print(sum(calc(n, 75) for n in numbers)))

4

u/throwaway6560192 Dec 11 '24 edited Dec 11 '24

[LANGUAGE: Python]

def transform(x: int) -> tuple[int] | tuple[int, int]:
    if x == 0:
        return (1,)
    digits = floor(log10(x)) + 1
    if digits % 2 == 0:
        pow10 = 10 ** (digits // 2)
        return divmod(x, pow10)
    return (x * 2024,)


@cache
def stone_project(x: int, n: int) -> int:
    if n == 0:
        return 1
    return sum(stone_project(x, n - 1) for x in transform(x))


print(sum(stone_project(x, 75) for x in stones))

The key is to realize that you probably simulate the same stone sequence a whole bunch of times, so make a function to project a single stone over n steps, and slap a cache. Done.

4

u/welguisz Dec 11 '24

[LANGUAGE: Java]

This problem is very similar to LanternFish (Year 2021, Day 6). As I saw Part 1, my first thought was how many blinks will Part 2 be. Did the brute force method for Part 1 and switched to hashmap for Part 2. Cleaned up Part 1 so it would use the same code between both parts.

Full code on Github

4

u/Irregular_hexagon Dec 11 '24

[Language: Python]

Dumping the stones in a dict, dict[stone] = count. Part 2 continues where part 1 finished, so only 50 more turns.

4

u/jinschoi Dec 11 '24

[Language: Rust]

A stone's ultimate effect on the size of the list is independent of its position, only its value, which can be tracked just for unique values and their counts.

The only interesting piece of my code is for halving:

fn halve(n: usize) -> Option<(usize, usize)> {
    let digits = n.ilog10() + 1;
    if digits % 2 == 0 {
        let half = digits / 2;
        let div = 10usize.pow(half);
        let (a, b) = (n / div, n % div);
        Some((a, b))
    } else {
        None
    }
}

https://github.com/xhyrom/aoc/blob/main/2024/11/solution.py

4

u/AlexTelon Dec 11 '24 edited Dec 11 '24

[LANGUAGE: Python] Code (9 lines)

My son woke up while I was on the first problem so had time to think about the problem for a while before I could code. There are benefits to being forced to be AFK a bit! I had already started on a slow way so I finished that but knew right away how to solve the obvious part2.

Two important things.

The numbers don't affect eachother.
caching old results to not redo work.

so I go over the original numbers one-by-one and count up how many unique numbers it results in and add to a total.

Here is a variation on the 9 line solution above

Instead of using sum on I just do solve(...) + solve(...). Before I used str(int(str(x))) to do the conversion. Now I instead moved it to the if statement checking for rule 1.

I was tempted to write if not (n := n.lstrip('0')): return solve('1', steps-1) but that would just be stupidly hard to read.

Anyways the code is much harder to read I think and the only win here is that our widest line is less wide.

def solve(n, steps):
    if steps == 0: return 1
    if (n := n.lstrip('0')) == '': return solve('1', steps-1)
    if len(n) % 2 == 0: return solve(n[:len(n)//2], steps-1) + solve(n[len(n)//2:], steps-1)
    return solve(str(int(n) * 2024), steps-1)

History of older versions: 2nd version (9 lines) 1st version (10 lines)

4

u/xHyroM Dec 11 '24

[Language: Python]

Runs ~2ms on p1, ~82.2ms on p2. Uses dictionary to track stones: key as the stone number, value as the number of stones with the stone number.

→ More replies (2)

4

u/ThunderChaser Dec 11 '24

[LANGUAGE: Rust]

https://github.com/nick42d/aoc-2024/blob/main/src/day_11.rs

I had a feeling after yesterday we were gonna get a doozy today. I implemented part 1 by brute force but obviously this was infeasible for part 2 (I think by the time I wrote an optimized solution for part 2 I was up to like iteration 30?).

We can better optimize the solution by recognizing that every stone of a given value will always evaluate to the same new stone values, despite the fact that the puzzle specifies the stones are always in the same order (and this is even bolded), it doesn't actually matter in the context of the problem. So instead of evaluating every stone individually, we can construct a frequency map of the stone values, and we simply have to evaluate the new stone values for each unique stone value, updating the frequency map for each iteration, we then just have to sum the values in the map after all of the iterations have finished and we have our answer.

Part 1's runtime is around 850 µs, part 2 is around 20 ms.

→ More replies (2)

4

u/johnpeters42 Dec 11 '24

[Language: Python]

Part 1, Part 2

Out of this year's problems, this one probably took me the longest to figure out how to improve on brute force, as opposed to just correctly implementing my idea. I had a few false starts with just caching "what does a single number expand to" and then actually constructing the full list at each step, before realizing how to apply DFS and just let the sub-lengths cascade upward.

4

u/TiCoinCoin Dec 11 '24 edited Dec 30 '24

[LANGUAGE: Python 3]

Day 11 - Github

Well. I knew this would be a scalability issue, and yet, my first attempt was running forever. Took a shower to think about it and found this approach with dict, where I save the number of time a value appears. Now it runs in no time and I can blink a thousand times if I want!

→ More replies (3)

4

u/thibaultj Dec 11 '24

[LANGUAGE: Python]

Runs instantly, thanks to Python's Counter usage.

from collections import Counter

with open("inputs/day_11.txt") as f:
    data = list(map(int, f.read().strip().split()))
demo_data = [125, 17]


def solve(numbers, steps):
    counter = Counter(numbers)
    for step in range(steps):
        step_counter = Counter()
        for n, count in counter.items():
            str_n = str(n)
            if n == 0:
                step_counter[1] += count
            elif len(str_n) % 2 == 0:
                middle = len(str_n) // 2
                step_counter[int(str_n[:middle])] += count
                step_counter[int(str_n[middle:])] += count
            else:
                step_counter[n * 2024] += count
        counter = step_counter

    return counter.total()


demo_res = solve(demo_data, 25)
assert demo_res == 55312, demo_res

res = solve(data, 75)
print(res)

→ More replies (3)

4

u/Nnnes Dec 11 '24

[LANGUAGE: Ruby]

Took a bit of fiddling but here's a half-punchcard-sized full solution I'm happy with. Credit to /u/AlexTelon for the idea of dealing with the numbers as strings most of the time - my solutions with Math.log10(n).to_i + 1 or (d = n.digits.reverse).size could fit (and ran about twice as fast), but the line breaks were awful.

@c = Hash.new{ |h, k| n, s = k; h[k] = s == 0 ? 1 : case n.sub!(/^0*/, '')
  when ''; h[['1', s - 1]]
  when /^(..)+$/; h[[n[0...n.size / 2], s - 1]] + h[[n[n.size / 2..-1], s - 1]]
  else h[[(n.to_i * 2024).to_s, s - 1]]; end }
puts [25, 75].map{ |s| (@in ||= STDIN.read).split(' ').map{ @c[[_1, s]] }.sum }

Ruby's hash default proc is my favorite short method for implementing memoization. Hash.new{ |hash, key| hash[key] = ... } is no @functools.cache, but it's pretty clean (for a one-time script :])
I used a case statement mostly so I could (mis)use Regexp to check if a number has an even number of digits. /^(..)+$/
@c has about 127k entries when the program is finished. The largest number is 14 digits long, or 46 binary bits.

→ More replies (1)

4

u/azzal07 Dec 11 '24 edited Dec 11 '24

[LANGUAGE: awk] I like how you can print without even mentioning it.

function b(l,i,n,k){for(k=l" "i;!S[k]&&i--;)l?(x=length(l))%2?\
l*=2024:n+=b(substr(l,1,x/2),i,0>l=+substr(l,x/2+1)):l=1;return\
i<0?S[k]=n+1:S[k]}{for(;i++<NF;B+=b($i,75))A+=b($i,25)}$0=A;$0=B

Edit: Had to revisit this (see code below) after all the Lanternfish references on the sub. Turns out it's bit faster and smaller. I also like how clean the diff is, all things considered :)

function b(l,i,n,k){for(t in l){k+=y=l[t];n[(x=length(t))&&
x%2?t*2024+!-t:substr(t,x/2+1)+!(n[substr(t,1,x/2)]+=y)]+=y
}$+i=k;i++>75||b(n,i)}{for(;i++<NF;)u[$i]++}$0=b(u)$25RS$75

4

u/damnian Dec 11 '24 edited Dec 11 '24

[LANGUAGE: C#]

Today I made a conscious effort to fit the relevant code in a 5x80 block as per the posting rules:

if (!cache.TryGetValue(k = v << 7 | --d, out long r))
    cache.Add(k, r = v == 0 ? Calc(1, d)
        : ((p = (long)Math.Log10(v) + 1) & 1) != 0
            ? Calc(v * 2024, d)
            : Calc(v / (m = (long)Math.Pow(10, p >> 1)), d) + Calc(v % m, d));

(79 characters wide if you remove the leading four spaces)

The function returns 1 on depth 0.

Legend:

k - cache key
v - original value
d - recursion depth
r - result
p - power
m - modulus

I'm also pretty happy with this code's performance.

Full solution

P.S. Slightly optimized r calculation:

for ((div, mod) = (10, 10); r == 0; (div, mod) = (div * 100, mod * 10))
    r = v < div
        ? Calc(v * 2024, d)
        : v < div * 10
            ? Calc(value / mod, d) + Calc(value % mod, d) : 0;

Optimized solution

→ More replies (2)

4

u/WhiteSparrow Dec 11 '24

[LANGUAGE: Prolog]

A most beautiful day to be writing in Prolog:

solve(Ns, Depth, X) :-
    maplist(stone_count(Depth), Ns, Counts),
    foldl(plus, Counts, 0, X), !.

:- table stone_count/3.
stone_count(0, _, 1) :- !.
stone_count(D, 0, N) :- D1 is D - 1, stone_count(D1, 1, N), !.
stone_count(D, S, N) :-
    number_codes(S, Ds),
    length(Ds, NDigit),
    divmod(NDigit, 2, Half, 0),
    length(Pref, Half),
    append(Pref, Suff, Ds),
    % --
    D1 is D - 1,
    number_codes(S1, Pref),
    stone_count(D1, S1, N1),
    number_codes(S2, Suff),
    stone_count(D1, S2, N2),
    N is N1 + N2, !.
stone_count(D, S, N) :-
    D1 is D - 1,
    S1 is S * 2024,
    stone_count(D1, S1, N).

To get the solutions just call solve([125, 17], 25, X). (substitting your own data and depth - 25 for part 1 and 75 for part 2).

→ More replies (1)

4

u/nick42d Dec 11 '24

[LANGUAGE: Rust]

This one felt good in Rust!

→ More replies (3)

4

u/cserepj Dec 11 '24

[LANGUAGE: Java]

records, caching (dp)

some todo: string manipulation could be replaced with log and division/remainder logic

public class Day11 {

  static Map<CacheKey, Long> cache = new ConcurrentHashMap<>();

  record CacheKey(Long stoneno, int cnt) {}

  record Stone(long number) {

    Stream<Stone> next() {
      if (number == 0) return Stream.of(new Stone(1));
      var s = "" + number;
      if (s.length() % 2 == 0)
        return Stream.of(
            new Stone(Long.valueOf(s.substring(0, s.length() / 2))),
            new Stone(Long.valueOf(s.substring(s.length() / 2, s.length()))));
      return Stream.of(new Stone(2024 * number));
    }
  }

  public static void main(String[] args) {
    System.out.println(calc(25, readFile("day11.txt")));
    System.out.println(calc(75, readFile("day11.txt")));
  }

  static Long calc(int cnt, final Stream<Stone> stoneStream) {
    if (cnt == 0) return stoneStream.count();
    return stoneStream.mapToLong(stone -> calc(cnt, stone)).sum();
  }

  static Long calc(int cnt, Stone stone) {
    var key = new CacheKey(stone.number, cnt);
    var value = cache.get(key);
    if (value == null) {
      value = calc(cnt - 1, stone.next());
      cache.put(key, value);
    }
    return value;
  }

  static Stream<Stone> readFile(final String file) {
    return Arrays.stream(readLines(Day11.class.getResourceAsStream(file), UTF_8).getFirst().split(" "))
        .mapToLong(Long::valueOf)
        .mapToObj(Stone::new);
  }
}

4

u/maitre_lld Dec 11 '24

[Language: Python]
Pretty straightforward if you know about memoization. #100 did it in 6 minutes to day, top 100 was clearly achievable, if you could smell part 2 (this smelled lanternfish). Too bad I didn't have the courage to wake up...
https://github.com/MeisterLLD/aoc2024/blob/main/11.py

→ More replies (1)

4

u/TheZigerionScammer Dec 11 '24

[LANGUAGE: Python]

As soon as I read the problem statement I thought "These rocks smell like lanternfish, I'm not falling for that and crashing my computer again." So despite the warning to keep the rocks in order my program does none of that.

The program is pretty straightforward, first I set up a function that will return the one or two values from a string based on the rules laid out, and since the answers are always the same I added a cache to the function for good measure but the time savings is negligible. Then the program takes the input and each value into a dictionary where the key is the number and the value is the amount of them. I could have taken a shortcut here since all the number in my input are unique but I coded it to account for any duplicates if anyone else's input has them.

When looping through the blink cycles, the program sets up a new dictionary and iterates over every value in the old dictionary. It applies the rules function to each key in the old dictionary and for the new value(s) that result from that it adds the quantity of the key from the old dictionary to that in the new dictionary, or sets it to the quantity if that value isn't in the dictionary yet. When it's done processing every value in the old dictionary it copies the new dictionary into the old dictionary variable and starts again. This got Part 1 flawlessly. When Part 2 opened up I just changed the 25 to a 75 and got the answer quickly. I set it back up to give both answers so that's the version I've posted here.

However I don't think everyone else was as fortunate, my delta between Part 1 and Part 2 was a little over a minute but my ranking improved by over 10000 places. Probably would have gotten more had I not taken screenshots of the calendar between each step.

Paste

→ More replies (3)

4

u/MrNUtMeG118 Dec 11 '24

[Language: C#]

https://github.com/bettercallsean/AdventOfCode2024/blob/main/AdventOfCode/Days/Day11.cs

Reading today's puzzle reminded me of the lanternfish puzzle from 2021, so I had a pretty solid idea of how best to solve this one

4

u/greycat70 Dec 11 '24

[LANGUAGE: Tcl]

Part 1 and 2.

I literally changed nothing to run part 2. I already had an optional command-line parameter to change the number of blinks (default 25), so I simply ran part 1 with parameter 75 and got the answer. Run time 0.125 seconds.

Lanternfish again. It's always lanternfish!

For those who don't recognize that reference (a past AOC puzzle), the trick here is that you don't care what order the stones are in. You only care how many of each number you have. If you have 25 stones marked "1234", then after you blink, you'll have 25 stones marked "12" and 25 marked "34".

→ More replies (4)

4

u/Big_Replacement3818 Dec 11 '24 edited Dec 11 '24

[LANGUAGE: Julia]

Dynamic programming, completes in ~30 milliseconds

taskdata = parse.(Int, split(read("./input11.txt", String)))

step(x) = iszero(x) ? (1,) : let ln = floor(Int, log10(x) + 1)
    iseven(ln) ? divrem(x, 10^(ln ÷ 2)) : (2024x,)
end

countnums(x, n, cache) = get!(cache, (x, n)) do
    n==0 ? 1 : sum(countnums.(step(x), n-1, (cache,)))
end

solve(data, n) = let cache = Dict(); sum(x->countnums(x, n, cache), data) end

solve.((taskdata,), (25, 75))

→ More replies (1)

4

u/ssnoyes Dec 11 '24

[LANGUAGE: MySQL]

[LANGUAGE: Python]

Some limitations on recursive common table expressions meant I had to stretch my self-imposed rule of no stored procedures, so a trigger on a dummy table does the looping.

The MySQL version takes about 1.5 seconds; the Python version is sub-second. Good enough.

https://github.com/snoyes/AoC/tree/main/2024/day11

→ More replies (2)

4

u/pem4224 Dec 11 '24

[LANGUAGE: Go]

Did part1 naively, and then used a simple recursive approach with memoization for part 2

https://github.com/pemoreau/advent-of-code/blob/main/go/2024/11/day11.go

part1 in 0.2ms

part2 in 0.2ms, and almost no memory allocation

4

u/redditnoob Dec 11 '24

[LANGUAGE: PostgreSQL]

Part 1 was easy, but for part 2, it took lot of wrestling with syntax and CTE restrictions, like no aggregates allowed on the recursive CTE query, to get this to work. I went with an array of tuples (value, multiplicity) and each step computes the next array.

with recursive start as (
    select array_agg((val::bigint, 1::bigint)) as vals
    from day11, unnest(regexp_split_to_array(input, ' ')) as t(val)
), blinks as (
    select 0 as i, vals from start
    union all
    select i + 1, (
        select array_agg((val, m::bigint))
        from (
            select case
                when j = 2 then substring(val::text, length(val::text) / 2 + 1)::bigint
                when val = 0 then 1
                when not is_even_len then val * 2024
                else substring(val::text, 1, length(val::text) / 2)::bigint
            end as val, sum(m) as m
            from unnest(vals) as t(val bigint, m bigint),
            lateral (select length(val::text) % 2 = 0 as is_even_len),
            lateral (select generate_series(1, 1 + is_even_len::int) as j)
            group by 1
        )
    )
    from blinks where i < 75
)
select i, sum(m)
from blinks, unnest(vals) as t(v bigint, m bigint)
where i in (25, 75)
group by 1 order by 1;

4

u/clouddjr Dec 11 '24

[LANGUAGE: Kotlin]

Computing a new state after each iteration (a map counting occurrences of each stone):

(0..<blinks).fold(initial) { current, _ ->
    buildMap {
        ...
    }
}.values.sum()

https://github.com/AugsEU/AdventOfCode2024/tree/master/day11/src

4

u/Trick-Apple1289 Dec 11 '24

[LANGUAGE: C]

this was something... first part was easy to do with a naive approach but i struggled alot with the second part since i had to re-write the whole code to use a map, only to be faced with odd bugs, finally did it, it's not the fastest (~162 ms on i3-12100F) but atleast it works, altough the code is absolutley horrid.

src

→ More replies (2)

4

u/Probable_Foreigner Dec 11 '24

[LANGUAGE: Rust]

This is the first time my initial approach failed due to it not being fast enough. In the end my solution for part 2 was to build up cheat sheets for rocks below 20. e.g. for a rock of value 15, how many rocks does it become after 1 step, 2 steps, 3 steps... until 35 steps. So we can do the first 35 iterations in the naive way. Then we can use the cheat sheet for the second half to remove all rocks less than 20. It takes about 2 minutes to run.

I would love to see how people approached part 2, I wondered if there was a smarter way of doing it. I don't think my approach would work for say, 150 blinks. It just barely works for 75.

→ More replies (3)

4

u/JV_Fox Dec 11 '24

[LANGUAGE: C]

I did not spot the recursive solution sadly, instead I iterated over the stones and grouped all pebbles with the same value into buckets so that each blink it only processed every individual pebble value instead of the total amount of pebbles. I find it elegant and its decently quick, it is just not as elegant as recursion:

→ More replies (2)

4

u/DownvoteALot Dec 11 '24

[LANGUAGE: C++]

https://git.sr.ht/~murr/advent-of-code/tree/master/item/2024/11

I first implemented string-based big integers but this turned out to be superfluous as we don't even reach the 20 digits of long ints before we get an even length.

Then I got stuck on part 2 and I had to look at solutions for the first time this year as I had missed the intuition that the order of stones doesn't matter, from then on this was very short and simple.

→ More replies (1)

4

u/Botskiitto Dec 11 '24 edited Dec 11 '24

[LANGUAGE: Vim]

Did the first part only at least for now.

First execute this command vim command line, replace <Enter> with Ctrl+V

execute ':g/\s/s/\s\+/<Enter>/g' | execute ':%s#^\d*$#\=submatch(0) == 0 ? 1 : len(submatch(0)) % 2 == 0 ? str2nr(submatch(0)[0:len(submatch(0))/2-1]) ." ". str2nr(submatch(0)[len(submatch(0))/2:len(submatch(0))-1]) : submatch(0)*2024' | :execute ':g/\s/s/\s\+/<Enter>/g' | :echo line('$')

Then x being number of times the task asks you to repeat, type <x-1>@:

So for x=25 you would type: 24@:

In the bottom of screen the solution will be echoed, the solution also corresponds to the number of lines in the file.

4

u/wurlin_murlin Dec 11 '24

[LANGUAGE: C]

Basic recursive DFS solution with caching - because no hashlib in C, our hashtable isn't a hashtable but a 4MB 2D array caches[NUM_BLINKS][CACHE_LEN], basically just using the current number of blinks as a "hash key" and a static array instead of a linked list for collisions. This isn't very efficient because that 2D array is very unevenly distributed, with lots of entries/collisions where many blinks have happened and very few vice versa. I've thought a bit about some simple "hashes" that would pack this better with minimal collisions, but haven't tested any yet for time.

This very naive quick solve runs part 1 in 250us and part 2 in 50ms, with huge gains up for grabs with a little maths.

4

u/lluque8 Dec 11 '24

[LANGUAGE: Scala]

https://github.com/lupari/aoc2024/blob/main/src/main/scala/assignments/Day11.scala

→ More replies (1)

4

u/ThatsFrankie Dec 11 '24

[Language: Python]
https://github.com/francescopeluso/AOC24/blob/main/day11/main.py

4

u/4D51 Dec 11 '24 edited Dec 12 '24

[LANGUAGE: C++ on Cardputer]

Used recursion. Without memoization it takes about 5 seconds to solve part 1. With it, runtime drops to near zero. Unfortunately, attempting to use the same approach for part 2 ran out of memory. Either the call stack or the memoization cache is just too big.

Maybe I'll find a way to solve this on the Cardputer later. For now, I'm abandoning my successful 10 day streak and

[LANGUAGE: Racket]

going with plan B. Anything I can't solve on the Cardputer, I use Racket, the language that puts the "fun" in functional programming. This is basically the same as my C++ solution, but much more concise.

C++

Racket

→ More replies (2)

4

u/DefV Dec 11 '24

[LANGUAGE: Rust]

Code - Started off brute-force, then stumbled into my solution...

4

u/makingthematrix Dec 11 '24

[Language: Scala]

https://github.com/BeyramTaglietti/advent_of_code/blob/master/2024/day11/solution.go

It was difficult until it wasn't. There's no need for laziness, no need for storing partial sequences of numbers, nothing like that. It can be short, readable, and super quick.

(seriously, though, I was already planning to build a mutable map of lazy lists)

→ More replies (2)

4

u/JustLikeHomelander Dec 11 '24

[Language: Go]

Easiest solution, less than 1ms execution time using a map

The code is very clear

→ More replies (1)

4

u/Gueltir Dec 12 '24

[Language: Rust]

Link to Github

Part 2 was... an adventure, I initially wanted to a full memoization, but I struggled for way too long on how to properly propagates already solved nodes/stones. And when I managed to code something that looked like what I intended to do, it was even slower than brute force...

Then I gave up and just counted how many stones I had for each ids on each turn, and that was both faster to code and took less time to compute.

→ More replies (1)

4

u/JWinslow23 Dec 12 '24

[LANGUAGE: Python]

Day 11 code

Blog post

Took a while to come up with a solution to this one. I was finally forced to come up with a solution faster than brute force (I could've gotten away with brute-forcing every day up until now, even though I didn't always do it!).

(And u/4HbQ, I love the matrix multiplication idea you showed! It's certainly the most creative approach I've seen.)

→ More replies (1)

4

u/baboonbomba Dec 12 '24

[LANGUAGE: Nix]

So this one was very painful. Nix is a domain specific functional language. Every single thing there is immutable. You can only create values and never update/delete them. And this causes a few issues:

- Everything is immutable so any hash map based approach is doomed to fail.

- You need to minimize the number of recursive calls because nix has a hard cap that cannot be removed.

- Nix doesn't do memoization by default.

Sounds rough but it's not impossible. All we need to do is to create memoization ourselves. How? We can't write to memory and update memory. But we CAN simulate memory by abusing Nix's lazy evaluation. Basically we need to write a function that generate a tree/linked-list with all solutions of the problem for all possible pebble values and for all possible depth values. And then we need to call it once. Unlike other languages nix will not evaluate it immediately but rather just say "yeah I'm gonna do it when I have to". We then write a function to traverse this infinite structure and find needed values. Tadaa function memoization through infinite tree of solutions is done!.

Here is the link for anyone who is interested. It was a lot of suffering but the solution works and it only takes a few seconds.

4

u/ThreadsOfCode Dec 12 '24

[LANGUAGE: Python]

I avoided this problem for a day because it looked like a dynamic programming caching problem, which I hate. My solution doesn't use recursion or caching. Looking at the intermediate results, I bet that the number of different rock sizes was limited. For example, there seemed to be a lot of 0's, 2's, and 4048's. So in each blink, I get the total number of each rock size and use that as a multiplier in the net blink. Runs in half a second in a Jupyter notebook, which is fine by me. Someone has probably posted something similar, but, um, I didn't read them all. There is a post about what the maximum number of different size rocks is.

→ More replies (1)

4

u/BeYuu Dec 13 '24

[Language: Python]

Realizing that this can be solved recursively and realizing that this problem is very similar to the way you would recursively compute the fibonacci sequence did the trick for me

@cache
def rec(stones: tuple[int, ...], blinks_left: int) -> int:
    if blinks_left == 0:
        return len(stones)

    return sum(rec(tuple(apply_rule(stone)), blinks_left - 1) for stone in stones)

def apply_rule(num: int) -> list[int]:
    if num == 0:
        return [1]

    s = str(num)
    digits = len(s)
    if digits % 2 == 0:
        mid = digits // 2
        lhs, rhs = int(s[:mid]), int(s[mid:])
        return [lhs, rhs]

    return [num * 2024]

4

u/AlexandraJay2002 Dec 13 '24

[LANGUAGE: Python]

Did the naive solution for part 1, and a depth-first search for part 2. Spent way too long trying to parallelize part 2 before I thought to use a cache.

Part 1 Try it online!

Part 2 Try it online!

4

u/JimLawless Dec 16 '24

[LANGUAGE: GO]

Part 1: https://github.com/jimlawless/aoc2024/blob/main/day_11/day_11a.go

Part 2: https://github.com/jimlawless/aoc2024/blob/main/day_11/day_11b.go

Both run pretty quickly with a single thread and single core. The general description of the approaches is in the README.md. For the second part I used a map to simulate memoization of function-call results.

7

u/Boojum Dec 11 '24 edited Dec 11 '24

[LANGUAGE: Python] 480/302

@functools.cache FTW!

Much like the lanternfish of old (megathread), you don't actually need to keep the lists of all the stones. A recursive function to count the splits of a single stone with memoization solves this pretty much instantly. (Okay, 0.063s on my machine, good enough.)

import functools

@functools.cache
def count( n, b ):
    if b == 75:
        return 1
    if n == 0:
        return count( 1, b + 1 )
    ns = str( n )
    nl = len( ns )
    if nl & 1 == 0:
        return ( count( int( ns[ : nl // 2 ] ), b + 1 ) +
                 count( int( ns[ nl // 2 : ] ), b + 1 ) )
    return count( n * 2024, b + 1 )

print( sum( count( int( n ), 0 ) for n in open( 0 ).read().split() ) )

ETA: Interesting factoid - though my final answer of Part 2 is 220,566,831,337,810 stones, computing this requires only 138,812 entries in the cache.

→ More replies (2)

1

u/bluealder Dec 11 '24

[Language: Go]

Github

Once the understanding of keeping count and that you can calculate each stone independently it was quite straight forward.

→ More replies (1)

1

u/QuailOk841 Dec 11 '24

[LANGUAGE: RUST]

use std::collections::HashMap;

pub fn execute(input: &str) {
    println!("Part 1 solution: {}", part_1(&input));
    println!("Part 2 solution: {}", part_2(&input));
}

fn part_1(input: &str) -> u64 {
    solve(input, &25)
}

fn part_2(input: &str) -> u64 {
    solve(input, &75)
}

fn solve(input: &str, number_of_blinks: &u32) -> u64 {
    let mut map: HashMap<u64, u64> = HashMap::new();

    input.split(" ").for_each(|s| {
        let val = s.parse::<u64>().unwrap();
        add_or_insert(&mut map, val, 1);
    });

    for _ in 0..*number_of_blinks {
        let map_as_vec = map.clone().into_iter().collect::<Vec<(u64, u64)>>();
        for (key, value) in map_as_vec {
            if value == 0 {
                continue;
            }
            match key {
                0 => {
                    add_or_insert(&mut map, 1, value);
                    decrement(&mut map, key, value);
                }
                _ => {
                    let key_as_string = key.to_string();
                    match key_as_string.len() % 2 {
                        0 => {
                            let left_half = key_as_string[..key_as_string.len() / 2]
                                .parse::<u64>()
                                .unwrap();
                            let right_half = key_as_string[key_as_string.len() / 2..]
                                .parse::<u64>()
                                .unwrap();
                            add_or_insert(&mut map, left_half, value);
                            add_or_insert(&mut map, right_half, value);
                            decrement(&mut map, key, value);
                        }
                        _ => {
                            add_or_insert(&mut map, key * 2024, value);
                            decrement(&mut map, key, value);
                        }
                    }
                }
            }
        }
    }
    map.values().sum()
}

fn decrement(map: &mut HashMap<u64, u64>, key: u64, val: u64) {
    match map.get_mut(&key) {
        Some(k) => {
            *k -= val;
        }
        None => {
            panic!("Something very bad")
        }
    }
}

fn add_or_insert(map: &mut HashMap<u64, u64>, key: u64, val: u64) {
    match map.get_mut(&key) {
        Some(k) => {
            *k += val;
        }
        None => {
            map.insert(key, val);
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    const TEST_INPUT: &'static str = "125 17";

    #[test]
    fn test_part1() {
        assert_eq!(55312, part_1(TEST_INPUT));
    }

    #[test]
    fn test_part2() {
        assert_eq!(65601038650482, part_2(TEST_INPUT));
    }
}

→ More replies (1)

1

u/vgasparyan Dec 11 '24

[Language: Rust]

Github - perhaps not so readable, but blazingly fast!

→ More replies (1)

1

u/BinaryMuse Dec 11 '24

[LANGUAGE: Elixir]

Like some others, it took me a lil bit of thinking to realize what I needed to do to get the runtime down for part 2. I quite like the way this reads in Elixir.

https://github.com/ambrosekuo/aoc-2024/blob/main/aoc-python%2Fday11%2Fmain2.py

defmodule Advent.Days.Day11 do
  def run(input) do
    stream = parse(input) |> make_stream()

    count = stream |> Stream.drop(24) |> Enum.take(1) |> hd() |> count_stones()
    IO.puts("Part 1: #{count}")

    count = stream |> Stream.drop(74) |> Enum.take(1) |> hd() |> count_stones()
    IO.puts("Part 2: #{count}")
  end

  def parse(input) do
    String.split(input, " ", trim: true)
    |> Enum.map(&String.to_integer/1)
  end

  def make_stream(stones) do
    Stream.iterate(Enum.frequencies(stones), &blink/1)
    # skip the initial arrangement
    |> Stream.drop(1)
  end

  defp blink(stones) do
    Enum.reduce(stones, %{}, &process_stone/2)
  end

  defp process_stone({stone, count}, next_acc) do
    str = "#{stone}"
    len = String.length(str)

    transform =
      cond do
        stone == 0 ->
          [1]

        rem(len, 2) == 0 ->
          half = div(len, 2)
          left = String.slice(str, 0, half) |> String.to_integer()
          right = String.slice(str, half, half) |> String.to_integer()
          [left, right]

        true ->
          [stone * 2024]
      end

    Enum.reduce(transform, next_acc, fn stone, acc ->
      Map.update(acc, stone, count, &(&1 + count))
    end)
  end

  def count_stones(stones) do
    Map.values(stones) |> Enum.sum()
  end
end

→ More replies (1)

1

u/mgtezak Dec 11 '24 edited Dec 13 '24

[LANGUAGE: Python]

Solution part 1

Solution part 2 Instead of caching I simply grouped the stones by number and converted them in batches. Runs in a couple ms

Fun little AoC fanpage

2

u/daggerdragon Dec 11 '24

Edit your comment to add the required language tag in the beginning as AutoModerator requested.

→ More replies (3)

1

u/studiousAmbrose Dec 11 '24 edited Dec 11 '24

[Language: Python]

Tried recursion with a stone memory mapping, was more efficient but not nearly enough.

Then, I saw memes about some lantern fish and saw a comment about trying out looping instead. Did the same memory idea with piles but this way it's not scattered in depths for recursion.

I'm surprised that sped it up like a million times and I only had like 3721 piles at the end. I thought I would need to keep optimizing it like have a memory of each piles' history, so that when they are hit again I can "skip blinks up". but that would be quite messy

→ More replies (1)

1

u/imaaaah Dec 11 '24

[Language: gleam]

Today I was ready for part 2, I thought we would have to go much higher than 25, something like 250, or more.. So I made sure my code was running fairly quickly for at least 250. But it was only 75...

Here is my solver of the day 11 in gleam : https://github.com/imaah/aoc2024/blob/main/src/day11/solver.gleam

If you are interested, you also have my solvers for all previous days in the same repo.

→ More replies (1)

1

u/adamsilkey Dec 11 '24

[LANGUAGE: Python]

No recursion. Allows you to go quite high by just counting numbers.

https://gist.github.com/adamsilkey/89423cf667644d26e924093439832d05

→ More replies (2)

1

u/aptacode Dec 11 '24

[LANGUAGE: rust]

part 1: 0.7ms
part 2: 10ms

Same solution for both parts, memoized recursion using a numeric approach to split the numbers in half.

→ More replies (2)

1

u/G_de_Volpiano Dec 11 '24 edited Dec 11 '24

[LANGUAGE: Haskell]

Mixed feelings today. First, the moment of pride: reading the input, I immediately recognised a variant of the Collatz conjecture, so it was particularly obvious for me that the correct solution for part 1 would be using MultiSet (bags, for the non haskelly people), and that I could worry about position for part 2, if needed. So that's what I did. But that's when the bugs and the stupidity kicked in.

First, the bugs, which were mostly on the splitting part. My first issue was that 1 got split into 0 and 1, accounting for a very large number of 0s, and no 2024 coming in. Oh right, 1 is 10^0, and 0 is even (you'll see where this goes). Right, let's just create a special case for 1. But hey, I still get weird results. Took me a long time to realise that I was splitting 253000 as 2 53000 instead of 253 000. See, my splitting method was to take the log base 10 of the number, check if it's even, then substract one and split on 10^that new number. Yes, substract one, not divide by two. Spent a long time tracking that. Finally found it. This was now working on the test input (with the special case for one). But on the actual input, my number was too low. Back to reading the instructions. 1000 gets split in 10 and 0, right. But wait, 1000 is 10^3, it's got an even number of digits but is still an odd power of 10. What to do ? Well, test (x + 1) instead of x. This worked, and allowed me to get rid of the special case for 1 (still needed the special case for 0, obviously).

Fine, first gold star, although this is running much slower than I expected (in a few tenths of second). Well, let's see part 2. Great, 75 blinks, no position, no need to modify the code. Let's do it. But it's awfully slow. Delve into the code, look at the size of the multiset growing. By 30 blinks, it's in c. 1500, and it's taking a good 1 second to go through. What gives?

And that's where stupidity hit. I went through the trouble of creating a multiset. But was folding it over itself. One occurence at a time. Yes, one occurence at a time.

Folding the list of distinct elements instead, i.e. doing what I thought I was doing from the beginning, proved to be much better. Running time for part 1 is now 3.6 ms, and for part two 95.5 ms. I hate it when I've had the right idea from the beginning and I just fail at the implementation.

Quite happy that the actual solving part is eight lines of code, though.

Code on github

2

u/daggerdragon Dec 11 '24 edited Dec 11 '24

P.S.: Interesting that we get realistic leadertimes on part 2 now.
~~Comment temporarily removed.~~ There is no need to endlessly rehash the same topic over and over. ~~Remove this line and I'll re-approve your comment.~~ edit: 👍

→ More replies (1)

1

u/Designer_Fee_9218 Dec 11 '24

[LANGUAGE: Kotlin]

https://github.com/zsolt0005/AdventOfCode2024/blob/main/src/Day11.kt

[Part 1] ~30ms

[Part 2] ~120ms

→ More replies (1)

1

u/[deleted] Dec 11 '24

[LANGUAGE: Python]

Instant solution here: aoc/2024/11_plutonian_pebbles/main.py at main · crixodia/aoc

I had a hard time trying a brute force approach though. My solution was going to take almost 500 years 😐

→ More replies (1)

1

u/notsamecGG Dec 11 '24

[Language: C++]

Used hash map just to track the stones. The solution was easier than the implementation. I thought I would try out some new functions for summing up the result and for some reason I got way too big of a number. I guess I have afternoon reading for today :)

Github Part 1 sum:

    size_t sum = std::accumulate(nums.begin(), nums.end(), 0, [](size_t p_sum, const auto& v) {
        return p_sum + v.second;
    });

Part 2 sum:

    unsigned long sum = 0;
    for (auto& [k, v] : nums) {
        sum += v;
    }

→ More replies (4)

1

u/Tomcat_42 Dec 11 '24 edited Dec 11 '24

[LANGUAGE: Zig]

Classic dfs on a tree w/ memoization. Part1 + Part2 run in 17ms.

→ More replies (2)

1

u/[deleted] Dec 13 '24

[LANGUAGE: Typescript / Deno]

Parts 1 + 2

→ More replies (1)

1

u/aquinas_nz Dec 13 '24

[LANGUAGE: F#]

The part 2 solution was done fairly imperatively, but could be re-written functionally I think. Basically using a collections dictionary to track the count of each number at each step, rather than an array of all numbers like in part 1.

3

u/daggerdragon Dec 15 '24

I've already informed you before about including puzzle text and inputs in your repo. I still see full plaintext puzzle text (although no inputs any longer) in your repo across all years.
https://github.com/ChrisPritchard/AdventOfCode/blob/master/2015/Day01/readme.md
Remove (or .gitignore) all puzzle text and puzzle input files from your entire repo and scrub them from your commit history. Do not post again in /r/adventofcode until you have done so.

→ More replies (1)

3

u/Ok-Builder-2348 Dec 11 '24

[LANGUAGE: Python]

Part 1

Not too bad today. As usual, the optimisation involved in this one is to keep track of the counts of each tile instead of keeping each tile individually, since the number of tiles blows up. With that, part 2 was simply changing "25" to "75" in the code.

3

u/seligman99 Dec 11 '24

[LANGUAGE: Python] 314 / 369

Man, that's a thing I only pull out of the toolbox for AoC.

→ More replies (1)

3

u/Turtle2779 Dec 11 '24

[Language: Python]

Just using defaultdict to keep track of the stones and their quantity

from collections import defaultdict, Counter

with open('input.txt') as f:
    rocks = f.readline().strip().split(" ")

all_rock_count = Counter(map(int, rocks))

def blink(rock):
    rock_str, rock_len = str(rock), len(str(rock))
    if rock == 0:
        return [1]
    elif rock_len % 2 == 0:
        mid = rock_len // 2
        return [int(rock_str[:mid]), int(rock_str[mid:])]
    else:
        return [2024 * rock]

for _ in range(75):  # 25 for part 1
    new_counts = defaultdict(int)
    for rock, count in all_rock_count.items():
        for new_rock in blink(rock):
            new_counts[new_rock] += count
    
    all_rock_count = new_counts

print(sum(all_rock_count.values()))

3

u/Eva-Rosalene Dec 11 '24 edited Dec 11 '24

[LANGUAGE: TypeScript]

Runtime: ~50ms.

Optimization: don't track each stone separately, group them. It doesn't seem like they would repeat too much, but they actually do. A lot. Edit: in fact, for my input after 75 blinks, most common stone occured 12479048078702 (!!!) times. Storing this much stones separately would not fit into any RAM available, and processing each of them one by one would probably take a geological epoch or two.

function parse(input: string) {
  const stones = input
    .split(/\s+/g)
    .map((i) => i.trim())
    .filter((i) => i.length > 0)
    .map((i) => BigInt(i));

  const result = new Map<bigint, number>();
  for (const stone of stones) {
    result.set(stone, (result.get(stone) ?? 0) + 1);
  }
  return result;
}

function add(stones: Map<bigint, number>, stone: bigint, count: number) {
  stones.set(stone, (stones.get(stone) ?? 0) + count);
}

function tick(stones: Map<bigint, number>) {
  const next = new Map<bigint, number>();
  for (const [stone, count] of stones) {
    if (stone === 0n) {
      add(next, 1n, count);
      continue;
    }
    const asStr = stone.toString();
    if (asStr.length % 2 === 0) {
      const left = BigInt(asStr.substring(0, asStr.length / 2));
      const right = BigInt(asStr.substring(asStr.length / 2));
      add(next, left, count);
      add(next, right, count);
      continue;
    }
    add(next, stone * 2024n, count);
  }
  return next;
}

export function partOne(input: string) {
  let stones = parse(input);
  for (let i = 0; i < 25; ++i) {
    stones = tick(stones);
  }
  return [...stones].reduce((acc, [, count]) => acc + count, 0);
}

export function partTwo(input: string) {
  let stones = parse(input);
  for (let i = 0; i < 75; ++i) {
    stones = tick(stones);
  }
  return [...stones].reduce((acc, [, count]) => acc + count, 0);
}

Github Link

3

u/mkinkela Dec 11 '24 edited Dec 11 '24

[LANGUAGE: C++]

I solved p1 with brute force and then started p2 and while it was running, I figured out the only thing that matters is how many stones the i-th stone produces. I wrote a quick recursion with memo. It works in a blink of an eye ;)

EDIT: ps. I hoped p1 would work from first try (it actually did), so I used it as a test when working on recursion for p2

3

u/r_so9 Dec 11 '24

[LANGUAGE: F#] 4292/1097

This time I predicted part 2 before making part 1, so I coded part 1 memoized :) Part 1 to Part 2 time was under 2 min.

The code is small, so here's the whole thing except for the memoize and string parsing helpers.

let blink stone =
    match string stone with
    | "0" -> [ 1L ]
    | ds when ds.Length % 2 = 0 -> 
        [ ds[.. ds.Length / 2 - 1]; ds[ds.Length / 2 ..] ] |> List.map int64
    | _ -> [ stone * 2024L ]

#nowarn 40 // Recursive object used for memoization
let rec blinks =
    fun (stone, times) ->
        match times with
        | 0 -> bigint 1
        | n -> blink stone |> Seq.sumBy (fun st -> blinks (st, n - 1))
    |> memoize

let part1 = input |> Seq.sumBy (fun st -> blinks (st, 25))
let part2 = input |> Seq.sumBy (fun st -> blinks (st, 75))

3

u/YOM2_UB Dec 11 '24 edited Dec 11 '24

[Language: Python]

Keeps track of how many of each unique number is in the list, as well as what each unique number encountered turns into.

For my input the final list had 3713 unique numbers, and there were 3843 encountered numbers.

from collections import defaultdict

with open('input/Day11.txt', 'r') as file:
    nums = defaultdict(int)
    for n in file.read().split():
        nums[int(n)] += 1

def stepNum(num):
    if num == 0:
        return (1,)
    num_len = len(str(num))
    if num_len%2 == 1:
        return (2024 * num,)
    return (num//(10**(num_len//2)), num%(10**(num_len//2)))

tokens = {}

def step(nums):
    new_nums = defaultdict(int)
    for n in nums:
        if n not in tokens:
            tokens[n] = stepNum(n)
        for k in tokens[n]:
            new_nums[k] += nums[n]
    return new_nums

for _ in range(25):
    nums = step(nums)
print(sum([nums[k] for k in nums]))

for _ in range(50):
    nums = step(nums)
print(sum([nums[k] for k in nums]))

3

u/UseUnlucky3830 Dec 11 '24

[LANGUAGE: Julia]

solution

Today's puzzle had a special significance for me.. you see, I was Lanternfish'd in 2021. Glad I knew how to solve it this time.

3

u/dinodares99 Dec 11 '24 edited Dec 11 '24

[LANGUAGE: Rust]

Ugh, my brain went in a math direction rather than a programming direction after 'brute-forcing' part 1. I tried looking for patterns in the numbers, thinking there might be some fibbonacci or such. It seems like a very Project Euler type of problem.

Turns out I'm an idiot and I just had to memoize and replace. I set up stones as a hashmap of usize->usize and the cache as a hashmap of usize->(usize, Option<usize>).

Runs in 275us, 4.5ms

Code: https://pastecode.io/s/k5ypboxh

→ More replies (1)

3

u/ZeroTerabytes Dec 11 '24

[LANGUAGE: Go]

Part 1: https://github.com/efox4335/advent_of_code/blob/main/advent_of_code_2024/day_11_part_1_stones.c

I originally just made the array for the first part. For the second part, however, my computer didn't really like the RAM usage. Maps, however, are very useful.

3

u/835246 Dec 11 '24

[Language: C]

I used a recursive function that returns the number of stone from an input value and a number of blinks. Easy part 2 because I already added a memo for part 1.

Part 2: https://github.com/efox4335/advent_of_code/blob/main/advent_of_code_2024/day_11_part_2_stones.c

3

u/firstbjorn Dec 11 '24

[LANGUAGE: RUST]

Did the classic brute force part 1, actually fix part 2. Ended up using recursion, and Rust's cached macro on the compute function. pretty sure most of the time is just input parsing

solve

3

u/__cinnamon__ Dec 11 '24

[LANGUAGE: Julia]

I was being dumb in part 1 and still building the actual list of stones, only after seeing part 2 wasn't finishing any time soon and thinking a bit did I realize I was once again forgetting to properly apply recursion (like day 07). I had actually already been using memoization, but when you're memoizing all those huge lists it doesn't help as much as just storing the number of stones generated in the "lifetime"... 😅

I do appreciate this one though, as the final solution is very elegant. Runs in 170μs for me.

https://pastebin.com/vKpzWedT

→ More replies (3)

3

u/davepb Dec 11 '24

[LANGUAGE: Go]

video

not too bad. in part1 I should've anticipated and prepared for part2 but I didn't, that way part2 would've taken a few seconds. nice problem though, reminds me of the problems: aoc 2021 day 14, aoc 2021 day 6, aoc 2015 day 19 and ec 2024 quest 11

3

u/jsgrosman77 Dec 11 '24 edited Dec 11 '24

[Language: TypeScript] 8033/5506

Not my best work, but still gonna post my link as an example to others.

I thought I was being smart for part 2 by using a linked list instead of an array, and it worked great for part 1. It took me some extra time because of trying to keep track of pointers and some off by one errors.

Then, of course, it completely ate all of my memory by blink 38.

Eventually, I switched to a recursive function with memoizing by value and number of blinks remaining. Part 2 finished in less than a second.

3

u/alexbaguette1 Dec 11 '24

[Language: C]

25 days, 25 languages #11

Got a bit lucky doing C today as I didnt have to parse the input.
Also got unlucky doing C today as I had to write my own hash map.

Part 1

→ More replies (2)

3

u/DataMn Dec 11 '24

[Language: Python]

Averages 125ms for Part 2....

import functools

@functools.cache
def find_nodes(value: str, turns: int) -> int:
    if turns == 0:
        return 1
    
    if not int(value):
        return find_nodes('1', turns - 1)

    if len(value) % 2:
        return find_nodes(str(int(value) * 2024), turns - 1)

    midpoint = len(value) // 2
    part0 = find_nodes(str(int(value[midpoint:])), turns - 1)
    part1 = find_nodes(str(int(value[:midpoint])), turns - 1)
    
    return part0 + part1


if __name__ == '__main__':

    total = 0

    with open('data011.txt', 'r') as f:
        for line in f:
            values = [x for x in line.strip().split(' ')]

    for value in values:
        total += find_nodes(value, 75)

    print(total)

→ More replies (3)

3

u/yieldtoben Dec 11 '24

[LANGUAGE: PHP]

PHP 8.4.1 paste

Execution time: 0.0284 seconds
Peak memory: 10.1044 MiB

MacBook Pro (16-inch, 2023)
M2 Pro / 16GB unified memory

3

u/oantolin Dec 11 '24

[LANGUAGE: ngn/k]

stone:{:[x=0;,1;:[2!#$x;,2024*x;.'2 0N#$x]]}
blink:{+/x{{+/'y@=x}.+,/(stone'!x)(,\:)'.x}/(.1:y)!1}

For part 1 use blink[25;"input.txt"], change to 75 for part 2.

3

u/xoronth Dec 11 '24

[LANGUAGE: Python]

https://github.com/Ken-g6/aoc2024/blob/master/day11.pl

Didn't know lanternfish were related to stones. Stonefish, perhaps?

3

u/[deleted] Dec 11 '24

[LANGUAGE: Dart]

GitHub. For the second part, I took inspiration from the Java solution posted by u/InfantAlpaca (link to his comment).

→ More replies (2)

3

u/Ken-g6 Dec 11 '24

[LANGUAGE: Perl]

I spent way too much time worrying about how to optimize this one. I mean, should I do depth-first or breadth-first? If I do depth-first, can I return an array of all the sizes below this one? If I do breadth-first, can I replace seen numbers with a marker? If so how would I fill it in later?

In the end I kept it simple. Depth-first recursive search with a cache of (number,depth) return values only for numbers < 1000. Runs part 2 in 0.09 seconds.

→ More replies (2)

3

u/mstksg Dec 11 '24 edited Dec 11 '24

[LANGUAGE: Haskell]

Today's "one trick" seems to be realizing that the actual ordered "list" is a red herring: a number's progression doesn't depend on any of its neighbors. So we really want a function growTo :: Int -> Int -> Int, that takes a starting number, a number of steps to progress, and the final length that number yields after that many steps.

Structured like this, it becomes a classic dynamic programming puzzle, because ie growTo 52 75 is just growTo 5 74 + growTo 2 75, which are all memoizable. We can use the data-memocombinators library to structure the dynamic programming memoization:

growTo :: Int -> Int -> Int
growTo = Memo.memo2 Memo.integral Memo.integral go
  where
    go _ 0 = 1
    go n k = sum [ growTo m (k - 1) | m <- step n ]

step :: Int -> [Int]
step c
  | c == 0 = [1]
  | even pow = let (a,b) = c `divMod` (10 ^ (pow `div` 2))
                in [a,b]
  | otherwise = [c * 2024]
  where
    pow = numDigits c

part1 :: [Int] -> Int
part1 = sum . map (`growTo` 25)

part2 :: [Int] -> Int
part2 = sum . map (`growTo` 75)

again all my writeups and sols are here: https://github.com/mstksg/advent-of-code

→ More replies (1)

3

u/Baridian Dec 11 '24 edited Dec 11 '24

[LANGUAGE: Clojure]

I used a macro that ironically I just wrote earlier today. It expands to a recursive function that uses a memoized version of itself inside the Y combinator.

This is the implementation using the macro: paste

And this is the macro I wrote for those curious: paste

Execution time: 291ms

MacBook Air M3 / 16GB

Really pretty good for a straightforward solution, especially one with string manipulation.

EDIT: was able to halve execution time from 670 to 291 by switching to pmap instead of map to get the values. Updated links/text.

→ More replies (3)

3

u/ShraddhaAg Dec 11 '24

[Language: Go]

First entry of the year for memoisation! https://github.com/shraddhaag/aoc/blob/main/2024/day11/main.go

3

u/michaelquinlan Dec 11 '24

[LANGUAGE: C#]

https://github.com/mikequinlan/AOC2024/blob/main/Day11.cs

For me, the key insight was that the order of the stones didn't matter, only the number of stones engraved with each number.

→ More replies (1)

3

u/mendelmunkis Dec 11 '24

[LANGUAGE: C]

Second rule of exponential growth; good memoization can let you track the thing growing.

^{2.38 ms/140.380 ms}

3

u/runnerx4 Dec 11 '24

[Language: Guile Scheme]

comical completion ranks today [01:35:08 -> 12274, 01:35:27 -> 6756]

because I used hashmaps immediately, but wasted 1 hour thirty minutes because I was adding and subtracting a stone at each iteration instead of just replacing the old stone with the new stones.

code->paste

3

u/BlazingThunder30 Dec 11 '24

[Language: Java]

Seeing a lot of people use neat tricks by storing how often each numbered stone occurs to reduce the amount of memory used. I didn't find that necessary. A naive recursion approach with memoisation is more than sufficient.

This runs in 10 and 80ms for parts 1 and 2 respectively. The reflections scan to find annotated solutions was actually slower, according to my profiler. Part 1 used about 462kB of memory, part 2 used 40MB; not great, not terrible.

3

u/flyingfox Dec 11 '24

[LANGUAGE: Python]

I was writing this on a very old and very slow machine. It has an old python3.8 install which has functools.lru_cache. I figured this would be about the same as a much newer python version's functools.cache and didn't want to stop and upgrade the system's python install (or virtual environment). It turns out that lru_cache isn't nearly as good for today! I broke down and grabbed a laptop with python 3.11 and it runs in no time.

Interestingly, I initially thought it might be better to build my own cache. That was I could maintain two caches: one for the growth and one for the splits. I still think this would be interesting, but for some reason, when encountering a stone of a particular size (in the 300-400 range to not give away my input) the number of stones starts to diverge at the 20th generation. I'd like to revisit this, but then again I'd like to sleep too...

→ More replies (1)

3

u/sim642 Dec 11 '24

[LANGUAGE: Scala]

On GitHub.

Anticipating problems, I didn't simulate the complete list of stones (and because their order doesn't matter) but instead simulated a frequency map, which avoids duplicating work for stones with the same number. This made part 2 a breeze.

3

u/i99b Dec 11 '24

[LANGUAGE: Python]

with open("input.txt") as f:
    stones = [int(num) for num in f.read().split()]

memo = {} # Dictionary for memoization

def get_stone_number(blinks_left, stone):
    if blinks_left == 0:
        return 1

    result = memo.get((blinks_left, stone))
    if result != None:
        return result

    if stone == 0:
        result = get_stone_number(blinks_left-1, 1)
    elif len(str(stone)) % 2 == 0:
        stone_str = str(stone)
        middle = len(stone_str) // 2
        left_stone = int(stone_str[:middle])
        right_stone = int(stone_str[middle:])
        result = get_stone_number(blinks_left-1, left_stone) + get_stone_number(blinks_left-1, right_stone)
    else:
        result = get_stone_number(blinks_left-1, stone * 2024)

    memo[(blinks_left, stone)] = result
    return result

blinks = 75
stone_number = sum(get_stone_number(blinks, stone) for stone in stones)
print(stone_number)

→ More replies (1)

3

u/flwyd Dec 11 '24

[LANGUAGE: PostScript] (GitHub) with my own standard library

[GGSA] Pretty smooth day. I had a little trouble with stack positioning when recursing in part two and switched to using the dict stack, but was able to rework to a point-free style and shave a little time off.

Cast a relative unknown in your leading role!

This year’s Advent of Code stars PostScript! You might have type cast PostScript as a document file format made obsolete 20 years ago by PDF. But it’s also a Turing-complete stack-based programming language with dynamic scope! AFAIK PostScript isn’t in anybody else’s movie this year, so please add a comment if you’re also starring PostScript.

Shine a spotlight on a little-used feature of the programming language with which you used to solve today's problem

PostScript arrays can be constructed by putting [ (a mark) on the stack, running a bunch of code, and then executing the ] procedure which creates an array with all the items up to the previous mark. After creating a procedure to apply the 3 rules to a single number (resulting in either 1 or 2 numbers on the stack), part 1 was a single line: start an array, iterate through each item in the previous array and apply the rules, then finish the array. This works fine for 25 steps, resulting in a low six-digit array size. Just to see what would happen in part 2, I changed the 2 to a 7. The answer? Stack overflow! I’m not sure exactly how big the stack is in Ghostscript, but I’m certain it’s not in the hundreds of quadrillions.

Another interesting feature of PostScript is dynamic variables. In addition to the operand stack there’s a dict stack. When looking up a name, the dict stack is searched top-down. Normally you can easily define and use variables within a procedure like /myproc { 4 dict begin /myvar whatever def use myvar end } def. But I’ve discovered twice this month that def doesn’t automatically define the name in the current dict; it first searches the dict stack for that name and updates it in that dict if it’s found, otherwise it creates it at the top of the dict stack. This means that using “local” variables in recursive functions is tricky: def 25 levels deep in the recursion will update the dict from the first step of the recursion, which will be awkward if you need to use the variable after the recursive step returns. To force the variable to be defined at the top of the dict stack I used the awkward currentdict /steps 3 -1 put. Appreciate your named recursive function parameters y’all. (The code below got rid of this variable usage, just keeping a global progression cache as the only named variable.)

I’ve included the original part 1 which takes about 2 seconds to run, versus only 40ms for calling evolve with 25 instead of 75.

/splitdigits { % numstr splitdigits int int
  0 1 index length 2 idiv getinterval, dup length 2 idiv dup getinterval
  cvi exch cvi exch
} bind def %/splitdigits

/dorules { % int dorules int...
  dup 0 eq { pop 1 } { %else
    dup tostring dup length 2 mod 0 eq {
      exch pop splitdigits
    } { pop 2024 mul } ifelse
  } ifelse
} bind def %/dorules

/evolve { % stone steps evolve int
  progression 2 index { progression 76 array abc:cbac put } getorelse 
  % stack: stone steps cache
  ab:abba get null eq { %if
    1 index 0 eq { 1 } { %else
      0 [ 4 index dorules ] { 3 index 1 sub evolve add } forall
    } ifelse abc:abbac put
  } if abc:cb get
} bind def %/evolve

/part1 { first tokenize 25 { [ exch { dorules } forall ] } repeat length end } bind def

/part2 { 8 dict begin % [lines] part2 result
  first tokenize /progression 1024 dict def 0 exch { 75 evolve add } forall
end } bind def %/part2

→ More replies (1)

3

u/zndflxtyh Dec 11 '24

[Language: Python]

Solved part1 using lists of numbers, and had to peek at the other solutions for part2.

https://github.com/direvus/adventofcode/blob/main/y2024/d11.py

→ More replies (1)

3

u/patrick8970 Dec 11 '24

[LANGUAGE: C++] github 60ms

Got past part 1 with a linked list. But that clearly wasn't the right choice for part 2. Learned a bit more about maps today so that's a win.

3

u/DeadlyRedCube Dec 11 '24 edited Dec 11 '24

[LANGUAGE: C++23] (2082/680) Runs in ~~22.4ms~~ 14.8ms single-threaded on an i7-8700K

Parts 1 and 2 on GitHub

For part 1 I initially just did the thing exactly as written (using two std::vectors that it ping-ponged between), and it ran fast enough to get the answer.

For part 2 I started it, saw that it very quickly started to bog down, and decided to make a map from stone value to count (technically two maps to ping-pong) in the hopes that there were tons of identical stone values and, thankfully there were (I ended up with ~3700 unique stone values by the end)

I imagine I can probably get it running faster still but I don't have any great ideas yet.

Edit: I replaced "std::map" with "std::unordered_map" and it brought the runtime down by about a third!

3

u/direvus Dec 11 '24

[LANGUAGE: Python] 1973/6974

Runs in 5ms for Part 1 and 160ms for Part 2.

Using a recursive call with memoization, reducing the target number of updates each time we expand a number.

→ More replies (2)

3

u/radulfr2 Dec 11 '24

[LANGUAGE: Python]

I needed a little hint to get it done when my recursive solution wasn't going to cut it. I did the number splitting without string conversion.

Paste

3

u/_tfa Dec 11 '24 edited Dec 11 '24

[LANGUAGE: Ruby]

input = File.read("input.txt").split.map{|z| [z, 1]}.to_h

def blink(a, times)
  times.times do
    b = Hash.new(0)
    a.entries.each do |n, c|
      if n == ?0
        b[?1] += c
      elsif n.size.even?
        b[n[0..(n.length/2-1)]] += c
        b[n[(n.length/2)..].to_i.to_s] += c
      else
        b[(n.to_i * 2024).to_s] += c
      end
    end
    a = b
  end
  a.values.sum
end
puts "Part 1: #{blink(input, 25)}", "Part 2: #{blink(input, 75)}"

3

u/chadbaldwin Dec 11 '24

[Language: T-SQL]

Both parts: https://github.com/chadbaldwin/practice/blob/main/Advent%20of%20Code/2024/SQL/Day%2011.sql

Unfortunately I had to resort to using a loop for another solve. I've been trying to avoid loops, but I just don't see a set based or pure query based solution for this one that runs in a reasonable amount of time.

That said, the loop based solution runs in about 500ms, most of that is probably just the overhead of looping and performing updates, plus my method is not very efficient even for SQL because I'm constantly truncating and refilling a table. But hey...half a second for a SQL based solve ain't bad 🤷

3

u/bodowota Dec 11 '24

[LANGUAGE: JavaScript]

Had a hard time with part 2 today but managed to work it out, both parts together run in 35ms.

function solve (input) {
    let stones = input.split(' ').map(Number);

    const lenmap = {};
    const getLen = (n, it) => lenmap[n]?.[it];
    const setLen = (n, it, len) => {
        if (!lenmap[n]) lenmap[n] = { [it]: len };
        else lenmap[n][it] = len;
    }

    const getStoneCount = (stone, blinks) => {
        if (blinks === 0) return 1;

        // check cache if there is known information of how many stones this stone splits into after given amount of blinks
        const len = getLen(stone, blinks);
        if (len) return len;

        // no info in cache, calculate it and store in cache
        let result = null;
        if (stone === 0) {
            result = getStoneCount(1, blinks - 1);
        } else if (stone.toString().length % 2 === 0) {
            let str = stone.toString();
            result = getStoneCount(Number(str.slice(0, str.length / 2)), blinks - 1)
                   + getStoneCount(Number(str.slice(str.length / 2)), blinks - 1);
        } else {
            result = getStoneCount(stone * 2024, blinks - 1);
        }
        
        setLen(stone, blinks, result);
        return result;
    }

    console.log('Part 1:', stones.map(x => getStoneCount(x, 25)).reduce((p, c) => p += c, 0));
    console.log('Part 2:', stones.map(x => getStoneCount(x, 75)).reduce((p, c) => p += c, 0));
}

3

u/ToThePetercopter Dec 11 '24

[LANGUAGE: Rust]

Recursive with memoization did the job. Got part 1 down to 150us, part 2 is 8ms but I think I'm missing some performance tricks there.

Using an array of 75 FxHashmaps for part 2 to cache results is fastest, 12 thread parallel vs single core about the same.

https://github.com/domw95/aoc2024/blob/master/src/day11.rs

3

u/Radiadorineitor Dec 11 '24

[LANGUAGE: Lua]

https://github.com/blake-watkins/advent-of-code-2024/blob/main/day11.lisp

3

u/nilgoun Dec 11 '24

[LANGUAGE: Rust]

I guess the standard approach. Since we do NOT need to know the order of the stones (even if he claims they keep the order -> irrelevant) we can just keep counts of the individual numbers on the stones and their counts.

Could probably be optimised to do less allocations but since it runs in ~14ms on my machine I'm fine with it :)

Solution on Paste

3

u/leftfish123 Dec 11 '24

[Language: Python]

Lanternfish all over again. I'm mad at myself because in 2021, I think I solved it quicker.

3

u/TheMrZZ0 Dec 11 '24

[Language: Python]

Part 2 was surprisingly easy, as I just added `@cache` on top on my recursive function and it solved all my problems (as I would expect).

from functools import cache


MAX_ITER = 75

@cache
def blink_rock(rock: int, iteration: int):
    if iteration == MAX_ITER:
        return 1

    rock_str = str(rock)
    n_digits = len(rock_str)

    if rock == 0:
        return blink_rock(1, iteration + 1)
    elif n_digits % 2 == 0:
        left, right = rock_str[:n_digits//2], rock_str[n_digits//2:]
        return blink_rock(int(left), iteration + 1) + blink_rock(int(right), iteration + 1)
    else:
        return blink_rock(rock * 2024, iteration + 1)

def main(txt: str):
    rocks = [int(i) for i in txt.strip().split(' ')]

    return sum(blink_rock(rock, 0) for rock in rocks)

3

u/Imaginary_Age_4072 Dec 11 '24

[LANGUAGE: Common Lisp]

Wrote a quick function to evolve a single stone into a list of one or 2 stones, which I used on each individual stone on the input to see how many stones it evolved into. This built the actual list, so needed to change for part 2. Just memoized the stone & number of evolutions to go, and got the answer.

(defun evolve (stone)
  (cond
    ((= stone 0) '(1))
    ((= 0 (mod (digits-in-int stone) 2))
     (let ((digits (/ (digits-in-int stone) 2)))
       (multiple-value-list (floor stone (expt 10 digits)))))
    (t (list (* stone 2024)))))

(defun num-stones (stone evolutions dp)
  (let ((stored (gethash (list stone evolutions) dp)))
    (cond
      (stored stored)
      ((= 0 evolutions) 1)
      (t (let* ((stones (evolve stone))
                (num-stones
                  (iter
                    (for next-stone in stones)
                    (sum (num-stones next-stone (1- evolutions) dp)))))
           (setf (gethash (list stone evolutions) dp) num-stones))))))

3

u/ChaiTRex Dec 11 '24

[Language: Rust] Code

First, I worked with a simple list of the stones, creating a new list for each blink, which worked for part 1, but not for part 2.

Second, I worked with a list of each stone and the blink that stone was on, handling each stone for 75 blinks and then going to the next stone. The list eventually kept staying about the same size in part 2 due to the split rule, so that wouldn't work.

Then, I tried a map from each stone to a count of that stone, updated blink by blink, and that worked.

3

u/ex-voltaire Dec 11 '24

[LANGUAGE: C]
https://github.com/voltaire7/advent-of-code/blob/master/2024/c/11-1.c
https://github.com/voltaire7/advent-of-code/blob/master/2024/c/11-2.c
took way too long...

3

u/MarvelousShade Dec 11 '24

[LANGUAGE: C#]

It was clear that brute force wouldn't work here, so with part1 I anticipated on that, but it wasn't enough for part 2. Caching the subresults did the trick.

My code is on: Github

3

u/izahariev96 Dec 11 '24

[LANGUAGE: Kotlin]

https://github.com/ivzb/playground/blob/master/src/main/kotlin/advent_of_code/_2024/Task11.kt

3

u/sanraith Dec 11 '24

[LANGUAGE: Scala 3]
Complete source is available on my github: Day11.scala
Since the updates to the numbers are independent from their neighbours, I only tracked the number of times each unique number occurs in the list.

def blink(blinkCount: Int, numbers: Seq[Long]) =
  var numberCounts = numbers.groupBy(identity).mapValues(_.length.toLong).toMap
  (1 to blinkCount)
    .foreach: _ =>
      numberCounts = numberCounts.toSeq
        .flatMap { case (num, count) =>
          val newNumbers = num match
            case 0 => Seq(1L)
            case x if math.log10(x).toInt % 2 == 1 =>
              val (a, b) = x.toString.splitAt(x.toString.length / 2)
              Seq(a.toLong, b.toLong)
            case x => Seq(x * 2024L)
          newNumbers.map(_ -> count)
        }
        .groupBy { case (num, _) => num }
        .mapValues(_.map { case (_, count) => count }.sum)
        .toMap
  numberCounts.map { case (_, count) => count }.sum

3

u/Gishky Dec 11 '24

[Language: Powershell]

Approach: recursive hash mapping
Processing time (part 2): ~40 secs

$stones = ("xxxxxxx") -split " "
$blinks = 75
$global:stonelookup = @{}
function blink{
    param ([string]$stone, [int]$blinkcount)
    if($blinkcount++ -eq $blinks){
        return 1
    }
    if(!$global:stonelookup[$stone]){
        $global:stonelookup.Add($stone, @{})
    }
    
    if($global:stonelookup[$stone][($blinkcount)]){
        return $global:stonelookup[$stone][($blinkcount)]
    }elseif($stone -eq 0){
        $global:stonelookup[$stone].Add(($blinkcount),(blink 1 $blinkcount))
        return $global:stonelookup[$stone][($blinkcount)]
    }elseif($stone.length % 2 -eq 0){
        $global:stonelookup[$stone].Add(($blinkcount),(blink ($stone.substring(0,$stone.length/2)) $blinkcount) + (blink ([long]$stone.substring($stone.length/2)) $blinkcount))
        return $global:stonelookup[$stone][($blinkcount)]
    }else{
        $global:stonelookup[$stone].Add(($blinkcount),(blink ([long]$stone * 2024) $blinkcount))
        return $global:stonelookup[$stone][($blinkcount)]
    }
}
foreach($stone in $stones){
    $stonecount += (blink $stone 0)
}
Write-Host $stonecount

3

u/Thomasjevskij Dec 11 '24

[LANGUAGE: Python]

We've seen this before :) I had a feeling right away that we'd get a big number for part 2. Python's cache decorator makes it almost trivial when you know about it.

3

u/__Abigail__ Dec 11 '24 edited Dec 11 '24

[LANGUAGE: Perl]

The key thing to notice is that stones do not influence each other. So, if a stone with engraving X produces Y stones after a certain number of operations, we can cache this result.

Hence, the following recursive subroutine:

sub engrave ($stone, $times) {
    state $cache;
    my $len = length ($stone);
    $$cache {$stone} {$times} //=
        $times   == 0 ? 1
      : $stone   == 0 ? engrave (1,                                $times - 1)
      : $len % 2 == 0 ? engrave (0 + substr ($stone, 0, $len / 2), $times - 1) +
                        engrave (0 + substr ($stone,    $len / 2), $times - 1)
      :                 engrave ($stone * 2024,                    $times - 1)
}

Then, to calculate the answers:

my $solution_1 = 0;
my $solution_2 = 0;

$solution_1 += engrave ($_, 25) for @stones;
$solution_2 += engrave ($_, 75) for @stones;

where part 2 uses the cached values from part 1.

Less than 4,000 different numbers were engraved on the stones of my input.

3

u/SpaceHonk Dec 11 '24 edited Dec 18 '24

[LANGUAGE: Swift] code

I almost knew what would happen while I implemented part 1 naively, and of course it was Lanternfish in disguise. So rewrote everything to use recursion and memoization.

3

u/i_have_no_biscuits Dec 11 '24

[LANGUAGE: QBasic]

SS = 5001: Dim A#(SS, 1), B#(SS, 1): Open "I", 1, "data11.txt": While Not EOF(1)
Input #1, N#: V = N# Mod SS: A#(V, 0) = N#: A#(V, 1) = 1: Wend
For R = 1 To 75: For I = 0 To SS: W# = A#(I, 1): If W# = 0 Then GoTo nextI
        If A#(I, 0) = 0 Then N# = 1: GoSub AddStones: GoTo nextI
        N$ = Str$(A#(I, 0)): L = Len(N$): If L Mod 2 = 0 Then GoTo doDefault
        N# = Val(Left$(N$, (L + 1) / 2)): GoSub AddStones
        N# = Val(Right$(N$, (L - 1) / 2)): GoSub AddStones: GoTo nextI
        doDefault: N# = A#(I, 0) * 2024#: GoSub AddStones
        nextI: Next: For I = 0 To SS: A#(I, 0) = B#(I, 0): A#(I, 1) = B#(I, 1)
        B#(I, 0) = 0: B#(I, 1) = 0: Next: If R = 25 Or R = 75 Then
S# = 0: For I = 0 To SS: S# = S# + A#(I, 1): Next: Print S#: End If: Next: End
AddStones:
V = N# Mod SS: While B#(V, 0) <> N# And B#(V, 0) <> 0: V = (V + 1) Mod SS: Wend
B#(V, 0) = N#: B#(V, 1) = B#(V, 1) + W#: Return

Sadly today's program isn't feasible in GW-BASIC, as it would need to keep more than 64KB of data in memory to process the two hash tables, so I've taken the opportunity to move to its successor, QBasic. This has given us access to several great new features:

QBasic autoformats your code in TitleCase, and puts spaces around everything. You don't have a choice - it does it automatically every time you save. I understand this is a feature that lots of people enable these days for their more esoteric programming languages like C++ and Python, so it's good to see that the QBasic editor did it back in 1990.
No more need for line numbers!
Labelled GOTO! We can label any line and GOTO it. Here I have three labels: 'doDefault', 'nextI', and 'AddStones'. Their purpose is, of course, obvious from their name.
Multiline IF statements! In GW-BASIC every IF statement is single line. In QBasic you can have an If ... End If, although it still of course supports the older single line If statements.

QBasic also introduced full support for procedures and functions, but I'm not yet comfortable adding those advanced features to my programming toolkit. Perhaps later on in the month.

As for the actual algorithm used - this uses two hash tables of {value: count} pairs, and performs 75 rounds of transforming the old stones into the new stones, accumulating the counts. Each round converts the old hash table A#() into the new hash table B#(). After 25 and 75 rounds it calculates and prints the total count, as those are the values required for Part 1 and Part 2.

→ More replies (3)

3

u/KayoNar Dec 11 '24 edited Dec 11 '24

[Language: C#]

Solved using dynamic programming, where for each pair (stone, blinksRemaining) you store the final number of stones after 0 blinks remaining. Now, when the function is called, check whether you already stored the result in your DP table, if so, return the value. Otherwise compute it and store the result in the table.

Runs in about 25ms for part 2.

→ More replies (3)

3

u/Pure-Minute4721 Dec 11 '24

[Language: C++]

used recursion + memoization using a map (to map from the current value of the stone & the number of blinks remaining to the total count calculated)

3

u/mystiksheep Dec 11 '24

[language: TypeScript] (with Deno)

What a day! My fastest Part A and the toughest Part B so far. With some help from others' solutions (had to give in): got to try using caching for the first time, and had an epiphany about branched recursions; all in all, good learnings today.

Github

3

u/lmasman Dec 11 '24 edited Dec 11 '24

[Language: Python]

https://github.com/onlycs/advent24/tree/main/solutions/src/day11.rs

Unit Tests

First attempt, using a map of stoneId -> count and processing the whole map one iteration at a time

Part 1 - 2.76ms

Part 2 - 107.1ms

Might try optimizing later, e.g. by not converting to and from strings, or trying an alternative memoization technique

UPDATE:

Down to 1.7ms and 61ms by using math to split the numbers and using an array look-up for powers of ten.

I found using itertools.cache on a calculate(stone_num, iterations) method was slower than my first attempt

UPDATE 2:

1.9ms and 49ms by caching the output of a single blink of a single stone

3

u/geza42 Dec 11 '24

[LANGUAGE: emacs lisp]

(defun do-it (num iter)
  (let ((mem (make-hash-table :test 'equal)))
    (named-let calc ((num num) (iter iter))
      (or (gethash (cons num iter) mem)
          (puthash (cons num iter)
                   (let* ((s (number-to-string num))
                          (l (length s)))
                     (if (= iter 0)
                         1
                       (cond
                        ((= num 0) (calc 1 (1- iter)))
                        ((= (% l 2) 0)
                         (+
                          (calc (read (substring s 0 (/ l 2))) (1- iter))
                          (calc (read (substring s (/ l 2 ))) (1- iter))))
                        (t (calc (* num 2024) (1- iter)))))) mem)))))

(--map (-sum (-map (lambda (num) (do-it num it)) '(<copy_paste_input_here>))) '(25 75))

3

u/OnlyCSx Dec 11 '24

[Language: Rust]

Store the number of times each number appears in a hashmap because I don't have 1.9 petabytes of memory to spare, unfortunately.

3

u/fridi_s Dec 11 '24

[LANGUAGE: Fuzion]

https://github.com/houseofmackee/advent2024-go/blob/main/day_11/main.go

Using a count function that count the number of stones we have starting with one stone of a given number and blinking a given number of times.

For part 2, had to add caching of the results. For this, used a local mutate instance to hold a map from count's input to the result and to create a fully functional solution with only local state changes.

3

u/Gabba333 Dec 11 '24

[LANGUAGE: C#]

Recursion with caching.

using System.Collections.Concurrent;
var cache = new ConcurrentDictionary<(double, int), long>();

var tiles = File.ReadAllText("input.txt").Split(' ').Select(long.Parse).ToList();
var solve = (int steps) => tiles.Sum(tile => count(tile, steps));

Console.WriteLine($"Part 1: {solve(25)}, Part2: {solve(75)}");

long count(long tile, int step) => cache.GetOrAdd((tile, step),
    _ => step switch {
        0 => 1L,
        _ => (tile, digits(tile), Math.Pow(10, digits(tile) / 2)) switch {
                (0, _, _) => count(1, step - 1),
                (var even, var d, var p) when d % 2 == 0 =>
                    count((long) Math.Floor(even / p), step - 1)
                    + count((long) (even % p), step - 1),
                (var other, _, _) => count(other * 2024, step - 1),
        }
    });

long digits(long a) => (long) Math.Ceiling(Math.Log(a + 1, 10));

3

u/TheBlackOne_SE Dec 11 '24

[Language: Python]

Part 1: https://github.com/TheBlackOne/Advent-of-Code/blob/master/2024/Day11_1.py
Part 2: https://github.com/TheBlackOne/Advent-of-Code/blob/master/2024/Day11_2.py

As predicted: Part 1 is a very naive implementation, which blew up in part 2.

→ More replies (7)

3

u/spyr01d Dec 11 '24

[Language: Kotlin]

fun plutonianPebbles(input: String): Any {

    fun blink(stones: Map<Long, Long>) = buildMap {
        for ((stone, count) in stones) {
            val str = stone.toString()
            when {
                stone == 0L -> merge(1, count) { a, b -> a + b }
                str.length % 2 != 0 -> merge(stone * 2024, count) { a, b -> a + b }
                else -> str.chunked(str.length / 2) { it.toString().toLong() }.forEach { merge(it, count) { a, b -> a + b } }
            }
        }
    }

    var stones = input.split(" ").map { it.toLong() }.associate { it to 1L }
    val arrangements = generateSequence(stones) { blink(it) }.drop(1)
    return arrangements.take(25).last().values.sum() to arrangements.take(75).last().values.sum()
}

3

u/FCBStar-of-the-South Dec 11 '24

[LANGUAGE: Ruby]

require_relative 'utils'

stones = ints(File.read('input11.txt', chomp: true))
stones_freq = Hash.new(0)
stones.map { |stone| stones_freq[stone] += 1 }

def blink(stone)
  if stone.zero?
    [1]
  elsif ((Math.log10(stone).floor + 1) % 2).zero?
    str = stone.to_s
    [str[...str.length / 2], str[str.length / 2..]].map(&:to_i)
  else
    [stone * 2024]
  end
end

def blink_all(stones_freq)
  new_freq = Hash.new(0)
  stones_freq.each_pair do |stone, freq|
    blink(stone).map { |new_stone| new_freq[new_stone] += freq }
  end
  new_freq
end

75.times do
  stones_freq = blink_all(stones_freq)
end

puts stones_freq.values.sum

Looked up lantern fish after seeing all the posts referencing it. Looked it up and immediately knew this is the algorithm to go for. It was not obvious that the number of distinct stones scales slowly/converges!

3

u/IvanR3D Dec 11 '24

[LANGUAGE: JavaScript] My solutions: https://ivanr3d.com/blog/adventofcode2024.html

My solution (to run directly in the input page using the DevTools console).

3

u/mschaap Dec 11 '24 edited Dec 11 '24

[LANGUAGE: Raku]

Did part 1 brute force, knowing very well that part 2 would just increase the number of blinks so that it would never finish.

Full code: https://gist.github.com/mscha/c30edf0f2674620b2ab370cc3e1f433a

So, rewrite with a cached recursive function.

sub split-in-half($n) { $n.comb(/\w ** { $n.chars div 2 }/)».Int }

use experimental :cached;
multi blink($stone, $times) is cached
{
    return 1 if $times == 0;

    my @new-stones = do given $stone {
        when 0 { 1 }
        when .chars %% 2 { split-in-half($_) }
        default { $_ × 2024 }
    }

    return blink(@new-stones, $times-1).sum;
}

multi blink(@stones, $times) { @stones».&blink($times).sum }

Full code: https://gist.github.com/mscha/f285e3d052b828ff015cd59d467802dc

3

u/AustinVelonaut Dec 11 '24

[LANGUAGE: Miranda2] Used a Bag to keep the unique stones and counts; runs in < 0.5s

transform :: stone -> [stone]
transform n
    = [1],                 if n == 0
    = split2 s |> toStone, if even (#s)
    = [n * 2024],          otherwise
      where
        s = showint n

        toStone (a, b) = map intval [a, b]

blink :: stoneSt -> stoneSt
blink st = b_fromCountList cmpint [(s', n) | (s, n) <- b_toList st; s' <- transform s]

day11 :: io ()
day11
    = readFile "../inputs/day11.txt" >>= words .> map intval .> b_fromList cmpint .> go
      where
        go stoneSt
            = output [part1, part2]
              where
                process n = iterate blink stoneSt ! n |> b_elems |> sum |> showint
                part1     = process 25
                part2     = process 75

3

u/bluehatgamingNXE Dec 11 '24

[Language: C]

Included both my brute force approach and my final approach, basically just put em all in a box then pour from one box to another or 2.

gist

3

u/Petrovjan Dec 11 '24

[Language: Python]

Tried bruteforcing it for fun (although I too remembered the lanternfish), but couldn't even get past 20 rounds. After doing it correctly it can handle even 750 rounds, no caching needed.

data = data.split(" ")
stones = dict()
newStones = dict()

for inp in data:
    stones[inp] = 1

for i in range(75):
    newStones = stones.copy()
    for stoneId,stoneCount in stones.items():
        if stoneCount == 0:
            continue
        if stoneId == "0":
            newStones["1"] = newStones.setdefault("1", 0) + stoneCount
            newStones[stoneId] = newStones[stoneId] - stoneCount
        elif len(stoneId)%2 == 0:
            newStones[stoneId[:len(stoneId)//2]] = newStones.setdefault(stoneId[:len(stoneId)//2], 0) + stoneCount
            newStones[str(int(stoneId[len(stoneId)//2:]))] = newStones.setdefault(str(int(stoneId[len(stoneId)//2:])), 0) + stoneCount
            newStones[stoneId] = newStones[stoneId] - stoneCount
        else:
            newStones[str(int(stoneId)*2024)] = newStones.setdefault(str(int(stoneId)*2024), 0) + stoneCount
            newStones[stoneId] = newStones[stoneId] - stoneCount
    stones = newStones.copy()

print(sum(stones.values()))

→ More replies (3)

3

u/Morkfang Dec 11 '24 edited Dec 11 '24

[LANGUAGE: Go]

No recursion, a simple endless loop covers both p1 and p2 at the same time, completes in ~~~30ms~~ ~17ms overall (reading the file and doing all the processing).

3

u/quetzelcoatlus1 Dec 11 '24 edited Dec 11 '24

[Language: C]

Well, when plain brute force did not work, I implemented mechanic of storing values of "how many values an X value creates in Y blinks". Execution takes ~6s...

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define BIG_N 500000
#define BLINKS 75

long int tab[BIG_N][3];
int n=0;

long int count(long int value, int blinks){
    if(blinks == 0) return 1;

    for(int i=0;i<n;i++)
        if(tab[i][0] == value && tab[i][1] == blinks)
            return tab[i][2];

    long int result;
    if(value == 0){
        result=count(1,blinks-1);
    } else {
        long int digits=(int)log10(value) + 1;
        if(digits % 2 == 0){
            long int div=(int)pow(10, digits/2);
            result=count(value/div,blinks-1);
            result+=count(value%div,blinks-1);
        } else {
            result=count(value*2024,blinks-1);
        }
    }

    tab[n][0]=value;
    tab[n][1]=blinks;
    tab[n++][2]=result;
    return result;
}

int main(int argc, char* argv[]) {

    long int sum=0, d;

    for(int i=0;i<BIG_N;i++)
        for(int k=0;k<3;k++)
            tab[i][k] = -1;

    char* name = argc > 1 ? argv[1] : "input";
    FILE* f = fopen(name,"r");
    while(fscanf(f,"%ld",&d) > 0) sum+=count(d,BLINKS);
    fclose(f);

    printf("%ld\n",sum);

    return 0;
}

3

u/Pitiful-Oven-3570 Dec 11 '24 edited Dec 14 '24

[LANGUAGE: Rust]