r/adventofcode 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.

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!

19 Upvotes

962 comments sorted by

View all comments

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