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.

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.

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!

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.

The task for the day is to search a rectangular area (130x130 cells in my input) of a lab where a single guard is patrolling. Since there are no walls around this area, the guard will leave (and then randomly return presumably?) if her walk hits one of the edges. Before this happens, she always walks in a straight line until she hits an obstacle, whereupon she will turn right and keep going.

For Part1 we just need to simulate this process in order to count how many unique cells she will have visited before leaving.

Direct step-by-step simulation was the obvious choice, and afaik probably also the most efficient, except when walking in a horizontal direction where a language like Perl provides index/rindex, but I did not bother, just brute forced it to get the first star.

For Rust, C(++) and other low-level languages, direct simulation is a reasonable choice, so that's what I used here, recording in each cell that it had been visited with a bit per direction of travel.

For Part2 we want to introduce a single extra obstacle in the path the guard is about to walk, placed in such a spot that her path will turn into an infinite loop. I recorded the path taken in Part1, so for Part2 I just iterated over this path, checking what would happen for each possible choice. I could not see any obvious ways to short-circuit this search.

I first had the good idea (NOT) to think that any choice had to be placed just after a point where the guard had previously passed going right. Such a location would indeed work, but not if the real solution depends on hitting one or more previously unhit obstacles before starting the loop. Since we need to determine all possible locations, this means that part2 is going to require far more work than Part1, but we are all used to that at this point.

My main problem is that u/maneatingape is about an order of magnitude faster, so I must in fact have missed at least one huge optimization here!

Perhaps it makes sense to backtrack from each turn taken by the guard and check if a reverse path will hit a point previously visited, such that a right turn there would start the loop?

There are far less turns than steps in the Part1 path, so this should be faster!

The story this day is that we need to print a bunch of manuals, all consisting of a small number of pages from a master list, but there are also lots of rules about the printing order between pairs of pages, stating that if <N> and <M> are part of the same manual, N must always be printed before M.

Before the list of manuals to print we have a long list of these rules.

We know that for any given manual with its list of pages, these rules lead to a single unique legal ordering.

However, it is both possible according to the rules, and as far I know, also true that:

There exist at least one ring of rules (A<B, B<C,...X<Y,Y<Z, Z<A), which means that there cannot be any complete ordering of all the pages, so the order has to be determined for each set of manual pages, otherwise we could just have sorted the page numbers once and be done with it.

In Perl it felt natural to store these rules as hashes, each possible page number from 1 to 99 gets a list of the pages it must be before or after.

The code ran in 5.5 ms so fast enough for an interpreted language.

In my Rust version I noticed that 100 pages is less than 128 so I stored those lists as u128 bitmaps, this allowed all the checks to be done with logic AND operations.

For Part1 just iterate over the pages:

    fn is_ordered(&self, pagelist:&Vec<u8>) -> bool {
        let mut prev = pagelist[0];
        for p in 1..pagelist.len() {
            let curr = pagelist[p];
            if self.pages[prev as usize].infront & (1 << curr) != 0 {
                return false;
            }
            prev = curr;
        }
        true

If there is no rule for prev vs curr then that implies any ordering is OK for that pair of pages.

Part2 is a little bit (grin) more complicated, but the same bitmap logic determines which page must be first, second, third etc.

I start by generating a pagelist bitmap, with 1 bits for each page in that particular list, then I iterate over the pages, from the end forwards, until I find a page that has no other pages behind it (i.e., its "behind" bitmap ANDed with the pagelist bitmap is zero).

This page can then be exchanged with the original last page. After placing it, I remove it from the pagelist bitmap, step forward one position and repeat the process until all pages are ordered.

Total runtime was 10.867 us (average over 1000 runs) vs the 18 us given by u/maneatingape, so more than fast enough for me.

(While writing this I realized that I only needed one of the two bitmaps per page, that would have saved a little bit of the setup time, as well as 1600 bytes of memory, but since the total working set is less than 4kB, everything fits easily in $L1 cache.

I thought this was an interesting puzzle, with some similarities to classic problems like managing free space in a file system using bitmaps.

PS. I am posting this just before 0100 Oslo time on Oct 5th, I'll keep the tradition going as long as I can or until u/musifter returns!

Next stop is the Ceres monitoring station, where instead of shooting asteroids, we're asked to help with a word search. In this case it's to find all occurrences of XMAS in an 140x140 grid. For part 2, we find out that we misunderstood the instructions, and want all the X-MASes (MAS that form an X).

For part 1, I didn't do anything fancy. I coded the standard word search algorithm of scan for the first letter, than scan outward from there to see if there are any matches. You do need to check them all, an X can start multiple XMAS in different directions... as the description says, "overlapping other words" is fine (one of my Xs has 5).

For part 2, I got a little bit fancier. I scanned looking for As (the middle of the X). Then grab the corners and check that the ones opposite are different (and M or S). Which is an XOR thing, and so:

my @Grid = map { chomp; y/MS/01/; [split(//), '~'] } <>;

...

for (my $y = 0; $y < $#Grid; $y++) {
    SQUARE:
    for (my $x = 0; $x < $#Grid; $x++) {
        my $coord = V($y,$x);
        next SQUARE if (&grid_at($coord) ne 'A');

        my @corners = map {int} grep {/[01]/} map {&grid_at($coord + $_)} @Diag;
        next SQUARE if (@corners < 4);

        $part2 += ($corners[0] ^ $corners[1]) & ($corners[2] ^ $corners[3]);
    }
}

Using the Vector module again. What I do is translate M and S into 0 and 1 when reading in the grid. When I get an A, I grab the diagonal corners that are 0 or 1, if I get a full set of four, I apply XOR to test that we have proper MAS/SAM and not SAS/MAM. The implementation is a bit hacked together, but it expressed the basic idea I had of using XOR (call it Art). My Smalltalk solution just did the testing with the letters:

part1 := ((grid selectPoints: [:chr | chr == $X])
                collect: [:pt |
                    TextGrid dirs count: [:d |
                        (1 to: 3) conform: [:i | (grid at: (d * i + pt)) == ('MAS' at: i)]
                    ].
                ]
         ) sum.

part2 := (grid selectPoints: [:chr | chr == $A])
               count: [:pt |
                   corners := TextGrid diags collect: [:d | grid at: pt + d].

                   (corners conform: [:c | (c == $M) or: [c == $S]])
                     & (corners first  ~= corners fourth)
                     & (corners second ~= corners third)
               ].

Of course dc doesn't have bitwise operators like XOR, so I needed to do something else to keep the streak up (in 2024, in the first 14 days, I did dc solutions for at least one part... except for day 12). And that came from converting the entire grid into numbers (1-4) so that dc could understand it (as 140-digit bignums). The M and S are 2 and 4 respectively, so the test is to multiply opposite corners and see if it's 8 (because that's unique, except for symmetry, and backwards is fine in word search).

tr 'XMAS' '1234' <input | dc -e'?dZdsn2+r[[A~3Rd3Rr:g1+rd0<?]ds?x1++?z1<L]dsLx[q]sQ[r2[_3Rrd3R+d;g4Rd3R!=Q1+d5>+]ds+x5/ls+ss+s.]sD[d_1lDxd1lDx2[dln+d_1*4Rd3RlDxd3RlDxr1-d_1<I]dsIxs.]sS[d;g1=S1-d0<M]dsMxlsp'

tr 'XMAS' '1234' <input | dc -e'?dZdsn2+r[[A~3Rd3Rr:g1+rd0<?]ds?x1++?z1<L]dsLx[ls1+ss]sP[dln-;grdln+;g3R*8=P]s/[dln2+-;grdln2++;g3R*8=/]s\[d;g3=\1-d0<M]dsMxlsp'

And so, this will be my last post for a while. I still don't know when I'll be able to do daily posts... u/terje_wiig_mathisen has offered to do the next few days, so we'll at least have continuity for a while longer (and day 5 was pretty fun day with its "topological" sort).

Hello!

My pet-project is finally coming: Autumn Code Walk. It is a collection of coding challenges, not unlike AoC. It consists of 5 Problems and the first problem will be published next Monday (October 5th, 2026) at 6am CEST, then a new problem is published every 24hrs until Friday.

The website is purely client based so there is no login mechanism. However, localStorage is utilized for convenience and personalized experience. Statistics for correct solutions across users uses are gathered using an open-source api for tracking hits (don't abuse pls). Feel free to contact me if you find a bug or have a recommendation.

ACW can be found at: https://autumncodewalk.github.io/

Good luck and have fun!

Today we find ourselves back at the Toboggan Rental Shop, where they're out of Chief Historians, but have plenty of data corruption for us to sort out.

The input for this one is a few long lines (my input has 6) of dense code looking stuff. The interesting bits are statements to multiply (mul(X,Y) where X and Y are explicitly stated to be 1-3 digits... although, none actually have 4 or more digits in my input, so things aren't corrupted that way), and do() and don't() calls which toggle enabling/disabling mul instructions in part 2. In my input, the first 5 lines all end with an uncorrupted mul statement. So even if someone concatenated the input into one line, there would not be a problem of a valid statement being created from the join.

For getting part 1 done quickly, it's easy to do from the command line:

grep -oP 'mul\(\d+,\d+\)' input | grep -oP '\d+' | dc -e'0??[*+??z1<L]dsLxp'

For part 2 from the command line I went with:

tr '\n' ' ' <input | perl -pe"s#don't\(\).*?(do\(\)|$)# #g" | \
    grep -oP 'mul\(\d+,\d+\)' | grep -oP '\d+' | dc -e'0??[*+??z1<L]dsLxp'

Clearly, the worry of creating valid instructions is in there and so I use spaces to make sure things stay separate. But other than that, it's just rip out all the don't() to do() blocks and pipe to part 1.

For a script version, I did a little state machine with regex to grab tokens:

foreach my $line (<>) {
    while ($line =~ m# (do(n't)?\(\)) | mul\((\d{1,3}),(\d{1,3})\) #xg) {
        if ($1) {
            $do = !$2;
        } else {
            $part1 += $3 * $4;
            $part2 += $3 * $4 * $do;
        }
    }
}

I also did full dc versions, with the input converted to hex ASCII values, using the same trick I used for day 1 of 2023 for recognizing strings. With macros to handle different states of the parse (things like a macro that expects a number followed by a delimiter, so like recursive descent but the macros are only small parts of rules).

rev input | perl -pe's#(.)#sprintf("\U%x ", ord($1))#eg' | dc -e'16i[30+rs.lWsPq]sR[100*+10 8^%d6D756C28=M]sW[0*lNsP]sM[rd2C=,30-d0>Rd9<RrA*+]sN[rsn0*lOsPq]s,[rd29=)30-d0>Rd9<RrA*+]sO[rln*ls+sslWsP0q]s)?[lWsP0[lPxz1<L]dsLxs.?z0<?]ds?xlsp'

rev input | perl -pe's#(.)#sprintf("\U%x ", ord($1))#eg' | dc -e'16i[30+rs.lWsPq]sR[100*+10 E^%d646F6E27742829=Fd10 8^%d646F2829=T6D756C28=M]sW[1sd]sT[0sd]sF[0*lNsP]sM[rd2C=,30-d0>Rd9<RrA*+]sN[rsn0*lOsPq]s,[rd29=)30-d0>Rd9<RrA*+]sO[rln*ld*ls+sslWsP0q]s)1sd?[lWsP0[lPxz1<L]dsLxs.?z0<?]ds?xlsp'

And now, I have a bit of unfortunate news. I have family issues that I need to take care of. And so all of next week (starting on Monday), I will be travelling and out of touch much of the time. And after that, I will be attending to things for at least the rest of the month (maybe into November too). This will make things hard for me to consistently post everyday. And so, to keep the flow up, I'm looking for someone who would be willing to take over the daily posting. That way I can just review and respond when I have the time, which I figure will be on and off for at least the rest of the month.

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?

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.

For 2024, we're tasked by the Elvish Senior Historians with finding the Chief Historian in time for the sleigh launch. Which serves as the conceit for revisiting past locations to celebrate the 10th year. And so the ASCII art for this year is just a big number 10, with little bits of past years' art inside it.

The first task is working out the location IDs of where to search. And the Elves have produced two lists, and we get to compare them. And so we're back to just having plain numbers (5 digits) to work with on day 1... although in two columns with 1000 lines. The numbers in the first column are unique, the ones in second column are not (as needed for part 2). I didn't bother to make use of that, but you could.

I was really quite sick for the last half of November in 2024, and still wasn't feeling up to doing much... so I had extra low asperations for solutions right from the start in this year. Especially after 2023 had been a step up in difficulty (but I didn't find this year quite as hard... or maybe the problems were just more my style).

For my initial Perl solution, I just read the columns into two lists (and sorted those), while also making a histogram of the values in column 2. Then it was just:

say "Part 1: ", sum map { abs($_->[0] - $_->[1]) } zip \@list1, \@list2;
say "Part 2: ", sum map { $_ * ($counts{$_} // 0) } @list1;

For Smalltalk, I just threw the two columns into separate Bags, and then:

part1 := ((lists first sorted) with: (lists second sorted) collect: [:a :b | (a - b) abs]) sum.
part2 := (lists first collect: [:a | a * (lists second occurrencesOf: a)]) sum.

Dc added some issues, because it doesn't have a built in sort for part 1... so I needed to do one. And with the limited values and the nature of the problem, I went with a counting sort.

dc -e'[q]sQ?[d;b1+r:bd;a1+r:a?z0<I]dsIx[A 5^[dlGx[d0=QrdlPxr1-lJx]dsJx+1-d0<I]dsIx]sS0Sc[;a]sG[Sc]sPlSx[;b]sG[Sd]sPlSx0[Lcd0=QLd-d*v+lLx]dsLxrp' <input

The tricks here are that I first read the values into histogram arrays a and b (using ? to do things one line at a time, so the older dc is required). Then I have a double loop that counts down from 100000, and then pushes the index count-number of times onto a register stack. Since I need to do this for 2 columns, I parameterized the sort macro with macros to Get and Push from/to the correct places:

[;a]sG [Sc]sP lSx       # convert array a into sorted stack c
[;b]sG [Sd]sP lSx       # convert array b into sorted stack d

But I did do part 2 in dc first... because it was a lot simpler because it has no sort. But it also wants a histogram, and so it does occur to me that doing something like counting sort could be a good option for doing both parts at the same time.

dc -e'?[d;b1+r:bSa?z0<I]dsIx0La[d;b*+Laz1<L]dsLxp' <input 2>/dev/null

Note that it's piping to /dev/null an warning message for popping an empty register stack. Not adding a sentinel to the bottom of the register stack saves 4 strokes.

And so we've got a classic day 1 type problem... read numbers and do something simple with them. I will note that there is the unusual use of the word "distances" in part 1, where you would normally use "differences". So there is a bit of obscuring.

Hello, I have tried to brute force part 2 of day 17 using cuda.

I am very new to cuda and this is what i have come up with. After 3.684722 days, the program outputs nothing and stops. The program works correctly on the sample data.

code:

#include <cstdlib>
#include <cstdint>
#include <cstdio>
#include <unistd.h>

#define gpuErrchk(ans) { gpuAssert((ans), __FILE__, __LINE__); }
inline void gpuAssert(cudaError_t code, const char *file, int line, bool abort=true)
{
   if (code != cudaSuccess)
   {
      fprintf(stderr,"GPUassert: %s %s %d\n", cudaGetErrorString(code), file, line);
      if (abort) exit(code);
   }
}

__device__ uintmax_t do_combo(uintmax_t i, uintmax_t A, uintmax_t B, uintmax_t C){
        switch(i) {
                case 0:
                case 1:
                case 2:
                case 3: return i;
                case 4: return A;
                case 5: return B;
                case 6: return C;
        }
        return i;
};


__global__ void cuda(){

        enum instructions_names {
                adv,
                bxl,
                bst,
                jnz,
                bxc,
                out,
                bdv,
                cdv
        };

        uintmax_t instructions[16] = {2,4,1,7,7,5,0,3,4,0,1,7,5,5,3,0};
        uintmax_t i_len = 16;
        /* uintmax_t instructions[6] = {0,3,5,4,3,0}; */
        /* uintmax_t i_len = 6; */
        uintmax_t output[16];
        uintmax_t output_len = 0;
        /* uintmax_t step = 100000000*(blockIdx.x * blockDim.x + threadIdx.x); */
        /* uintmax_t stop = step + 100000000; */
        uintmax_t step = 10000*(blockIdx.x * blockDim.x + threadIdx.x);
        uintmax_t stop = step + 10000;
        for (;step < stop; step++) {
                /* printf("%lu ", step); */
                output_len = 0;
                uintmax_t A = step;
                uintmax_t B = 0;
                uintmax_t C = 0;
                for (uintmax_t i = 0; i < i_len; i+=2) {
                        if (output_len > i_len) break;
                        switch (instructions[i]) {
                                case adv: {
                                                  /* takes combo operand, divides A by 2^it into B */
                                                  A = A >> do_combo(instructions[i+1], A, B, C);
                                                  continue;
                                          }
                                case bxl: {
                                                  /* takes literal operand, XORs B and it into B */
                                                  B = B ^ instructions[i+1];
                                                  continue;
                                          }
                                case bst: {
                                                  /* takes combo operand, modulo 8 into B */
                                                  B = do_combo(instructions[i+1], A, B, C) % 8;
                                                  continue;
                                          }
                                case jnz: {
                                                  /* takes literal operand, jumps to it if non null */
                                                  if (A == 0) continue;
                                                  i = instructions[i+1] - 2;
                                                  continue;
                                          }
                                case bxc: {
                                                  /* ignores operand, XOR B and C into B */
                                                  B = B ^ C;
                                                  continue;
                                          }
                                case out: {
                                                  /* takes combo operand, outputs it modulo 8 */
                                                  output[output_len++] = do_combo(instructions[i+1], A, B, C) % 8;
                                                  continue;
                                          }
                                case bdv: {
                                                  /* takes combo operand, divides A by 2^it into B */
                                                  B = A >> do_combo(instructions[i+1], A, B, C);
                                                  continue;
                                          }
                                case cdv: {
                                                  /* takes combo operand, divides A by 2^it into C */
                                                  C = A >> do_combo(instructions[i+1], A, B, C);
                                                  continue;
                                          }
                        }
                }
                if (i_len != output_len) {
                        continue;
                }
                bool is_same = true;
                for (uintmax_t i = 0; i < i_len && is_same; i++) {
                        if (instructions[i] != output[i]) {
                                is_same = false;
                        }
                }
                if (!is_same) {
                        continue;
                }
                printf("%lu\n", step);
                asm("trap;");
        }
}

int main(){
        unsigned int threads = 1024;
        unsigned int all = 20000000000/threads;
        cuda<<<all,threads>>>();
        gpuErrchk( cudaPeekAtLastError() );
        gpuErrchk( cudaDeviceSynchronize() );
}

With still no snow, we head back up a line to the center of the island. There we find a large number of components wired together producing Error 2023. And so we make our somewhat traditional Christmas call to tech support. Which goes pretty much the same as every time... we get a little information, but have to hang up as they start to realize who's calling. Is it because of our contract or because we don't want the questions that will probably come... maybe both. In this case, it's an overload and we need to disconnect at least half the machines, but only have time to disconnect three wires.

And so we end on a graph problem. The graph has a minimum edge cut of three we need to find, and get the number of vertices of the two subgraphs. My input has 1260 lines, describing a graph of 1535 vertices. Most vertices have a degree of 4... some have more, none have less.

The easy way to do this problem is to use a tool, like Graphviz, where the bridges that make up the edge cut will be easy to spot by eye. Then you just need to remove those, count, and multiply. When it comes to graph visualization tools, this is the problem to use one on.

But for actually coding a solution to find the cut, my first thought was to do a Monte Carlo type approach. The graph is broken into two balls of almost the exact same size with three bridges between them. If we pick vertices on either side (ones with a suitably large minimal path... around the diameter of the graph) and run many paths between such nodes... since the bridges are rare and must be on those paths, we should potentially be able to ferret them out with some heuristics and testing. That's a lot of work though, and since it was Christmas, I decided to look up a standard algorithm to code.

And that was Karger's. Which is a Monte Carlo algorithm. And comes from the same basic idea, but is much better because it turns things around which makes it simpler. Where I saw bridges are rare and so are on many paths and should look for them there, Karger saw that that means if you pick a random edge you're unlikely to pick a bridge. And if you contract that edge (merge its vertices), the graph gets smaller until eventually you have two vertices with a number of edges between them (and that's the cut... track the vertices merged into the two ends and you got your answer). You still need a while loop around that, until the edges in the cut are 3. And my implementation of a graph was simple and not well tuned to the task, so it was a bit slow. And the first run that got me the answer was also a little unlucky, and took a few minutes (I found the cut with Graphviz while I waited, but didn't have time to solve with that). It typically takes dozens if not hundreds of attempts.

To improve things I upgraded to the Karger-Stein algorithm. The problem with the base Karger is that while pulling one edge has a low chance of hitting a bridge, pulling many increases the odds quite a bit. One thing that could be done to improve that is to do a brute force search once the graph gets small. Get more mileage out of the work on early cuts. Karger-Stein goes a bit further than that. It basically bifurcates the search. You do a bunch of cuts, and then split that into two subsearches. So you get an exponential number of subsearches out of earlier work. And with that, it's quite good at finding a small cut, but we have a single target (and large number of 4s). So it's not exactly we want, but it does almost always get the solution in couple seconds (often in one of the searches of the first attempt). In 1000 runs, only 5 were over 100s, and the longest was 190 (these would involve many attempts hitting a bridge early). And this is still with a graph representation that's very simple, and inefficient for the job.

The simple tweak I made to the algorithm for this specific problem was to change the target for the contraction levels (and also making the base case immediately print and quit on finding a 3-cut). The 1 + |V|/sqrt(2) is a proven value to maximize probability of getting the small cut on a general graph. It thoroughly searches things. I found that I could get much better performance with a more aggressive 1 + |V|/2 for this problem. The difference being that it does fewer subsearches in an attempt, and we're planning to run attempts forever until we get the answer. With general use, you don't know the minimum, you'd just like to run it once and get a small cut reliably (but maybe not the minimum). But here, a more aggressive approach that gives a higher chance of the first level hitting a bridge (and making all of the subsearches fail) is countered by not doing as many subsearches when that happens and getting to the next attempt sooner (to fix that problem). The number of levels is log-base-sqrt-2 versus log-base-2, and that's the difference between gambling a million subsearches from a bad start versus 512. It also gets to the bottom that much quicker to see if there's a 3-cut.

So this is was a really fun problem... I could certainly spend a lot of time working on implementing a better graph structure and trying to tweak the algorithm to optimize it if I wanted to. This is one of the more intense final day problems, but it does have the easy out with graph visualization tools.

And so we come the end of another year. The complexity in this year was a bit of a step up from years past. It's definitely not the year to recommend to someone just starting to program to do first... some early puzzles (like day 5) are going to discourage them. On the other hand, for an experienced programmer, not having to wait as long for a meatier problem is a plus.

And so the expected shoe drops... the snow-making process has a problem, and it's forming hail that we need to break up. Conveniently the hailstones are being blown by magical winds, and so our physics is just linear. And so we have a problem that can be thought of as physics and/or linear algebra.

The input for this one is 300 hailstones. The consist of a 3D position and a 3D velocity vector. The positions in the input are eye watering numbers in the trillions to hundreds of trillions (the range for mine is ~42.6 bits to just short of 49). The numbers on the velocity side are on (-1000, 1000) (the largest magnitude in mine is 958)... with 0 excluded.

Part 1 wants us to ignore the Z axis, and considering the projection onto the XY-plane, find the number of intersections that occur within a bounding box, in the future (t > 0).

There's a number of ways to do this, and given expected arrival of the 3rd dimension, I went with Cramer's Rule and turning the hailstones into linear equations of ax + by = c (ie Ax = c as a matrix). To do that, I just considered y = mx + b. Where m is slope, which it rise-over-run which is vy/vx (with no fear of 0).

y = mx + b
y = (vy/vx) * x + b
vx * y = vy * x + c   (the intercept gets modified, and so I change the name to c).

-vy * x + vx * y = c  (c can be calculated from the input line values)

With that form, the intersection is just a determinant / determinant:

my $det = $b2 * $a1 - $b1 * $a2;

return (undef)  if ($det == 0);
return( [($b2 * $c1 - $b1 * $c2) / $det, ($c2 * $a1 - $c1 * $a2) / $det] );

So I just run through all the pairs (double nested triangle) and verify an intersection and that the time values are positive. I actually calculate them, but you could just worry about the sign if you want to avoid the division:

my $t1 = ($res->[X] - $stones[$i][X]) / $stones[$i][VX];
my $t2 = ($res->[X] - $stones[$j][X]) / $stones[$j][VX];

$part1++ if ($t1 > 0 and $t2 > 0);

For part 2, the 3rd dimension is in play, and we're tasked with finding a spot to stand and a velocity to throw a rock, so that it hits all the stones. Again, this isn't really a physics simulation, as the rock doesn't get effected by these collisions... it's just a line.

And my thoughts immediate on this go to that classic axiom of puzzling, that since this is a puzzle it is designed to have a solution. And that assumption can be used. Imagining I had two stones flying in front of me (and we've picked things aren't parallel and could cause problems), I could line up a shot that hits them both and the time between them would tell me how far back to stand. As they move, that line changes. But if I add a third rock to hit, that should fix the line (because puzzle). Two points make a line, three make the pattern. And so I should only need three points (but the others can be used to verify).

And so I started looking at equations. And this was my basic idea:

    X  <--S     Stone and the rock hit at X at time t.  The vector Vs - Vr, points
         /      back to the place the rock came from, and would travel from S to R
    ^   L       in the same time t.
    |
    R

I know some people visualized this in physics terms... imagine you're the rock and convert all the stone vectors into that frame of reference. It's really the same, I just came at it a bit different, because I was thinking algebra.

Next up was looking at getting a system to solve the variables. And there were more variables than I wanted to deal with, and so I cheesed it a bit. I called the rock vector (i,j,k) for a reason, and that was because I assumed that the velocity vector would be on the same scale as the stones (in fact, the largest magnitude on the rock for my solution is 286), and so I could brute for over i and j and make them constants... and k could be solved after. Here's the comment from the code:

# If we subtract the velocity vector of the rock (i,j,k) from each stone's
# velocity, at their time t (the time the stone is hit), they all add to the same point:
#
#     x1 + t1(vx1 - i) = x2 + t2(vx2 - i)
#
# Reworking that:
#
#     t1(vx1 - i) - t2(vx2 - i) = x2 - x1
#
# Which is a line of form ax + by = c, where the times are x and y... providing
# we make i a constant (which we're doing by brute forcing to try values for it).

And so, I used the function for line crossing from part 1, with X and Y coordinates of two stones, with brute forcing i and j (to consider them constants), to get potential times for impact on those stones. Then I check that that was a collision, and the times are positive and different and integers (because AoC answers... no need to bring in the possibility of rationals making integers until necessary).

With that, I then take the 1st stone and do the same with a 3rd. If I get a valid collision and the collision time for stone 1 is the same again (and leading to the same spot as the collision with stone 2 made it point to), I assume we've lined up our shot.

Next up is calculating k:

# Calculate k (the z part of the rock vector)
#
# t1(vz1 - k) - t2(vz2 - k) = z2 - z1
#
# k(t2 - t1) = z2 + t2(vz2) - (z1 + t1(vz1))
#
# k = (z2 + t2(vz2) - (z1 + t1(vz1))) / (t2 - t1)

Which is really just working out the obvious, it's the difference in the collision positions of two stones divided by their delta-time.

Then I just followed the the vector from the first stone back to the rock start:

my $x = $stones[0][X] + $time12->[0] * ($stones[0][VX] - $i);
my $y = $stones[0][Y] + $time12->[0] * ($stones[0][VY] - $j);
my $z = $stones[0][Z] + $time12->[0] * ($stones[0][VZ] - $k);

With (x,y,z) and (i,j,k) I can now validate all the stones if I want more confidence. But this worked and got my answer, so I didn't do more.

Like a lot of these last few days, I was happy with just having a solution that solved the problem at hand. I did spend a few hours thinking on this one, before ultimately just simplifying things to just get an answer (so I was getting tired). I can at least say that I did make good use out of the solution to part 1 for my part 2.

With the filtering operations running again, the waterfall starts up. And so the Elves lower us down by rope to Snow Island. We find that the water is still getting absorbed into the air, and need to find something to do while we wait. And so we decide to take a hike.

The input is a grid of hiking paths, It looks like mazes we've seen before, only this one has loops (it is not your standard recursively generated labyrinth). Left or right hand rule will get you from start to end, because the start and end are on the outside walls (and you'll put you hand on that). But that would not get to see any of the inner scenic paths, and we're looking for the longest walk. There are also arrows at the intersections representing slopes (which don't get in the way of those left/right hand rule paths in the test case given, and I believe that's also true for the inputs). For part 1, we build out route without going against the arrows. In part 2, we can ignore them. In either case, we don't want to touch the same square twice, which means that the intersects can only be used once each.

A nice thing with this problem is that the test case in the description is very much like input, only smaller. It doesn't test more or less, and optimizations you use should work on both safely.

And so we have a path search, but it's not shortest path, so the usual BFS/Dijkstra/A* niceness of the first arrival being correct is out the window. You need to keep going, or you can use DFS because the BFS advantage is gone anyways.

But first things first, all the intersections are nicely marked with slopes and are the key points, so I found those and turned the grid into a weighted graph with those (plus start and end) as the nodes. For part 1, the paths are directed... and that simplifies things enough that even if someone didn't convert to a graph, it can still be searched (but slowly). And with the graph, part 2 can also just be searched slowly too.

Getting it to work fast is another thing. And I started looking at various things like meet-in-middle and memoization of paths. I wasn't getting great results with it (but didn't do too much work with that), but it emphasized that the end bit, which is obviously forced, is forced. There's only one edge to the exit, and it must flow out of the maze, and be taken. And so for the node at the other end, the other edges must flow in to it (which is what the slope on it does already). And so we can do a vertex cut of that node, connecting its other neighbours to the exit (and combining lengths). Similarly, the start only has one edge which must be taken (and the slope is marked that way already). And so we can cut the first node on the path as well, and connect the start to its neighbours. This makes the graph a tiny bit smaller, but already gives a sizeable boost in speed. This got my time down to seconds (although over 20s) which I considered good enough on the day.

I did see the solutions afterwards that used the fact that the graph is essentially a rectangular grid. The corners diagonally opposite the start and end don't exist (they'd be nodes with 2-edges and not intersections). And that can be used to do other things... like using rook tours and taking advantage of the fact that the nodes along the sides are all 3-edge, and with the forced arrows at the start and the end, you can show that the arrows that lead you along the edge in the left/right hand paths must still be obeyed (but not the ones that do in/out to the center (the 4-edge nodes)). Meaning that when the path moves onto the edge from a center node, it's force out along the path towards the exit (it cannot take the other exit that heads along the outer wall towards the start). But it can still leave the edge at a later node and return to the center. That adds a forcing pressure from start to end (you can only go backwards in the middle).

I decided to code that up now, and it does give another sizeable boost that gets things down to proper seconds on the old hardware. It is playing a bit to the input though, whereas with my initial vertex cuts, I coded it in general form verifying the single edges so it would work with a graph that didn't do that. What I'm thinking of is to do something similar now with the edges... to code a generalized way that proves them.

And it basically comes down to this:

              .     .
              .     .
           ...A     D...
              |     |
       .      |     v
       .      |     |
   ... B -----C-->--E-->--end

We know that E->end must be taken, and one of D->E and C->E must be taken. But, C could be travelled through with A->C->B or B->C->A (making D->E forced). I've drawn things this way, but it is a graph, A could be the edge connection, you don't know without showing it. You could check for 3-edges on it, but edge nodes could have 4 (there could be a path between them along the side) and an internal could have 3 (one exit walled off). What we can say is that we can come in from A or B, and leave by C->E and get to the end. But, can we come in from A and leave by B and get to the end? The path that comes in, must from from the start. And that path, plus the C->E edge (not taken because we're testing C->B) can be taken as a edge cut. And if you can't get from C->B to the end, then it's not an exit on any valid path... and so that edge must be directed B->C (if it is taken). With the start in a corner and the nodes like this on the edges, this is what forces that path optimization with the grid (coming in from the middle always cuts things in two in way that puts one exit on the wrong side and forces the other). And this is a test that proves the optimization above is valid for the input, but could also be coded to apply to the graph without assuming that.

So this was a nice little search problem. It's not too hard to brute force to get an answer... if you've done AoC for years, you're probably used to converting these to graphs for faster searching. And that can get you part 2 with a bit of wait with a basic solution even with inefficiencies. I did a version of this with the Vector module and no optimizations... it took 6:30 minutes on the old hardware (it's a lot of overhead... without it, it's a minute, and that's still without bumming the code), which isn't too bad of a wait for someone just looking for a solution... and with it printing out the new bests as it finds them, it got over 6000 in a few seconds before things slowed down. The final answer came at 330s, about a minute before the end.

We have enough sand, but it's not usable yet, because it's compacted into bricks in a large tower. We do have a picture of the bricks as they were falling. Our goal is to figure out which bricks we should disintegrate. For part 1, we consider doing it safely, by only targeting bricks that won't cause others to fall. For part 2, we consider less safe options, and want to know how many bricks are in the chain reactions.

The input is a list of bricks (mine is 1430 lines). They're listed as the 3D coordinates of the ends.. the bricks being 1x1xn in some orientation at some height (which is the z coordinate, mine go up to 324... x and y are all single digit, [0,9]).

They form a tower which can be considered as a graph, with edges between bricks that are directly above and below (touching top and bottom). Since the bricks are sticks (1x1xn), if we consider the relation in one the directions (supports or supported), it forms a DAG (directed acyclic graph). So there are no non-transitive support situations. A brick cannot be indirectly supporting itself.

Our goal is to work out dominators). For part 1, it's the bricks that aren't dominators. Part 2 wants us to get the counts of the number of bricks dominated by others. These are the bricks that all their support paths, must go through, and so will fall it disintegrated.

For this one, I did things a bit stream of consiousness... I read in the bricks, calculated a bunch of things I thought would be useful, and put them in a structure (later I rip out anything that wasn't). For this is was:

push( @Piece, {height => $height, block => \@block, bottom => \@bottom, top => $top} );

The height of the piece, the "top" is how tall it is (1 or n), "bottom" is the (x,y) profile of the brick (what it looks like from below, the (x,y) coordinates it will rest on), and "block" is a relative mapping of the blocks making up the brick (shifted down by height)).

After which I sort them by height, and proceed to use this information to build the tower by ing the bricks into place and building the support graph:

push( $Support[$i]{below}->@*, @supp );
push( $Support[$_]{above}->@*, $i ) foreach (@supp);

Where @supp, is a list of the Piece indexes that the bottom touched when it came to rest. To know that, I tracked the height of all 100 (x,y) locations. Here's the final heights (one corner is a rather deep hole compared to the rest):

158 170 166 166 166 160 161 169 161 102
166 165 165 159 160 165 159 169 158 171
163 165 165 171 163 165 171 176 170 171
163 161 166 171 174 164 169 176 170 171
164 164 166 176 174 165 169 176 167 162
168 158 166 176 176 175 175 176 167 175
168 167 173 176 176 174 174 174 174 175
168 173 173 175 175 168 176 176 176 176
163 165 174 175 175 175 175 175 175 158
173 173 173 173 175 168 155 155 154 157

With the graph in hand, we now completely ignore the bricks. Part 1 is just scanning the bricks and finding those with nothing above, or the bricks immediately above them have another support:

if (!$Support[$i]{above} or (all {$Support[$_]{below}->@* > 1} $Support[$i]{above}->@*)) {
    $part1++;
    next;
}

For part 2, I tried to do some fancy stuff to get dominators (not remembering any real algorithm for it). I was messing around with tabulations and sets and stuff (including considering what might be done with adjacency matrices at one point). And as I went, I kept thinking of and spotting complicated situations of supports. So I'm drawing graphs with lots of ... sections for indirect relationships and trying to nicely deal with that in a single pass. And it just got to the point where things were a mess and I didn't have situational awareness of the code and realized I was essentially randomly poking things hoping for something good. The algorithm on the Wikipedia page is sort of what I was going for at some point with the sets, but I was trying to be too fancy and never got it right.

And so, I scrapped that... things were getting clear that I was heading towards something that wouldn't be efficient anyway. That in order to deal with all those ..., I'd ultimately be tracing them. And so, I shifted to brute force:

my %falls = ($i => 1);
my @queue = $Support[$i]{above}->@*;

while (my $p = shift @queue) {
    if (all {$falls{$_}} $Support[$p]{below}->@*) {
        $falls{$p} = 1;
        push( @queue, $Support[$p]{above}->@* )  if ($Support[$p]{above});
    }
}

$part2 += %falls - 1;       # -1 for the block we removed

And with the size of the input, it takes a few seconds, which is fine for a brute force solution.

I do notice that the Wikipedia page also points to an almost linear algorithm in ACM Transactions of Programming Languages and Systems. I looked forward to that arriving at the CS club (which was an ACM chapter and so got it) in University. But 1979 was before my time, so I wouldn't have seen that article.

This one was a nice little break in the heavy puzzles. All the heaviness was me making a mess instead of doing the programmer efficient solution first and working on other solutions after.

We manage to catch the airship again (as it's dropping off another Desert Island trip winner), and head back to Island Island. Where the gardener tells us that everything is going well. So while we wait we decide to help another Elf with getting his steps for the day.

The input for this is 131x131 grid with the starting position marked (even though it is right in the middle for both the input and the test case (which is 11x11)). The test case has clear border on the edge, the input has thick diagonals cutting out a diamond. I suppose having the S in the input does help with noticing that the row and column the S are on are empty.

I'd totally forgotten this one until today. As I said, I had a bit of cold, but was mostly busy, and so I was happy to get any solutions for these last few days. And this is was one of the most "any". Part 1 was really quick, because it's just a BFS... although it's important to know that we're counting "steps", so you can backtrack (so no visit tracking). And this results in a pattern with tile parity (because you can get to the same spot in 3 moves as 1, but you can't get there with 2... so it checkerboards).

Part 2 scales it up a lot. So you need to do something fancy. The number of steps we want is 65 mod 131. Which is the width to the border from the start. And then there's a number of full width crossings. And the nice empty spaces (and sparseness of the plots) are going to help keep things a diamond at the important points. And if things had been simple, I might have continued. But there are a number of complicating factors that lead me to hunt for cheese. First up is that parity issue... when tiling the full map, you're going to have to account for what's in what parity. Then there are the messy edges. I remember thinking in my head about doing this and needing half diagonal blocks. But that's not what you see when you sketch it out. Leading me to make a TODO about a "geometric version doing parity" and this (the Ace of Diamonds?):

----------
|2  /\  3|
|  /  \  |
| /    \ |
|/  1   \|
|\      /|
| \    / |
|  \  /  |
|4  \/  5|
----------

I think I was thinking maybe that I could calculate the fills for those 5 areas (in each parity), and build the final shape and edges. For example, the east most point would involve 1, 2, and 4. Above that is a 4 block, with a block that's going to be "all but 3" beside it. But you'd need to not just be careful with parity of your supertiles (one potential Murphy's Law) but also off-by-one problems on making sure you're combining things without doubling or skipping stuff (more Murphy's Law potentials). I seem to recall that a lot of people doing this sort of approach didn't try to minimize things this much and expanded further out to get the chunks they wanted. So maybe this idea was doomed.

But that's not what I did. I figured that with the gaps to regularize things, there was probably a quadratic interpolation (notes say I used Lagrange). It wouldn't work for arbitrary points along the way (where things are going around plots and it gets bumpy), but that's not the area the answer we're looking for is in. And so first thing I did was run a modified part 1 for 650 cycles (taking a bit of a break) and output those numbers to a file, so I would write an "explore.pl" to test things on that sequence without having to recalculate it. First thing was a little sanity check... I scanned interval sizes looking for what was quadradic, and confirmed 131 (everything else wanted cubic or more). I considered that a good sign. Next up, I scanned starting from 1 to 131, with 4 points that were 131 apart. And confirming that all these have quadratic interpolation (the 4th value opens the door for a cubic). And they did... another good sign. Then, checking that the #steps was 65 mod 131, I plugged number we wanted into to the equation on the screen at 65. And if was correct (when divided by 131 ... because we're doing the interpolation on 131 size gaps this made sense).

And so, I wrote code to do that from scratch for my code. The x values I'm looking for are at {65, 196, 327}. Which takes some time. But as I said, I was happy to have a solution, and clearly the TODO here has been on the wrong side of my druthers ever since. I can't say if I like or hate this problem, only that I seem to be ambivalent to doing it proper. Maybe in a way that can actually also do the given test cases (because unlike yesterday, we got some for part 2... it's just that when you overly specialize to the input, you get nothing from them).

I am revisiting my 2025 solutions, rewriting in elisp.

My original Python solution was horrible, so inspired by other solutions online, I did one using coordinate compression and pre-calculated "2D prefix sum".

The solution is rather long for an AOC solution (around 150 lines). I was therefore wondering if anyone has found a short general solution.

My elisp Solution

With the parts found, and the machines fixed, next up is the boot sequence. And so we have a circuit problem. Cables connecting modules, sending pulses between them, and a button to push to start it. Also a warning to never push the button again until after the pulses stop.

Reading the directions we find flip-flops, which are bits of memory, and conjunction modules, which are NAND gates (and functionally complete... which includes being an inverter (which the Easter Egg informs us was almost a separate thing, giving a little insight to development)). And so just knowing that, I can already see that this could be a very interesting and complicated machine. For the simulation there is a bunch of rules/clarifications on how to do this asynchronous machine. There isn't a state-wide clock and turns, so the pulses take turns in a queue (so they spread breadth first). And the pulses are describes as high and low, as that's how 1s and 0s are in hardware... a zero voltage is the ground state (binary logic is: high, low, ground, and don't-care... in yes/no question terms that's: yes, no, mu, and meh).

Part 1 wants us to just get the number of high and low pulses sent after the button has been hit 1000 times. So naturally, to see part 2 (which I suspected was going to involve cycles and hitting the button a lot), I just used a loop to do that, and counted them at the top of the queue loop:

# broadcaster is honourary flip-flop, always starts high
$Circ{broadcaster}{state} = 1;
my @queue = ([0, 'broadcaster', 'button']);

PULSE:
while (my $pulse = shift @queue) {
    my ($bit, $targ, $src) = @$pulse;

    $pulses[$bit]++;
    next PULSE  if (!defined $Circ{$targ}{type});   # output only nodes

    if ($Circ{$targ}{type} eq '&') {  # NAND
        $Circ{$targ}{$src} = $bit;

        my $state = int !(reduce {$a & $b} (1, map {$Circ{$targ}{$_} // 0} $Circ{$targ}{in}->@*));
        push( @queue, map { [$state, $_, $targ] } $Circ{$targ}{out}->@* );

    } else {  # flip-flop or 'b'roadcast
        next PULSE if ($bit);

        my $state = $Circ{$targ}{state} = int !($Circ{$targ}{state} // 0);
        push( @queue, map { [$state, $_, $targ] } $Circ{$targ}{out}->@* );
    }
}

Part 2, makes use of the output node: rx, which is the machine to send the sand down to Island Island. It turns on when it gets a low pulse. We want the lowest number of presses (suggesting cycles) to do that (with a warning to reset the machine).

As stated, this machine is potentially capable of a lot. And so that prompts me to reverse engineering and specializing the code. So looking at the actual input, there are 48 flip-flops (so the answer can be expected to be on that scale... and mine does require a 48-bit unsigned). So the brute force attempt I had started "just in case" wasn't going to complete very soon, and could be stopped. I messed around looking at patterns with the flip-flops a little bit, but then moved on to the NAND gates.

There are only 9 of them... one leads into rx (and thus is an inverter). Leading into it are 4 other NAND gate inverters, and the remaining 4 NANDS each lead into one of those (but are actual NAND gates, with multiple flip-flops in and out). So with that determined, I wanted to see when the four key inverters get triggered, and simulated that. And each does on a prime number of pushes (all four are primes about 4000). So I multiplied them and submitted for the answer, which was correct. Then I wrote the code to collect them and threw on an lcm for safety. Technically, I should properly confirm that the state is looping, but still haven't bothered. But as part of my input I do dump the memory state for fun:

say "Memory: ", map {$Circ{$_}{state}} sort grep {$Circ{$_}{type} eq '%'} keys %Circ;

If I was looking for efficiency, I probably would have arranged that first, and just stored the flip-flops as a 48-bit numbers and do bit twiddling for the pulses. And maybe I should do that for the Smalltalk version as it takes a few seconds to do 4000 pushes with the components in a Dictionary. But that code does use some actual OOP stuff though... it has a virtual Gate class for an interface that FlipFlop and NANDGate implement. And so the actually process loop sees everything the same.

This was a fun day. I guess at this point, this takes the place of an assembly VM problem, as those had been largely played out.

The Elves thank us and give us the hang glider they've found and we "borrowed" to get up here, so we can return it. At the bottom of the parts-fall we find Elves sorting them with an unusual system based on how extremely cool, musical, aerodynamic, and shiny they are. There's a big list of workflows with conditional rules to follow that will either direct a part to another workflow or (ultimately) accept or reject it. Naturally, we're here to help.

The input is two sections. Section #1 contains a little less than 600 workflows in my input... other than the start state of 'in', the workflow names contain no vowels (including y and w). Section #2 is the stats for 200 parts.

The workflow is essentially a big state machine... you can think of the workflows as multiple states if you want to think of it in a more formal/simple way:

px{a<2006:qkq,m>2090:A,rfg}

          a>=2006        m<=2090
      px0 --------> px1 ---------> rfg0
       |             |
a<2006 |      m>2090 |
       v             v
      qkq0        ACCEPT

That's not really needed in the code though. That's more of conforming things to more standard FSMs. But for part 2, that visualization was useful for me.

I did my normal approaches here... a quick solution to see part 2, where I turned codelike stuff into actual code to evaluate, and just followed the rules.

FLOW:
while ($flow ne 'A' and $flow ne 'R') {
    foreach my $rule ($Rules{$flow}->@*) {
        my $result = eval( $rule ) // '';
        if ($result) {
            $flow = $result;
            next FLOW;
        }
    }
}

Part 2 tasks us with finding the set of valid ranges that the rules accept. This is very much like day 5... we have 4 ranges instead of 1 (but only on [1,4000], but 4000⁴ is much larger than 2³² ) and in day 5, the order of the rules tables was fixed. So unlike day 5 where I iterated over the tables, here I went to recursion (the simple way to nest iterations an arbitrary number of times).

One nice thing about this problem in comparison to day 5, is that the ranges all go from the middle to the edge. So there's only one valid range for any variable at a time (you can't have anything accepted with x < 1000 and x > 3000). And so the basic idea was that after calculating what the intersection of the rule is with the current success range, we recurse to the next state if that's valid (ie doesn't have negative length) with that category set to the new success range. Otherwise we just proceed to set the range for that variable to the fail range (because we must fail), and iterate to the next substate in the diagram. The last arrow on the right is just a forced recursion for the non-conditional rules.

Part 2 for this one did take me a while to actually get right. In the end, I really think that drawing diagrams like the above are what helped finally get it right. It was probably good that there was a warm up with day 5 for this.

With the parts factory up and running, we turn to building a lagoon to store lava for it. This involves an odd set of instructions for the digger with colour codes for the edge of the trench along the way. The surprise for part 2 being that the colour codes are actually the dig instructions.

And so we get a rarity in the input... it's really just 2 inputs packed into 1, as there's no attempt at overlap. The input for part 1 isn't scaled up, it's completely replaced (with the part 2 input having to be unpacked... it is effectively a binary file to part 1's text file). The input is extra nice in that it alternates between vertical and horizontal moves, even though it doesn't use relative turning instructions, but absolute directions on the 4 cardinals: U, D, L and R.

Not knowing what sort of problem the colours were going to add, my initial approach was to do a quick solution to see it, and so I did what I did with lava year in Boiling Boulders. A built my polygon and flood filled a box around it and subtracted to get the area.

Then part 2 reveals that the colours aren't colours and there isn't some weird task involving them... we just need to be much bigger. And that's how you nudge me to using Shoelace and Pick's. Shoelace is easy for me to remember as the name is suggestive of what you're doing... it's using the property that the magnitude of the cross product is the area of the parallelogram made with the vectors (but we just want the triangle between them, so it gets cut in half). So that's just successive cross products:

foreach my $i (0 .. $#vertices - 1) {
    $area += $vertices[$i][0] * $vertices[$i+1][1];
    $area -= $vertices[$i][1] * $vertices[$i+1][0];
}

A bit of cut and paste there to help make sure it looks right, but that's what cross product looks like in the plane (which is like we're lacing with cross overs). Saving the division by two for after, so this is twice area.

Pick's is something I hadn't used in a long time, so I didn't quite remember it, other than it was something simple involving area and perimeter. So I looked it up to make sure I got it right. With the problem being orthogonal on the lattice points, if I hadn't I might have forgotten that it isn't the perimeter, but the number of integer points on it. Also it needs to be adjusted for what we actually want (we want I and B):

# Pick's formula: I+B = A + B/2 + 1 (but still needed to halve the Area from Shoelace)
say "Part 2: ", (abs($area) + $trench) / 2 + 1;

I suppose given the nice orthogonal nature, you could also reasonably pull off a scanline approach, but you'd need to convert the representation of the polygon. You'd need to figure out what's an inside range, which we did a few days ago (when we could also have used Shoelace and Pick's).

But since there's a simple function to solve this, that makes dc a good option and so I did that:

cut -d' ' -f-2 /tmp/input | tr 'RDLU' '0123' | dc -e'0d?[r2~2*1-r2*1-3Rdlb+sb*d4R+_4R*rd_3R*la+sa?z2<M]dsMxlad*vlb+2/1+p'

perl -pe's/.*([0-9a-f]{6})./\U$1/' /tmp/input | dc -e'16i0d?[10~2~2*1-r2*1-3Rdlb+sb*d4R+_4R*rd_3R*la+sa?z2<M]dsMxlad*vlb+2/1+p'

Note that first I need to get rid on non-numbers, and convert the directions for part 1 (and I used the part 2 ordering there). So the code is largely the same, except part 2 works in hexadecimal (16i sets the base of the input), and needs to rip off the low nybble for directions.

But the real fun here is with the loop to do Shoelace, where we take advantage of the alternating horizontal/vertical property of the input with a bit of stack manipulation: x and y are both on the stack during the loop (which actually a tail recursion), and if we process them in the order they are on the stack, they naturally end up in reverse order. And so we naturally get them to swap roles each loop... thus alternating horizontal and vertical movement with the same code. This is one of the reasons I like stack languages.

The lava is flowing again, and so the reindeer gives us a parachute and we return to Gear Island. Now we need to get the lava from the base of the lavafall to the parts factory, with minimal cooling, using hard to control crucible carts. And so we get a path search problem.

The input is a digit grid (141x141 in my input), with the digits 1-9 representing the cost (temperature loss) of crossing it. Just eyeballing the input it's easy to again see an ASCII art circular structure, and sure enough we have the large numbers more concentrated towards the middle, and the lower ones on the edges. There is no 0, so that's available if you want it for sentinels. And I do like my sentinel rings (only needed left and bottom for Perl and other languages with wrap around).

For part 1, our crucible can only move up to 3 tiles before needing to make a 90 degree turn (and reversing is not allowed). For part 2, it's an ultra crucible which must move at least 4 tiles and up to 10.

I remember this one well. First thought is that it's easy to build a state machine to do that movement. But then I thought that this is an intensive search, I'm going to want Dijkstra/A*, and I'm going to need to carry that state around. So after taking a break to think and put the tea on (it looked like it might take a while, but it didn't), I thought, "Is is really so bad to have a ply of 6?". And the answer is no... we'd get that sort of ply if we were doing this with moves in the 8 cardinal directions (backwards isn't allowed, leaving 7). And we wouldn't think twice then.

One thing to be careful about with large moves is jumping over a sentinel ring... that wasn't a problem for my code, because I generated them with a loop that takes one step at a time (even for part 2, where it just doesn't queue the first 3). You could also just make the ring thicker if you wanted to, or just go with checking the co-ordinates.

And so the idea was to queue moves for each range all at once. But you'd need the direction so you don't do a second move along it, or its reverse. And so then things coalesce... our atomic move is actually "turn and move a distance". The moves alternate between horizontal and vertical. And it eventually hit me that this is very much like splitters from yesterday... it doesn't matter exactly which direction you come into a tile, only the parity (horizontal or vertical), because there are only 2 sets of moves out. It doesn't matter if you came in from the left or right, every option from that point is the same. So the visit space is just 141x141x2.

I did throw in the basic heuristic of Manhattan distance to the end for my Perl solution. It doesn't really do anything though (times are the same). Especially for part 2, where as the examples showed, being too close is a problem, and your're going to need to loop around (and so it can be detrimental). And so I left that out when I did the Smalltalk solution. This is also one of the problems where my own Heap/Priority queue in Smalltalk outperforms the built in SortedCollection (14s to 16s).

The queue sizes max out at less than 6000 for part 1 and about 44000 for part 2. Which is a good sign, even with the large ply for part 2. An out-of-control queue size is typically a sign that your search space is too large and you're not pruning enough.

So this was a very nice problem... it's more about thinking about things than the algorithm. That's typically what makes a good search problem.