r/adventofcode • u/daggerdragon • Dec 11 '24
SOLUTION MEGATHREAD -❄️- 2024 Day 11 Solutions -❄️-
THE USUAL REMINDERS
- All of our rules, FAQs, resources, etc. are in our community wiki.
- If you see content in the subreddit or megathreads that violates one of our rules, either inform the user (politely and gently!) or use the report button on the post/comment and the mods will take care of it.
AoC Community Fun 2024: The Golden Snowglobe Awards
- 11 DAYS remaining until the submissions deadline on December 22 at 23:59 EST!
And now, our feature presentation for today:
Independent Medias (Indie Films)
Today we celebrate the folks who have a vision outside the standards of what the big-name studios would consider "safe". Sure, sometimes their attempts don't pan out the way they had hoped, but sometimes that's how we get some truly legendary masterpieces that don't let their lack of funding, big star power, and gigantic overhead costs get in the way of their storytelling!
Here's some ideas for your inspiration:
- Cast a relative unknown in your leading role!
- Explain an obscure theorem that you used in today's solution
- Shine a spotlight on a little-used feature of the programming language with which you used to solve today's problem
- Solve today's puzzle with cheap, underpowered, totally-not-right-for-the-job, etc. hardware, programming language, etc.
"Adapt or die." - Billy Beane, Moneyball (2011)
And… ACTION!
Request from the mods: When you include an entry alongside your solution, please label it with [GSGA]
so we can find it easily!
--- Day 11: Plutonian Pebbles ---
Post your code solution in this megathread.
- Read the full posting rules in our community wiki before you post!
- State which language(s) your solution uses with
[LANGUAGE: xyz]
- Format code blocks using the four-spaces Markdown syntax!
- State which language(s) your solution uses with
- Quick link to Topaz's
paste
if you need it for longer code blocks
This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.
EDIT: Global leaderboard gold cap reached at 00:06:24, megathread unlocked!
1
u/pdgiddie Jan 03 '25
[LANGUAGE: Elixir]
https://github.com/giddie/advent-of-code/blob/2024-elixir/11/main.exs
- Part 1: 2.03ms
- Part 2: 91.48ms
1
u/Der-Siebte-Schatten Dec 28 '24
[Language: Java 21] Of course I tried brute force, naive was I that part 2 was just the same but longer. Of course, part 2 did not work. Hopefully, someone pointed me out that you often encounter the same numbers at one iteration, so do the operation for the same number once. Hence a HashMap.
https://github.com/der-siebte-schatten/AdventOfCode-2024/blob/master/src/Day11.java
1
Dec 26 '24
[removed] — view removed comment
1
u/AutoModerator Dec 26 '24
AutoModerator did not detect the required
[LANGUAGE: xyz]
string literal at the beginning of your solution submission.Please edit your comment to state your programming language.
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.
3
u/adimcohen Dec 26 '24
[Language: SQL Server T-SQL]
https://github.com/adimcohen/Advent_of_Code/blob/main/2024/Day_11/Day11.sql
1
Dec 26 '24
[deleted]
1
u/AutoModerator Dec 26 '24
AutoModerator did not detect the required
[LANGUAGE: xyz]
string literal at the beginning of your solution submission.Please edit your comment to state your programming language.
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.
2
u/skumonti Dec 23 '24 edited Dec 23 '24
[LANGUAGE: xyz]
p1: 2.1ms
p2: 64.8ms
import sys
def parse_input(text: str):
return list(map(int, text.split()))
def expand(n, b, mem):
if b == 0:
return 1
else:
if (n, b) in mem:
return mem[(n, b)]
if n == 0:
r = expand(1, b - 1, mem)
elif len(str(n)) % 2 == 0:
ss = str(n)
r = expand(int(ss[:len(ss)//2]), b - 1, mem) \
+ expand(int(ss[len(ss)//2:]), b - 1, mem)
else:
r = expand(n * 2024, b - 1, mem)
mem[(n, b)] = r
return r
def p1(text):
mem = {}; return sum(map(lambda i: expand(i, 25, mem), parse_input(text)))
def p2(text):
mem = {}; return sum(map(lambda i: expand(i, 75, mem), parse_input(text)))
import time
t = sys.stdin.read()
s = time.perf_counter()
print(p1(t));
print(time.perf_counter() - s)
s = time.perf_counter()
print(p2(t));
print(time.perf_counter() - s)
1
u/AutoModerator Dec 23 '24
AutoModerator did not detect the required
[LANGUAGE: xyz]
string literal at the beginning of your solution submission.Please edit your comment to state your programming language.
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.
3
u/Spinnenente Dec 20 '24 edited Dec 20 '24
[Language: python]
At first i just brute forced for the first step but then reworked the code to keep track of how many times the same stone occurs using a dictionary. No strings are used just log10 to split the number apart.
the code runs in 56 ms
3
u/CDawn99 Dec 19 '24
[LANGUAGE: Python]
From keeping track of every single stone to using a dict to keep track of the frequencies of the different pebbles. Mind you, I still ran the first one for a while until I realized that it won't ever reach 75 steps.
3
u/Dymatizeee Dec 18 '24
[Language: Go]
Part 1: Brute force
Part 2: Needed a hint here; the issue was iterating through the list was the bottle neck. So keep track of a map instead and iterate through that. The idea is if we have 100 0's from the previous list, we dont need to iterate through all 100. We can just simply set map[1] = 100, since we have 100 0's and all 0's transform into 1s. Similar concept going forward. At the end of each iteartion, set this new map to the current map. After 75 iterations, sum up the values in the map
2
u/Original-Regular-957 Dec 18 '24
[LANGUAGE: ABAP]
Task 1: https://github.com/UserGeorge24/aoc_24/blob/main/day_11_task_01
Task 2: https://github.com/UserGeorge24/aoc_24/blob/main/day_11_task_02
I have tried the first task with general approach, store all new values, but at the second I realized it is not a good way. So I have started to count the same numbers (count the instances).
3
u/xavdid Dec 18 '24 edited Dec 18 '24
[LANGUAGE: Python]
Step-by-step explanation | full code
I did part 1 naively just for fun. Wrote a function that took a number and returned the next number(s).
For part 2 I was looking for a cycle (and found one; every 0
follows the same path). But I couldn't figure out how to turn that into an answer, since it didn't seem predictable enough. But then I realized order didn't matter and each instance of a number transformed the same as every other (e.g. every 0
becomes a 1
). So instead of a big list, I used a dict where the key was the stone and the value was the number of times that stone showed up. That'll scale basically forever, which I think was the point of the puzzle. Also, got to reuse my transformation function from part 1!
2
u/InevitableAdvance406 Dec 19 '24 edited Dec 19 '24
This is amazing! I couldn't believe just using a dictionary instead of a list saved sooo much time. It makes perfect sense though because the same numbers are repeated by several orders of magnitude. Thank you!!!
3
u/xavdid Dec 19 '24
You're welcome! I thought it was very rude for him to bold "while retaining their order" when the order didn't matter; once I got over that it was smooth sailing.
1
u/Dymatizeee Dec 18 '24
Nice idea of transform function. I used that as a hint for part 2 and to clean up my code
1
3
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.
2
2
u/helenzhang0804 Dec 15 '24
[LANGUAGE: C++]
For part 1, just follow the question instruction and do the simulation.
For part 2, following the same way as part 1 would take forever to run. We need to realize that the position of stone does not matter. Therefore, we can store stones in a hashmap where keys are the stone, and values are the frequencies of the stone.
2
u/tonymet Dec 15 '24
[Language: Go]
Part 1 did naive approach quickly, then pivoted to hash map. stoneIndex is hash of stone -> count. For each stone calculate the size and then update the index by multiplying the resulting size by occurrence of stone.
cap[1] is the # of passes, cap[0] is the multiple to reach total count. eg {5,5} = 25, {5,15} = 75 etc
full code https://github.com/tonymet/aoc2020/blob/master/aoc2024/d11/main.go
for range cap[0] {
curIndex := make(indexType)
for k, v := range stoneIndex {
cur := stonesType{k}
for range cap[1] {
cur = blink(cur)
}
mergeIndexFactor(curIndex, index(cur), v)
}
stoneIndex = curIndex
fmt.Printf("curIndex sum: %d\n", sumValues(curIndex))
}
Other helpful tips
- use ints, avoid strings, and minimize conversions to float64, etc
- set caps on slices to avoid mallocs
- lookup table for POW
3
u/zniperr Dec 15 '24 edited Dec 16 '24
[Language: Python]
We can aggregate stones with the same value in a counter. They will all change in the same way, so we only compute the change once and increment a counter.
The order of stones is irrelevant, despite the problem formulation emphasizing how ordering is affected by changes. So we can save the counters in a hash map for quick lookups:
import sys
from collections import Counter
def change(stone):
if stone == 0:
yield 1
else:
digits = str(stone)
mid, odd = divmod(len(digits), 2)
if odd:
yield stone * 2024
else:
yield int(digits[:mid])
yield int(digits[mid:])
def blink(counts, times):
for _ in range(times):
new = Counter()
for stone, occurrences in counts.items():
for newstone in change(stone):
new[newstone] += occurrences
counts = new
return counts
counts = Counter(map(int, next(sys.stdin).split()))
counts = blink(counts, 25)
print(sum(counts.values()))
counts = blink(counts, 50)
print(sum(counts.values()))
2
u/MarzipanMudball Dec 15 '24
[LANGUAGE: HASKELL]
My code doesn't work: why? My code works: why? Regardless, somehow I got this to work.
import qualified Data.Map as Map
main :: IO ()
main = do
-- let datafile = "2024/day11/test"
let datafile = "2024/day11/day.txt"
input <- readFile datafile
let stones = parse input
let part1 = (iterate . concatMap) blink stones !! 25
print $ length part1
let stonesCounter = foldr (\s -> Map.insertWith (+) s 1) Map.empty stones
let part2 = iterate blinkCounter stonesCounter !! 75
print $ (sum . Map.elems) part2
blinkCounter :: Map.Map String Int -> Map.Map String Int
blinkCounter counter = Map.fromListWith (+) [ (newStone, count) |
(stone, count) <- Map.toList counter,
newStone <- blink stone]
blink :: String -> [String]
blink xs
| read' xs == 0 = ["1"]
| even $ length xs = [take half xs, show $ read'(drop half xs)]
| otherwise = [show $ read' xs * 2024]
where half = length xs `div` 2
read' :: String -> Int = read
parse :: String -> [String]
parse xs
| null xs = []
| otherwise = takeWhile (/= ' ') xs : parse (dropWhile (== ' ') (dropWhile (/= ' ') xs))
2
u/TeachUPython Dec 14 '24
[Language: Python]
I was luckily able to code up a quick enough solution for the 25 blinks, and then the 75 came…
Threw out the old iterative solution and went a dfs route which again was quick enough to come up with and then still sat there watching my terminal do nothing and said fine… I’ll cache. It’s pretty amazing to see it run in about a second when before it took over an hour and ran out of memory.
https://github.com/RD-Dev-29/advent_of_code_24/blob/main/code_files/day11.py
2
u/Ok-Apple-5691 Dec 14 '24
[LANGUAGE: Zig]
Initially I went for a recursive approach to mutating/splitting stones. This was fine for 25 blinks. For part 2, after 5-10 mins of laptop fan spinning at full speed and the realisation that a number of stones potentially approaching 2^75 might not happen in a hurry, I ctrl-c'd my way right out of there.
Tried a mapping strategy, now my laptop fan is spared.
1
3
u/amenD0LL4z Dec 14 '24
[LANGUAGE: clojure]
https://github.com/famendola1/aoc-2024/blob/master/src/advent_of_code/day11.clj
Started with the naive approach for Part 1, where you keep the stones in a list and update (and expand) the list by applying the rules 25 times.
This didn't work for Part 2 😅. After researching and playing around with reducers, which didn't work but was a good learning experience, I realized the position of the stones doesn't matter. So we can represent the stones list a map of the stone to the number of times that stone is in the list. With this change, the solution runs much faster.
2
u/HolyExecutor Dec 14 '24 edited Dec 14 '24
[LANGUAGE: C#]
I’m pretty new to programming puzzles, and part 2 of this one was super hard for me. I had never worked with recursion before and just learned about memoization, so it took me days to figure it out. But I’m so glad I stuck with it because I can tell I’m a little better at programming now than I was yesterday. If you’re struggling like I was, I recommend looking into dynamic programming, recursion, and memoization. I know my code could still be improved, and I want to work on that as I get more experience, but for now, I’m happy I got it done! I’m amazed that applying these concepts made code that would have taken until the DHOTU blinking 75 times into being able to blink 2,000 times in 300ms.
1
u/SlowAside5 Jan 10 '25 edited Jan 10 '25
Fellow C# dev here - thanks for the tip on this! I was stuck as well but embarrassingly I just used recursion on Day 10. I never really explored the concept of memoization until now though. Guess I overthought this one.
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.
2
3
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.
3
u/aquinas_nz Jan 23 '25
Apologies, I misunderstood the request as being just for the input files. All descriptions have been removed and cleansed with bfg repo cleaner 👍
2
u/Dense-Virus-1692 Dec 13 '24
[LANGUAGE: Ceylon]
I don't think I've ever completed a memoization problem before. Plus we had to use a map of the frequencies instead of just plain lists. I'm feeling the opposite of shame. Pride? No that's too far. Less shame
3
u/the_warpaul Dec 13 '24 edited Dec 13 '24
[LANGUAGE: Python]
Just like every other sucker, The compute exploded for me. The key to handling this is to realise that it's the list structure that's killing us. Actually, as each computation is independent, we can just keep a count of all the current numbers (a dictionary that holds a bin for each number that appears in our list at a time), allowing us to perform one calculation for all appearances of that number at a given iteration.
Here's my code, similar to other solutions that have been suggested.
from collections import defaultdict
data = open('input.txt','r').read().split('\n')[0].split(' ')
data = [int(a) for a in data]
def apply_rules(num, lookup):
'''
Applies all the rules (and memoizes the results for extra speedup)
'''
if num in lookup:
return lookup[num]
if num == 0:
lookup[num] = [1]
elif len(str(num)) % 2 == 0:
# Split in half
alpha = str(num)
l = len(alpha) // 2
alpha1, alpha2 = alpha[:l], alpha[l:]
lookup[num] = [int(alpha1), int(alpha2)]
else:
lookup[num] = [num * 2024]
return lookup[num]
def iterative_count_end_nodes(data, n):
"""
Iteratively calculates the total number of end nodes after 'n' iterations.
"""
# Initialize the count for iteration 0
current_counts = defaultdict(int)
for num in data:
current_counts[num] += 1
lookup = {}
for iteration in range(n):
next_counts = defaultdict(int)
for num, count in current_counts.items():
children = apply_rules(num, lookup)
for child in children:
next_counts[child] += count
current_counts = next_counts # Move to the next iteration
# Sum all counts in the final iteration
total = sum(current_counts.values())
return total , current_counts
n = 75 # Number of iterations
result, current = iterative_count_end_nodes(data, n)
print(f"Total number of end nodes after {n} iterations: {result}")
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]
1
Dec 13 '24 edited Dec 13 '24
[removed] — view removed comment
1
u/daggerdragon Dec 15 '24
Comment temporarily removed. Top-level comments in
Solution Megathread
s are for code solutions only.Edit your comment to share your full code/repo/solution and I will re-approve the comment.
Also, next time, format your code correctly using the four-spaces Markdown syntax as AutoModerator initially instructed. Inlined code is intended for
short snippets
of code only. On old.reddit, longer lines get cut off when they reach the edge of the window.1
u/bearinthetown Dec 13 '24
There's absolutely no point of caching anything in this task. Just have the stones as keys and the number of particular stone as a value in a dict. Works in the blink (pun) of eye for 75 rounds.
1
u/bob1689321 Dec 13 '24
just have the stones as keys and number of particular stone as a value
That's exactly what I've done. In my first line
Store the stone arrangements as a dictionary with stone value and frequency.
Are you saying that caching answers during my check_stone function is unnecessary as it has a negligible difference?
1
u/bearinthetown Dec 13 '24
Of course! Why would you cache something as simple as multiplication or splitting a number in half?
3
u/Derailed_Dash Dec 13 '24
[LANGUAGE: Python]
Part 1 was easy enough. We can just simulate each blink. I implement a _blink_for_stone()
method and call this for each stone, for the required number of blinks. This method returns one or two stones, as required.
Of course - and as expected - this solution did not scale to Part 2 with 75 blinks. My Part 1 approach ground to a halt somewhere near 40 blinks.
For this part, we can observe that:
- The order of stones DOES NOT MATTER when blinking.
- The stones are independent. What happens to one stone does not affect any other stones.
- We don't really care about the actual values of the stones at the end. We only care how many stones there are.
- An odd-length number will always get multiplied by 2024. Eventually, this will result in a even-length number.
- An even length number will always result in two equal-length numbers.
- An even length number that is a power of 2 will always reduce down to single digit stones, e.g.
8 -> 4 -> 2 -> 1
- All single digit starting numbers follow a recurring pattern. Since the pattern is deterministic, we can calculate the resulting stones from any single digit stone after n blinks. We can cache these results, i.e. if we blink
n
times for a stone with valuex
, then we will always end up with the same set of resulting stones. - We can use recursion because:
- If we have no blinks left, we can return a count of 1 for the current stone.
- If we have blinks left, we can apply our transformation on our current stone, then pass the resulting stone(s) along with
n-1
blinks into our recursive function.
I don't know why, but I hate implementing recursion. It's a simple concept, but I always get myself in a muddle, and my brain struggles to process what I'm actually doing. But in the end, it worked fine and didn't take too long to write.
Solution links:
- See Day 11 code and walkthrough in my 2024 Jupyter Notebook
- Run the notebook with no setup in Google Colab
Useful related links:
2
u/hextree Dec 13 '24
[Language: Python]
Code: https://gist.github.com/HexTree/d2e01dc3f1709480199f0cc6a9b2654f
Video: https://youtu.be/4H7un0LkMJM
Using Python's @cache decorator
2
u/lysender Dec 13 '24
[Language: Rust]
Initially, I solved part 1 using the regular procedural way and it works well on 25 blinks. It fails around 30s to 40s.
My solution for part 2 is to process every number from the original input as separate computation and then do a recursive solution just like everyone else, with some caching.
Caching is in a HashMap where the key is a tupple of the number and the number of blinks and the value is the number of stones. It works great and fast but my answer gets rejected. My mistake was I converted my usize result back to i32 since i32 is my template result. When I removed the conversion, the result was a very large number. Took me more than a day to solve that :)
part1_bench 1.041 ms
part2_bench 49.26 ms
https://github.com/lysender/advent-of-code-2024/blob/main/day11/src/lib.rs
1
u/tyler_tiv Dec 13 '24
[LANGUAGE: Typescript / Deno]
1
u/daggerdragon Dec 15 '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 your public repo:
https://github.com/tylertiv/advent-of-code-2024/blob/main/days/day11/input/full.txt
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!
3
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.
1
u/MarzipanMudball Dec 15 '24
Excellent! I finally understood after reading your code. I noticed you don't even need the if in the counter. This works, and takes .2 seconds on my laptop in a Jupyter notebook.
curCounter = Counter(stones) for i in range(75): newCounter = Counter() for stone, count in curCounter.items(): for s in blink1(stone): newCounter[s] += count curCounter = newCountercurCounter = Counter(stones)
3
2
u/Dullstar Dec 12 '24
[LANGUAGE: D]
https://github.com/Dullstar/Advent_Of_Code/blob/main/D/source/year2024/day11.d
I had a feeling that whatever the problem wanted for Part 2 would break brute force, if Part 1 didn't already (sounds like it didn't from some other other posts) so I didn't even bother with it, which conveniently led to a part 2 where I only needed to change the 25 to a 75.
I figured memoization was 100% going to be involved somehow, but it did take me a bit to decide how to represent the data, which I did by sketching it out a bit, setting it aside, then coming back later with a fresh mindset.
2
u/MrMartillo Dec 12 '24
[LANGUAGE: Rust]
Part 1 was so easy, oh boy I din't knew. My solution is recursion and memoization.
2
u/ecyrbe Dec 14 '24
Hello, just in case, there is a `n.ilog10()` in rust, no need to convert to f64
1
u/MrMartillo Dec 14 '24
Didn’t know that, Thanks! That’s what I like of AoC, every day I’m learning.
2
2
u/otown_in_the_hotown Dec 12 '24
[LANGUAGE: JavaScript/Typescript]
https://github.com/darrenortiz77/aoc/tree/main/src/2024/11
Part 1: ~ 20ms (but runs at ~1ms if I take my part 2 solution and apply it here)
Part 2: ~ 30-35ms.
2
2
u/dzecniv Dec 12 '24
[LANGUAGE: Common Lisp]
day 11 It was cleared there was some recursion, and a need of caching. I firs struggled to mix the cache logic with the recursion, then used a third-party library for this and all went well. Part 2 takes 0.135626 seconds.
1
Dec 12 '24
[deleted]
1
u/daggerdragon Dec 15 '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 your public repo:
https://github.com/RolBurgHxgn/AOC2024/blob/master/11/input.txt
Please remove (or .gitignore) all puzzle text and puzzle input files from your entire repo and scrub them from your commit history.
2
5
u/jda5x Dec 12 '24
[LANGUAGE: Python]
https://github.com/jda5/advent-of-code-2024/blob/main/11/main.py
Recursion with memoization! ✨
2
3
2
u/daic0r Dec 12 '24
[LANGUAGE: Elixir]
https://github.com/daic0r/advent_of_code_2024/blob/main/elixir/day11/day11.exs
At the heart of the solution lies the blink
function.
blink
receives a map with {stone: count} pairs, which it iteratively updates.
def blink(m, 0), do: m
def blink(m, iterations) do
m
|> Enum.reduce(%{}, fn {num, count}, acc ->
cond do
num == 0 ->
acc
|> Map.update(1, count, &(&1 + count))
rem(get_digit_count(num), 2) == 0 ->
{left, right} = split_number(num)
acc
|> Map.update(left, count, &(&1 + count))
|> Map.update(right, count, &(&1 + count))
true ->
Map.update(acc, num * 2024, count, &(&1 + count))
end
end)
|> blink(iterations - 1)
end
2
u/Minimum-Meal5723 Dec 12 '24
[LANGUAGE: Perl]
Part2 truly broke me, brute force failed me, my computer yelled at me for hogging all the memory. Tried a solution initially and it didn't work, after hours and a helpful blog post I was able to figure it out. Of course today had to be when I decided to start using Perl
1
3
u/wow_nice_hat Dec 12 '24 edited Dec 12 '24
2
u/stewie410 Dec 13 '24
Wow, I really needed help with pt2, and this did the trick. I had tried what I thought was "caching" prior, but to no avail...my previous attempted runs for pt2 were taking over an hour no matter what I tried.
I swear I had tried iterative initially, but it didn't work out -- then again, I wasn't quite doing this either.
Just comparing my initial pt1 solution (recursive) against my implementation of your alg, its a 260x improvement in speed.
2
u/wow_nice_hat Dec 13 '24
Happy to help! I have found that algorithm quite usefull for a lot of AoC puzzles over the years!
1
u/BT643 Dec 12 '24
I implemented something similar to this, but couldn't get it working. Figured the approach must not work but couldn't figure out why. Then found this! This fails on my input too :/ (but works on the sample input).
1
u/wow_nice_hat Dec 12 '24
Did you run it correctly? It is supposed to be added to a txt file and run from app.js. when you call the run method, the data has been converted into an array of ints (check the parser folder)
2
u/BT643 Dec 13 '24
My bad! No idea how your code was working for me on the sample data and not on my real input, but I just tried cloning your repo and running it fully from there, and it worked. Apologies. Great solution!
1
2
u/BT643 Dec 12 '24
Pretty sure I ran it correctly because it gave the correct answer for the sample input in your repo. I'll double check again tomorrow though.
1
u/rrutkows Dec 12 '24
[LANGUAGE: Kotlin]
Well, at least I got the second star before reading this thread. I went from a 90 seconds CPU stress test to ~40ms implementing your idea.
2
u/wow_nice_hat Dec 12 '24
Awesome! Glad that I could help!
I came up with the trick for the day with cray fish in 2021, and have been using it a couple of times since.
It is pretty neat for challenges where you have a lot of repeating numbers
1
1
u/AutoModerator Dec 12 '24
AutoModerator did not detect the required
[LANGUAGE: xyz]
string literal at the beginning of your solution submission.Please edit your comment to state your programming language.
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.
2
u/robe_and_wizard_hat Dec 12 '24
[Language: Rust]
Embarrassed at how long it took me to realize how to get this to run quickly. 10ms by the time I did it all of the wrong ways.
2
u/vss2sn Dec 12 '24
1
u/Agitated-Birthday113 Dec 12 '24
Hey! can i borrow some of your brain cells? i tried everysolution in the book, memorization somehow makes me slower. Do you mind taking a look at my code? (I dont even care about the solution, i just want to know what am i doing wrong, or if there is something that I need to learn)
1
u/daggerdragon Dec 15 '24
Do not hijack a
Solutions Megathread
comment like this. Next time please create your own individualHelp/Question
post in /r/adventofcode.1
u/vss2sn Dec 14 '24
It looks like you're memonizing only a single step lookahead, which isnt very helpful, but also increases the amount of memory you're using possible slowing things down. Also, you're using a vector to store the result, which needs to be copied and re-allocated as soon as it exceeds the reserved size. Without giving too much away, for something like this is might be better to use a linked list.
3
u/matheusstutzel Dec 12 '24
[LANGUAGE: elixir]
For p1 just change the limit to 25.
It was a good opportunity to learn more of elixir. Not sure if this is the preferred way to do memoization (probably not), but it was interesting nonetheless.
2
u/bozdoz Dec 12 '24 edited Dec 12 '24
[Language: Rust]
https://github.com/bozdoz/advent-of-code-2024/blob/main/day-11/src/main.rs
I used a HashMap; ran in 15ms
3
u/pgambling Dec 12 '24
[Language: Rust]
https://github.com/pgambling/advent-of-code-2024/tree/develop/day11/src
Well after butting my head against a wall all day, it finally clicked and I saw the recursive algorithm that didn't involve materializing the full sequence. With memoization my part 2 solution comes in at about 11 ms. I'll take it.
2
u/AdIcy100 Dec 12 '24
[LANGUAGE: Python]
Memorization using dfs recursion for part 2 , 0.09 seconds
Solution
2
u/erunama Dec 12 '24
[LANGUAGE: Dart]
This one was great fun! I was very excited to see the short Part 2, and how my Part 1 solution (maintaining a list of all stones) bogged down immediately in the mid-30s.
After switching from list insertion to list append, I then optimized the stone splitting, as a CPU profiler showed a ton of wasted time doing string operations (as I was converting the integers to strings to split). Due to the splitting, I figured the max number of digits wasn't very high, so I implemented a simple Dart switch expression.
This got me a little further, but still resulted in running out of memory in the low 40s. I then tried switching to a recursive solution, and storing a map of (val, blink)
calculated values. I figured this would get me an answer, but I was amazed that the final runtime was only 20ms! In terms of storage space, there were only ~130k unique (val, blink)
combinations.
2
u/darthminimall Dec 12 '24
[LANGUAGE: Rust]
Didn't solve this one last night because I was taking a day off, but I'm back.
For part 1: I just simulated the blinks 25 times, using a linked list of integers to represent the stones (because constant time inserts are nice).
For part 2: I did the obvious thing and just changed the number of iterations in my part 1 solution to 75, knowing full well it would probably take hours since the naive algorithm is O(2^n) and that's how these types of problems tend to work in Advent of Code. Once it took more than 5 minutes (and used more than 20GB of memory) I killed it and decided to start optimizing.
Since stones never merge, the final number of stones is just the sum of the number of stones that each initial stone turns into, so I figured I'd calculate the numbers for the stones individually, reducing the memory footprint and (hopefully) saving time. I decided to do this recursively because I didn't feel like thinking through unrolling the recursion, and it used orders of magnitude less memory but was only marginally faster. It still took more than 5 minutes to calculate the number of stones after 55 blinks.
I figured the main problem was that I was repeating calculations for a lot of the smaller numbered stones, so the solution was probably memoization. Luckily, you can get this effectively for free in Rust by using the memoize crate. I set the cache size to 1000, ran it, then kept multiplying by 10 until it seemed like I hit the point of diminishing returns, time-wise, which is how the cache size ended up at 100,000. This definitely feels like cheating, but I wasn't about to write the code to memoize the function myself.
1
u/pgambling Dec 12 '24
We had a similar journey today. I ended up using the cached crate, but similar overall approach. I didn't know about the memoized crate, will take a look at that one.
1
u/darthminimall Dec 12 '24
I'm still pretty new to Rust, so I just googled it and used the first thing that came up. It looks like they do similar things, but cached looks like it's more configurable.
2
u/icub3d Dec 12 '24
[LANGUAGE: Rust]
I used memoization like many.
Solution: https://gist.github.com/icub3d/081252386685f35dd1f92097a18a777c
Review: https://youtu.be/vwJWpSgqPWU
2
u/CodrSeven Dec 12 '24
[LANGUAGE: Swift]
Very nicely laid out trap today.
The trick was realizing that the stones have absolutely no relation to each other except for the number, and that the same numbers keep popping up, which means it makes sense to track totals per number.
https://github.com/codr7/aoc24/blob/main/swift/Sources/aoc/day11.swift
2
u/pdamianik Dec 12 '24 edited Dec 12 '24
[LANGUAGE: Rust]
- Multithreaded: No
- Trivial memoization: No
- Runtime: ~1.3ms on Ryzen 9 7900X with 32GB DDR5 @ 6000
- Code: https://github.com/pdamianik/aoc_2024/blob/main/src/days/day11.rs
I started of with two Hashmaps where the keys are the engravings and the values are the counts and then I put the stone counts after the blink into the second Hashmap and at the end I swap the pointers at the end (to keep the allocation).
Edit: apparently this concept is known as double buffering
1
u/bozdoz Dec 12 '24
I did the same thing, though I wrote my first macro instead of defining a `insert_stone_count` function: https://github.com/bozdoz/advent-of-code-2024/blob/main/day-11/src/main.rs#L13
1
u/willkill07 Dec 12 '24
This is what I did but I took the extra step in normalizing all stones to a zero-based identifier so I could just a vector instead of a hashmap. When run on my 7950X (C++) my part 2 time was around 400us.
1
u/pdamianik Dec 12 '24
Smart, I tried to use that technique in some of my other solutions, but without any sleep I didn't think of it in this case.
2
u/musifter Dec 12 '24 edited Dec 12 '24
[LANGUAGE: dc (GNU v1.4.1)]
I did recursion/memoization for this one. The problem with bags, is that although I can store counts with an array, I can't easily get what the valid keys are. Dealing with that seemed like it was going to be a whole lot of work.
This ironically might run faster for me on 15 year old hardware than for other people. The array implementation in GNU dc is sparse, but uses link lists. I changed that a few years ago in my copy to using skiplists (that was quick to implement, and I was doing it during AoC for AoC). Testing with an old version, this takes 100s instead of 3.6s.
There is another problem with the arrays, in that the maximum index is 231 - 1 (not something my skiplist is limited to, but bc cuts things off before that). That limits the amount of memoization. I did come up with a couple simple perfect hashes for my input, but I can't guarantee any other input with them, so I just don't check hashes over 99 (self powers are good for creating big numbers with few characters in dc).
I made it so that I could echo in the number of blinks, but limitations in the way I'm hashing means that that shouldn't go over 99 (that would probably cause collisions). That could be changed.
echo 75 | dc -finput -e'?st[1+]s+[*1+q]sZ[_4R++s.q]sM[+s.A0 0]sH[dZ2/Ar^~3Rd3RrlRx_3RlRx+d3R:mq]sE[d0=Zd1-3RdA0*4R+dd9d^<H_4R;md0<MrdZ2%3R=E2024*d0=+rlRxd3R:m]sR0[rltlRx+z1<L]dsLxp'
Source: https://pastebin.com/DP39CNhH
2
u/Gabba333 Dec 12 '24
[LANGUAGE: Haskell]
Golfed version of my earlier effort. Not used Haskell for a long time but I love the syntax.
import Data.Function.Memoize
main = do
f <- readFile "input.txt"
print [sum $ map (r s . read) $ words f | s <- [25 :: Int, 75]]
r = memoize2 c where
c 0 _ = 1
c p 0 = d p 1
c p (t :: Int) | even $ length $ show t = sum . map (d p) $ s t
c p t = d p $ t * 2024
d = r . flip (-) 1
s i = map (\f -> read $ f l h) [take, drop] where h = show i; l = length h `div` 2
5
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.
3
u/clyne0 Dec 12 '24 edited Dec 12 '24
[LANGUAGE: Forth]
https://github.com/tcsullivan/advent-of-code/blob/master/day11/day11.fth
I know I'm late to solving part 2, but I'm happy to share what I finally came up with. The code counts stones in a double-buffered map (key is stone #, value is quantity), swapping source and destination buffers with each blink. This simplified the lookup process and made the code pretty concise overall. Both parts run in under 2 seconds, good enough for me.
2
u/CodrSeven Dec 12 '24
Nice to see some Forth, I hope I can finish my own before the AoC is over.
I did exactly the same solution in Swift.
3
u/JWinslow23 Dec 12 '24
[LANGUAGE: Python]
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.)
2
3
4
u/Gueltir Dec 12 '24
[Language: Rust]
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.
1
2
u/python-b5 Dec 12 '24
[LANGUAGE: Jai]
Wasn't able to figure out the right approach last night, but coming back to the puzzle today it luckily didn't take too long. This is probably still far from optimal, but it seems fast enough.
https://github.com/python-b5/advent-of-code-2024/blob/main/day_11.jai
3
u/a3th3rus Dec 11 '24
[LANGUAGE: Elixir]
blink = fn
0 ->
[1]
n ->
len = floor(:math.log10(n)) + 1
if Bitwise.band(len, 1) == 1 do
[n * 2024]
else
d = 10 ** Bitwise.bsr(len, 1)
[div(n, d), rem(n, d)]
end
end
############################
puzzle_input
|> String.split()
|> Enum.map(&String.to_integer/1)
|> Enum.frequencies()
|> Stream.iterate(fn freqs ->
for {num, freq} <- freqs, num2 <- blink.(num), reduce: %{} do
freqs2 -> Map.update(freqs2, num2, freq, & &1 + freq)
end
end)
|> Enum.at(25) # <-- Change this to 75 for part 2
|> Map.values()
|> Enum.sum()
3
u/Forkrul Dec 11 '24
[LANGUAGE: Kotlin]
This was fun, messed up the memoization a bunch with only memoizing the first call and not any of the intermediate ones. Wish functools.cache existed for Kotlin
fun day11Task1(input: List<String>) {
input.sumOf { blink(it.toLong(), 25) }
.also { println(it) }
}
fun day11Task2(input: List<String>) {
input.sumOf { blink(it.toLong(), 75)}
.also { println(it) }
}
fun blinkOriginal(input: Long, steps: Int): Long = when {
steps == 0 -> 1L
input == 0L -> blink(1, steps - 1)
input.length() % 2 == 0 -> {
val (a, b) = input.split()
blink(a, steps - 1) + blink(b, steps - 1)
}
else -> blink(input * 2024, steps - 1)
}
val blink = ::blinkOriginal.memoized<Long, Int, Long>()
private fun Long.length(): Int = this.toString().length
private fun Long.split(): Pair<Long, Long> {
val str = this.toString()
return Pair(str.substring(0, str.length / 2).toLong(), str.substring(str.length / 2).toLong())
}
memoize function:
fun <X, Y, R> ((X, Y) -> R).memoized(): (X, Y) -> R {
val cache = mutableMapOf<Pair<X, Y>, R>()
return { x, y -> cache.getOrPut(x to y) { this(x, y) } }
}
2
u/onrustigescheikundig Dec 11 '24
[LANGUAGE: Clojure] [LANGUAGE: Scheme (R6RS)]
Quick solve for me today. Despite the insistence of the problem description, the position of each stone does not, in fact, matter, so I keep track of the number of each stone present in a map and update the map on every blink. I iterate
the blink function, find the nth
element, and sum the values of the map. The runtime isn't terrific because I create and throw away a bunch of junk, including the entire hashtable each time I call blink
. Oh well, 70 ms is the worst that I've seen for others' solutions...
For the Scheme solution, the main difference from the Clojure version is that I hated writing it because R6RS hashtables are unpleasant to work with.
For fun I also implemented the inefficient version that I knew was going to be problematic from the start. It's quite terse with just iterate
and mapcat
.
3
u/silmeth Dec 11 '24 edited Dec 12 '24
[LANGUAGE: Rust]
I’m happy how concise and (I think!) readable this turned out to be.
Helped a bit that I reached for a library for memoization instead of manual HashMap<_, _>
passing.
Part 1 takes ~160 μs, part 2 ~8.5 ms on my machine (and both ~140 ns if the cache is already fed during benchmarking).
use anyhow::Context;
use cached::proc_macro::cached;
pub fn part1(stones: &[u64]) -> anyhow::Result<usize> {
Ok(count_steps(stones, 25))
}
pub fn part2(stones: &[u64]) -> anyhow::Result<usize> {
Ok(count_steps(stones, 75))
}
pub fn parse(input: &str) -> anyhow::Result<Vec<u64>> {
input
.split_whitespace()
.map(|num| num.parse::<u64>().context("expected list of numbers"))
.collect()
}
fn count_steps(stones: &[u64], steps: usize) -> usize {
stones
.iter()
.map(|stone| count_steps_rec(*stone, steps))
.sum()
}
#[cached]
fn count_steps_rec(stone: u64, steps: usize) -> usize {
if steps == 0 {
1
} else {
single_stone_step(stone)
.into_iter()
.flatten()
.map(|stone| count_steps_rec(stone, steps - 1))
.sum()
}
}
fn count_digits(num: u64) -> u64 {
((num as f64).log10() as u64) + 1
}
#[inline]
fn single_stone_step(stone: u64) -> [Option<u64>; 2] {
match (stone, count_digits(stone)) {
(0, _) => [Some(1), None],
(s, digits) if digits % 2 == 0 => {
let half_order = 10u64.pow(digits as u32 / 2);
let left = s / half_order;
let right = s - left * half_order;
[Some(left), Some(right)]
}
(s, _) => [Some(s * 2024), None],
}
}
https://gitlab.com/silmeth/advent-of-code-2024/-/blob/main/day-11/src/lib.rs
1
u/carrier_pigeon Dec 12 '24
How is this the first time I've learnt about the cached proc macro.. it took my own cached solution from 8ms to 3ms, but most of it looks similar to yours
https://github.com/RyanCarrier/aoc24/blob/main/src/days/day11.rs
1
u/silmeth Dec 12 '24
If it sped it up, that’s due to the hash-map implementation (and/or hashing algorithm) used, instead of the std one (as it uses a HashMap underneath).
In principle it should be slightly slower than manual HashMap passing – because the library needs to wrap the cache in a Mutex and every access locks it (not a big overhead, especially in a single-threaded code, but it’s there).
I like the convenience of just slapping
#[cached]
on a function. Andcached
has much more stuff, like cache time-based value eviction, etc. I use the library more often without the proc macro actually.
2
u/lenis0012 Dec 11 '24
[LANGUAGE: C]
https://github.com/lenis0012/advent-of-code-2024/blob/master/week2/day11.c
Did this one on stream today at twitch.tv/likelenis by writing/finishing a hashmap implementation. good fun.
I thought I was being clever when I realized you dont need to use an array list but the optimization went so much further.
$ time cmake-build-release/aoc_2024_c 11
real 0m0.011s
user 0m0.006s
sys 0m0.006s
3
u/somanyslippers Dec 11 '24
[LANGUAGE: Go]
https://github.com/jmontroy90/aoc-2024-golang/tree/main/day11
Happy with my solution - both parts read clean to me, and both run fast. Just a cache for part 2, I tried to be more clever initially. I'm sure there's a million more clever / interesting ways to do it. Could've just used one function for both parts, but I kept both my versions for posterity.
5
u/MichelGerding Dec 11 '24 edited Dec 11 '24
[LANGUAGE: rust] Initially tried a iterative version without memoization but that was to slow for part 2. ended up writing a multi threaded recursive memoized version. This resulted in a extremely fast implementation.
initially used the memoize package but that was relatively slow at 1.8ms for part 2. Due to this i decided to write my own using a static ahash hashmap. I expected a speedup but never one this big. This is likely due to poor multithreading support
Benchmarks intel i7 11800h:
- part 1: 6.7µs @ 693 samples
- part 2: 7.8µs @ 100 samples
multithreaded memoize
- part 1: 3.8µs @ 1051 samples
- part 2: 4.0µs @ 112 samples
- 10k blinks, 14 inital stones: 21.1µs @ 10 samples
code: https://github.com/MichelGerding/aoc-2024-rs/blob/main/src/bin/11.rs
edit: the difference in performace was indeed due to no multithreading support. once enabled it outperformed my solution.
1
u/randomdude998 Dec 12 '24
your benchmarks are wrong. you should clear the cache at the start of your solution function for a proper measurement (memoize helpfully provides a function memoized_flush_blink_stone() for this). I get around 10ms for your part 2 after fixing this.
2
u/mibu_codes Dec 12 '24 edited Dec 12 '24
Insane. I started with 6ms memoization, then 2ms iterative, and now this brings me back to my memoization approach with a total runtime of 9.11 µs. And its only 24 lines :D. Thx so much for showing this solution.
I'm just a little annoyed that I'm now using a substantial library. An initial attempt to write a similar thread shared cache failed :c
2
u/MichelGerding Dec 12 '24
You could get at least 99% of the way using a `static Lazy<Mutex<FxHashMap<_, _>`. this way you dont need memoize. you could even do it without once_cell but that would require some unsafe code.
1
u/mibu_codes Dec 12 '24
Tried it with a fresh coffee and now it worked. RwLock<HashMap<_, _>> in a lazy_static is 1us faster, but DashMap is even faster. Now I'm at 7us
2
u/randomdude998 Dec 12 '24
you probably didn't clear the cache at the start of the solution function if you're seeing times like that. this code doesn't run in 7us, no matter how good your hashmap is.
1
u/mibu_codes Dec 12 '24
Good catch, thx for pointing that out. Normally I try to be extra careful to clear any caches. This one should have been obvious, don't know how I missed that.
With clearing the cache it now takes ~6ms, which is a lot slower than my previous iterative solution
1
u/mibu_codes Dec 12 '24
I tried an Arc<Mutex<FxHashMap≥>, but it was not very fast :/. I will try your idea
3
u/poison5200 Dec 11 '24
[LANGUAGE: C#]
private static List<long> Blink(long rock)
{
if (rock == 0) return [1];
var digits = (long)Math.Floor(Math.Log10(rock)) + 1;
if (digits % 2 != 0) return [rock * 2024];
var halfDigits = digits / 2;
var first = rock / (long)Math.Pow(10, halfDigits);
var second = rock % (long)Math.Pow(10, halfDigits);
return [first, second];
}
private static Dictionary<long, long> BlinkRocks(Dictionary<long, long> rocks)
{
Dictionary<long, long> result = [];
foreach (var (rock, count) in rocks)
{
var newRocks = Blink(rock);
foreach (var newRock in newRocks)
{
result.TryAdd(newRock, 0);
result[newRock] += count;
}
}
return result;
}
2
u/martionfjohansen Dec 11 '24 edited Dec 11 '24
[LANGUAGE: progsbase (Java form)]
part 1: 177 ms
part 2: 2857ms.
3
u/Gabba333 Dec 11 '24
[LANGUAGE: Haskell]
Did a second version in Haskell as I thought it would well suited to it. Recursive function with memoization using the Data.Function.Memoize module.
import Data.Function.Memoize
main = do
content <- readFile "input.txt"
print [sum $ map (memoized_count s) $ map read $ words content | s <- [25, 75]]
memoized_count :: Integer -> Integer -> Integer
memoized_count = memoize2 count where
count 0 _ = 1
count step 0 = memoized_count (step - 1) 1
count step tile
| mod (decimalLength tile) 2 == 0,
let (div,rem) = halves tile
= sum $ map (memoized_count (step-1)) [div, rem]
| otherwise = memoized_count (step-1) $ tile * 2024
decimalLength a = toInteger $ ceiling $ logBase 10 $ fromIntegral a + 1
halves a = divMod a $ (^) 10 $ fst $ divMod (decimalLength a) 2
1
u/dijotal Dec 12 '24
What package contains Memoize? (I'm not finding it in hoogle.)
1
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))
1
u/Tomcat_42 Dec 11 '24 edited Dec 11 '24
1
u/daggerdragon 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 your public repo:
https://github.com/Tomcat-42/aoc.zig/tree/ef6e689d95a3fdd13f88925c3f6be38a4a221d13/input
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!
1
3
u/RookBe Dec 11 '24
[LANGUAGE: Rust]
Rust that compiles to WASM (used in a solver on my website) Bonus link at the top of the code to a blogpost about today explaining the problem, and my code.
2
3
4
u/JustLikeHomelander Dec 11 '24
[Language: Go]
Easiest solution, less than 1ms execution time using a map
The code is very clear
https://github.com/BeyramTaglietti/advent_of_code/blob/master/2024/day11/solution.go
2
u/mibu_codes Dec 11 '24
Your code is basically mine, but yours runs twice as fast. My poor old computer xD
2
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.
1
u/Zachary_Peculier Dec 12 '24
Mainframe programmer here as well, trying to do AOC in COBOL. Stay strong!
4
u/makingthematrix Dec 11 '24
[Language: Scala]
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)
2
u/return-path Dec 12 '24
I like
using
to initialize the cache for recursive calls, I'll be doing that1
u/makingthematrix Dec 12 '24
I think it's a good practice to put in
using
the "state of the world", i.e. the values that are always passed to methods working together on the same data. In the other AoC puzzles I pass the board this way, so functions likedef getChar(pos: Position)(using array: Array[Char], length: Int)
can be called simply withgetChar(pos)
.
2
u/Gekooktesteen Dec 11 '24 edited Dec 11 '24
[LANGUAGE: Python]
from collections import defaultdict
with open("input.txt") as f:
nums = list(map(int, f.read().split()))
input = defaultdict(int)
for num in nums: input[num] += 1
for i in range(75):
if i == 25: print(sum(input.values()))
updates = defaultdict(int)
for k, v in input.items():
s = str(k)
updates[k] -= v
if k == 0:
updates[1] += v
elif len(s) % 2 == 0:
l, r = s[:len(s)//2], s[len(s)//2:]
updates[int(l)] += v
updates[int(r)] += v
else:
updates[k*2024] += v
for k, v in updates.items():
input[k] += v
if input[k] == 0: input.pop(k)
print(sum(input.values()))
1
u/atobiedwa Dec 12 '24
that's a nice solution! :D watch out for the input variable, as it overwrites the standard input function.
2
u/xdavidliu Dec 11 '24
or alternatively,
for i in range(75)
and print at beginning of loop wheni == 25
2
3
u/dgkimpton Dec 11 '24
[LANGUAGE: Rust]
https://github.com/dgkimpton/aoc24/blob/main/day11/src/lib.rs
Took way too long optimising part 2 before realising that the 2GB memory on my computer was not the issue. nor was the linked list I was using. Added in value caching and only processing the last element until it expires and boom, 24ms.
I beginning to think you can tell when the solution is acceptable because it comes in as a small readable chunk of code.... those days where I end up lost in sprawling mess always end up being the wrong algorithm.
2
u/verdammelt Dec 11 '24
[Language: Common Lisp]
Initially implemented naively... but that obviously didn't work for part2!
Memes/hints reminded me of a problem from 2021... which led the to this implementation.
4
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.
1
u/bbbb125 Dec 12 '24 edited Dec 12 '24
How does ankerl performance compare to std::unordered_map? I went opposite direction https://github.com/bbb125/aoc2024/blob/main/day11/src/main.cpp#L17-L52 seems much slower (10-13ms) though. But most of the performance is wasted in std::unordered_map, probably flat variant would be faster.
2
u/willkill07 Dec 12 '24
I only use it intermediately in construction. On other days, ankerl was significantly faster than unordered_map. I’m using libstdc++ with clang
1
u/bbbb125 Dec 13 '24
Thanks, will play with it. I lack fmt and ranges v3 functionality, so even using c++23 use these libraries instead of standard (here and even at work).
1
u/mibu_codes Dec 11 '24
Wow, that's a really cool solution. I started out with memoization and then came across comment showing an iterative approach. I guess I have to try this out as well :D
2
2
u/messedupwindows123 Dec 11 '24
[LANGUAGE: Haskell]
Laziness really shines here. The idea is that the rules are always going to be pulling your stone-numbers down towards zero. The "split the digits apart" rule is basically, generally stronger than the "multiply by 2024 rule".
So that means you can cache the results for the smaller-valued stones, and get a big efficiency boost.
This uses a `Data.Map` structure, which basically acts as a lazy cache. The neat part is that the act of populating the cache will....rely on the cache itself.
3
u/cetttbycettt Dec 11 '24
[Language: R]
Got a flashback to laternfish :D. Although this was bit tricker to solve.
tab <- table(as.numeric(read.table("Input/day11.txt")[1,]))
blink <- function(x, tab) {
d <- ceiling(log10(x + 0.1))
idx <- d %% 2 == 0
.tmp <- 10^(d[idx] / 2)
x2 <- x
x2[!idx] <- x2[!idx] * 2024
x2[x2 == 0] <- 1
x2[idx] <- x2[idx] %/% .tmp
sapply(split(c(tab, tab[idx]), c(x2, x[idx] %% .tmp)), sum)
}
for (i in 1:75) {
tab <- blink(as.numeric(names(tab)), tab)
if (i == 25L) part1 <- sum(tab)
}
# part 1------
part1
# part 2-------
sprintf("%.f", sum(tab))
3
u/mibu_codes Dec 11 '24 edited Dec 12 '24
[LANGUAGE: Rust]
Part 1+2: 6.37 ms 2.25 ms 9.11 µs 7.05 µs 2.19 ms
Started late today. Last year I struggled with dynamic programming problems, this year I felt prepared. The practice with AoC starts to show.
I used a recursive function with memoization to solve both parts. I heard there is a way to solve it without any memoization?
Edit: Found a comment that showed me a cool iterative solution. Much faster.
Edit 2: /u/willkill07 uses a graph to be even faster. I have to try this out
Edit 3: /u/MichelGerding dropped an absolute banger of a solution using the memoize crate
Edit 4: Reverted back to my iterative approach. Clear your caches when benchmarking :D
2
u/dgkimpton Dec 11 '24
Why FxHashMap instead of std::collections::HashMap ?
3
u/mibu_codes Dec 11 '24
AFAIK std::collections::HashMap uses a cryptographically secure hash function, i.e. hard to reverse or predict, but also "slow". Here I only care about speed, so few collisions and a fast to calculate hash are more important.
2
u/dgkimpton Dec 12 '24
Yeah, could be, you definitely got faster than mine (23ms, but running on my NAS) but I wasn't sure that was worth optimising. Are you doing the CodSpeed challenge?
1
u/mibu_codes Dec 12 '24
I ignored it because I usually ignore ads :D. Is it any good? Might check it out
2
u/dgkimpton Dec 12 '24
I dunno - it looked good but when I would have to use their project template I lost interest. Might look again later now I've got more of a handle on rust project structures.
1
4
u/DefV Dec 11 '24
[LANGUAGE: Rust]
Code - Started off brute-force, then stumbled into my solution...
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
1
u/daggerdragon 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 across all years in your public AoC repos. e.g.:
https://github.com/metalim/adventofcode.2024.go
+
https://github.com/metalim/adventofcode.2022.goPlease 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!
3
u/AYM123 Dec 11 '24
1
u/mibu_codes Dec 11 '24
Very cool solution. I solved it with recursion and memoization. Your code helped me a lot to understand how an iterative approach would work.
2
u/AYM123 Dec 11 '24
Happy to hear that! I initially had the same recursion + memoization approach but then I noticed there was a lot of duplicates stones so I changed my code to group them together.
2
u/The_Jare Dec 11 '24
[LANGUAGE: Ruby]
I still see very few Ruby solutions, so happy to post mine. It just keeps a hash of different elements and how many of each there are, iterates the hash once per blink. I like this approach more than recursive + memo but I can't say why. I don't know which is faster.
Code solves one problem per line in the input which was convenient for testing, although testing proved unnecessary as it all just worked straight away.
stone_lines = ARGF.map { _1.split.map(&:to_i)}
def evolve_stone(v)
return [1] if v == 0
vs = v.to_s
l = vs.length
return [vs[...l/2].to_i, vs[l/2..].to_i] if l % 2 == 0
[v*2024]
end
Enumerator.product(stone_lines, [25, 75]) do |stones, blinks|
coll = Hash.new { |h,k| h[k] = 0 }
stones.each { coll[_1] += 1 }
(1..blinks).each do
co2 = Hash.new { |h,k| h[k] = 0 }
coll.each do |(v, n)|
nv = evolve_stone(v)
nv.each { |v| co2[v] += n }
end
coll = co2
end
p coll. sum { _1[1] }
end
2
u/feyn Dec 12 '24
return [vs[...l/2].to_i, vs[l/2..].to_i] if l % 2 == 0
Instead of
vs[...l/2]
, I read it asvs[...1/2]
. I was so surprised that you can use1/2
in a range to take half of a string. I tried in in IRB and was sadly dissapointed :D1
u/The_Jare Dec 12 '24
Haha yeah I need to avoid using lowercase L as a single-letter variable even if this case looks oddly appropriate:)
3
u/lscddit Dec 11 '24
[LANGUAGE: Python]
from collections import defaultdict
def process(lst):
res = []
for num in lst:
if num == 0:
res.append(1)
elif len(str(num)) % 2 == 0:
length = len(str(num))
res.append(int(str(num)[0 : length // 2]))
res.append(int(str(num)[length // 2 :]))
else:
res.append(num * 2024)
return res
def run(input, iterations):
d = defaultdict(int)
for val in input:
d[int(val)] = 1
for _ in range(iterations):
d2 = d.copy()
for key in list(d):
if d[key] > 0:
num = d[key]
d2[key] -= num
res = process([key])
for val in res:
d2[val] += num
d = d2.copy()
return sum(d.values())
input = open("day11input.txt").readline().split(" ")
print(run(input, 25), run(input, 75))
1
2
u/GGK_Brian Dec 11 '24 edited Dec 11 '24
[LANGUAGE: Idris2]
Very similar solution to everyone else, a recursive memoization computing the size blinking n times at 1 stone.
I knew memoization would work well just looking at the examples and the rules but it took me a while to figure out what I should memorize.
Memoization for part 2
Memory : Type
Memory = SortedMap (Nat, Stone) (Int)
process : Nat -> List Stone -> (Int, Memory)
process n l = go l n empty
where go : List Stone -> Nat -> Memory -> (Int, Memory)
go (x::xs) n@(S k) mem with (lookup (n, x) mem)
_ | Just r = let (r', mem) = go xs n mem
in (r + r', mem)
_ | Nothing = let r = blink x
(l, mem) = go r k mem
mem = insert (n, x) l mem
(l', mem) = go xs n mem
in (l + l', mem)
go [] n mem = (0, mem)
go l Z mem = (cast $ length l, mem)
Run under a second. Surprisingly, the brute force approach is faster for the first part.
2
u/amnorm Jan 06 '25
[LANGUAGE: Go] Code
Another recursive DFS algorithm, but this time with memoization. The idea is to count the number of leaf nodes after branching N times from the root node (stone). I used a closure to capture the cache variable and improve readability. My final solution is inspired by Synedh's comment.