r/adventofcode

Today we find ourselves on Pluto, and leave the searching of the infinite doughnought maze to the Historians. Our attention is instead taken by a set of what appear to be quantum-locked stones, that move and reproduce whenever we blink. Each stone has a number, and they're in a perfectly straight line... numbers with an even number of digits split, else they get multiplied by 2024 (or incremented to 1 if 0). The starting configuration for my input has 8 stones, with a 0 plus numbers with each of 1-7 digits.

This one is one of those one's where it emphasizes that the stones are ordered in a line, which should make you think how important that really is. Especially since the answer we want is order independent. And when you start looking at it that way, you see that you've got things in states, that have products that are independent and never interfere with the products of others. In other words, it's a Lanternfish problem.

And so typical Lanternfish approaches are going work for getting the scale up for part 2. So with Smalltalk that's moving things from a Bag of states to a new Bag based on the rules. In Perl I used substr to split the numbers in half, but arithmetic is much faster in Smalltalk for this:

stones contents keysAndValuesDo: [ :value :num |
    len := (value floorLog: 10) + 1.    " Note: floorLog returns 0 for value == 0 "
    (len even) ifTrue: [
        factor := 10 raisedToInteger: len // 2.
        next add: value // factor  withOccurrences: num.
        next add: value \\ factor  withOccurrences: num.
    ] ifFalse: [
        next add: value * 2024 + (value == 0)  withOccurrences: num.
    ]
].

Note that Boolean has been extended to promote to zero for the odd case.

Of course, there's one little detail to worry about with this problem and Lanternfish approaches... and that's that you should be somewhat concerned that the rules might make the states potentially open ended or very chaotic making the number of states explode with the stones. But this problem is nicely designed not to do that... my input tops out at 3811 states (and only 3759 are used for the first 75 generations), with the largest at ~38.6 bits. That's a very large matrix if you want to do that Lanternfish approach.

Since the input is numbers, I did do a dc solution for this one where you can just echo in the number of blinks you want:

echo 75 | dc -finput -e'?st[1+]s+[*1+q]sZ[_4R++s.q]sM[+s.A0 0]sH[dZ2/Ar^~3Rd3RrlRx_3RlRx+d3R:mq]sE[d0=Zd1-3RdA0*4R+dd9d^<H_4R;md0<MrdZ2%3R=E2024*d0=+rlRxd3R:m]sR0[rltlRx+z1<L]dsLxp'

This was originally written for v1.4.1, but you needed a hacked version like mine with skip lists if you wanted it to run reasonably (otherwise it could take minutes because of all the array accessing... it's fast to 50, but then it explodes). But the use of ? here just to read the number of blinks and is not a problem for dc v1.5.2 with hash table arrays, so it run well with that.

EDIT: Did a bit more exploration into the patterns in the input. Although my input stabilizes to 3811 states in every generation, there are 3849 different states that occur. The highest value is actually about ~44.44 bits and occurs 2 blinks in from the largest value in the input. That value is also responsible for the last new values that are reached... seven 4 digit numbers that all arrive on the 73rd blink, and all trace their origin back to that same largest input value.

Today we are going to help a reindeer reconstruct the hiking trail map of an area recently scoured by lava. We have a digital height map (0 to 9) and are told to, for all starting points (elevation 0) find out how many peaks (elev. 9) can be reached from that point while always climbing exactly one level per step.

The total peaks sum is the part1 answer.

Solving this reminded me a lot of several previous map search puzzles, so I did it the obvious way: Use the input as a linear flat map, with newlines as a guard between each horizontal line and the next. I also put a line of guard characters before and after the input.

Next was a scan of the input map, for each '0' start a recursive DFS, using a parallel seen[] array to note visited cells, then just aggregate the counts.

In hindsight, it would probably be better to cache the search results from each visited cell, so that later searches could reuse the work previously done.

For part2 we are instead told to count how many different ways there are to reach a top, here I also used a recursive search, but totally forgot to make it memoizing!

Adding just two lines just now to return early with a cached answer, otherwise do the search and cache the result made my code more than twice as fast. The only reason it wasn't even larger was because every path had to be just/exactly 8 steps long, with very limited fanout, so the total overhead wasn't anything like previous search puzzles where a cache could very often save 95-99% of the work.

We're on the roof of the top-secret Easter Bunny installation, where we realize that the city contains a bunch of antennas, at many different frequencies. They are named with single digits, upper or lower-case letters, so there can be up to 62 different kinds.

For Part1 we are told to look for antinodes, defined as a location that are in line with a pair of same-frequency antennas, at the same distance away as the internal pair offset. We want to determine how many total locations contain one or more anti-nodes.

In Perl I created a hash of arrays, the hash is keyed by the antenna name (ascii byte value), this points to an array which contains the (x,y) coordinates of every antenna with that name. The list of anti-nodes was another hash table, keyed by the corresponding (x,y) pair. The main issue is that we have to ignore any locations that are outside of the city grid.

This worked pretty much as quickly as I could type it in.

For Part2 we need to iterate over all multiples of the internal distance, so we get a lot more antinodes, but otherwise it was more or less the same process. The only possible wrinkle was that if an offset between two antennas (dx,dy) has a common divisor, then we must get rid of that so I had to write a gcd() function to fix this even though it seems like it never actually happened?

Total Perl runtime 16 ms.

In Rust I first implemented it the same way, using HashSet, but later on decided that the name key set was small enough that it didn't matter if I extended it by filling in the gaps between '9' and 'A' and between 'Z' and 'a', and instead of a HashSet of antinode addresses I just used a linear byte array, using bit 1 for Part1 and 2 for Part2 locations.

When I ran my code just now the fastest was 3.9 us, so I'll have to average 1000 iterations to get a more precise measurement:

...

The average over 1000 iterations was 3519 ns, so less than half the 8 us shown by u/maneatingape.

I therefore tested 'cargo bench year2024::day08' and got

running 3 tests
test year2024::day08::parse_bench ... bench:       3,745.39 ns/iter (+/- 247.27)
test year2024::day08::part1_bench ... bench:         724.87 ns/iter (+/- 29.24)
test year2024::day08::part2_bench ... bench:       1,375.97 ns/iter (+/- 94.11)

So his total was about 5.8 us on my machine, not a very big but still somewhat significant difference.

Today an amphipod has a classic problem: It has a disk that is fragmented and it wants to defragment it.

The disk map is stored in a compressed format, alternating between a file length and a free space length. If there is no free space between two files, the free space length is 0.

For Part1, the amphipod moves blocks, starting with the last file block which it then moves into the first free block, systematically moving all blocks as close to the front as possible, and as a side effect reversing the storage order for all moved files. We then produce a disk checksum consisting of summing up for every file block the product of the file number and the block position.

For Part2, because the amphipod realized that the disk becomes too fragmented, it will instead only move full files as close to the front as it can find a large enough free space for them. The checksum is then calculated in the same way as Part1.

My Perl code solved this one using brute force for Part1:

First expand the run length encodings, using -1 to designate free blocks, the filenr ID for the files. My input contained 10K files, so worst case this could be expanded to an array with 9*2*10K = 180 K entries, but the average should be closer to half of this.

This setup made part1 really easy, just iterate from the front to locate free blocks and from the end to find file blocks to move.

For part2 we need to find open gaps large enough for a full file, so here it made much more sense to have free lists, either organized by size (1-9) and location, or just by location. Since all partially filled free spaces would result in a tail space which would have to be inserted in the right order in the smaller map I decided to use the simpler setup of a single free list.

I thought about keeping a cache of the last found free list entry of each size, but went brute force instead, always scanning from the beginning. I counted the scan iterations, the average was 133 entries inspected before finding a large enough slot, so a better data structure would have been faster.

Perl runtime was 271 ms on my slow Surface.

I started on a more ambitious Rust version but never had time to finish it the way I would have liked.

It would in fact have been easier to solve the defragmentation problem in an optimal way, using size-ordered free lists and always try to move files to an exactly large enough gap, only fall back to larger slots if none could be found.

Later edit:

Watching TV with my wife ("71 degree North", check it out if you can!) and waiting until Oslo midnight to make the reddit post, I looked somewhat unhappily at what I had written above:

I decided to at least implement the simplest possible cache I mentioned, just a table of the last found free entry for each size, this immediately dropped the runtime to 47.8 ms, so nearly 6x faster!

The number of free list steps dropped from 133 to 4.6 per file.

The only small problem was that I had to update the cache also for the tail end of a partially filled free space, when that was before the current cache entry.

    if ($flen >= $len) {
        my $remfree = $flen - $len;
        $free[$f] = $remfree;
        $free[$f+1] += $len;    # update free block position
        $files[$i+2] = $fpos;   # The file is moved here
        $lastfree[$len] = $f+2; # Next scan starts after this entry
        
        if ($remfree && $lastfree[$remfree] > $f) { $lastfree[$remfree] = $f; }
        last;
    }

Note that my lastfree[] array has entries for 0..9, so that I could blindly update it also for totally filled slots, but it was a percent or two faster to check for this situation and skip the zero updates.

Today we need to cross a bridge which is currently under repair, only the final calibrations remain, but the engineers have a problem: Each calibration consist of a target value and a computation which is supposed to reach that value. A group of nearby elephants have stolen all the operators so that only the numbers remain, our task is to figure out where we can insert '*' (multiplication) or '+' (addition) between the numbers to make it come out OK.

These equations ignore normal operator precedence rules, both are at the same level and will be applied as soon as possible.

In the test data set the number of values is so low that it seems OK to just try all combinations, in the real input we find up to 12-14 numbers but we would still only need to test 4096-16384 possibilities.

However, it is immediately clear that if the last operator is a multiplication, then the target value must be divisible by the last number. Otherwise it must be an addition, so then we can just subtract that value from the target and retry with the remaining set.

The obvious choice is therefore a recursive descent where we for each level first test if multiplication works, if so divide and recurse down, otherwise subtract and recurse.

This process finished in a ms or two in Perl.

For Part2 we are told that one elephant had hidden away a third operator, concatenation!

At this point all Perl programmers rejoiced since for Perl any number is both a string and a numeric value, so that checking if the last N digits match an N-digit value is dead simple, and so is removing the corresponding digits from the current target so that we can recurse.

My Rust code started out with the exact same logic, converting numbers to ascii and back for each concatenation attempt, and it took about twice as long as the Ape, even though I started with a sanity check: For concatenation to be possible, the last digits had to match so I checked this before doing the string conversion and comparison.

After I had stared at this logic for a while I realized that I could repeat the final digit check until it either stopped matching or all digits were OK, at which point the temporary target would contain the remaining leading digits, without any need for any binary-to-ascii and ascii-to-binary conversions!

At this point the inner logic was quite short & nice, it ran in 163 us:

fn try_part2(target:u64, nums:&Vec<u64>, pos:usize) -> bool
{
    if pos == 0 {return false;}
    let pos = pos - 1;
    let n = nums[pos];
    if pos == 0 { return n == target; }

    if target % n == 0 {
        let rem = target / n;
        if try_part2(rem, nums, pos) {return true;}
    }
    let mut n2s = n;
    let mut t2s = target;
    while n2s > 0 && n2s % 10 == t2s % 10 {
        n2s /= 10;
        t2s /= 10;
    }
    if n2s == 0 {
        if try_part2(t2s, nums, pos) {return true;}
    }

    let diff = target - n;
    try_part2(diff, nums, pos)
}

I guessed that u/maneatingape should have very similar logic, his time of 136 us on an Apple CPU could easily be explained by the optimized divider circuit in later Apple cores, but when I tested with cargo bench year2024::day07 I got 133 us on my Intel CPU, so he is still a fraction more efficient!

I am using the standard library to split the input into lines, I then parse each line with an extract_u64() function. When I tried to go hardcore with a full custom input parser, it turned out to be significantly slower.

>Each bit in the gamma rate can be determined by finding the most common bit in the corresponding position of all numbers in the diagnostic report.

what do they mean finding the most common bit in the corresponding position? what's the corresponding position? I thought at first that the most common bit is how many 1's or 0's there is in the binary number, but it's not, I couldn't find the pattern here plus my native language is not english

edit: okay now i get it, thanks for the replies!

First stop in our search is the nuclear plant where we made medicine for Rudolph in 2015. While the Historians search for their Chief, we agree to help analyze some data for the engineers.

And so we get another problem that just deals with numbers. The input has 1000 lines, each is a report which is a list of 5-8 numbers in the [1,99] range. A safe report is one which is monotone increasing or decreasing, and adjacent levels differ in the range of 1 to 3. For part 2, we discover that they have a Problem Dampener, that tolerates a single bad level.

Since I wasn't feeling well, I just brute forced this. Took the diffs and:

$part1++ if (all { abs($_) <= 3 && ($diffs[0] * $_) > 0 } @diffs);

For part 2, if this fails, I try splicing out each number in turn until one works (on not). I remember thinking a little bit about trying to spot the problem on the go... and it went like: if I get to the third number and discover there's a problem, the first or second could still be the problem to remove. And with these short lists, 3 items is a huge portion of it. So simpler to just go with programmer efficiency and test them one at a time. If things were longer it'd make more sense to get into doing things smart.

One interesting thing to note with the solution above is the use of arithmetic logic. I was already thinking of how to do this in dc. And so the trick in there to tell if things are monotone increasing or decreasing... I multiply each diff with the first. If that's always positive, things are monotone (ie all diffs have the same sign as the first one).

A side effect of this type of arithmetic logic is needing to consider the 0 value. And here we see it used to handle a case that appears at first glance to be missing... the check that the difference is at least 1. A difference of 0 fails the second multiplication test, and so that check actually handles 1½ of the rules.

In any case, the dc ended up as:

dc -e'[0*]sZ[1+]sC0?z[2-dsn[3Rd4R-Sdr1-d0<I]dsIx*ld+sa0ln[rLddd*v3<Zla*0<Cr1-d0<I]dsIx+ln/+?zd1<M]dsMxrp' <input

The combining of the two rules is done by conditionally multiplying difference >3 by 0, making that 0 in the second part of the test cover both parts. Another little trick in this one was that it keeps a count of the number of steps that pass and then divides it by the number of steps... a simple way to check that they're equal and get a 1 or 0 to add to the total for the answer (as we're working with 0 precision). And, whereas yesterday, the use of ? wasn't really that important to tell things apart, here each line has a different number of numbers... and being able to read the input one line at a time is useful without having to add delimiters to the input (although 0 is conveniently available for that).

And so for a problem I basically brute forced, I did do some interesting stuff in my solutions.

so the only thing i need is convert the item types to priorities. is there a better way to do this without making a big ol' if statement?

https://preview.redd.it/yp8wdtovq5th1.png?width=400&format=png&auto=webp&s=9189ba9997c370b8919213cbb3afddedc4dc9c6a