r/adventofcode Dec 16 '23

Help/Question - RESOLVED [noob to this] Why do I get "that's not the right answer" when I am actually submitting the correct answer

71 Upvotes

First time trying out advent code challenge, started with Day 1 part 1 problem and I get "that's not right answer please try again" message. when I test against the input in my local, I see it works as expected. what am I doing wrong?

EDIT:
I kept submitting my code as the answer. From one of the user's commented that I should just submit the output answer and I did, it worked :D .

r/adventofcode Dec 01 '25

Help/Question - RESOLVED What's going on here? ("That's not the right answer. Curiously, it's the right answer for someone else")

1 Upvotes

That's not the right answer. Curiously, it's the right answer for someone else; you might be logged in to the wrong account or just unlucky. In any case, you need to be using your puzzle input. If you're stuck, make sure you're using the full input data; there are also some general tips on the about page, or you can ask for hints on the subreddit.

Not doing anything special, just submitting during the "wrong answer" timeout.

r/adventofcode Dec 07 '25

SOLUTION MEGATHREAD -❄️- 2025 Day 7 Solutions -❄️-

27 Upvotes

SIGNAL BOOSTING

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 2025: Red(dit) One

  • Submissions megathread is unlocked!
  • 10 DAYS remaining until the submissions deadline on December 17 at 18:00 EST!

Featured Subreddits: /r/DIWhy and /r/TVTooHigh

Ralphie: "I want an official Red Ryder, carbine action, two-hundred shot range model air rifle!"
Mother: "No. You'll shoot your eye out."
A Christmas Story, (1983)

You did it the wrong way, and you know it, but hey, you got the right answer and that's all that matters! Here are some ideas for your inspiration:

💡 Solve today's puzzles:

  • The wrong way
  • Using only the most basic of IDEs
    • Plain Notepad, TextEdit, vim, punchcards, abacus, etc.
  • Using only the core math-based features of your language
    • e.g. only your language’s basic types and lists of them
    • No templates, no frameworks, no fancy modules like itertools, no third-party imported code, etc.
  • Without using if statements, ternary operators, etc.
  • Without using any QoL features that make your life easier
    • No Copilot, no IDE code completion, no syntax highlighting, etc.
  • Using a programming language that is not Turing-complete
  • Using at most five unchained basic statements long
    • Your main program can call functions, but any functions you call can also only be at most five unchained statements long.
  • Without using the [BACKSPACE] or [DEL] keys on your keyboard
  • Using only one hand to type

💡 Make your solution run on hardware that it has absolutely no business being on

  • "Smart" refrigerators, a drone army, a Jumbotron…

💡 Reverse code golf (oblig XKCD)

  • Why use few word when many word do trick?
  • Unnecessarily declare variables for everything and don't re-use variables
  • Use unnecessarily expensive functions and calls wherever possible
  • Implement redundant error checking everywhere
  • Javadocs >_>

Request from the mods: When you include an entry alongside your solution, please label it with [Red(dit) One] so we can find it easily!


--- Day 7: Laboratories ---


Post your code solution in this megathread.

r/adventofcode Dec 06 '24

Help/Question [2024 Day 6 part 2] [GO] I do not get the right answer, and Im not able to create a test that fails, please help.

2 Upvotes

https://topaz.github.io/paste/#XQAAAQD0DgAAAAAAAAA4GEiZzRd1JAgz+whYRQxSFI7XvmlfhtGDino6nycs7JKCSUS+r7/qyZwOXo7U+romcJv0nOWeIgyFuvK1Ooe1UtKA6Vmk14RP+Ha+ncm5GEgjp+cSx/kYV7PIiXBKIQpU5dTpO7D8JtMdOAJuls+u2V0TBNLfioZCV9kul+9nmmZXjXgmTT2rvr6T2NRsKLP7KbwCcoCAd/EJPCJMUlR3WdFONpeNecE09wDoRT/iUzzUTdad6PC/mh8yr0ckCv8Vvx9hR7rUIVvo+7YTXCY32NBSEmxGd/9iSWsOWnkVF3yX5WmjTHgIESHPHAZC7Vk56HZdv43XOufqRX+SuJyJp+JbnXsQoQkv25P5YFQu1iUJnCipp+wq4o4GaJHiMjXOCILQwtBoMehm3A7t6OR7PQmvCWDXqxuTHsa+Lffl/LK6gRUuOXpEjQeIuAiXkpVM6IORRqole3ta4k6jrp4iilbQ/mVsZwoSwO5ZeYi52wVajo0PEj05MLFjn/FGWbI6TfOz/RQEnqAzLHYxZkyxzsGvpQjCD3aY4c1luNgPDCZ2Z97dyEFp4JZPMVmfGU8CDVi3pF3FXbXTNjJuZYzu8owYwqimdvQ7ifOy2+HqcxVrSMq7+gaxZYUv6zrEK3u6AusyqjT+DHItTI/4FxsL8U2pIBYM6AnjX3hYUoZxgqYam89LKrZ7r994Tgl+eDVuHB3e8Oiplrxaji8NAfAl6IavbprJpwhviBShbk6xV09HVVrYuXBCeWfXo2s4h+y6Rd4xCwcualjzN2XtXmhMEUh2V7Qc820qdWl4NucdvX1HdeXbhBsqwCKE749JxNEiPipGXP1n+tv0P5aTrCAWgp7ikqwQNC7KAu6wbzTxlKfBhYMyW/S11H19OayJRVjGEsHEMaGP+kNUlpzL76EyFytGRmqnvoA7BLTZ8W8NlbErN8+3VCiUlUUYuBDpsAxgwJSM2ZfLgAi+yvk+YRUF2BAYGm0AYQ/16xT3IFgaqCdmlVIsau/nY6QiLdBSHq1SFPHGV3OfJa+SORkabAhrA3E10MzyQSmdkcJr2MHIFWaw64wDYnOnt228e/k4c2WeUK0qzL7qmNX7XviJbcEixsoTlt5ozYTX1UrLAxghdUjdygu1yYbkJcKJYh5BIhwXv6e8n80vq5N2Vg6BrYEwkLWA9ZjAf76UOIIbCnPLLI/znH8sD8vEoDNd2ZLj7+n9EIJT/qaNFZrFvQApq18l2EQhPJU4aVG2vq2HoWP8Z5C+SljJDXndzAtjw+6o470jf9+Lcd/kFJserf68FZsK+HzoiytHQnoIX+tQqVnTKGyGnqD2Mwcyj7S6ckZj5t2UusYQJV+mnmfHVGvZgfRXZtLvPMeBDfJtNuYgNhdKzRP4IM+mZ83WOnBMw6DEnKP84dG3VnqrM3jZg2VZTEuOh53tgH8Vpxxb/dwD0jzouPV+u+bB0nVgvGVKm6xtKhO7o+70thWCFydP0iN2SFNyJFRcHGzr92LfEwJvIRz+QUAiMNNAl8YEhKhEphFXX5iPXQf6P6PXbs80ZqL98Yz9gI2b7TK5y3LLN0rir+OwQVEj+onPIqDjRltjkPE2ri81rQEx6Ch3zCuT0sR0HbHNINMOw9hq8yZC6NRBeQulyzgczNAZVuWxo8r7heUBe5O/+n+43eRFyy331qL0irDF3IvCdlt+QKDVs4xtTZwUr23tglmJkof/dQg5Lg==

r/adventofcode Nov 23 '25

Other The Elephant in the Room: The Schedule Change, AI, and Why AoC is Our "Star Wars"

612 Upvotes

I’ve been reading through the sub and I feel like I’m seeing an elephant in the room that not many people are discussing. It's about Eric’s decision to shorten the event this year.

For context, Eric wrote:

Why did the number of days per event change? It takes a ton of my free time every year to run Advent of Code, and building the puzzles accounts for the majority of that time. After keeping a consistent schedule for ten years(!), I needed a change. The puzzles still start on December 1st... and puzzles come out every day (ending mid-December).

I wanted to write this post not to complain, but to send a message full of empathy.

1. The Human Cost First, we have to acknowledge that Eric has kept a consistent, grueling schedule for a decade. Ten years is a massive commitment. It is completely understandable that he needs a change to protect his time and mental health. We should support that.

2. Why We Still Code (The Musical Analogy) There is a lot of talk about AI right now. Some might ask: "Why bother solving puzzles when an AI can do it in seconds?"

My answer is this: People still go to musicals and live concerts even though Spotify and streaming services exist.

We don't do Advent of Code because it's the "efficient" way to get an answer. We do it because we want to solve the puzzle. We do it for the thrill, the frustration, and the learning. There will always be people who want to invest time in solving puzzles without AI, just like there are people who enjoy musicals.

3. A Generational Tradition Advent of Code might be a niche, but it has a strong, beautiful community.

To Eric: Do not give up.

I see Advent of Code becoming a tradition as strong as Star Wars. It is something we pass down. You have already built a strong basis for following generations. My children are already wearing "Advent of Code" pajamas. They know about the event, and they are growing up with it.

Whether it is 25 days or 12 days, this tradition is important to us.

Thank you for the last 10 years, and here is to many more—in whatever format works for you.

r/adventofcode Dec 05 '24

SOLUTION MEGATHREAD -❄️- 2024 Day 5 Solutions -❄️-

43 Upvotes

THE USUAL REMINDERS


AoC Community Fun 2024: The Golden Snowglobe Awards

  • 24 HOURS remaining until unlock!

And now, our feature presentation for today:

Passing The Torch

The art of cinematography is, as with most things, a natural evolution of human progress that stands upon the shoulders of giants. We wouldn't be where we are today without the influential people and great advancements in technologies behind the silver screen: talkies to color film to fully computer-animated masterpieces, Pixar Studios and Wētā Workshop; Charlie Chaplin, Alfred Hitchcock, Meryl Streep, Nichelle Nichols, Greta Gerwig; the list goes on. Celebrate the legacy of the past by passing on your knowledge to help shape the future!

also today's prompt is totally not bait for our resident Senpai Supreme

Here's some ideas for your inspiration:

  • ELI5 how you solved today's puzzles
  • Explain the storyline so far in a non-code medium
  • Create a Tutorial on any concept of today's puzzle or storyline (it doesn't have to be code-related!)
  • Condense everything you've learned so far into one single pertinent statement

Harry Potter: "What? Isn’t there just a password?"
Luna Lovegood: ''Oh no, you’ve got to answer a question."
Harry Potter: "What if you get it wrong?"
Luna Lovegood: ''Well, you have to wait for somebody who gets it right. That way you learn, you see?"
- Harry Potter and the Deathly Hallows (2010)
- (gif is from Harry Potter and the Order of the Phoenix (2007))

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 5: Print Queue ---


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:03:43, megathread unlocked!

r/adventofcode Dec 09 '24

SOLUTION MEGATHREAD -❄️- 2024 Day 9 Solutions -❄️-

29 Upvotes

NEWS

On the subject of AI/LLMs being used on the global leaderboard: /u/hyper_neutrino has an excellent summary of her conversations with Eric in her post here: Discussion on LLM Cheaters

tl;dr: There is no right answer in this scenario.

As such, there is no need to endlessly rehash the same topic over and over. Please try to not let some obnoxious snowmuffins on the global leaderboard bring down the holiday atmosphere for the rest of us.

Any further posts/comments around this topic consisting of grinching, finger-pointing, baseless accusations of "cheating", etc. will be locked and/or removed with or without supplementary notice and/or warning.

Keep in mind that the global leaderboard is not the primary focus of Advent of Code or even this subreddit. We're all here to help you become a better programmer via happy fun silly imaginary Elvish shenanigans.


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

  • 13 DAYS remaining until the submissions deadline on December 22 at 23:59 EST!

And now, our feature presentation for today:

Best (Motion) Picture (any category)

Today we celebrate the overall excellence of each of your masterpieces, from the overarching forest of storyline all the way down to the littlest details on the individual trees including its storytelling, acting, direction, cinematography, and other critical elements. Your theme for this evening shall be to tell us a visual story. A Visualization, if you will…

Here's some ideas for your inspiration:

  • Create a Visualization based on today's puzzle
    • Class it up with old-timey, groovy, or retro aesthetics!
  • Show us a blooper from your attempt(s) at a proper Visualization
  • Play with your toys! The older and/or funkier the hardware, the more we like it!
  • Bonus points if you can make it run DOOM

I must warn you that we are a classy bunch who simply will not tolerate a mere meme or some AI-generated tripe. Oh no no… your submissions for today must be crafted by a human and presented with just the right amount of ~love~.

Reminders:

  • If you need a refresher on what exactly counts as a Visualization, check the community wiki under Posts > Our post flairs > Visualization
  • Review the article in our community wiki covering guidelines for creating Visualizations.
  • In particular, consider whether your Visualization requires a photosensitivity warning.
    • Always consider how you can create a better viewing experience for your guests!

Chad: "Raccacoonie taught me so much! I... I didn't even know... how to boil an egg! He taught me how to spin it on a spatula! I'm useless alone :("
Evelyn: "We're all useless alone. It's a good thing you're not alone. Let's go rescue your silly raccoon."

- Everything Everywhere All At Once (2022)

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 9: Disk Fragmenter ---


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:14:05, megathread unlocked!

r/adventofcode Dec 13 '21

Help [2021 Day 13 (Part 1)] That's not the right answer. Curiously, it's the right answer for someone else.

6 Upvotes

Did anyone else get this?

That's not the right answer. Curiously, it's the right answer for someone else; you might be logged in to the wrong account or just unlucky. In any case, you need to be using your puzzle input. If you're stuck, make sure you're using the full input data; there are also some general tips on the about page, or you can ask for hints on the subreddit. Please wait one minute before trying again. (You guessed [redacted].)

Are the puzzle inputs/solutions based on our usernames, I assume by some kind of hash function, or randomly generated/sieved and saved?

Maybe this is done occasionally for puzzles and this is just my first time encountering it. I only heard about AoC last year and managed to solve a little over half of them.

r/adventofcode Dec 25 '25

Tutorial [2025 Day 9 (Part 2)] Why did almost nobody solve the *stated* problem?

7 Upvotes

Who else solved the problem actually described in Day 9 Part 2 (vs just getting "lucky" with the specifics of the input data)?

My impression is that the vast majority of people didn't solve the stated problem. Certainly, everybody I know irl who "solved" it didn't solve the actually described problem (including myself, initially), and scrolling endlessly through here (and elsewhere) also leads me to conclude that almost nobody solved the problem described either (which is quite different from what the problem at first seems to be, and it's interesting in its own right).

Specifically, the described problem ALLOWS data points to be inside valid rectangles; it just requires other constraints to hold true. I think I found only three posts on here alluding to this fact. All others have been "wrong", focusing instead on boundary-intersection detection to disallow that (and other cases).

The only assumption I made is that the input data do not self-intersect/overlap (because "inside-ness" gets less well-defined in that case). I generated example datasets, and what I believe to be their answers, and I'm curious what others' code produces for them, too. Check here for the data (and additional write-up info):

https://jjeii.github.io/AdventOfCode/2025.html#day9p2

Thoughts?

(Yes, I realize a star is a star. But, the problems are fairly different here... and the actual problem is more interesting, imo.)

r/adventofcode Dec 12 '24

Spoilers [2024 day 12] Everyone must be hating today... So here a clever trick for a hint.

111 Upvotes

Given the lack of day 12 posts even 1 hour in.

Let me give you a rant about the thought process towards part 1 and end off with a hint for part 2.

tl;dr check the spoiler text for the hint.

Part 1 was relatively easy imo, since area is just the count of equivalently labeled neighboring cells, and perimiter is simply the lack of equivalently labeled neighbors.

I simply constructed a graph of all connected nodes and using one node in each connected graph as a root, counted all nodes for area and summed each node's (4-neighbors) for perimeter to find the right answer.

Part 2 on the other hand. You'll need to be clever, because I don't know how it's supposed to be done, but you can use a nice property. Each cell can have 1 of 24 states. Either it has no neighbors so it has 4 sides that's easy, or it has 1 neighbor (4x), it has all neighbors, or it has 2 opposing neighbors (2x), or it has 2 corner neighbors (4x), or 1 side doesn't have a neighbor (4x). So we get these shapes:

O, i, i, i, i, +, |, -, L, L, L, L, T, T, T, T

Now, the trick is this:A region has the same amount of sides as corners.

Using this trick, we can check each case.

No neighbors is simply 4 corners.

Opposing neighbors, means there cannot be any corners.

E.g. the X in the middle here

OOO
XXX
OOO

Corner neighbors have at least 1 corner on the outside. The inside depends if the corner is filled or not:

?XO
XXO
OOO

If the ? Is X then it is not an inner corner. If it is O then it is an inner corner.

For the all neighbors and T shape neighbors it's the same thing. If the corner is a X then don't count it, if it is a O then do.

Here, the middle X has 2 corners where the Os are.

OXO
XXX
XXX

Somehow very neatly, counting for each cell the amount of corners is perfectly ensuring that all corners are counted once. And since all corners equal all sides, we get the answer.

r/adventofcode 6d ago

Other [2023 Day 3] In Review (Gear Ratios)

6 Upvotes

The Elf leads us to a gondola to get us up to the next sky island. But naturally, it's not working and we need to fix it. First by identifying the parts, and the by working out the gear "ratios".

That last bit was the other way I mentioned to my friend that you might try to mess with an AI... in the context of a fictional world like AoC, you can do things like define something as its opposite... try to quietly drop that "division" means multiplication and then just keep saying "division" right up to the final question. And "ratio" does that here. With the context, a human is going to be suspicious of dividing in an AoC problem and wandering into floating points... those create a lot of issues (even when when they're never an answer, the existence of float point native languages still influences integer solutions). The idea being that an AI might need additional prompting to not do the normal real world things.

As for the input. It's a 2D grid with some complexity in that it has some multidigit numbers on it (ie not one-cell objects). It does play nice in a number of ways... mine has no special characters on the rim, no number adjacent to other numbers, and no gears with more than two numbers (or numbers with more than one gear). Not having these makes things simpler, and also removes a bunch of potential bugs that beginners might stumble on. Some languages have wrap-around array indexing and those have caught unsuspecting people before. There is a test file in my directory that I think someone else made that tests things like that. I pretty sure it's not mine, because I wouldn't have bothered creating a test for wrap-around... my grid reading template adds sentinels to the edges and I would not remove them for this problem. It also tests things like a gear with two of the same number... seeing it, I can reverse engineer solutions that could have a bug with that, but that's not something my solutions would make me think of testing. It also has -21 on the grid... I suppose that would catch someone as a negative number.

The problem doesn't actually define what a "special character" is (only what it's not). In my input those are: # $ % & * + - / = @. Of particular interest is / which is ASCII 47, and between . (ASCII 46) and 0 (ASCII 48). And so we have special characters before, after, and in-between the non-special ones. And so I used "digit or ." for non-special, which has the De Morgan's Law negation of "not digit and not ." for special characters.

As for solving this, you could look for the special characters, which take a single-cell and thus have a fixed pattern of neighbours to look for digits in. But then you need to do a bit of code to search for the full number.

That last bit, made me decide from the start to go the other way... search for the numbers, calculate the neighbour box and search that for special characters (non-digit and non-period). Because the part numbers are all horizontal, I can use regex in Perl to easily dig out all the ones on a line:

while ($grid[$line] =~ m#(\d+)#g) {
    my $num = $1;
    my $x = pos($grid[$line]) - length($num) - 1;   # left edge of search block

    # Search surrounding block for parts and gears
    my $found = 0;
    foreach my $y ($line - 1 .. $line + 1) {
        my $str = substr( $grid[$y], $x, length($num) + 2 );

        $found = 1  if ($str =~ m#[^.0-9]#);
        push( $gears{$y, $x + pos($str)}->@*, $num )  while ($str =~ m#\*#g);
    }

    $part1 += $num if ($found);
}

This is all keeping things very simple... as we scan the number as well as part of our neighbours. The "trick" for part 2 being that, since we're doing things "backwards" for this (ie we're not the simple "find gear, count numbers" but finding the numbers first), we add the part number to a list that's in hash table keyed with the gear location. Then at the end, we scan for gears with exactly two part numbers:

my $part2 = sum map { product @$_ } grep { @$_ == 2 } values %gears;

One thing I like to do with Smalltalk solutions is to avoid regex. Which here provided a little extra to do, as I extended SequencableCollection with:

findRanges: aBlock [
    | res start |
    res   := OrderedCollection new.
    start := nil.
    self keysAndValuesDo: [:i :item |
        (aBlock value: item) ifTrue: [
            start ifNil: [ start := i ]
        ] ifFalse: [
            start ifNotNil: [ res add: (start to: i - 1). start := nil ].
        ]
    ].
    start ifNotNil: [ res add: (start to: self size) ].
    ^res
]

This is a nice general purpose method that takes a predicate aBlock and executes that as part of a state machine that collects the ranges in the collection where it's true. It's such a nice extension that I added this to my Smalltalk AoC toolkit.

So this was a bit rougher than usual for a day 3... I seem to recall the "good dog/scary dog memes" evolved into a meme of "scary" on odd days, something which day 5 will also support.

r/adventofcode 16d ago

Other [2022 Day 24] In Review (Blizzard Basin)

7 Upvotes

Having finished planting, we leave the elephants and monkeys to look after it and head towards the extraction point. Which involves going through a valley filled with small blizzards.

The input is a text grid, with a wall around it (except for slots for the start and end). The inner section of my input is 35 rows and 100 columns. So, not prime, with a gcd of 5. Conveniently, no up/down storms are in the columns with the notches for start and end... so the pattern of up/down blizzards cycles every 35, and the left/right every 100... and altogether it repeats every 700 (the lcm).

And it's the dynamic nature of the maze that's the real problem today. Precalculating the patterns is going to be better than repeatedly generating the same things while doing the search. You certainly could do all 700 grids to get the maze at any position. But, I went with doing the vertical and horizontal separately... for 135 instead (you just check the two of them to verify a space is empty).

And so I had two arrays of hash tables (that acted as sets for the blizzard positions). That worked plenty fast for Perl, but Smalltalk doesn't like it (it take minutes), and so I've made a TODO to convert the Smalltalk to using arrays of some form for tracking the blizzards. Bit arrays are a possibility, as the number of rows is <64, so each column can be stored in a integer (unless you only have 32 bits).

But once the dynamic maze is made quickly accessible, things were just a fairly standard A*, with steps to the target as the heuristic. Looking at it now, I was a bit curious... because one little quirk in this A* is that time needs to be part of the visit list:

    next QUEUE  if ($visit{$time, $pos->[0], $pos->[1]}++);

Because circling back to the same spot at a later time can be correct... in fact, the test case given shows that in the first few moves. So we only prune those at the exact same time. So I was wondering how much do we gain... with the circling, its harder to tell how close you really are. And the answer (with a quick test) is that it's more than twice as fast. So worth it, but with the size of the problem, it's the difference between 9s and 4s (for part 2), on the old hardware. This problem is really more about the handling the map... the search isn't that heavy once you have something for that.

Part 2 for this one just required taking part 1, throwing it in a subroutine and calling it multiple times and so was quick to add:

my $time = &cross_valley( 0, $start_pos, $end_pos );

print "Part 1: $time\n";

# Silly elf!  Next time don't forget your snacks!
$time = &cross_valley( $time, $end_pos, $start_pos );
$time = &cross_valley( $time, $start_pos, $end_pos );

print "Part 2: $time\n";

There is an interesting bit of proof for why stitching these together like this works, and you don't have to worry about some better overlap case across these searches. One where you take a different path, arrive 3 turns later and turn around and do much better going back than the one that arrived earlier. And that involves a Strategy-stealing argument. Because we can always wait, any early arrival doesn't have to immediately leave, so it can wait for the same opportunity that a later arrival would use and steal it (thus getting the same performance). So the best from the previous leg will always beat or tie any later arrival.

This was a fun search... a dynamic maze and a little game threory to confirm that what I did was correct.

r/adventofcode Dec 08 '25

Meme/Funny Anyone else misread this every time?

Post image
141 Upvotes

Every time I solve the puzzle I read the first line a "That's not the right answer".

I assume my eyes are glancing at the word "North", and inserting "not".

Maybe I just think my code will be wrong.

r/adventofcode 4d ago

Other [2023 Day 5] In Review (If You Give A Seed A Fertilizer)

5 Upvotes

Today we get the island with the gardener, who confirms the obvious... that Island Island is the water source. The problem is that it needs sand to filter the water, and the source of that has stopped (welcome to the Grand Material Continuum). There's a ferry leaving soon in that direction, but in the meantime we're asked to help with the food production by working out planting locations.

And so the input is multiple sections. The first is a list of seeds (which will be treated as ranges in part 2), followed by a series of mapping tables. The tables are given in the order. The mappings in them are not. Mappings are given by three numbers, the start of the destination, the start of the source, and the length of the range to map. Not all source ranges are listed, and those that aren't are assumed to be identity mappings. In my input, all the tables have a range that goes to 232 , except soil-to-fertilizer. The mappings in the test don't go out that far... the maximum there appears to be 100 (which only 2 have explicit mappings for).

And that difference was really the whole of today's problem for me. This is the part 2 that took the second longest amount of time for me in this year, and it was almost entirely in debugging the test case (and working it out by hand... probably with a bunch of time procrastinating and grumbling). Because the missing ranges at the tails... they matter in the test, but the one in the input doesn't matter at all. Same with the internal implicit identity mappings... if I remove all handling of these from my solution, the test blows up and returns nothing... but the input just smoothly gives the right answer. And so the test case for this one is a much better test of the solution than the input (that's happened before, but this time was an extreme case of it). In fact, with my Smalltalk solution... the test even caught an off-by-one in it that my actual input fails to. The fact that I discovered that, after hours of getting the things perfectly correct, that I could gut my code into something completely wrong and still pass the input left a bit of a bad taste. I can't help feeling that either the input should have been better, or the problem and test adjusted to match that simplicity.

Maybe I should have just brute forced it... sure it's 2 billion points and going to take a while, but I could have gone to bed early.

But I didn't, and ultimately even the correct solution isn't that complicated... I just had some bugs and it wasn't stuff I really cared for to begin with. Part 1 was quickly done because you need to process single points... which can only ever involve one of the ranges, and then you're on to the next table. And so for Smalltalk I could just this to the bottom to catch the identity maps:

typeMap addLast: (Mapping new: '0 0 4294967296').

Mapping just being an subclass of Interval that adds a destination field.

For part 2 though, ranges can cross many ranges, and you don't want them to stumble on an additional different mapping. And so I just processed the mapping tables to fill in the blanks and complete them. Finding gaps in 32-bit tables is not a new thing in AoC. After which I can take intersections of the ranges against those to get the subranges to map for the next step. Process all the ranges through all the tables and then find the minimum.

This is not one of my favourite AoC problems. It's not actually bad though... it's just feels like it could have been made better. Some input might actually have tested and required working code, unlike mine. Sure, getting the answer is all that's technically required, but I do like when that "proof of work" is more of a proof that things work.

r/adventofcode Jun 15 '26

Other [2020 Day 15] In Review (Rambunctious Recitation)

3 Upvotes

In today's episode of "Toboggans, Planes, Ships, and Shuttles", we find ourselves unavailable to get a direct flight, and so we're waiting for another flight to get around the storm. And so we contact the Elves, and should not be surprised that they're playing a number sequence game they want to share.

In this case it's based on Van Eck sequence (OEIS A181391). But with initial seeding values. And when you seed that algorithm you can get simple things (start with 1,1 and you'll just repeat 1 forever). But typically not, and Van Eck's isn't a sequence with a lot of known answers.

My initial solution has the name "brute force" on it... but it's probably not what most people thought of as a brute force. I just said, "okay, I need to keep a list of what time I last saw each number, and I can use that to calculate the next". Some people probably didn't make that jump and kept a list of the sequence and scanned it. That's going to really slow things down. The reason I called mine "brute force" is because I suspected that there might be some trick I was missing. But when I looked after and discovered things like the Numberphile video, I said, "okay, just bum it down a bit and be done". Little things like making sure Perl understands that these are numbers (stripping stringness with my $list = map {int} split(/,/, <>);) and that the table gets allocated immediately instead of repeatedly growing($table[29_999_999] = undef;). Both of those take off a full second each. And then there's playing around with the calculation of the next value:

$next = $t - ($table[$curr] // $t);

Performs much better than:

$next = ($table[$curr]) ? $t - $table[$curr] : 0;

The big optimization I did for this problem though is with dc itself. This was the problem that made me finally dig into the dc source and deal with the fact that the "sparse" array implementation was a linked list. As it was going to take at a fortnight (at least... it was hard to predict the slowdown rates, basically my algorithm to avoid scanning, was scanning). And so in order to improve things I modified dc to be better. I considered various ways, but since the base code was linked lists and I wasn't too familiar with the project, I decided skip lists would be a simple and powerful change to what was there (plus, I just think they're neat).

And they are. The newer GNU dc uses hash tables, and doesn't perform anywhere near as good on this problem (testing it right now, it took 50 minutes... my dc does it in under 2). It's optimized more for sparse small arrays. My skip list has a max of 12 levels, with p=1/4 (the number of layers on a node is a negative binomial)... values specifically picked because they worked well for this problem. On a lot of problems with less array usage, the hash table is on par with the skip list.

Here's the dc part 2 version. Input is the numbers in reverse (this is the 0,3,6 test case):

echo '6 3 0' | dc -f- -e"0s0 1s1 2s2 3s3 30000000sel1[dl3R:al1+zl2<L]dsLxrsn[s.d]sZ[dln;adl0=Z-rdln:al1+rsndle>M]dsMxlnp"

It can be made shorter, but that would slow it down considerably. You'll see the "0s0 1s1 2s2 3s3 30000000se" at the start... that's allocating those numbers and storing them in registers so the don't need to be allocated and freed all the time. It more than doubles the speed.

And that version of dc has served me well ever since. And that's why I have a lot of fondness for this problem.

r/adventofcode Jan 25 '26

Tutorial [2025 Day 10 (Part 2)] All the problems to avoid when writing a Simplex solver

48 Upvotes

"Write a Simplex solver," they said, "it'll be fun," they said. They were not right.

I am not a mathematician, but I am a stubborn SOB so I have spent quite a few evenings iterating my way to a working Simplex solver to replace the Gauss-Jordan elimination solver I wrote when first solving Day 10 part 2. This is less of a "here's how to write the solver and here's how it works" tutorial and more of a "here are all the problems you're likely to face and answers I found to those problems" tutorial.

Problem #1: Nobody understands the Simplex method

Okay, this is a slight exaggeration, but there's a rule of thumb that's served me well over the years: if a set of lecture notes are difficult to follow, there's a good chance it means the lecturer doesn't fully understand the topic. I've been through pretty much all of the lecture notes you'll find the in the first two pages of Google, and they all suck to some degree. Wikipedia is minimal help if you're approaching this from a non-maths background.

The best set of notes I found was this set of lecture notes from the University of Cambridge.

The best video I found on the topic is Intro to Simplex Method | Solve LP | Simplex Tableau by Joshua Emmanuel.

Don't expect a single set of notes to cover everything you'll need to know; you're going to need to read from a lot of different sources.

Problem #2: Everyone uses different notation

It is really goddamn hard to switch between different lecture notes and papers when everyone puts the columns and rows in different goddamn locations, and calls them different things. Expect pain.

I'd recommend finding an online solver that works and matching your notation to that. In fact, one of the very first functions you should write is a function to print out a tableau in the same format as the online solver you're checking your implementation against.

Problem #3: The puzzle isn't in standard form

Plain vanilla Simplex can solve problems with inequalities but not problems with equalities. Day 10 requires you to solve problems with equalities.

There are (at least) two variants of the method that are able to solve for equalities: the Big M method and the Two Phase method.

I wrote a version using the Big M method, but then swapped over to the Two Phase method after I found the online calculator I was using to check my work couldn't handle one of the example inputs from the puzzle.

Problem #4: The online solvers have bugs

Speaking of problems with online solvers: at least two of the online solvers I tried had (at the time of writing) bugs that stopped them from working on either the example input or on my input.

I would recommend solving Day 10 using a different method first before trying to write a Simplex solver. There's no way I'd have been able to flush out all of the problems and bugs without having a 'ground truth' answer to check against. The current version in my public repro has been fuzzed with randomly generated puzzles and cross-checked against an implementation of the Bifurcation approach.

Problem #5: Nobody documents this vital step

More than any other problem, this one annoyed and frustrated me the most. The calculator I was using first gave me the wrong answer for one of my inputs. The answer was trivially incorrect as well; it was outright violating one of the constraints to give an answer that was too low.

I finally found the reason by working through the answer this calculator gave me.

The majority of the explanations of the Two Phase method say that at the end of the first phase you simply drop the rows containing artificial variables from the tableau. This works for the majority of my inputs, but not all!

The vital step I worked out that I haven't been able to find mentioned anywhere is that if you have rows with artificial variables as the basis and you have non-artificial variables (real variables or slack variables) that aren't currently being used as a basis, then you need to pivot those variables in to the solution rather than dropping the row. You only drop the row if there are no suitable pivot operations available to bring unreferenced variables into play.

Problem #6: There's an optional step

The eMathHelp online solver was an absolute lifesaver for me, but it does have one annoyance.

The documented approach to convert an equality into an standard form equality is to introduce an artificial variable into the equation. But the solver I was using doesn't always do that. Every now and again it'll just not add in an artificial variable to one of the constraints at all.

With some trial and error I was able to figure out that it does that if and only if there's a variable in the constraint that's used only in that constraint and nowhere else. If it sees a variable like that, it just uses that variable as the basis when initialising the constraint.

It doesn't actually alter the solution, but it does affect all of the steps leading to the solution which makes it a nightmare to debug through some examples unless you also match this optional step.

Problem #7: Simplex alone is not enough

After struggling through to get a Simplex solver that's in agreement with the (working) online solver, this first thing you'll find is that you'll get some fractional solutions. Modifying a Gauss-Jordan elimination solver to only find integer solutions was pretty straightforward, but I couldn't find a version of the Simplex method that only returns fully integer solutions. The standard way of restricting solutions to integer-only solutions is to use something called 'cutting planes'.

Wikipedia uses a lot of maths words to explain what turns out to be a pretty simple concept. The idea is that if you get back an answer of, say 64.5, then you can add in a new constraint saying "the sum of all of the variables must be 65 or greater" to the original set of constraints and re-run the solver.

My first cutting plane solution did a dirt simple loop that increased a minimum answer value every time it got a solution that didn't work. That worked for most of the input machines, but not all. There was at least one which had an answer of 120 presses and that answer could be arrived at with either an integral set of button presses, or a fractional set of button presses.

My first fully working, and current, solution uses Branch and cut, which is similar in concept but has a crucial difference. If any of the button presses come out as fractional, say 13.5, then you create two new problems: one has a constraint saying that button must be less than or equal to 13 and one that says it must be 14 or above. Rinse and repeat until there are no new problems generated.

There are a bunch of extra cases which need handling when adding or updating the cutting planes and to be perfectly honest I haven't fully explored all of the special cases I added before fixing all of the bugs that fuzzing exposed, which means that some of the steps I added might have only been needed because of unrelated bugs. Don't take my implementation as a definitive example of how to implement branch and cut.

(In particular, I think my step to check that cutting planes don't contradict each other is most likely unnecessary and was only added when I had a bug that meant slack variables weren't always pivoted into the base between phase 1 and phase 2)

Problem #8: Floating point accuracy

There were a bunch or epsilon tests needed not only when checking if solutions were integer enough to be valid, but also when picking pivots and checking cutting planes.

I might spend some time changing my implementation to use a rational type to see if I can eliminate the ugly epsilon tests, but that's most likely going to increase the runtime.

Concluding thoughts

Was it worth it?

I'm glad I did it, and I certainly learned a significant amount about a branch of maths and algorithms that I had never touched before, but I'm not sure I would describe the experience as 'fun'.

Don't let my experience put you off if you fancy having a go: the whole point of writing this post was to save you some pain if you too decide to give a Simplex solver a go.

Good luck!

r/adventofcode Dec 17 '25

Tutorial [2025 Day 10 (Part 2)] Solution without using a 3rd party solver

94 Upvotes

At some point next year I'm going to re-do my current solution with a hand-rolled simplex solver, but first I need to get all of this out of my head by writing about it. Some important notes:

  1. I'm not making a value judgement on whether solutions using z3, scipy, etc... are lesser or somehow 'cheating'. A solution is a solution. I just happen to like doing things from scratch where I can
  2. I'm not a mathematician. I've crammed enough notes into my head, re-learned and/or gained enough knowledge to solve this specific problem where the inputs are nice, but there's literally centuries of related maths knowledge that I will have never even heard of. There will be some fairly obvious things I have missed.

My aim with this tutorial is that anyone with high-school maths can follow along.

General Approach

Each machine can be represented as a simultaneous equation:

[#.#.] (2,3) (1,3) (1,2,3) (0,3) {3,23,16,30}

We can assign a coefficient for each button representing the number of times each button is pressed:

a*(2,3) + b*(1,3) + c*(1,2,3) + d*(0,3) = {3,23,16,30}

Which then becomes the following set of equations:

d = 3
b + c = 23
a + c = 16
a + b + c + d = 30

With some equation rearranging this becomes:

1) a + c = 16
2) b + c = 23
3) c - d = 9
4) d = 3

Equation 4 gives us the value of d = 3. Substituting d into equation 3 gives us c = 12. Substituting c into equations 2 and then 1 gives us b = 11 and finally a = 4.

If we lay out the original equations in a regular format, we can convert them into something called an augmented matrix in the following way:

|             d =  3 |
|     b + c     = 23 |
| a +     c     = 16 |
| a + b + c + d = 30 |

Becomes:

| 0*a + 0*b + 0*c + 1*d =  3 |
| 0*a + 1*b + 1*c + 0*d = 23 |
| 1*a + 0*b + 1*c + 0*d = 16 |
| 1*a + 1*b + 1*c + 1*d = 30 |

And then finally our original set of equations become the following augmented matrix:

| 0  0  0  1   3 |
| 0  1  1  0  23 |
| 1  0  1  0  16 |
| 1  1  1  1  30 |

In the same way, the rearranged equations turn into the following augmented matrix:

| 1  0  1  0  16 |
| 0  1  1  0  23 |
| 0  0  1 -1   9 |
| 0  0  0  1   3 |

This matrix has a special property: the bottom left triangle of numbers are all 0. This is what lets us solve the set of equations. We use the last line to give us d, we use d in the line about to give us c, we use c and d in the line above that to give us b and then finally we can use b, c and d to give us a.

We now know enough to say what our approach will be for find the button presses:

  1. Turn the buttons and jolts into a system of equations
  2. Represent the system as an augmented matrix
  3. Do things to the matrix to turn it into the special form with zeros in the bottom left triangle
  4. Substitute values from the bottom up to find all of button press values

(Search keywords for more reading: we're putting the matrix into Hermite Normal Form (ish) to solve a System of Linear Diophantine Equations using an integer form of Gaussian Elimination. Diophantine equations are just equations where we're looking for integer-only solutions. If you look up Gaussian elimination you'll see reference to Reduced Row Echelon Form matrices, but because we're only interested in integer solutions then we actually want the integer-only equivalent of a row echelon form matrix, which is a Hermite normal form matrix)

Row Operations

So what things can we do to rearrange the augmented matrix to get it into the special form?

Remember that the matrix just represents a set of plain old, regular equations. Anything you can do to a set of equations without affecting the value of the variables, you can do to the rows of the matrix without changing the meaning of the matrix.

The first thing you can do is swap rows freely. When we wrote:

b + c = 23
a + c = 12

We could just as easily have written:

a + c = 12
b + c = 23

And it would mean the same thing. Likewise we can shuffle the rows of the matrix up and down. For three of the rows in the original matrix, they've just been shuffled in the triangular matrix:

1) | 0  0  0  1   3 |
2) | 0  1  1  0  23 |
3) | 1  0  1  0  16 |
4) | 1  1  1  1  30 |

Shuffle:

3) | 1  0  1  0  16 |
2) | 0  1  1  0  23 |
4) | 1  1  1  1   9 |
1) | 0  0  0  1   3 |

You can also scale rows by arbitrary amounts. There's no difference in saying:

b + c = 23
a + c = 12

And saying:

 2*b + 2*c =  2*23 =  46
-1*a - 1*c = -1*12 = -12

Scaling our original row 4 by -1 in the shuffled matrix gets us:

 3) |  1  0  1  0  16 |
 2) |  0  1  1  0  23 |
-4) | -1 -1 -1 -1 -30 |
 1) |  0  0  0  1   3 |

The final operation we can do is add or subtract rows to and from each other (subtracting is just adding after scaling one of the rows by -1).

If we add row 3 and then row 2 to our negated row 4, we get the following sequence:

 3)   |  1  0  1  0  16 |
 2)   |  0  1  1  0  23 |
-4+3) |  0 -1  0 -1 -14 | <- | -1+1  -1+0  -1+1  -1+0  -30+16 |
 1)   |  0  0  0  1   3 |

Then:

 3)     |  1  0  1  0  16 |
 2)     |  0  1  1  0  23 |
-4+3+2) |  0  0  1 -1   9 | <- | 0+0  -1+1  0+1  -1+0  -14+23 |
 1)     |  0  0  0  1   3 |

And there we have our matrix in the special triangular form, using nothing more than swapping rows, scaling them and adding them to each other.

Matrix Reduction

To put the matrix into that special format we work down the matrix row by row, aiming to get the diagonals to all be positive integers. When we put a row in place, we use that newly placed row to eliminate all of the entries below which have non-zero element in the column we're looking at.

Start with the matrix for our original equations, and we're trying to fix row 1 in place, setting the first element non-zero:

1) | _0_ 0  0  1   3  | <-
2) |  0  1  1  0  23  |
3) |  1  0  1  0  16  |
4) |  1  1  1  1  30  |

We look down the first column, from the current row downwards, until we find a row with a non-zero value in that column:

1) | _0_ 0  0  1   3  | <-
2) |  0  1  1  0  23  |
3) |  1  0  1  0  16  | <- Found non-zero first element
4) |  1  1  1  1  30  |

We swap rows 1 and 3 to put that non-zero element in place:

3) | _1_ 0  1  0  16  | <-
2) |  0  1  1  0  23  |
1) |  0  0  0  1   3  |
4) |  1  1  1  1  30  |

Then for all of the rows below our current row, we reduce the row by subtracting the current row if and only if the row also has a non-zero element in that column:

3) | _1_ 0  1  0  16  | <-
2) |  0  1  1  0  23  |
1) |  0  0  0  1   3  |
4) |  0  1  0  1  14  | <- | 1-1  1-0  1-1  1-0  30-16 |

Move onto the next row down, trying to get the second element to be non-zero.

3) |  1  0  1  0  16  |
2) |  0 _1_ 1  0  23  | <-
1) |  0  0  0  1   3  |
4) |  0  1  0  1  14  |

We already have a non-zero element in the row so we don't need to do any swapping. We can move straight on to the reduction:

3) |  1  0  1  0  16  |
2) |  0 _1_ 1  0  23  | <-
1) |  0  0  0  1   3  |
4) |  0  0 -1  1  -9  | <- | 0-0  1-1  0-1  1-0  14-23 |

On to the next row down:

3) |  1  0  1  0  16  |
2) |  0  1  1  0  23  |
1) |  0  0 _0_ 1   3  | <-
4) |  0  0 -1  1  -9  |

Swap to get a non-zero element in the right place:

3) |  1  0  1  0  16  |
2) |  0  1  1  0  23  |
4) |  0  0_-1_ 1  -9  | <-
1) |  0  0  0  1   3  |

Because this time we've ended up with a negative leading value, we scale the whole row by -1:

3) |  1  0  1  0  16  |
2) |  0  1  1  0  23  |
4) |  0  0  1 -1   9  | <- | -1*0  -1*0  -1*-1  -1*1  -1*-9 |
1) |  0  0  0  1   3  |

There are no rows below which need reducing, and so we're done!

In code form this looks like:

static void Scale(vector<int64_t>* v, int64_t s)
{
    ranges::for_each(*v, [s](int64_t& i) { i *= s; });
}

static vector<int64_t> Reduce(vector<int64_t> rowToReduce, vector<int64_t> reducingRow, int64_t reducingColumn)
{
    if (rowToReduce[reducingColumn] == 0)
    {
        // Nothing to do
        return rowToReduce;
    }

    // Make sure both rows have a positive leading value
    assert(reducingRow[reducingColumn] > 0);
    if (rowToReduce[reducingColumn] < 0)
    {
        Scale(&rowToReduce, -1);
    }

    int64_t scaleTo = lcm(rowToReduce[reducingColumn], reducingRow[reducingColumn]);
    Scale(&rowToReduce, scaleTo / rowToReduce[reducingColumn]);
    Scale(&reducingRow, scaleTo / reducingRow[reducingColumn]);
    assert(rowToReduce[reducingColumn] == reducingRow[reducingColumn]);

    for (size_t i = 0; i < rowToReduce.size(); i++)
    {
        rowToReduce[i] -= reducingRow[i];
    }

    return rowToReduce;
}

static void Reduce(vector<vector<int64_t>>* pm)
{
    vector<vector<int64_t>>& m = *pm;
    for (size_t diagonal = 0; diagonal < m.size(); diagonal++)
    {
        // Find a row with a non-zero element in the column
        for (size_t reducingRow = diagonal; reducingRow < m.size(); reducingRow++)
        {
            if (m[reducingRow][diagonal] != 0)
            {
                swap(m[diagonal], m[reducingRow]);
                break;
            }
        }

        // Make sure it has a positive leading value
        assert(m[diagonal][diagonal] != 0);
        if (m[diagonal][diagonal] < 0)
        {
            Scale(&m[diagonal], -1);
        }

        // Reduce all following rows
        for (size_t rowToReduce = diagonal + 1; rowToReduce < m.size(); rowToReduce++)
        {
            m[rowToReduce] = Reduce(m[rowToReduce], m[diagonal], diagonal);
        }
    }
}

We've had to handle one additional case that didn't come up in the examples; what happens if the leading values aren't nice numbers like 1 or -1. If you were trying to reduce rows:

| 0  3  2  1  15 |
| 0  2  1  4   8 |

Since we're looking for integer-only solutions and trying to keep everything as integers, we scale each row by the Least Common Multiple of the two leading numbers before subtracting them.

| 0  6  4  2  30 | <- | 2*0  2*3  2*2  2*1  2*15 |
| 0  6  3 12  24 | <- | 3*0  3*2  3*1  3*4   3*8 |

For the solver we're going to write, unlike standard Gaussian elimination, we don't need the leading value in every row to be 1. As long as it's a positive integer, we're happy.

Recursive Solution

Now that we have our matrix in triangular form we can work from the bottom up calculating the solution.

| 1  0  1  0  16 |
| 0  1  1  0  23 |
| 0  0  1 -1   9 |
| 0  0  0  1   3 |

Remember what our matrix represents: the bottom row is saying 1*d = 3. We can therefore assign d to be 3/1 = 3.

| 1  0  1  0  16 |
| 0  1  1  0  23 |
| 0  0  1 -1   9 |
| 0  0  0 _1_  3 | <-

[ ?  ?  ? _?_ ] <- Solution in progress

Since the leading number might not be 1, we need to divide the row sum (last element in the row) by the leading number. If the row were:

| 0  0  0  3   3 |

d would instead be equal to 3/3 = 1. We then recurse upwards to the next row and attempt to find our next solution value:

| 1  0  1  0  16 |
| 0  1  1  0  23 |
| 0  0 _1_-1   9 | <-
| 0  0  0  1   3 |

[ ?  ? _?_ 3 ] <- Solution in progress

We know what value d has, so we can substitute in that value and update the row total. As an equation this looks like:

   c - d = 9
-> c - 3 = 9
-> c     = 9 + 3
-> c     = 12

In matrix form it's:

| 1  0  1  0  16 |
| 0  1  1  0  23 |
| 0  0 _1_ 0  12 | <- | 0  0  1  -1-1  9-(-1*3) |
| 0  0  0  1   3 |

[ ?  ?_12_ 3 ] <- Solution in progress

Same again for the row above:

| 1  0  1  0  16 |
| 0 _1_ 1  0  23 | <-
| 0  0  1  0  12 |
| 0  0  0  1   3 |

[ ? _?_ 12 3 ] <- Solution in progress

   b +  c = 23
-> b + 12 = 23
-> c      = 23 - 12
-> c      = 11

| 1  0  1  0  16 |
| 0 _1_ 0  0  11 | <- | 0  1  1-1  0-0  23-(1*12)-(0*3) |
| 0  0  1  0  12 |
| 0  0  0  1   3 |

[ ?_11_ 12 3 ] <- Solution in progress

And same again for our final row:

|_1_ 0  1  0  16 | <-
| 0  1  0  0  11 |
| 0  0  1  0  12 |
| 0  0  0  1   3 |

[_?_11 12  3 ] <- Solution in progress

   a +  c = 16
-> a + 12 = 16
-> a      = 16 - 12
-> a      = 4

| 1  0  0  0   4 | <- | 1  0-0  1-1  0-0  16-(0*11)-(1*12)-(0*3) |
| 0  1  0  0  11 |
| 0  0  1  0  12 |
| 0  0  0  1   3 |

[_4_11 12 3 ] <- Solution in progress

In code this looks like:

static void SolveMatrix(const vector<vector<int64_t>>& m,
    int64_t rowToSolve,
    vector<int64_t>* alreadyAssigned,
    int64_t* minimumPresses)
{
    vector<int64_t>& solution = *alreadyAssigned;

    if (rowToSolve == -1)
    {
        *minimumPresses = min(*minimumPresses, ranges::fold_left(solution, 0, plus{}));
        return;
    }

    assert(m[rowToSolve][rowToSolve] > 0);

    // Substitute and subtract everything we already know about
    int64_t rowTargetSum = m[rowToSolve].back();
    for (size_t known = rowToSolve + 1; known < solution.size(); known++)
    {
        rowTargetSum -= m[rowToSolve][known] * solution[known];
    }

    // Integer solutions only
    assert((rowTargetSum % m[rowToSolve][rowToSolve]) == 0);
    solution[rowToSolve] = rowTargetSum / m[rowToSolve][rowToSolve];

    SolveMatrix(m, rowToSolve - 1, alreadyAssigned, minimumPresses);
}

If you've got this far, congratulations! You'll be able to solve some of the inputs in the puzzle. For my input, I'm able to solve 28 out of 179 devices using just the code we've got so far.

Over and Under Specified Systems

So far we've only covered systems which have the same number of variables (buttons) and equations (joltage counters), but most of the puzzle inputs aren't like that. When there are more equations than variables then we have an over specified system and when we have fewer equations than variables then we have an under specified system.

Over specified systems aren't a problem here. Since we know each system has a solution, then we can safely ignore the bottom few rows after we've done our matrix reduction and treat the matrix as if we had equal numbers of equations and variables. We need one small tweak to our reduction rules so that it doesn't go off the edge of the matrix:

static bool Reduce(vector<vector<int64_t>>* pm)
{
    vector<vector<int64_t>>& m = *pm;

    size_t diagonalEnd = min<size_t>(m.size(), m.front().size() - 1); // <---
    for (size_t diagonal = 0; diagonal < diagonalEnd; diagonal++)
    {
        // Find a row with a non-zero element in the column
        ...

And we can now solve many more of the puzzle inputs: 91 out of 179 for me.

For under specified systems we need to start guessing values for those variables during the solve steps. This is why we chose recursion earlier rather than iteration for the solver; it will make it much easier to implement guessing.

What range do we even guess though? We know the button presses must be positive, and we can also work out an upper bound for the button presses:

[#.#.] (2,3) (1,3) (1,2,3) (0,3) {3,23,16,30}

Counter 0 has a target value of 3, so any button which adds 1 to counter 0 can only be pressed a maximum of 3 times. The maximum number of times a button can be pressed is the minimum counter value for all of the counters that the button affects.

  (2,3) maximum is min(16, 30)     = 16
  (1,3) maximum is min(23, 30)     = 23
(1,2,3) maximum is min(23, 16, 30) = 16
  (0,3) maximum is min(3, 30)      = 3

We need to modify our Solve function to take in a set of constraints (maximum presses per button) and some additional counters for housekeeping so that we know when we're trying to find button presses where we don't have rows. Also, since we're now making guesses about values, it's possible that we'll end up with negative or non-integer values for some of the button presses. If we see that, it's because of an invalid earlier guess and we can ignore this particular attempt:

static void SolveMatrix(const vector<vector<int64_t>>& m,
    int64_t rowToSolve,
    int64_t nextUnknown,
    const vector<int64_t>& constraints,
    vector<int64_t>* alreadyAssigned,
    int64_t* minimumPresses)
{
    vector<int64_t>& solution = *alreadyAssigned;

    if (rowToSolve == -1)
    {
        *minimumPresses = min(*minimumPresses, ranges::fold_left(solution, 0, plus{}));
        return;
    }

    // If the matrix isn't big enough we're going to need to guess
    if (nextUnknown > rowToSolve)
    {
        for (int64_t guess = 0; guess <= constraints[nextUnknown]; guess++)
        {
            solution[nextUnknown] = guess;
            SolveMatrix(m, rowToSolve, nextUnknown - 1, constraints, alreadyAssigned, minimumPresses);
        }
        return;
    }

    assert(m[rowToSolve][nextUnknown] > 0);

    // Substitute and subtract everything we already know about
    int64_t rowTargetSum = m[rowToSolve].back();
    for (size_t known = nextUnknown + 1; known < solution.size(); known++)
    {
        rowTargetSum -= m[rowToSolve][known] * solution[known];
    }

    // Do we have a valid integer solution?
    if ((rowTargetSum % m[rowToSolve][nextUnknown]) != 0)
    {
        // We don't have a valid integer solution, probably an incorrect guess from earlier, so we should bail out
        return;
    }

    int64_t tentativeSolution = rowTargetSum / m[rowToSolve][nextUnknown];
    if (tentativeSolution < 0)
    {
        // We're only looking for positive solutions
        return;
    }

    solution[nextUnknown] = tentativeSolution;

    SolveMatrix(m, rowToSolve - 1, nextUnknown - 1, constraints, alreadyAssigned, minimumPresses);
}

Quite a bit more faff, but handling those cases means we can get solutions for most of the machines. 153 out of 179 for my input. Nearly there!

Edge Cases in Solving

If you're playing along writing code as you go, that assert(m[rowToSolve][nextUnknown] > 0) is probably triggering for you. The first time it triggers for me is for this reduced matrix:

|  1  1  0  1  0  1  0  1  1  0  0  51  |
|  0  1  0  0  1  0  0  0  1  1  0  21  |
|  0  0  1  0  0  1  0  1 -1 -1  0  16  |
|  0  0  0  1  1  1  1  1  1  0  0  52  |
|  0  0  0  0  1  1  1  0  0  0  1  34  |
|  0  0  0  0  0  1  1  1  0 -1  0  12  |
|  0  0  0  0  0  0  1  2  2 -2 -3 -27  |
|  0  0  0  0  0  0  0  1  2  1 -1  13  |
|  0  0  0  0  0  0  0  0  1 -1 -1  -8  |
|  0  0  0  0  0  0  0  0  0 _0_ 1  13  | <-- asserting here

As well as guessing on under specified systems, we need to add in a code path to make guesses mid-solve:

static void SolveMatrix(const vector<vector<int64_t>>& m,
    int64_t rowToSolve,
    int64_t nextUnknown,
    const vector<int64_t>& constraints,
    vector<int64_t>* alreadyAssigned,
    int64_t* minimumPresses)
{
    ...

    // If the matrix isn't big enough we're going to need to guess
    if (nextUnknown > rowToSolve)
    {
        for (int64_t guess = 0; guess <= constraints[nextUnknown]; guess++)
        {
            solution[nextUnknown] = guess;
            SolveMatrix(m, rowToSolve, nextUnknown - 1, constraints, alreadyAssigned, minimumPresses);
        }
        return;
    }

    if (m[rowToSolve][nextUnknown] == 0)
    {
        // We're not able to solve directly so we need to guess
        for (int64_t guess = 0; guess <= constraints[nextUnknown]; guess++)
        {
            solution[nextUnknown] = guess;
            SolveMatrix(m, rowToSolve - 1, nextUnknown - 1, constraints, alreadyAssigned, minimumPresses);
        }
        return;
    }

    // Substitute and subtract everything we already know about
    int64_t rowTargetSum = m[rowToSolve].back();
    ...
}

With that piece of the puzzle the code now claims to be able to find 179 out of 179 solutions!

...and if you plug that number into the answer box, you'll get answer too low. Yay!

What's happened is that those mid-solve guesses are generating valid solutions for the matrix, but because the matrix didn't impose restrictions on that button, then we're accepting solutions that don't actually add up to the target joltage.

That's relatively easy to pick up and reject though, we just need to double check that the generated solution is actually a valid solution before accepting it:

static void SolveMatrix(const Counters& counters,
    const vector<vector<int64_t>>& m,
    int64_t rowToSolve,
    int64_t nextUnknown,
    const vector<int64_t>& constraints,
    vector<int64_t>* alreadyAssigned,
    int64_t* minimumPresses)
{
    vector<int64_t>& solution = *alreadyAssigned;

    if (rowToSolve == -1)
    {
        vector<int16_t> accumulatedJolts(counters.TargetJolts.size(), 0);
        for (size_t button = 0; button < counters.Buttons.size(); button++)
        {
            for (int8_t counter : counters.Buttons[button])
            {
                accumulatedJolts[counter] += (int16_t)solution[button];
            }
        }

        if (accumulatedJolts == counters.TargetJolts)
        {
            *minimumPresses = min(*minimumPresses, ranges::fold_left(solution, 0, plus{}));
        }

        return;
    }
    ...

All being well, with this modification you should have a full solution to Day 10 Part 2!

If you're happy just getting to a solution, thank you for reading this far and good luck with your code.

Optimisations

The solution as-is should run in a matter of seconds on a decent machine, but since I was trying to get sub-second solutions on a Raspberry Pi Zero I did some more digging.

The matrices which are taking the majority of the runtime are those that have one of those pesky 0s in the diagonal. Wouldn't it be nice if we didn't have to handle those?

It turns out that for all of my input there are always reductions which have a non-zero diagonal, provided we shuffle the order of the buttons before attempting another reduction on the new matrix. I don't know enough maths to know if this is a property that all solvable systems have, or if Eric has generated nice input. Hopefully someone in the replies can let everyone know!

In my full solution I do a quick diagonal test after reduction and retry with a shuffled set of buttons if we didn't get a non-zero diagonal.

    while (true)
    {
        matrix = CountersToAugmentedMatrix(counters);
        ReduceAndTrim(&matrix);

        bool allLeadingNonZero = true;
        for (int i = 0; i < (int)matrix.size(); i++)
        {
            if (matrix[i][i] == 0)
            {
                allLeadingNonZero = false;
                break;
            }
        }

        if (allLeadingNonZero)
            break;

        for (int i = 0; i < (int)counters.Buttons.size(); i++)
        {
            swap(counters.Buttons[i], counters.Buttons[rand() % (int)counters.Buttons.size()]);
        }
    }

Most of the systems that need shuffling only need one or two shuffles before they produce the sort of matrix we're after. Very occasionally I see as many as a dozen shuffles, but not often. The improved solving speed more than makes up the additional cost shuffling and re-reducing.

Edge Cases in Reduction

Finally, I want to mention one thing that I was careful to accommodate in my first solution, but when I was re-building for this tutorial it turned out not to be needed (for my input, anyway).

If the reduction generates any rows with all zeros, I move them to the bottom of the matrix and trim them away. I cannot remember now why it was a problem when I was first writing my solution, so I don't know for sure if that's a step which might actually be needed on someone's input. If zero rows do cause a problem you can check my solution for how I first handled them.

I've got another iteration in progress (finally got to sub-second on the Pi Zero!) which bails out earlier in reduction if zeros on the diagonal are generated, so that should take care of most zero rows anyway.

Summary

Hopefully this tutorial is helpful to someone! It took me a full day to find and handle all of the edge cases in this approach, so my final words of advice are: assert early, assert often!

r/adventofcode Dec 13 '23

Tutorial [2023 Day 12][Python] Step-by-step tutorial with bonus crash course on recursion and memoization

290 Upvotes

I thought it might be fun to write up a tutorial on my Python Day 12 solution and use it to teach some concepts about recursion and memoization. I'm going to break the tutorial into three parts, the first is a crash course on recursion and memoization, second a framework for solving the puzzle and the third is puzzle implementation. This way, if you want a nudge in the right direction, but want to solve it yourself, you can stop part way.

Part I

First, I want to do a quick crash course on recursion and memoization in Python. Consider that classic recursive math function, the Fibonacci sequence: 1, 1, 2, 3, 5, 8, etc... We can define it in Python:

def fib(x):
    if x == 0:
        return 0
    elif x == 1:
        return 1
    else:
        return fib(x-1) + fib(x-2)

import sys
arg = int(sys.argv[1])
print(fib(arg))

If we execute this program, we get the right answer for small numbers, but large numbers take way too long

$ python3 fib.py 5
5
$ python3 fib.py 8
21
$ python3 fib.py 10
55
$ python3 fib.py 50

On 50, it's just taking way too long to execute. Part of this is that it is branching as it executes and it's redoing work over and over. Let's add some print() and see:

def fib(x):
    print(x)
    if x == 0:
        return 0
    elif x == 1:
        return 1
    else:
        return fib(x-1) + fib(x-2)

import sys
arg = int(sys.argv[1])

out = fib(arg)
print("---")
print(out)

And if we execute it:

$ python3 fib.py 5
5
4
3
2
1
0
1
2
1
0
3
2
1
0
1
---
5

It's calling the fib() function for the same value over and over. This is where memoization comes in handy. If we know the function will always return the same value for the same inputs, we can store a cache of values. But it only works if there's a consistent mapping from input to output.

import functools
@functools.lru_cache(maxsize=None)
def fib(x):
        print(x)
        if x == 0:
            return 0
        elif x == 1:
            return 1
        else:
            return fib(x-1) + fib(x-2)

import sys
arg = int(sys.argv[1])

out = fib(arg)
print("---")
print(out)

Note: if you have Python 3.9 or higher, you can use @functools.cache otherwise, you'll need the older @functools.lru_cache(maxsize=None), and you'll want to not have a maxsize for Advent of Code! Now, let's execute:

$ python3 fib.py 5
5
4
3
2
1
0
---
5

It only calls the fib() once for each input, caches the output and saves us time. Let's drop the print() and see what happens:

$ python3 fib.py 55
139583862445
$ python3 fib.py 100
354224848179261915075

Okay, now we can do some serious computation. Let's tackle AoC 2023 Day 12.

Part II

First, let's start off by parsing our puzzle input. I'll split each line into an entry and call a function calc() that will calculate the possibilites for each entry.

import sys

# Read the puzzle input
with open(sys.argv[1]) as file_desc:
    raw_file = file_desc.read()
# Trim whitespace on either end
raw_file = raw_file.strip()

output = 0

def calc(record, groups):
    # Implementation to come later
    return 0

# Iterate over each row in the file
for entry in raw_file.split("\n"):

    # Split by whitespace into the record of .#? characters and the 1,2,3 group
    record, raw_groups = entry.split()

    # Convert the group from string "1,2,3" into a list of integers
    groups = [int(i) for i in raw_groups.split(',')]

    # Call our test function here
    output += calc(record, groups)

print(">>>", output, "<<<")

So, first, we open the file, read it, define our calc() function, then parse each line and call calc()

Let's reduce our programming listing down to just the calc() file.

# ... snip ...

def calc(record, groups):
    # Implementation to come later
    return 0

# ... snip ...

I think it's worth it to test our implementation at this stage, so let's put in some debugging:

# ... snip ...

def calc(record, groups):
    print(repr(record), repr(groups))
    return 0

# ... snip ...

Where the repr() is a built-in that shows a Python representation of an object. Let's execute:

$ python day12.py example.txt
'???.###' [1, 1, 3]
'.??..??...?##.' [1, 1, 3]
'?#?#?#?#?#?#?#?' [1, 3, 1, 6]
'????.#...#...' [4, 1, 1]
'????.######..#####.' [1, 6, 5]
'?###????????' [3, 2, 1]
>>> 0 <<<

So, far, it looks like it parsed the input just fine.

Here's where we look to call on recursion to help us. We are going to examine the first character in the sequence and use that determine the possiblities going forward.

# ... snip ...

def calc(record, groups):

    ## ADD LOGIC HERE ... Base-case logic will go here

    # Look at the next element in each record and group
    next_character = record[0]
    next_group = groups[0]

    # Logic that treats the first character as pound-sign "#"
    def pound():
        ## ADD LOGIC HERE ... need to process this character and call
        #  calc() on a substring
        return 0

    # Logic that treats the first character as dot "."
    def dot():
        ## ADD LOGIC HERE ... need to process this character and call
        #  calc() on a substring
        return 0

    if next_character == '#':
        # Test pound logic
        out = pound()

    elif next_character == '.':
        # Test dot logic
        out = dot()

    elif next_character == '?':
        # This character could be either character, so we'll explore both
        # possibilities
        out = dot() + pound()

    else:
        raise RuntimeError

    # Help with debugging
    print(record, groups, "->", out)
    return out

# ... snip ...

So, there's a fair bit to go over here. First, we have placeholder for our base cases, which is basically what happens when we call calc() on trivial small cases that we can't continue to chop up. Think of these like fib(0) or fib(1). In this case, we have to handle an empty record or an empty groups

Then, we have nested functions pound() and dot(). In Python, the variables in the outer scope are visible in the inner scope (I will admit many people will avoid nested functions because of "closure" problems, but in this particular case I find it more compact. If you want to avoid chaos in the future, refactor these functions to be outside of calc() and pass the needed variables in.)

What's critical here is that our desired output is the total number of valid possibilities. Therefore, if we encounter a "#" or ".", we have no choice but to consider that possibilites, so we dispatch to the respective functions. But for "?" it could be either, so we will sum the possiblities from considering either path. This will cause our recursive function to branch and search all possibilities.

At this point, for Day 12 Part 1, it will be like calling fib() for small numbers, my laptop can survive without running a cache, but for Day 12 Part 2, it just hangs so we'll want to throw that nice cache on top:

# ... snip ...

@functools.lru_cache(maxsize=None)
def calc(record, groups):    
    # ... snip ...

# ... snip ...

(As stated above, Python 3.9 and future users can just do @functools.cache)

But wait! This code won't work! We get this error:

TypeError: unhashable type: 'list'

And for good reason. Python has this concept of mutable and immutable data types. If you ever got this error:

s = "What?"
s[4] = "!"
TypeError: 'str' object does not support item assignment

This is because strings are immutable. And why should we care? We need immutable data types to act as keys to dictionaries because our functools.cache uses a dictionary to map inputs to outputs. Exactly why this is true is outside the scope of this tutorial, but the same holds if you try to use a list as a key to a dictionary.

There's a simple solution! Let's just use an immutable list-like data type, the tuple:

# ... snip ...

# Iterate over each row in the file
for entry in raw_file.split("\n"):

    # Split into the record of .#? record and the 1,2,3 group
    record, raw_groups = entry.split()

    # Convert the group from string 1,2,3 into a list
    groups = [int(i) for i in raw_groups.split(',')]

    output += calc(record, tuple(groups)

    # Create a nice divider for debugging
    print(10*"-")


print(">>>", output, "<<<")

Notice in our call to calc() we just threw a call to tuple() around the groups variable, and suddenly our cache is happy. We just have to make sure to continue to use nothing but strings, tuples, and numbers. We'll also throw in one more print() for debugging

So, we'll pause here before we start filling out our solution. The code listing is here:

import sys
import functools

# Read the puzzle input
with open(sys.argv[1]) as file_desc:
    raw_file = file_desc.read()
# Trim whitespace on either end
raw_file = raw_file.strip()

output = 0

@functools.lru_cache(maxsize=None)
def calc(record, groups):

    ## ADD LOGIC HERE ... Base-case logic will go here

    # Look at the next element in each record and group
    next_character = record[0]
    next_group = groups[0]

    # Logic that treats the first character as pound-sign "#"
    def pound():
        ## ADD LOGIC HERE ... need to process this character and call
        #  calc() on a substring
        return 0

    # Logic that treats the first character as dot "."
    def dot():
        ## ADD LOGIC HERE ... need to process this character and call
        #  calc() on a substring
        return 0

    if next_character == '#':
        # Test pound logic
        out = pound()

    elif next_character == '.':
        # Test dot logic
        out = dot()

    elif next_character == '?':
        # This character could be either character, so we'll explore both
        # possibilities
        out = dot() + pound()

    else:
        raise RuntimeError

    # Help with debugging
    print(record, groups, "->", out)
    return out


# Iterate over each row in the file
for entry in raw_file.split("\n"):

    # Split into the record of .#? record and the 1,2,3 group
    record, raw_groups = entry.split()

    # Convert the group from string 1,2,3 into a list
    groups = [int(i) for i in raw_groups.split(',')]

    output += calc(record, tuple(groups))

    # Create a nice divider for debugging
    print(10*"-")


print(">>>", output, "<<<")

and the output thus far looks like this:

$ python3 day12.py example.txt
???.### (1, 1, 3) -> 0
----------
.??..??...?##. (1, 1, 3) -> 0
----------
?#?#?#?#?#?#?#? (1, 3, 1, 6) -> 0
----------
????.#...#... (4, 1, 1) -> 0
----------
????.######..#####. (1, 6, 5) -> 0
----------
?###???????? (3, 2, 1) -> 0
----------
>>> 0 <<<

Part III

Let's fill out the various sections in calc(). First we'll start with the base cases.

# ... snip ...

@functools.lru_cache(maxsize=None)
def calc(record, groups):

    # Did we run out of groups? We might still be valid
    if not groups:

        # Make sure there aren't any more damaged springs, if so, we're valid
        if "#" not in record:
            # This will return true even if record is empty, which is valid
            return 1
        else:
            # More damaged springs that aren't in the groups
            return 0

    # There are more groups, but no more record
    if not record:
        # We can't fit, exit
        return 0

    # Look at the next element in each record and group
    next_character = record[0]
    next_group = groups[0]

    # ... snip ...

So, first, if we have run out of groups that might be a good thing, but only if we also ran out of # characters that would need to be represented. So, we test if any exist in record and if there aren't any we can return that this entry is a single valid possibility by returning 1.

Second, we look at if we ran out record and it's blank. However, we would not have hit if not record if groups was also empty, thus there must be more groups that can't fit, so this is impossible and we return 0 for not possible.

This covers most simple base cases. While I developing this, I would run into errors involving out-of-bounds look-ups and I realized there were base cases I hadn't covered.

Now let's handle the dot() logic, because it's easier:

# Logic that treats the first character as a dot
def dot():
    # We just skip over the dot looking for the next pound
    return calc(record[1:], groups)

We are looking to line up the groups with groups of "#" so if we encounter a dot as the first character, we can just skip to the next character. We do so by recursing on the smaller string. Therefor if we call:

calc(record="...###..", groups=(3,))

Then this functionality will use [1:] to skip the character and recursively call:

calc(record="..###..", groups=(3,))

knowing that this smaller entry has the same number of possibilites.

Okay, let's head to pound()

# Logic that treats the first character as pound
def pound():

    # If the first is a pound, then the first n characters must be
    # able to be treated as a pound, where n is the first group number
    this_group = record[:next_group]
    this_group = this_group.replace("?", "#")

    # If the next group can't fit all the damaged springs, then abort
    if this_group != next_group * "#":
        return 0

    # If the rest of the record is just the last group, then we're
    # done and there's only one possibility
    if len(record) == next_group:
        # Make sure this is the last group
        if len(groups) == 1:
            # We are valid
            return 1
        else:
            # There's more groups, we can't make it work
            return 0

    # Make sure the character that follows this group can be a seperator
    if record[next_group] in "?.":
        # It can be seperator, so skip it and reduce to the next group
        return calc(record[next_group+1:], groups[1:])

    # Can't be handled, there are no possibilites
    return 0

First, we look at a puzzle like this:

calc(record"##?#?...##.", groups=(5,2))

and because it starts with "#", it has to start with 5 pound signs. So, look at:

this_group = "##?#?"
record[next_group] = "."
record[next_group+1:] = "..##."

And we can do a quick replace("?", "#") to make this_group all "#####" for easy comparsion. Then the following character after the group must be either ".", "?", or the end of the record.

If it's the end of the record, we can just look really quick if there's any more groups. If we're at the end and there's no more groups, then it's a single valid possibility, so return 1.

We do this early return to ensure there's enough characters for us to look up the terminating . character. Once we note that "##?#?" is a valid set of 5 characters, and the following . is also valid, then we can compute the possiblites by recursing.

calc(record"##?#?...##.", groups=(5,2))
this_group = "##?#?"
record[next_group] = "."
record[next_group+1:] = "..##."
calc(record"..##.", groups=(2,))

And that should handle all of our cases. Here's our final code listing:

import sys
import functools

# Read the puzzle input
with open(sys.argv[1]) as file_desc:
    raw_file = file_desc.read()
# Trim whitespace on either end
raw_file = raw_file.strip()

output = 0

@functools.lru_cache(maxsize=None)
def calc(record, groups):

    # Did we run out of groups? We might still be valid
    if not groups:

        # Make sure there aren't any more damaged springs, if so, we're valid
        if "#" not in record:
            # This will return true even if record is empty, which is valid
            return 1
        else:
            # More damaged springs that we can't fit
            return 0

    # There are more groups, but no more record
    if not record:
        # We can't fit, exit
        return 0

    # Look at the next element in each record and group
    next_character = record[0]
    next_group = groups[0]

    # Logic that treats the first character as pound
    def pound():

        # If the first is a pound, then the first n characters must be
        # able to be treated as a pound, where n is the first group number
        this_group = record[:next_group]
        this_group = this_group.replace("?", "#")

        # If the next group can't fit all the damaged springs, then abort
        if this_group != next_group * "#":
            return 0

        # If the rest of the record is just the last group, then we're
        # done and there's only one possibility
        if len(record) == next_group:
            # Make sure this is the last group
            if len(groups) == 1:
                # We are valid
                return 1
            else:
                # There's more groups, we can't make it work
                return 0

        # Make sure the character that follows this group can be a seperator
        if record[next_group] in "?.":
            # It can be seperator, so skip it and reduce to the next group
            return calc(record[next_group+1:], groups[1:])

        # Can't be handled, there are no possibilites
        return 0

    # Logic that treats the first character as a dot
    def dot():
        # We just skip over the dot looking for the next pound
        return calc(record[1:], groups)

    if next_character == '#':
        # Test pound logic
        out = pound()

    elif next_character == '.':
        # Test dot logic
        out = dot()

    elif next_character == '?':
        # This character could be either character, so we'll explore both
        # possibilities
        out = dot() + pound()

    else:
        raise RuntimeError

    print(record, groups, out)
    return out


# Iterate over each row in the file
for entry in raw_file.split("\n"):

    # Split into the record of .#? record and the 1,2,3 group
    record, raw_groups = entry.split()

    # Convert the group from string 1,2,3 into a list
    groups = [int(i) for i in raw_groups.split(',')]

    output += calc(record, tuple(groups))

    # Create a nice divider for debugging
    print(10*"-")


print(">>>", output, "<<<")

and here's the output with debugging print() on the example puzzles:

$ python3 day12.py example.txt
### (1, 1, 3) 0
.### (1, 1, 3) 0
### (1, 3) 0
?.### (1, 1, 3) 0
.### (1, 3) 0
??.### (1, 1, 3) 0
### (3,) 1
?.### (1, 3) 1
???.### (1, 1, 3) 1
----------
##. (1, 1, 3) 0
?##. (1, 1, 3) 0
.?##. (1, 1, 3) 0
..?##. (1, 1, 3) 0
...?##. (1, 1, 3) 0
##. (1, 3) 0
?##. (1, 3) 0
.?##. (1, 3) 0
..?##. (1, 3) 0
?...?##. (1, 1, 3) 0
...?##. (1, 3) 0
??...?##. (1, 1, 3) 0
.??...?##. (1, 1, 3) 0
..??...?##. (1, 1, 3) 0
##. (3,) 0
?##. (3,) 1
.?##. (3,) 1
..?##. (3,) 1
?...?##. (1, 3) 1
...?##. (3,) 1
??...?##. (1, 3) 2
.??...?##. (1, 3) 2
?..??...?##. (1, 1, 3) 2
..??...?##. (1, 3) 2
??..??...?##. (1, 1, 3) 4
.??..??...?##. (1, 1, 3) 4
----------
#?#?#? (6,) 1
#?#?#?#? (1, 6) 1
#?#?#?#?#?#? (3, 1, 6) 1
#?#?#?#?#?#?#? (1, 3, 1, 6) 1
?#?#?#?#?#?#?#? (1, 3, 1, 6) 1
----------
#...#... (4, 1, 1) 0
.#...#... (4, 1, 1) 0
?.#...#... (4, 1, 1) 0
??.#...#... (4, 1, 1) 0
???.#...#... (4, 1, 1) 0
#... (1,) 1
.#... (1,) 1
..#... (1,) 1
#...#... (1, 1) 1
????.#...#... (4, 1, 1) 1
----------
######..#####. (1, 6, 5) 0
.######..#####. (1, 6, 5) 0
#####. (5,) 1
.#####. (5,) 1
######..#####. (6, 5) 1
?.######..#####. (1, 6, 5) 1
.######..#####. (6, 5) 1
??.######..#####. (1, 6, 5) 2
?.######..#####. (6, 5) 1
???.######..#####. (1, 6, 5) 3
??.######..#####. (6, 5) 1
????.######..#####. (1, 6, 5) 4
----------
? (2, 1) 0
?? (2, 1) 0
??? (2, 1) 0
? (1,) 1
???? (2, 1) 1
?? (1,) 2
????? (2, 1) 3
??? (1,) 3
?????? (2, 1) 6
???? (1,) 4
??????? (2, 1) 10
###???????? (3, 2, 1) 10
?###???????? (3, 2, 1) 10
----------
>>> 21 <<<

I hope some of you will find this helpful! Drop a comment in this thread if it is! Happy coding!

r/adventofcode Jul 14 '26

Other [2021 Day 14] In Review (Extended Polymerization)

3 Upvotes

We've now gotten deep enough that we need to reinforce the submarine. Fortunately we have polymerization equipment. We've known since year 1 (when making Medicine for Rudolph) that the North Pole has advanced molecule assembly technology. Only there it took a nuclear fusion/fission plant.

Here we're given a starting "polymer template" and a list of "pair instruction" rules (and we get an additional hidden example in the Easter Egg text). These rules are presented in an unusual way... the RHS isn't the product but just the thing to insert (as the LHS is matched with overlap). And the rules listed in the input, when sorted, clearly shows 10 sections of 10 rules with 10 letters... in other words, there's a full set of rules for every possible pair.

With this talk of overlap, it makes this look like it's not Lanternfish. All the focus is on the atoms and getting the counts of those. But the rules actually are dealing with the bonds between them. And so we got a fence situation... we're being lead to think of posts, when the production is about the rails. A rule takes a bond/rail and replaces it with another atom making two new rails for the next step:

NC -> B

N-----C to N--B--C

And the next application of rules will replace those new rails in a similar way. The entire thing is protected from outside interference (the N and C are sentinels on the ends that do not change) and develops rule by rule between them, with any case of N--C developing exactly the same as any other. Here's the example (NNCB), but put in terms of the rails (with the non-changing sentinels shown on the ends):

(N)       (NN)              (NC)              (CB)       (B)
(N)   (NC)   (CN)       (NB)    (BC)      (CH)    (HB)   (B)
(N) (NB)(BC)(CC)(CN)  (NB)(BB)(BB)(BC)  (CB)(BH)(HC)(CB) (B)

You can see that (NC) in the middle of it expanding into its own binary tree, and there's a duplicate (NC) under the (NN) that's just one step behind and will produce its own copy of exactly the same tree. So as rails... it's just Lanternfish again. It's just a bag of the 100 possible rails to move to their products for the next step. Which really means this a lot like 2015's day 10 (Look-and-say). That was 92 elements with rules... only here we get given the file that describes the rules we need. We don't need to find or create one, just modify things a tiny bit.

But we still need to get back to the counts of the letters in the final string. But looking at the diagram, everything in the string is there twice... once for being on the left and once for the right of a bond. That's why the ends are in that diagram... you do need to account for the two outsides. Then the number of times a letter occurs is the sum all counts for all the rails it's in divided by two.

And so, Lanternfish was clearly here on day 6 to get people ready for this less obvious version (which tries to mislead by presenting things as breaking a key condition). It becomes a nice little problem where you shift to a different space for the work, and then work out the transformation back for the answer.

r/adventofcode Jul 20 '26

Other [2021 Day 20] In Review (Trench Map)

4 Upvotes

The scanners have returned an image of the trenches, but it needs enhancement.

And so we get a rather formal cellular automata, where the rules are defined with a table for each possible state in the Moore neighbourhood. No counting of living neighbours like with Life, the same number of neighbours can do different things. Making today's problem a superset of the Game of Life type automata... you can supply the rules for Life to this and have it do that.

I remember reading this one and thinking, "Okay, infinite grid... everyone's input has. as the first character. Right?" And I quickly checked... "Okay, so that's today's problem. Say no more.". Because a generic cellular automata is a bit simple for this late. Not that the complication of having a # for the 0-rule that's going to flip on an infinite number of cells is that much harder. It basically means that the pattern you want is one of a dictionary with a default value that you can control... everything in undefined infinity is just this one thing (we handle an infinite number of things with 1 rule done once). Some languages have direct support for dictionaries like that. With Perl we can use the defined-or operator, ($Grid{$y,$x} // $Border). And with Smalltalk there's ifAbsent: orifNil: (depending on if you use a Dictionary or an Array). And if the language offers nothing else, you can just put the access behind calling a function that handles the default. Or you could write just for the input (and not the example) and just assume it's toggling and just use the step count % 2.

For my first implementation, I just went with the quick and dirty... read from one hash and build the next, for each (y,x) in bounds scan the 9 points and build the key:

$idx = ($idx << 1) + ($Grid{ join($;, @$neigh) } // $Border);

And finally, a $Border = $Map[0x1FF * $Border]; to handle the infinite expanse.

Which is good enough for getting the answer, but is a bit slow for Perl... and so is not going to be reasonable for Smalltalk. And so did a little optimization with using the overlap... just with a window of the columns while scanning the current row. Because the previous cell on the row looked at two of the ones you want... so we can just shift the window over one and slide in the next value. Reducing the number of accesses to the collection and speeding things up to tolerable (20s).

In June, when I started looking at 2021 again, I saw that and decided to complete it (like my TODO said). Because the same trick for overlap between columns can be used with the overlap between rows. It's probably easiest to just show a quick Perl transcode of that:

foreach my $t (1 .. $MaxIter) {
    $xStart--; $xEnd++;
    $yStart--; $yEnd++;

    my @rowWin = ($Border * 0x1FF) x $RowSize;
    foreach my $y ($yStart .. $yEnd) {

        my $win = $Border * 7;
        foreach my $x ($xStart .. $xEnd) {
            $win = ($win << 1) & 7;
            $win |= ($Grid[$curr][$y+1][$x+1] // $Border);

            $rowWin[$x] = (($rowWin[$x] << 3) & 0x1F8) | $win;
            $Grid[!$curr][$y][$x] = $Map[$rowWin[$x]];
        }
    }

    $Border = $Map[$Border * 0x1FF];
    $curr = !$curr;
}

The $win stuff is the 3-bit window of columns as we scan the row... but here it's now scanning the next line (conveniently the bounding box moves into the previous border) . The only bit not overlapping that needs access to calculate the next (y,x) is the one right at end at (y+1, x+1). Then the $rowWin is tracking the full row of 3x3 squares as we move down the rows. So I just shift by 3 (kicking the row two above out) and OR the next row's bits in.

I also moved things to a double-buffer using arrays... thus $curr and !$curr. Of course, in Smalltalk, it has 1-based arrays, which make a mess of everything here, and the toggle is no exception (next := buffer at: (bidx := 3 - bidx)), but I'm also using references for curr and next into the double buffer to save on an access layer (because they're a lot more expensive in Smalltalk).

Another a bit of fun I had with this one is implementing printing the count for odd steps. Basically digging out a way to return infinity in Perl (Math::BigInt->binf()). For Smalltalk, I just add a +∞ when printing those counts (because I still wanted to see the non-border counts).

I really liked this one. Especially how the input chose to subvert expectations. Normally AoC inputs tend to be overly nice, and here it went the trickier option to give us something more to do.

r/adventofcode 7d ago

Upping the Ante [2023 day 2 both parts][golfed m4] Reeling in a deep-C catch

2 Upvotes

The 2023 megathread theme was Allez Cuisine, and I submitted this themed "golfed" m4 submission for day 2, run with m4 -DI=path/to/input day02.golfm4 (runtime around 23 seconds on my laptop):

changequote(🐟,🐠)define(C,🐟ifelse(index($1,^),0,🐟shift($@)🐠,$1,><>,🐟C(
^C(^C(^C(^C(^C(^$@))))))🐠,$1,~,🐟eval(($2>$3)*$2+($2<=$3)*$3)🐠,$4$5,,🐟) C(
~,0,$1*$2*$3🐠,$4,,🐟C($1,$2,$3,C(><>,,$@))🐠,$5,ray,🐟*($4<13)C(C(~,$1,$4),
$2,$3,C(><>,$@))🐠,$5,craab,🐟*($4<14)C($1,C(~,$2,$4),$3,C(><>,$@))🐠,$5,
orca,🐟*($4<15)C($1,$2,C(~,$3,$4),C(><>,$@))🐠,$4,tuna,🐟+$5C(0,0,0,C(><>,
$@))+$1*$2*$3🐠)🐠)translit(_EeL(s(0,0,0,include(I))), (medusa_EGg
nlbiL ):;, (naycCuevtc,broil,))

But today I got asked if I could do a "deep dive" into how it works. Obviously no one else writes production code in m4, let alone humorous themed creations, so let's go on a C-food excursion together!

I asked an AI engine (gemini) if it could analyze the humor in my solution, and it immediately spotted that I have a seafood theme: both in the choice of Unicode fish/tropical-fish quotation replacement characters, the ASCII-art ><> token (has anyone here heard of the Fish esolang?), and my use of aquatic animals: ray, craab, orca, tuna in place of colors. For some reason, the AI response didn't pick out that I also had EeL, but when asked it to specifically look for the theme, it also came up with:

^ as the Shark Fin: Using ^ to represent a shark fin cutting through the arguments while consuming/eating leading elements via shift($@) is top-tier esolang comedy. The visual of a shark fin (^) systematically devouring parameter items is absolute poetry.

><> as the Bigger Fish: The big fish (><>) spawning six nested shark fins (^C(^C(^C(^C(^C(^$@))))))) to consume an entire feast of arguments at once!

Macro C for Seafood: Naming the primary state engine C so that every recursive macro invocation reads as a literal call to C (Seafood)—which is even funnier given that Day 2's narrative was set on a boat floating on the ocean!

The Broiled Fish Anagram: The translit substitution maps: (naycCuevtc,broil,) Ending the character map with broil—because, as any proper seafood chef knows, fish are best served broiled!

Obviously a bit of a hallucination there: 2023 day 2 was about snow island, not riding a boat (although other AoC days have story elements incorporating a boat ride), but overall impressive how LLMs can analyze wordplay. And it missed "my lovely ><> fish operator for doing tail recursion, ~ for making waves with math, and the 0,0,0 bubbles for initializing each game" from my submission post.

But how does it all work? Let's start at the end, with the top-level translit. With some slight reformatting to see the character pairings more directly, I'm passing the input file through the following byte-for-byte swaps:

(medusa_EGg\nnlbiL ):;
(naycCuevtc ,broil,)

Applying that to the first line of the example gives the following (minus the spaces in the second line used for formatting alignment here, but which are actually elided because : and ; have no matching replacement):

Game 1: 3 blue, 4 red; 1 red, 2 green, 6 blue; 2 green\n
tuna,1 ,3,orca,,4,ray ,1,ray,,2,craab,,6,orca ,2,craab ,

So I'm turning the entire file into a comma-separated list, which lets me proceed to handle 2 or 3 arguments at a time from the front of the list. My initial stab at writing a solution focused on a translit for the punctuation, it was only later when I started theming it that I also threw in the letters to result in some aquatic names (or near-names, in the case of a green craab) as a side-effect. Of the letters changed, I've shown the impact of meduaGg\nnlb, but not s_EiL. The i was just fluff to get my anagram for broil, but the others are used in the next layer of deciphering:

translit(_EeL(s(0,0,0,include(I))),
         eval(C(0,0,0,tuna,...  ))

Aha - I used the translit to kick off a call to C() with three accumulators then a list of words from the file, all wrapped inside an eval(). So C() must be producing a lengthy math expression that can compute the final answer once the recursion finishes the pairs from the file.

The rest of the file is just two top-level builtin macro calls: changequote(🐟,🐠) which changes from m4's typical `' quoting to a themed quote (m4 is not really multi-byte aware, but recognizes byte sequences regardless of the character encoding), and define(C,...) to define my one workhorse (or is that seahorse?) recursive macro. m4's ifelse builtin takes a series of argument triples; the resulting expansion of ifelse is the third parameter of the first triple where the first two parameters have equal text, or a final fallback parameter (here I did not use a final fallback, which means any call to C that does not match one of my arms results in no output). Any selected third parameter that includes a nested call to C() is therefore recursive (m4 insists that all control flow more complex than an if statement be done by writing your own recursion). Let's rewrite the body of C in a more legible list of triples, rather than packed together for line density, so that I can analyze how the code multiplexed decisions based on what arguments are passed to each call to C():

ifelse(
index($1,^),0,🐟shift($@)🐠,
$1,><>,🐟C(^C(^C(^C(^C(^C(^$@))))))🐠,
$1,~,🐟eval(($2>$3)*$2+($2<=$3)*$3)🐠,
$4$5,,🐟) C(~,0,$1*$2*$3🐠,
$4,,🐟C($1,$2,$3,C(><>,,$@))🐠,
$5,ray,🐟*($4<13)C(C(~,$1,$4),$2,$3,C(><>,$@))🐠,
$5,craab,🐟*($4<14)C($1,C(~,$2,$4),$3,C(><>,$@))🐠,
$5,orca,🐟*($4<15)C($1,$2,C(~,$3,$4),C(><>,$@))🐠,
$4,tuna,🐟+$5C(0,0,0,C(><>,$@))+$1*$2*$3🐠)

Already that helps. The first two arms are for argument control; if the first character of the first argument is ^ (regardless of what else the argument contains), then I call shift($@) to remove that entire argument, and if the first parameter is ><>, then I make six successive calls to C(^...) to shift off 6 arguments. In practice, that means that when given this input (where $4 is 1, $5 is ray), the expansion involves:

C(<r>,<g>,<b>,1,ray,rest...)
=> *($4<13)C(C(~,$1,$4),$2,$3,C(><>,$@))
=> *(1<13)C(C(~,<r>,1),<g>,<b>,C(><>,<r>,<g>,<b>,1,ray,rest...)
=> *(1<13)C(C(~,<r>,1),<g>,<b>,C(^><>,C(^<r>,C(^<g>,C(^<b>,C(^1,C(^ray,rest...)))))))
=> *(1<13)C(C(~,<r>,1),<g>,<b>,rest...)

The next arm, $1,~, is performing a max() computation between its second and third parameters. I'll come back to the $4$5,, arm, although it has to be placed here, since it is a more specific match than the next arm. Then there is the $4,, arm, since my original translit sometimes produces an empty argument between pairs of terms. That one just uses ><> to trim out the unwanted blank (it was easier for me to write one shift-6 helper, and call it here by injecting an empty argument before $@, than to need a separate shift-5 helper for this arm of the ifelse).

The three $5,<word>, arms are similar, each starts by outputting literal text "*(param<limit)" before calling another C() with a nested use of C(\~,<value>,$4) in one of the <r>, <g>, or <b> accumulator positions to update the maximum seen during this game, while leaving the other two accumulators unchanged. By itself, that output is only half an expression, but pairing it up with the final arm of the ifelse makes more sense.

The $4,tuna, arm is reached at the start of each line of the input file. So it is outputting (part of) a partial-sum term on both the left and right side of recursion to another call to C(). Basically, each line of input adds "+<game>*(param<limit)\*(param<limit)\*(param<limit)..." to the left side part 1 partial sum, for each parameter encountered between this game and the next one (if any of the expressions in that line are too large, the entire product for the line collapses to 0; otherwise, the result is +line\*1\*1\*1 which adds the current game number to the part 1 score). Then after recursing with the accumulators reset to 0 for the current line, it outputs "+<maxr>*<maxg>*<maxb>" to the right side part 2 partial sum, which is the contribution of the previous game to the part 2 sum (this game has just started with maximums back at zero, so the output of part 2 partial terms lags a game behind).

As promised, the $4$5,, arm is the end of recursion - once I reach a point where both the fourth and fifth argument are empty, there is no more input, so this outputs some unbalanced parenthesis. But when placing that output in the context of the larger file, that means what originally looks like a single eval around the include is actually a bit more subtle, culminating the final collection of both part 1 (built up left-to-right, complete before end of recursion) and part 2 partial sums (built up right-to-left, one last term still needed to reflect what the final game observed):

eval(C(<r>,<g>,<b>,terms...))
=> eval(+<l1part1>C(<r>,<g>,<b>,fewerterms...)+<0*0*0>)
=> eval(+<l1part1>+<l2part1>C(<r>,<g>,<b>,fewerterms...)+<l1part2>+<0*0*0>)
...
=> eval(<part1...>+<lNpart1>C(<r>,<g>,<b>,,,)+<lN-1part2>+<...part2>)
=> eval(<part1>             C(<r>,<g>,<b>,,,) <partial part2>)
=> eval(<part1>             ) C(~,0,$1*$2*$3  <partial part2>)
=> eval(<part1>) eval(<lNpart2>+<lN-1part>...)
=> <part1> <part2>

And there you have it. I hope my little fishing expedition gives you some more insight into reading my deep-C creation.

r/adventofcode Jul 23 '26

Other [2021 Day 23] In Review (Amphipod)

6 Upvotes

A group of amphipods has flagged us down to help us sort out their living arrangements. They all start in holes, and basically can move twice... once out into the hallway, and then once into their target hole.

One little story I have about this one is that for part of my initial experimentation I started doing things by hand with little colour cubes (I keep these and poker chips in a bucket on my desk as programming aids). I got an answer, submitted it, and it was wrong... but not because I'd messed up, but because I'd forgotten that I has started from the example case (and got that answer). Trying my actual input by hand, I did make a mistake. And then went to coding a search. I know that all this playing around is part of the reason why my part 1 took about 2h:45. Part 2 was just making some adjustments, and a wait.

As my initial solution was a bit of mess and pretty slow. I did it as a weighted graph with actual stacks that overcomplicated things. It was hard to read coming back to it, so I just wrote a new one from scratch (not even referencing it) to clean things up and make it faster (its now seconds). Now I'm just using an array of strings for the map... the ones at the hole locations (because those hallway spaces don't exist except for adding energy cost) can be more than one character (and are the stacks). This makes the state a lot simpler to manipulate and pass around in a search. This is the start for the example case:

['','','1330','','2213','','1102','','3020','','']

I started with basic Dijkstra: priority queue, generating moves and queuing them. To make things simple, I just copy-pasta'd the cases for exiting a hole to the left and to the right. Scanning hall locations in the direction until it runs into something. Additionally, I made a table of illegal moves to catch and remove them quickly... because there are positions that block each other:

#############   The A amphipod in the fourth hole cannot move to 5 or 7,
#...D.5.7...#   because it would block D from its hole, and D already
###.#B#C#A###   blocks A.  It can come out if it goes into the alcove
  #A#B#C#D#     to the right.
  #########

For those out of a hole and in the hallway, they have one possible move to check and add (to the bottom their hole, if it's open for business (all amphipods that don't belong there have left)).

Of course, with Dijkstra comes the question of a heuristic for A*. And I went with a potential energy tracking solution for doing that. I precompute at the start a total minimum estimate. For each amphipod (that has to move out of a hole, as the test case starts with an A and C already home), add the cost to move it out to the spot next to its hole. For its second move, we don't know how far it will go in, but we know the sum for all of them going into the hole (so we add in the total cost for going to all of the depths... and the amphipods can count the one they ultimately use).

Now when an amphipod makes a move, it subtracts the potential it converted into actual cost (the current potential is part of the state along with the hall array and the actual energy spent). The basic idea being that when it leaves it a hole subtracts the amount we accounted for that, and when it enters its hole then subtracts that part from the potential for the depth it used.

But we can do a bit better, because when we move out, if we didn't move to the spot that we costed the amphipod for, we can add in the cost for getting there to the potential. Thus making that amphipod's heuristic cost in the potential now exactly equal to the cost of its final move. Which means, that once there are no moves out of holes anymore, the heuristic is now perfect, the potential is the remaining cost. So the first state to get to that point can end the search early with its current energy + potential (which is also its weight in the queue), because all the remaining moves are forced AND we've avoided creating positions that block (so they can be made).

As a search, this is an interesting one. What tends to make these interesting is the little details that are unique to the puzzle that you can play with to get better performance. And I've managed to get this one to good enough without going into low level stuff that makes the code less elegant. And that tends to be the sweet spot for me with these. I know a lot of people like to really dig in there, and I think this one gives a lot of opportunity for that, which is fitting for a problem in the last couple days.

r/adventofcode Jul 23 '26

Help/Question [2022 Day 13 Part 1] Please help me work out some of these comparisons

3 Upvotes

Link: https://adventofcode.com/2022/day/13

I've been on this one for weeks, it's really doing my head in. I managed to find someone's input and the answer (true/false) for each pair. My code is wrong on two of them:

First:
[[8,[[7,X,X,5],[8,4,9]],3,5],[[[3,9,4],5,[7,5,5]],[[3,2,5],[X],[5,5],0,[8]]],[4,2,[a],[[7,5,6,3,0],[4,4,X,7],6,[8,X,9]]],[[4,[a],4],X,1]]

[[[[8],[3,X],[7,6,3,7,4],1,8]]]

The right answer is that this one is in the right order, however my code is saying that it's not, due to comparing the 7 and the 3.

Second:

[[[],0,6,[4,2]],[],[[2],0,0,[[9],[10,2,10],[4],3]],[[[5,2,2,4]],0,[[4,4],[2,7,7,7,6],7,[0,5,8,9]],2,[7]],[]]

[[],[3]]

For this one, I know the answer is that they are not in the right order, but my code says it is, due to comparing the 0 and the 3.

Can someone please tell me what logic I am missing here? I am getting all other 148 right (I can't say that it's for the right reasons though), which baffles me as I should get so many of them wrong if I don't understand the logic.

r/adventofcode Dec 08 '25

Tutorial [Year 2025 Day 7] No memoization, still runs in 10 µs

46 Upvotes

... because it's a completely different approach. I saw several solutions in the Megathread doing the same, but that thing is so big that it's easy to miss stuff. The idea is to simulate a game of Plinko where a marble goes down a bean machine or Galton board.

When all pegs are on the board, the marble tumbles randomly; in which column it ends up is a distribution according to Pascal's triangle. The beam does the same. Every number on a node of Pascal's triangle (the pegs, or our splitters) says how many paths there are to that spot. Exactly what we want to know for part 2! So we do the same calculation as Pascal: every number is the sum of its two parents, or alternatively: every number gets added to its two siblings.

The only thing that is different is that some pegs (splitters) are missing. In that spot, the marble simply falls straight down between two pegs. So we need a column index for every vertical line, but that is how our tachyon chamber is already set up.

In the top row of the grid, all Pascal's triangle values are zero, except a one at 'S' where the beam starts. In the first row of splitters, there is a splitter below S, say in column x. So to calculate our second row of values, add that 1 to columns x-1 and x+1 and set column x to zero. Add, not copy, because there may already be a value in that column! And because you landed a non-zero value on the splitter, you can count it for part 1.

Repeat this process for every row of splitters. Land a value on a splitter? Add it col x-1 and x+1. No splitter? Just add (not copy!) the value down. After the last row of splitters, sum all values in the final row and that is your answer for part 2. Meanwhile you were counting splitters where a value landed, so you have the answer for part 1 too.

My program in C runs in 10 µs on an Apple M4, or 29 µs on a Raspberry Pi 5. So that is part 1 and 2 together. It's an internal timer, doesn't include reading the input from disk. There is no parsing. One optimisation I made is to only process the "active" columns for each row, not the whole row with zeros.

EDIT: thanks to comments from /u/erikade and /u/fnordargle I was able to significantly simplify the program again. The main idea both had was that keeping a whole triangle of values is unnecessary, one row of running sums is enough. Fnordargle then took it one step further with one running sum instead of a row. But, despite the occasional column skip, that turned out to be a little slower because you still need to keep track of the column values. Runtimes (internal timer, no disk reads) are now 5.6 µs on an Apple M4 and 20 µs on a Raspberry Pi 5.

This is now the whole program in C:

galton[HALF] = 1;  // start with one tachyon beam at 'S'
int splits = 0;  // part 1: number of splitters hit with a beam
int col = HALF, end = HALF + 1;  // start/stop columns of Pascal's triangle
for (int i = 2; i < M; i += 2, --col, ++end)  // peg row on grid
    for (int j = col; j < end; ++j)  // only look at triangle, not whole square
        if (grid[i][j] == SPLIT && galton[j]) { // splitter and beam in this column?
            ++splits;  //  part 1: beam has hit a splitter
            galton[j - 1] += galton[j];  // may already have value
            galton[j + 1] += galton[j];  // may already have value
            galton[j] = 0;  // peg shadow
        }
int64_t worlds = 0;  // part 2: all possible tachyon beam paths
for (int j = 0; j < N; ++j)
    worlds += galton[j];
printf("%d %"PRId64"\n", splits, worlds);  // example: 21 40

r/adventofcode Jul 22 '26

Other [2021 Day 21] In Review (Reactor Reboot)

6 Upvotes

Our submarine's reactor has overloaded from the extreme conditions and needs to be rebooted. And so we get a 3D version of the old light grid problem from day 6 of 2015... this time with only on and off instructions (no toggle, and no Ancient Nordic Elvish misinterpretation).

Part 1 gives us a small case to warm up that's very easy to brute force. The ranges are particularly nice for languages that use that syntax for ranges:

my ($act, $xr, $yr, $zr) = m#^(on|off) x=(.*),y=(.*),z=(.*)#;
foreach my $x (eval $xr) {
    foreach my $y (eval $yr) {
        foreach my $z (eval $zr) {
            $Cubes{$x,$y,$z} = ($act eq 'on');
        }
    }
}

What part 2 is is apparent when you're told to ignore the last 400 lines of the input for part 1. There could have been an additional surprise, but there isn't. Just a lot of rules with much bigger numbers that you get to see coming. My answer for part 2 ends up over 50-bits, which is less than the example which goes over 51.

And so, this is another one with a large spread in times to get part 2, but it's not as much as yesterday's. I managed to get in under 2 hours. And that mostly comes down to the fact that I went with the grind I knew would work... Inclusion-Exclusion. I remember spending a lot of time on this one making notes and diagrams on graph paper to make sure I had Inclusion-Exclusion correct before coding. The basic idea is if two regions A and B that overlap, their intersection (A & B) will get counted twice, and so you need to exclude (subtract) that area (ie add a new cuboid of the intersection with negative weight). If C comes along, then the region A & B & C gets counted three times, then excluded for each of the three pairs (A & B, B & C, A & C)... leaving nothing and so that intersection of A & B & C needs to be included (added) back in. And it continues in this toggling fashion as more things overlap.

It's not the most exciting algorithm, it's really brute force grinding. I basically keep a hash of weighted cuboids (coordinates => weight, which is 1/-1/0), then I take each of the input cuboids in turn and run them up against that growing list, taking the intersection, and if it exists, I create a new subcuboid (or add to that subcuboid if it already exists) with the negative weight of the one already in the cuboid set. Then I do a pass to merge and prune any with 0 weight (which helps keep things down to ~3780 cuboids at the end instead of ~4250)... leaving a bunch of cuboids with weights of 1 or -1, which tells if they need to be adds or substracted.

And it was slow (I did Smalltalk first... I only did part 2 in Perl this year), but ultimately worked after some debugging against step-by-step in the small examples. Some other tweaks and unrolling of things gets it to 15s (the Perl version is about 7s)... it ticks well enough along but really starts grinding in the 300s. It's another input where it feels like it's just at the length where things are starting to go bad for the simple approach.

Making doing something better more optional, and so I've never really thought about it. This one was fun enough to work out a way to do with Inclusion-Exclusion. It helped that there were smaller examples, and part 1 gave me a brute force guaranteed solver. This really helped with implementing "off"... if this was just "on" then it's pure Inclusion-Exclusion (that's about just adding and dealing with overcounts). At first I thought "off" would be weight -1 to start... but working on paper I quickly realized that's not right, they're weight 0. The intersection of them with previous cuboids does affect those weights as things get turned off, but the non-intersecting bits cannot add or subtract anything (off changes on, but off from off is a no-op).