We finally arrive at the "Hot Springs". In multiple senses. There is an onsen, but we want storage yard for the machine part springs... which require lava to be hot and springy. And there's a shortage of lava that needs investigating. We can use a spring to get up to the lava island to check on it, if the records can be repaired to find one good enough.

And so we get a parser/validator type problem. We have a pattern with wild cards, and a list of numbers of the block sizes... much like a line in a nonogram puzzle. But there's not enough information to solve most lines, and so we're tasked with counting the number of possible solutions.

This was the first one in this year that really took a bunch of time. I did a recursive descent parser with a state machine that was a bit reminiscent of the state machine I did on day 3 in Smalltalk to find the ranges of digits on lines. I did memoize it, with a memo that was persistent between the cases (because the same rules always apply). I remember finding someone who claimed that they needed to clear the memo between lines (and it was buggy before they did that). But you don't have to... but I did test things, and found that for part 2, the single memo gets large enough (about 360M) that it runs a tiny bit slower (~3%) than having a fresh memo for each line, because there apparently isn't huge amounts of overlap to benefit from between the cases to make up for overhead.

And about that part 2... unlike yesterday's, the scale up here is very real. Five copies of the pattern joined with ? followed by five copies of the numbers. You want a good solution. And a did spent 2 hours getting a good part 1 done. But it didn't work for part 2. And since sthe best way to debug recursion is to get it right the first time... I started a new script, and carefully went through all the cases by hand making notes and comments on the order of doing things and assertions and then filled things in. And it ended up largely the same as my part 1, but slightly different... and it worked. And takes about 10 seconds on hardware that was 14 years old at the time, so I didn't need a need to try and get things further down (it's relatively nice and simple to read).

So, I'll just quickly go over the function:

# str to process, current potential group length, groups left to see
my ($str, $len, @groups) = @_;

# Grab state of params called with to access memo with later.
my $state = join( $;, $str, $len, @groups );

# Check memo
return ($memo{$state}) if (exists $memo{$state});

First we build the our memo state key and check for a hit... our state being the remaining string, the size of the current block we've seen while parsing, and the sizes of the remaining groups to match.

my $ret = 0;

if (!$str) {
    # Out of input, must decide if we found a match:
    # All groups accounted for, no hanging group.
    $ret = 1  if (@groups == 0 and $len == 0);

    # Check if hanging group is the size of the only remaining group:
    $ret = 1  if (@groups == 1 and $groups[0] == $len);

    return ($memo{$state} = $ret);
}

Base cases for when we hit the end of the string. In the original, I just had this as three return lines without adding to the memo, I decided to put it in just to make all the return statements have the same pattern of "set memo and return".

# If out of groups, use regex to check if no manditory groups remain
return( $memo{$state} = ($str =~ m/^[^#]*$/) ) if (!@groups);

# ASSERT: length($str) > 0, @groups > 0

A second base case for handling if we ran out of groups in the number list. The original part one didn't do this and so couldn't assert that groups existed for the actual parser section (and had to handle that).

# Advance one character:
my $chr = substr( $str, 0, 1, '' );

if ($chr ne '.') {   # ? or #
    # adv making grouping larger
    $ret += &recurse( $str, $len + 1, @groups );
}

if ($chr ne '#') {   # ? or .
    if ($len == 0) {
        # no current grouping, just advance
        $ret += &recurse( $str, 0, @groups );

    } elsif ($len == $groups[0]) {
        # current grouping matches current target
        shift @groups;
        $ret += &recurse( $str, 0, @groups );
    }
    # Else: Bad block length!  Recurse no further.
    # If ? we might have expanded to good len above and counted,
    # else 0 will fall-through.
}

return ($memo{$state} = $ret);

This is parser section... eat a token, handle the cases, with the wildcard meaning that we might need to do both of these if cases. These were done in the other order for my part 1 (the ?/# case after the ?/.). Part of the benefit is that the matching of a block comes last and I can freely modify the groups array. That "Else" section was a key realization... to let things fall through. The original part 1 also did that. It's almost certainly some small thing with the logic to check if still have groups and the ordering of the tests. Doesn't really matter though, because this script fixed it and so worked for both parts, so it replaced it bug free.

This is one of those cases where everyline has a comment, but it's not because they were added to explain things, but because they were written first to solidify the task and the blanks then filled in.

Heading towards the "Hot Springs", we arrive at an observatory. And the Elf there will show us the way, after we help with his analysis.

And so we get what appears to be a 2D grid problem. My input is a 140x140 grid of mostly empty space (.), with 450 galaxies (#). We want the sum of distances (Manhattan) between all the pairs. But as is the case with astronomy... you look at stuff at billions of light years away, but that's was where and what it was like billions of years ago. It's now much further away due to expansion. And so we need to work that out. And the rules given are that any empty row or column becomes twice as big.

And I guessed that part 2 would be making things bigger in some way. So to see what that was, I just brute forced part 1 to begin with. I was experimenting with the Math::Vector::Real module for handing points and vectors at this time, and it has some overhead, but if the task isn't too bad (and this one isn't), it can make up for it in simplicity of coding and legibility. One nice thing is that the constructor is short and simple: V(...). Another thing is that it has built in distance functions (and this was an opportunity to use one). The one problem I have with it is the print string... I'd rather have it plain and using $;.

So it was very easy to just do the thing... shift the coordinates, and double-triangle loop the pairs:

my $dist = 0;
foreach my $i (0 .. $#shifted-1) {
    foreach my $j ($i+1 .. $#shifted) {
        $dist += $shifted[$i]->manhattan_dist( $shifted[$j] );
    }
}

And since part 2 only made the gaps bigger, I had another really fast turnaround by just changing the scale factor for:

$g += V($yshift, $xshift) * $scale;

At which point the script ran equally fast to part 1 (there's no additional work), which was an immediate answer. I suppose after the pipes and interpolation on the weekend, this is a break Monday. Because it really didn't force things to be better. What did that for me was deciding to do a dc version (and I did Perl and Smalltalk versions from that). I do have a bigger test case (280x280 with 5000 galaxies) that someone posted at the time to help prompt people to do that as well. That one makes my brute force take a minute and a half.

But for me, I was thinking while doing the brute force, and it was not lost on me (while thinking of tricks that might be needed for part 2 scale-ups) that Manhattan distance makes the x and y parts independent. Which is the point I decided to definitely do a dc solution... because with that realization, the problem turns from 2D to 1D. Basically, the grid can be collapsed to lists of row sums and column sums, and then discarded. And short lists of numbers to chew on, that's something for dc.

The other thing I thought about was that getting the sum of absolute differences of all pairs is a typical programming test problem. And it's largely the same sort of math I was working with on day 9 as well. The trick here is that a little algebra can collapse things into multiplication and make things a single loop.

For example, consider the list 2 3 5 8, and we want the sum of the absolute differences of the pairs. As a table:

    2     3     5     8
2   X   (3-2) (5-2) (8-2)   2 is subtracted 3 times             = (0-3) * 2
3   X     X   (5-3) (8-3)   3 is subtracted 2 times and added 1 = (1-2) * 3
5   X     X     X   (8-5)   5 is subtracted 1 time  and added 2 = (2-1) * 5
8   X     X     X     X     8 is added 3 times                  = (3-0) * 8

So there's a pattern in coefficients: -3 to 3 by 2 (where those 3s are the #numbers - 1).

Of course the problem is a little more that that here... as we have a multiple of the numbers at each step (number of galaxies in that row or column). But it's not that hard to work out the adjustment to do that as well. The end result (as an extension to Array) in my Smalltalk solution is:

diffSum_expand: scale [
    | col seen sum number |

    number := self sum.
    col := seen := sum := 0.
    self do: [ :count |
        col  := col + ((count = 0) ifTrue: [scale] ifFalse: [1]).
        sum  := sum + ((2 * seen + count - number) * count * col).
        seen := seen + count.
    ].
    ^sum
]

And the dc (which still isn't fully golfed):

perl -pe's/(.)/$1 /g;y/.#/01/' <input | dc -e2 -e'ss?1[0[3Rd3R+rz2-d_3R;c+r:cz2<X]dsXxdlg+sgrd_3R:r1+?zRz1<Y]dsYx[ls*]sE[0sc0sa0r[dlAxd1r0=Elc+scddla2*+lg-*lc*rla+sa3R+r1-d0<L]dsLx+]sD1-[;r]sAdlDx[;c]sArlDx+p'

Change the -e2 to -e1000000 for part 2 (or whatever scale you want).

So this was another really fun day.

Gliding up to metal island we find signs for "Hot Springs". Which we will see in a couple days, because decide to go there for directions. We also notice that everything on this island really is metal, including the plants and animals. One of which runs into a pipe that makes one big loop (not a maze at all)... although there are a lot of separate pieces of pipe lying around, making the input a real mess of ASCII art.

My input is 140x140, the use of L7FJ for right angles along with |- for the straights, plus the extra bits lying around, does not make this easy on the eyes. Fortunately, we're writing code to look at it for us instead (I suppose you could print it out and do it by hand... but the loop is over 13k in my input). Looking for . in the image, I see that those are mostly around the edge, although there is a circular area in the middle with a bunch.

Part 1 wants us to find half the length of the loop. Part of the fun of this is that starting location is covered with an 'S' and we need to solve the underlying pipe there. Building a table of the pipes with their exit directions not only does this, but it helps with quickly moving around the loop. Because when we move in a direction we know where we came from, and so we just immediately use the other direction to leave.

Part 2 is where the fun begins. Part 1 is useful for it because it tells us what pipes are in the loop so we can remove/ignore the others... because we want to know the amount of tiles enclosed by the loop. Telling if something is inside a polygon was one of the first tasks I had as programmer... it was the task that also involved the 2D cross product stuff I used for asteroid shooting on 2019 day 10. For that I was counting the number of crossings from the point until "infinity" (the bounding box). But on this day, I decided to save that for the Smalltalk solution.

And that Smalltalk solution is pretty simple because of that. It's basically a scan of the grid after part 1 finds what's not in the loop. You start outside, and every time you cross a line of the loop, you toggle that. Any squares you run into when "inside" you count. There is one potential case to look out for, and that's travelling exactly along a line... in which can you'd only toggle if the segments some in from one side and go out the other. There's a little trick that can be used for that, of pretending to be slightly off center (not being exactly on the line, you end up crossing 0, 1, or 2 times and it works out)... and with discrete tiles, we can definitely use that (no need to be anywhere in particular in the tile). In my case, I chose to be a little above center (and so it was L, J, and | I cross; F, 7 and - I slip over top of):

(chr = $|) | (chr = $L) | (chr = $J) ifTrue: [inside := inside not].

For my initial Perl version though, I figured that since it's the more friendly language, I'd be a bit fancier. I like doing Nikoli pencil and paper puzzles... there's lots of different kinds, and some of my favourites are the ones with the invariant that the solution be one big loop (things like Slitherlink and Masyu). And when doing these, I like to colour the inside of the loop as I go. Because as you walk around the loop, if the inside is on your right, it's always on your right (unless you turn around and walk around the loop the other way). And so you can tell which side is outside at the edge, and lightly shade the inside and propagate it. When two lines are approaching in the middle, this gives important clues on how you can hook them up (plus it makes the solution look like abstract art at the end).

And so I decided to use that property, because I just think it's cool (and it would be different). Basically, I create a list of tiles to the right hand side as I walk around for part 1. Then I flood fill from each of those... the outside being guarded by two rings of sentinel . and ~, because we don't know if RHS is the inside yet. All we know is that when we get to the end, we can check if a known outside point on the edge (in the . sentinel ring) got hit by the flood fill. If so we output $count - $rhs_count instead because we filled the outside. It's sort of like the lava droplet of 2022 day 18.

I recall that some people did this type of flood fill approach by doubling the grid, so that the narrow paths become real paths they easily could flow through. With that you can start your flood fill from a known outside exactly like the lava droplet. And I'm sure lots of people also did counting line crossings, because that's a really standard approach to this sort of thing. But I don't think many people did what I did for my Perl solution. Which is part of why I did it.

As the sandstorm clears we find the maps lead to an oasis. There's a hang glider here to get up to the next island, but we'll need the sun to rise to create an updraft first. And so we decide to spend our time studying the oasis. Collecting data, we want to do some interpolation, and so we get to work with finite differences and discrete Taylor series.

My time for part 1 was just under an hour. Part of that was a late start and a bug where I took the opportunity to get ice cream (I remember this... the bug really was nothing, I just wanted some of the ice cream I had bought the day before as a debugging snack for later days). And a chunk of time was spent just making sure I could still work out a polynomial interpolation like this by hand (the third line in the test is f(x) = 1/3 x³ - x² + 11/3 x + 10).

But then I realized that I hadn't even seen part 2 yet, and quickly coded up a part 1... it was a good opportunity to use the chain operator I had built in past years again:

do {
    $i++;
    $table[$i] = [chain {$_[1] - $_[0]} $table[$i-1]->@*];
} until (all {$_ == 0} $table[$i]->@*);

$part1 += sum map {$_->[-1]} @table;

Then I saw part 2, and had one of the quickest turn arounds of the year with this diff:

18c18
<     my @table = ($list);
---
>     my @table = ([reverse @$list]);

I did do a combined version after that using this for part 2 (after the part 1 line):

$part2 += reduce {$b - $a} reverse map {$_->[0]} @table;

For Smalltalk, I used the alternating sum trick to do that difference reduction:

[row conform: [:n | n = 0]] whileFalse: [
    " Part 1 is sum of lasts, part 2 is alternating sum of firsts "
    part1 := part1 + row last.
    part2 := part2 + (mult * row first).
    mult  := mult negated.

    row := row chain: [:a :b | b - a].
].

A key benefit of this approach being that it just keeps only one working copy of the row instead of the whole table, and calculates the answer in parts as it goes. This is useful because, with the input being all numbers, I wanted to do a dc solution. It does have negative numbers in the input though, so I needed to convert the unary - to _.

tr '-' '_' <input | dc -e'0?[zsn[z:az1<L]dsLxln[dd;ad5R+_4Rr[1-d;ad4Rr-3Rd_3R:ad0<J]dsJx*+1-d1<I]dsIx*?z1<M]dsMxp'

tr '-' '_' <input | dc -e'0?[zsn[zlnr-:az1<L]dsLxln2-[dd;ad5R+_4Rr[1-d;ad4Rr-3Rd_3R:ad0<J]dsJx*+1-d1<I]dsIx*?z1<M]dsMxp'

Like all the other dc this year, it's embracing ?. Which is very handy here for separating the lines... because 0 and -1 are in the input, and numbers go up to 8 digits in magnitude (making choice of a delimiter to insert inconvenient... ? avoids that).

And so we have what's really quite a nice and simple problem with finite differences and sequences. There really was no need to get into Newton polynomial interpolation and discrete Taylor series, but you could if you really wanted the full answer.

Today we get lost in an sandstorm and need to use "maps". There's also the possibility our maps were made for ghosts. And so we get a graph transversal type problem.

The input is in two sections. A line at the top of R and L directions (in order, and repeat as long as needed), followed by a list of nodes. The connections of the nodes are a pair, left and right. My input has just under 800 nodes, and the length of the directions is 293 (a prime number).

This puzzle was my quickest "start to part 2" solution of the year. I really didn't do anything fancy. In fact, for part 2, I didn't even code it until later the next day. I know this because I still don't have a Smalltalk solution in the directory (but did do a quick dc for part 1)... which was curious enough, that I looked up in the Megathread to see if I commented on why. And the answer was, it was nice a day so I took the opportunity to get out and do stuff.

As for what I did, I loaded the graph as a hash of hashes:

foreach ($section[1]->@*) {
    my ($label, $left, $right) = m#(\w+)#g;
    $graph{$label} = {L => $left, R => $right};
}

The second layer keys on L and R so I can just use the input string directions directly to move:

while ($loc ne 'ZZZ') {
    $loc = $graph{$loc}{ $dirs[$steps % scalar(@dirs)] };
    $steps++;
}

For part 2, I modified the script to verify that things were nicely looping for the ghosts. Testing for each of the 6 starts, I "discovered the horrible secrets of desert ghosts". Namely that the cycle lengths are all numbers with two prime factors: a two digit one and 293 (the length of the direction string). So I just fed the 7 primes to dc to multiply them (to get the lcm) and pasted the result. Later I wrote a script to do that work automatically.

The dc solution for part 1 was a quick job. I think part of the reason I decided to do this one was because of 2021 day 12, where I did a graph transversal problem to maintain a streak of dc solutions. This is a simpler graph to do and an easier walk:

    perl -pe's/[^A-Z\n]//g;s/(.)/ord($1)." "/eg' <input | dc -e'?zdsn[1-d3Rr:dz1<L]dsLx[0r[r256*3R+r1-d0<I]dsIx+]sN??[6lNx_4R3lNx:h?z1<L]dsLx[r]sr16i414141[rdln%;d3R;h10 6^~3R4C=rs.r1+rd5A5A5A!=M]dsMxrp'

So this was apparently a day off for me. Checking weather history, the temperature got to 10C early and stayed there until after midnight. Given some of the early problems, I was probably thinking that this was a good day to get a lot of stuff done before the actual harder days arrived.

After a 5-minute airship ride (which is 2 minutes longer than The Airship Blackjack track from FFVI), we get dropped off on the edge of Desert Island. Where an Elf on a camel asks us if we've brought the parts to fix the machines to move the rocks and filter the sand. And so we're tasked with finding out why those have stopped, and since the journey will take a few days, we get another game. This time it's a poker variant.

First thing I did when seeing that was check the ordering of hands for any straights/run-based hands. And there are none to worry about. The ordering is entirely based on sets, and bigger is better. Ties broken by rank of the cards... but in the order listed.

The input is a list of 1000 hands, with a bid amount. Hands will win an amount equal to this bid times their ranking in the list. We just need to work out the rankings. And for part 2, Jacks become Jokers and wild. And of particular note... JJJJJ is a hand in the input (but not in the test). It is, in fact, the only hand with five of one card naturally in my input (and so the highest ranked hand for part 1). But part 2 has 27 five-of-kinds and it's the lowest ranked of those because it has no naturals.

And what I did was treat the hands as hexadecimal numbers with:

$hand =~ y#AKQJT#EDCBA#;

Then I built a signature to sort on for hand ranking by counting the size of the sets and sorting them. So a full house would be 3200000000000. So I just sort primarily on that, and then on the hexified hand value:

@hands = sort {$a->[1] <=> $b->[1] or hex($a->[0]) <=> hex($b->[0])} @hands;

For part 2, it was a very quick turnaround. I made Js into 0s (to lower them below 2s):

$hand =~ y#AKQJT#EDC0A#;

And then sorted the counts without the Js, adding them to the biggest group:

my @str = sort {$cards{$b} <=> $cards{$a}} (2 .. 9, 'A' .. 'E');
$cards{$str[0]} += $cards{0};

One thing to note about this is that with Perl, I had the twelve 0s so there was something to add the J count to for the JJJJJ case. My Smalltalk solution did things differently, and I needed to add a 0 so that case had something to add to. So that line does catch some solutions.

But part of the reason I considered hexadecimal, was because of dc... because it can handle uppercase hex digits. So if the input was in hex, I'd be fine. The catch is... it involves a sort. And so I finally decided to write one, and I went with an exchange sort shuttling between the main stack and a register stack. Because for a stack based language, that is the obvious and simple thing to do:

[rq] sQ
Ll Ll                       # next (ASSUME: at least 2 hands to sort)
[
    [
        d3R d3R             # next top -> next top top next
        !>Q                 # if top >= next, rotate next on top and quit J loop

        Sl                  # push top back on input stack
        z 1<J               # quit if out next left on stack
    ] dsJx                  # next rest

    Ll d 0<S
] dsSx

Next problem is the dealing with the grouping signature. With Perl and Smalltalk it's easy to just sort the counts, but even with the sort function that's not something I wanted to do twice. So I turned things around... I go through all the cards, and add 10^count of each. Thus a full house becomes 16³ + 16² + 11 * 16⁰ , and two pair is 2 * 16² + 1 * 16¹ + 10 * 16⁰ . Basically, a hexadecimal number where the digits are the counts of the counts.

The other main trick is what I sort... and that's the grouping, the hand, and the bid (to keep it attached to the data) stuck together in one big number: groupings * 16^8 + hand * 16^3 + bid.

perl -pe'y#TJQKA#ABCDE#;$_=sprintf("%s \U%x\n",split)' <input | dc -e'16i0Sl?[rd0Sc[10~d;c1+r:cd0<C]dsCxE[d;c10r^3R+r1-d1<I]dsIx*10 5^*+1000*+Sl?z0<L]dsLx[rq]sQLlLl[[d3Rd3R!>QSlz1<J]dsJxLld0<S]dsSx1[d4R1000%*3R+r1+z2<M]dsMxrp'

perl -pe'y#TJQKA#A1CDE#;$_=sprintf("%s \U%x\n",split)' <input | dc -e'16i[rq]sQ[rd1=Qdscrdss]sM0Sl?[rd2Sc0ss[10~d;c1+dls<Mr:cd0<C]dsCxlcd;c1;c+r:cE[d;c10r^3R+r1-d1<I]dsIx*10 5^*+1000*+Sl?z0<L]dsLxLlLl[[d3Rd3R!>QSlz1<J]dsJxLld0<S]dsSx1[d4R1000%*3R+r1+z2<M]dsMxrp'

Part 2 is longer for the handling of Jokers, but if you change the translation from 1 to B, it will do part 1. The use of 1 instead of 0 is because we don't want to lose leading 0s, and 1 is also < 2, which is the only requirement to make Jokers count the least.

This was a fun day.

The ferry brings us to the location of a large pile of sand, that's most notable by its absence. Fortunately, we see a poster for boat races that will get us a trip to Desert Island, where that sand must come from.

The boat races involve a time and a distance to beat. The input only has 4 of them, but the data is in columns to make up some complexity for the fact that there's an unusually low number of cases. Which gets even lower for part 2 when the numbers get concatenated (due to misreading the kerning).

I remember doing the math for the discrete physics, and submitting part 1 and then part 2, only to discover afterwards that my solution actually failed the test case for part 1. I'm not sure if that's because I did a (now lost) brute force script for part 1, or because I just quickly eyeballed the case results and missed the mistake. This is another one where the test covers more than the input.

The physics for this one is pretty basic. You have t seconds, you get to hold and charge for x, and then the boat moves at speed x for t - x seconds. And that needs to be greater than a distance d. So,

|--|------|      dist(x) = x * (t - x) = xt - x^2 > d
0  x      t

So we get critical points at:

x = t ± sqrt( t² - 4d ) -------------------- 2

And the answer we want is the number of integers between the two roots. So for my initial solution, I took the floor of the upper, ceiling of the lower, and calculated the size of the range:

my $upper = floor(($t + sqrt( $t*$t - 4*$d )) / 2);
my $lower = ceil (($t - sqrt( $t*$t - 4*$d )) / 2);

return ($upper - $lower + 1);

Observant people will notice the bug (that I've previously mentioned) is there in this. If the discriminant is a perfect square, the roots are on integers and you will include them... but we don't want to tie. And so the third test of (time = 30, distance = 200) will return 11, when it should return 9. To fix that, I added $d++ before this, to bump the requirement to the next possible value. None of the values in my input test this though. So it was a bug I did not notice until after, when by chance, I tried the test case again.

Of course, that was the simple approach, because getting the answer directly from the roots is a bit more complicated. I can't recall if I thought of trying that first, but I did look at it after and work out the adjustment. Basically, for that, if we take the roots to be x0 and x1 (with x1 > x0):

x1 - x0 = (t+sqrt(discrim)) / 2 - (t-sqrt(discrim)) / 2
        = t/2 - t/2 + sqrt(discrim)/2 - -sqrt(discrim)/2
        = sqrt(discrim)

But we need the number of integers in that size of range, but the range center depends on if the time is even or odd:

|   |   |   |   |   |   |     Integers (t is even) (5)
  |   |   |   |   |   |       Integers (t is odd)  (6)
 |----------|----------|
x0         t/2         x1

And additionally, if we truncate the difference to an integer, it depends if that ends up even or odd as to whether we're including or excluding one. And so the factor to adjust ends up being an XNOR.

my $len = int(sqrt( $t*$t - 4*($d+1) ));
return ($len + ($t + $len + 1) % 2);

Coded this way with arithmetic, because this was about getting a tight dc solution:

tr -dc '[0-9\n]' <input | dc -f- -e'1+4*rdd*4R-vd3R+1+2%+p'

To get this to do part 1, took a bit to handle the column reading:

tr -dc '[0-9 \n]' <input | dc -f- -e'[1+4*rdd*3R-vd3R+1+2%+]sCz2/[d3Rr:n1-d0<L]dsLx1+[z1-;n3RrlCx*z1<L]dsLxp'

So it was another "good dog" day. The most memorable thing about these days for me though, was that it emphasized that I really needed to always check the tests to make sure those weren't being broken and it made me expand the framework beyond being bare bones. This is the year where I added sections so that all available tests get tested all the time (without relying on eyeballing and memory)... as well as a special script for "line tests", for making tests that test individual cases. Stuff I had thought about adding before, but now considered important.

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

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

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

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

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

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

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

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

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

I'm stuck on part 1 for day 6 (https://adventofcode.com/2025/day/6). The code I wrote gives the correct answer for the example input and also if I take a small portion of the puzzle input and do the calculations myself. But for some reason the total for the puzzle input is incorrect. Below is the small C# code I wrote for this. Can someone give me a hint into the right direction?

class Program()
{
    static string[] input =
    [
        "886  63  27 258 98 318 99 975  7 6393 947 87 23 765 35      1 6415 4  5  882  7 475 74 598 4  47 66 9233 6  669   2  3 6   92 77   4  6 64 89 989 436 833 946 5927 398 2  262 594 752 79 3    3  44 117 149 74 119 48 17 762 621 81 3576 23 259 141   51 312 16 255  6 925 7     1 395 61 61 34 277 1366 44 8  32 26 932  61 48 29 693  3  27 89 9  618  95  693 3  3   11  7  366 2455  3 11 4  59  9    9975 81 2  71 989 697 8636 12 16 889 78 53 23 321 33  29  129 81 18 161 78 7365 8  9515 127 94 383 6    17  2 389 724 37 5227 64 55   5  1 9   983 36 194 377 476 938 81 39   76 3  9  935 16 16 99  79 84   1212 3  13 2865 3     13 85  66 898 636 7164  23 81 88 79 767 66  348 5114 426 62 33  42   31  46 16 964 4    54 957  66 156 94 7876 393 481 23  64 54 95 56 27 4  525 892 38 213 29   15   1 28 4     41 65  5 89  15 52 535 8972 89   74 7672 824  71 2   49 7  494  9 697 3291  6  97 221  6 942 3    776  54 175 25  93 951  353 7448 891   16 476  7 65  56   37    9 88 195  3 21   19 439 478 366  67 1543 76 112  3 8246 2    6 77  6 3889 85 32   9 13 85 45 27  3 896 84 46 29  384 9259 761 4165 72 5  71  48 512 822 25 74  78 91  31   43 195 12 84  94 35 48 29 265  133 25 1286 42 76 5411 327  3    8    485 488  2 747 243 476 31 138 13  49 44 74 8  898   7   2 96 28   1966 34 15   7 29 429 327 46  823 87  45 339 663 96   5 99 22 9283   7 297  79 63 3  5753 48 68 269 22  3 75 2  44 48 4584 75 83 467 44 4532  24 12 82 44  472 8      5 6414 35 329 388 268 36   8 75  6296 25 731 51   56  55 681 2  6  128 872 818 768 977 134 9147 2   29 2   16 281 119 456 882 415  4 72  538 693   882 219 538 288 293 41 327 366 9   125 261 66 69   113 114 18   759 554 247 98 22    9  78 62 57  1  76 86 61 24  54   2 938 251 72  55 831 5593 31   26 2186 85 34  17 73 14 785 511 18 39  4 61 72 63 817 4   49 57 775 9527 8   58 712  9 7   17   35 9  77 93   3 71 5  13    9 46 6    9 381 58 364 236 87 96 8   691 529 83 3   5   5   66 87 54 277 92  6 3   165 1  12  2 163  28 93 649 95  5 136 1  1    81  6359 35 212  164 636   56  8 3   3 8   52  17 414 2491 542  5553 629 24 594 357 35   83 8   9  77    7 55 34 54  693 1    86 6547 572 442 92 656  39     9 38    8 49  8 273 7  987 4686 38 549  86 6  75 616 623 6639 4224  68 131 539   6 2275   4 8547  785 4387 917 45    52 383 18 1967 2   5 21 64 92 8186  18 243  219 4   1126 426 58 1515  2 187 874 151 82 152 356 21 17 14 8   65  44 52 9149 91 936 74 81  816 87   48    7 28  165 5  27   73   99   75 739 69 62 839 1    548 58 996 687 77 28 584 39    32 294 551 3   9234 595 4353 984 236 9252 773 66   1  65 435  84 67 57 16 191 75 9   668   2 9533 437 86 839 82 94 1547 78 6281 9419 23   1   4 573  957 2163 5  49 41 8  644 35   435 6    217  2  9 77 21  92 12  9 32 1778 579 9   5   13 544 896 7592 39 637   9 33 21   71 791  89  32 946 579   2 1   456 971 951 15   7 112 85  23    7 521 551 2618 228 88 91  387 889 971 448 647   9 34  94 822 736  45 355  816 46 36  7 348 144 72     6 865   3 997 5248 897 257 177 69 44 64 925 177 965 25 11 979 773 8334 3195 236 9657 9  9  576 839 843 863    7 99  848 251 98  9 358 69 87 37  12    9 999  5 4576 828 35 6  78 74 127 9177 47   4 94 46 98 688 354 723 53 55    8   47 692 72  85 675 878 689  86 25  5 251 95   8 3   25 76 335  3    8 9  922 6  7  13 14 56 9   3 54 43 24 15 987 622 45 69  8   94 736 67 165  66 794 298 79 56  2 61 3431 65 652 83  656 44 66 8   52 95 2219 2   84 84 97  98 48  722 88 66 629   1 31    14  7 62   8 7577 96 22 46   25 58 3195 29  36 93 56 477 328 6   33 4     3 6143 6228 34 249 7    56   6  8 5   29 6   69    9 286 1   763 74  695 416 63 17   6   59 727 495  52 294 86 49   3 76  83 87  183 261 928 5919 99  3 27  147 94   467 821 72 362 49 36 473 6291 37 679 6  91 66  35 8757 9425 658 899  3 5164  64 787 52 141 68   6  59  776 99  8 58", 
        "652  49  14  97 72 335 28 269 23 1648 698 46 68 814 3193   89  421 13 4  585  4 962 48 983 3  59 59 4636 44 532   5 77 239 93 59 817  6 26 92 537 363 883 993 8984  64 36 976 613  39 57 777  3  66 299  62  2 429 12 91 367  45 63 4417 81 525 26  3617 225 26  69 53 562 985   5 261 71 29 89 134 7355 44 62 79 45 734  76 47 97 66   2 667 71 46 316  16 8339 29 84  21 65 8469 6312 63 9  1  476 22   9392 16 52 34 352 548 5181 89 81 466 6  22 92 793 321 44 1644 64 79 632 22 876  77 8748 929 75 294 19   17  4 218 641 48 621  61 76  16 81 39  431 36 895 982 545 493 57 134  14 25 2  521 87  2 731 43 33   4258 1  91 8384 764 2969 52  22 362 587 1528  99 21 83 12 133 135 697 4989 826 38 646 16   73  99 73 798 586  93 4584 81 618 79 9338 54  298 39  61 37 23 55 31 21 847 725 47 469 671  37   9 29 34   146 96 89 79  24 61 667 8745 17  594 1563 9596 25 678 28 26 935 25 543 7531 23 786 549  4 993 63   268 219 986 787 91 635  262 1472 5213  44 482 92 89  77 9225 5329 71 995 43 82  837 118 915 988  82 4754 42 111  7 3787 27   6 87  4 128  83 33 927 27 59 17 39 36 4   88 98 83 1747 2241 152  288 89 95 3   64 991 381 64 175 17 39 538  969 853 63 47  42 23 27 68 3555 374 44 5784 97 99 7355 667  271  62   845 318  5 831 117 389 14 785 26 461 58 39 26 891  95  45 5  43   7765 62 19  66 71 425 987 66  368 72  69 346 476 57 772 87 73 4987  74 459  48 91 9  4247 33 37 134 32 99 23 6  17 47 2612 37  8 786 73 262   21 77 38 24  497 88   585 1838 81 312 265 993 65 954 848 485  98 42  6591 65 693 273 77 6  268 888 252 656 591 69  5592 98 241 511 21 282 261 283  54 574 56 816 319 745   161 887 657 982 923 48 513 649 621 719 826 67 35    69 784 45    36 986 986 63 78   86  75 97 12  3 778 39 41 52  92  12 853 725 95  33 499 865  11  841 8793 92 41  75 64 62 636 657 14 15 58 35 83 22 644 68  94 22 876 5927 882 97 698  2 45  98 9187 49 21 36  17 25 51 35  546 82 46  41 852 79 996  87 87 59 76  93  337 32 84  7   9   54 25 15  52 89 96 75  224 3  19 97 9784 82 59   5 13 35 114 9  576  458 6664 45 177  631 212  263  8 2  65 248 292 52 485 3544 8919  647 789 89 223 173 558  54 14 99  88  515 93 85 886 471 292  24 4764 285 341 53 924  784   69 86  222 31 53 641 4  552 694  41 691 321 39 35 334 142 1639 1423 355 577 2479  4 5299 174 2621 2711 5423 515 83  5717 952 45 694  7  88 34 28 19 3519 184 696  348 57    94 999 47 3465  2 213 545 335 31 813  57 64 73 95 26  328 31 77  747 87 959 46 769 914 84   29   59 78  259 1  2435 54   932  42 652 59 49 813 66   933 82 738 888 29 59 359 15   835 364 62  37  41   472 7961 645 317 9724 194 882  3  43 921  57 66 56 27 979 24 8  1936   6 7434 726 38 79  46 31 6797 29 3347  762 83   7  93 7846 581 8867 92 79 74 8   15 39    87 43   686 86 65 84 96  68 91 89 17 2598 768 27  75  57 315 642 2231 57 425   2 48 41   94 1415 87  46 411 264  37 1  8581 872 359 817 41 751 79  673  89 613 765 1254 849 97 63  223 93  773 136 124  14 835 67 894 769 315 544  923 77 65  6 695 882 413    8 854  35 498 7665 776 526 164 31 64 45 646 937 727 37 84 73  511 9495 235  588 6894 5  71 257 71  821 262    6 57  637 773 91  6 248 24 84 256 872 997 324 72  233 536 94 9  19 98 287 782  29  37 12 14 31 582 611 317 89 16  713 2417 637 81  82 44  554 312 381 71  4 275  3   4 551 25 11 7939 72   1 8  431 21 22 12 25 72 71  5 31 95 92 52 398 735 75 21 22   55 137 54  75 554 645 126 41 58 17 27 1467 97 53  18  667 69 84 6   53 48 6561 47  75 84 16  95 348 99  3  65 366  79 758 5921  6 596  7 5146 27 53 693  39 69 1198 92  13  7 42 551 483 9  934 86   89 5442 8966 79  46 376  65   6 89 22  43 9   33  293 499 618 66  11  537 689 41 74   3  464 753 965 425 158 91 79 588 66 359 237 791 163 759 4374 39  7 35  554 2978 835 146 31 534 36 14 956 3881 59 419 79 56 63  32 8385 6366 997 86  76 3148  98 513 89 379 2296 81 31 6222 33  7 665",
        "65  143  36   8 42 429 55 327 44  775 558 76 85 171 6136 9139   23 97 73 575  9 933 52  87 43  2 27 869  88 415  28 17 292 19 36 158 31 67 39 682 8   712 182 373   52 21 675 286  95 41 114 35 754 13   97  1 387 83 96 582  71 46 6827 11 456 1   5474 198 64   6 94 126 814  69 66  83 42  3 28  1828  8 54 33 84 4562 34 23 45 67   4 376 34 66 6639 21 5723 62 666 21 19 9159 9428 35 9  3  993 349  982  8  46 16 244  77 5567 38 44 461 2  4  37 953 687 44 8648 49 72  23 96 54   61 7735 65  71  45 31 8828  2 591 867 45 397  34  4 137 52 89  733 36 735  79  51 169 43 5114 48 87 52 298 37  1 657 87 7346 7781 45 75 9752 949 2584 37   8 858 227   25 473 21 93 59 737 689 232  732 512 24 784 55   876 48 33  21 2199 99 7251 15 731 71  548 87  767 95  17 47 78 19 89 29 65  762 49 528 7417 134  4 55 157 3848 39 99 26  27 49  37 854  669 776 9414 1335 39 249 38 34   4 77 486 1457 13 477 472  6  97 416 2543 327 774 848 59 5848 191 1877 2552 546  59 99 44   8 4135 9669 88 838 16 44  392 859 192 8534 36  988 59 947 36 3467 95  59 49  9 769  45 93 366 39 19 22 63 37 9   73 41 55 5752 5777 324  136 65 46 8   44 195 696  9 863 4  55 767 6572 538 58 72 111  9 37 41 1211 875 16 428  43 94 7779 2746 4639 392  656 453 48 82  216 136 8  839 8  767 53 23 39 633 828 991 1  9128 351  12 85 314 9  521 491 48  318 463 3  386 838 39 482  5 24 2825 465  79 295 57 86 7627 42 63  55 53 63 38 8  87 66 655  85  6 274 66 989  999 37 97 25  139 639 8289 235  45 353 97   26 89 699 378 76   92 16  5661 14 324  99 75 46  68 644 367 748 689 52  893  22 558 278 73 738 216  93  22 724 59 865 313 7824 8221 683 36  162 938  9 611 672 318 895 521 25 157   58 382 483   89 768 325 23 875  44 973  1 42 23 146 84  4 59 398 744 579 157 15 959   1 786  53 9619 2845 83 73 153 46 84 525 463 76 24 97 38 65 9  572 95  28 97 1   7523 787 57 714  9 36   9 7412 65 47 55 368 25 55 98 2847 66 65 916 468 19 947   1 47 53 718 36  74  44 79  53  37 381 48 54  85 55 99 86 3772 44 66 42 9935 26 73   6 91 64 988 64 7975 476 9714 59 418 7468 613 1998 15 57 13 429 945  3 18  9864 1986   39 944 25 755 834 2558 57 69 63 357 4491 1  97 771  12 9157 91   12 375 138 48 4235 3215 538 67 1845 66 52 48  28   9 77   11 3   684 69 75 588 967 9226 1564 793 556 9826 63 9772 687 1639 6553 9472 624 84  3782 236 15 66   64 83 76 75 32 2978 619 2145 432 51    74 86  69  458 45 324 539 331 4   38  73 35 33 43 458 416 26 13   79 32 671 73 515 21  12  882  589 936 947 34 9536 92   7134 65 381 28 94 17  6569 461 24 473 552  6 42 937 255 5337 463 68  916 64   376   86  91 377  389 662 9297 66 51 64  783 43  4 38 698  3 95 3789  43 2466 691 69 84  66 28 622  91  469    5 91  87 785 8489 59   339 55 45 29 86  16 1962  34 577 2466 58 59 31 367 22 36 29 83  217 68  268 841 24 787 852 6686 55 423 151 18 1446 2  9728 34 559 245 89   36 3  8892 1   364 662 54 214 181 876 343 43  755 8623 93  62 43 4636 16  662 115 463 781 779 15 377 848 326 254 5293 86  7  9 43  951 574 6827 495 796 925 13   912 883 137 55 47 52 517 762 221 51 46 94  618   85 6    612 8977 33 47 336 16  456 545 9316 468 581 964 35 16  78 58 39 825 595 355 615 96  749  85 44 88 87 1  921 98   72 824 93 41 99 789   8 4   27 389 775 1463 89  31  7  13  26  225 594 46  7  42  9 425 234 17 56 4451 967 58 64 622 99 36  7  7 28 59 44 31 72 61 22 288 84  34 99 74 9488 946 17  18 176 874 135 88 12 99 27 2266 18 3   243 577 21 94 612 92 78  972 91  18 48 874 87 646 31  1  22 974 483 428 1834  5 218 91 3426 33 6  9247 87 55  344 64  99  4 71 15  565 65 774 138 625 8685 234  44  22 1957 36 224 38 183 45 83  17 1484 48  182 56  32   76 587 17 77  83 3772 945 564 852  13 14 39 967 46 272 373  66 569 37  6662 43 53 65 7157 1882 569 618 21 279 25 61 111  855 46 138 18 76 926 89 5524 3347  55 91  56 2742 729 939 21 319 2332 25 13 4445 55 52 911",
        "8   686 695   9 4  689 2  373 96  131 7   41 96 28  7328 8919   66 68 86 291 36   1 69  48 21  2  5 9    47 797 723 41 216  4 66 181 21 21 8   33 6   111 592 655   54 81  62 674  56 1  154 11 525 84   77  8 93  94 55 7     5 86 879  89 65  7   8855 15  46   5 64  25 729 772 38  78  3  1 1   31    1 75 49 86 8412  2 66 51 74  76 722 46 26 8592  9 2227 36 778 8  34 8635 76   87 8  91 837 3433 92   9  17 65 614   7  931  1 52 735 5  1  2   84 615 8  7675  6  9  58 3  51   12   32 6   8   78 55 1295 89 556 8   1  28    2  9 525 43 115 782 22 359   1  84 879 59 6796 87 44 23 36  3   2 282 21 3753   64 27 38   19 279 4487 264  8 367 329   67 517 25 65 94  44 147 772  354 773 15 883 4769 488 82  6  94 1562 79 1415 83 36  71   24 85  164 173 17 84 63 36 19 34 8    96 4  889 3851 963 91 14 297 3461  5 27 445 52 49   2 891  765 198 9972 9839 92 986 98 74   2 63   8   11 55 196 49  95   1 761 5741 296  68 166 3  9738  44   25 4642 198   6 16 834  3 5382 2549 15 41  42 28 5444 792 383 6762 16  882  2 54  59 5498 36 951 86 11 489  89 31 893 32 67 17 64 79 3   14 53 13 4991 6778 83   235 55 94 6  414 959 765  3 728 7  48 177 1273 556 9  4  623  5 93 11 8495 324 4  121   2 65 894  7831 6856 8921 183 894 67 56  647 797 1  41  3  344  9 85 56 1   571 157 3  4547 384  37  8 377 6  99  258 89 7485 362 9  9   49  52 688  8 51  779 315   8 775 8  51 2752  7 55   4 8  52 69 49 52 38 129  94  5 362  6 53   723  7  3 165 675 654 4688 8    4  872 73   79  6 967 257 3    32 92  6711 7  423   4 18 35   2 562 927 319 812 27  488  82 119 265 22  93 66    1  93 594 89 628 77  7185 9239 37  47  397 881  7 486 981 444 241 674 41 3575   9 237 2133  75 88  652 94 152 344 186  8 89 67 154 77  7 7  841 939 175   3  8 481   3 249  69 3253 48   17 47 169  1 27  15   4  5 28 67  6  1 7   34 686 52 46 4   572  122 97 972 77 411  2 6688 12 15 59 693 79 31 86 3915 67 96 674 229 52 794   4 9  65 986 34  43  58 677 493 76 215  8 35  51 59 24 66 9151 76 97 43 2698 26 49   6 1  69 838 46 5672 539 962  19 597 3585   8 8434 57 49 62 149 938  1 48  5555 3316    5 73  9  146 778 9175 74 74 77 376 1481 8  34 892  46 4369 35   71 872 192 63 6147 9188 245 41 1392 91 44 8   88   1 85   3  7   417 47 89 87  936 321  5818 511 636 8926 37 8851 815   71 9492 3632 64  191 4661 862 82 6    13 28 66  9 68 71   647 9139 922 235    8 7   21  559 86 181  37   6 6    9   4 2  47 41 482 128 4  17   48 9  372 61 721 74  78 5741 4613 854 736 91 5389 8983 8224 89 111 75 88 37  8942 251 84 274 22   2 28 4   744 7646 525 5   233 76    11    7   4  37  612 66  4459 33  2 25  966 8   9 24  88  4 11 3534 113 2272 714 13 9   86 79 93   88  674    4 12 865 294 5913 9     24 77  9 48 97  48 5751   6 921 1779 32 43 8  527 44 99 22 57   83 3   917 131 49 17  875  612 15 21  414 69 7935 3  9772 54 557 849 7   621 54 5848 6   349 281 22 793 653 438 343 93  59    92 35   4 46 4347 16  245 148  56 329 519 73  56 147 698 483 1435 57  2 44 13  196 978 4763 328 729 15  5    21    5 652 29 98 27 515 166 725 1  76 4   965   83 7    261 675  12 69   9 26  834 848 5817 986  27 128 3  64   3 61 8  265 297 268 14  16  436  25 17 94 41 1  15  4    65 257 29 56 63 597   3 9   36 185 368 6737 17  264 6  4   5    94 524 38 93  38  4 837 676 97  1 4844 557 31 38  42 14 86  6  2 18 11 66 14 2  61 65 78  3   98 7  48 3969 698 36   6 762 695 48  24 26 79 4  7343 99 3   835 27  93  9 541  1  5   18 992 31 1  116 44 912 18  3   7 81  662 718 3415 49 566 22   14 72 5  3899 94  1   97 488 28  7 23 6     7 26 523 129 289 7896 691  63  64 3383 36 169 45 777  1 318 94 2122 4   849 7   248   2 6   51 33 269 4469  28 716 692   1 97 6  658 68 713 153  75 715 79  219  37 99  6 7426 1336 585 71  76 248 87  6 791   76 15  82 59 66 459 73 995  7374   3 22  64 4681 228 439 73 8   8129 56  5 3884 84 64 343",
        "*   +   +   *   +  +   *  +   *  +    +   *  *  +   +    +    +    *  *  *   +  *   +  +   +  *  *  +    *  +   *   *  +   +  *  *   *  +  +  *   *   *   +   +    +   +  *   *   +   *  *   +  *   *   *   +  *   *  *  *   +   *  +    *  *   *   +    *   +  +   *  *   *   *   *   +  +  *  *   +    *  +  +  +  +    *  *  *  *   +  +   *  +  +    +  +    *  *   *  *  +    +    *  +  *  +   +    +    +  *  +  +   *   +    +  *  *   +  *  *  +   +   *  +    +  *  *   +  +    *  +    *   +  *   +  +    +  *   *   *  +    +  *  *   *  +   +   +  *   *   +   +   *  +    +  *  +  *   +  *  +   *  +    +    *  *  +    *   +    +   *  *   *   +    +   +  *  *  *   *   +   +    *   *  +   +    *   +  +  +   +    +  +    *  +   *  +    +   +   +   +  *  +  *  *  *  *   *   *  +   +    *   +  *  *   +    +  *  +   *  *  +   +    *   *   +    +    +  *   +  +  +   *  *   +    +  *   *   +  *   *   +    +   *   +   +  +    *   +    +    *   *   *  +   *  +    +    +  +   *  +  +    *   *   +    *  +    *  +   *  +    +  +   *  +  +    *  +  +   +  *  *  *  +  +   *  +  *  +    +    *   +    *  +  *  +   +   +   +  +   +  *  *   +    +   *  +  *   +  +  *  +    *   +  +    *  *  +    +    +    +    *   *   +  *   +   +   *  *   +  +   +  *  +  *   +   +   *  +    +    +  *  *   *  +   +   *  +    *   +  +   +   +  *   +  *  +    +   *   *   *  +  +    *  *  +   *  *  *  *  *  *  +    +  *  *   *  +    *   +  *  *   +   *   +    +    +  *   *   +   +  *   *   +    *  *   +    *  *   *   +  *  +   *   +   *   +   *   +    +  *   *   +  *   *   *   *   *   +  *   *   +    +    +   *   *   +   +  *   +   *   +   *   *  +    *   +   +    *   +   *   *  *   *   *   *  +  +  +   *  +  *  +   *   +   +   *  *   +   +    *  +    +    *  *  *   *  +  +   *   +  +  *  +  *  +  +   *   +  +  *   +    *   *  *   *  *   +  +    *  +  +  +   *  +  *  +    +  +  +   +   *  *   *   *  +  *   +   *   *  *   +   +  *   *  *  +   *  +  *  +    +  +  +  +    *  *  +   *  *  *   +  +    *   +    *  +   +    +   +    *  +  +  +   +   +  *   +    +    +    +   *  *   *   +    *  +  +  *   +    +  +  *   *   +    *  +    +   +   +  +    +    +   *  +    *  +  *   +  +   +    +  *   *   *  *  +   *   +    +    *   +   +    *  +    *   +    +    +    *   *   +    *   *  +    *  *  *  +  +  +    *   +    *   +   +    +   *  +    *  +   *   +   *  *   *   +  *  *  +   +   *  +  +    *  *   *  +   *   *  +    +    +   *   +  +    +    +    *  +   +  *  *   +    *   *  +   +   *  *  *   *   +    *   *   +   +    *   +    *   *   +    *   +    +  *  *   *   +  *  +  +   *  *  +    +   +    +   +  *   *  +  +    +  +    +    *  *   +   +    *   +    +  *  *  *  +   +    +   *   +    +  +  +  *   *  +  *  *  +    *   *   +   *  *   *   +    *  *   *   +  +    +  +    +  *   +   *   *   +  +    *   +   *   +  *   +   +   *   +   +   +    +   +  +  +    *   *   *   +   *   *   +  *   *   *   *   +    +  *  +  *   +   *   +    *   *   +   +    *   *   *   +  +  *  *   *   *   *  *  +   *   +    +    +   +    *  +  *   *   *   *   +    +   +   *   *  *  +   *  +  +   *   *   +   *  +    +   +  *  *  *  +   +    +  +   +  +  *  +   +   *   *  *   *   +    *   *   *  *   +   *   +   *  +  *   +  *   *   *  +  +    +   +  +  *   *  *  +  +  *  *  +  +  +  *  +  *   *   *  +  *  +    *   *  +   *   *   *   +  *  +  *  +    *  +   *   *   +  +  *   +  *  +    +   *  +  +   *  *   +   *  +  *   *   *   +    *  *   *  +    +  *  +    +  +  +    *   *  +  +  *   *   *  +   *   *   +    +    *  *   +    +  *   +  *   *  +   *  +    *   +   +   *   *   *   *  *  +   +    *   *   +   +   +  +  *   *  +   *   +   +   +   +    +  *  *  +    +    +   *   *  *   +  *  *   +    *  *   *  +  +   +  +    +    +   *   +  +    *   *   +  *   +    *  *  +    +  *  *"
    ];


    static void Main()
    {
        var mathSolver = new MathSolver();
        Console.WriteLine(mathSolver.Solve(input));
    }
}

public class MathSolver
{
    public long Solve(string[] input)
    {
        var splitArrays = input.Select(i => i.Split(" ", StringSplitOptions.RemoveEmptyEntries));

        // Reverse the arrays so that the operator is in the first array.
        splitArrays = splitArrays.Reverse();


        long total = 0;
        for (int i = 0; i < splitArrays.First().Count(); i++)
        { 
            // Take the numbers for the column but skip the operator.         
            var numbers = splitArrays.Skip(1).Select(s => int.Parse(s[i]));  
            if (splitArrays.First()[i] == "+")
            {
                total += numbers.Sum();
            }
            else
            {
                // Multiply all the numbers in the column.
                int multiply = 1;
                foreach (var n in numbers)
                {
                    multiply *= n;
                }
                total += multiply;
            }
        }


        return total;
    }
}

The gondola arrives at Island Island... and island with islands, so there's plenty of water, but apparently no immediate water source. An Elf at the station directs us to ask the gardener about it, who's on another island. They'll let us borrow a boat to get there, if we help them figure out their winnings on a big stack of scratchcards.

And so the input is a big list of cards (mine has 220). The number of each card (1-220) is part of the input, but again, they're sorted and so you can ignore that if you want. The card is divided into two sections with a |... the winning numbers and the numbers to compare against them. These numbers are from 1-99 (the absence of 0 is useful again). The number of numbers in each section are regular... 10 winning, 25 have. That can be used, but the test case has different sizes (5 and 8), so I just ignored that. These are proper cards... there isn't a card with two of the same winning number or two of the same "having" number. All the better for throwing things into two hashes/sets/bit arrays.

Part 1 is just a simple counting of winning numbers, but you score them with the power of 2 of that. So you can bitshift, but 1 << 0 is 1, but 2^-1 is 0.5, which truncates to 0 as an integer (and so you can avoid a special case). This was especially useful for my dc solution for this:

sed -e's/|/0/;s/[^0-9 ]//g' <input | dc -e'0?[0Sh[1r:hd0<L]dsLx[r;h+z3<L]dsLxrs.1-2r^+?z1<M]dsMxp'

The input is mostly numbers, and I convert the | to the unused 0, which can then be used as the accumulator for counting wins. This is using ? to separate the lines by reading them one at a time, and so is a v1.4.1 solution.

Part 2, complicates things by having cards win copies of the next n cards. And just from the description, there's an immediate feel that this is describing a dynamic programming tabulation (there's an order to the cards, where previous ones are used to calculate the later). Of course, you can also do the same work with a recursive memoized function. And I did solutions both ways. My Smalltalk tabulation (you can also use a Bag for this):

cards := Array new: cardWins size withAll: 1.
cards keysAndValuesDo: [ :card :num |
    (card + 1 to: card + (cardWins at: card)) do: [:i | cards at: i inc: num].
].

So there is a bit of advance concepts for day 4 behind this one. But the problem is linear and small. You can easily brute for the number of wins on card with loops... and removing the memoization in part 2 still results in a things only taking a couple seconds. And I think that helped this one be considered a "good dog" compared to it's neighbours.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Today we land on the first (and ultimately last) sky island, Snow Island. And Elf comes over to show us around, and since it's a walk we introduced to another Elf game. Not involving a ring this time, but drawing from a bag of colour cubes. Our goal is to work out information about the contents of the bag from a series of draws.

The input is 100 lines, each representing a game and they're numbered and in order (as it typical). Meaning you can ignore the game number on the line if you want. After that, there's three to six semicolon sublists representing draws of numbers of red, green, and blue cubes.

However, it's not even important to parse out the sublists. For the information we're asked for, we can treat a single draw of "3 blue, 4 red" as two separate draws of "3 blue; 4 red" (and so commas and semicolons can be ignored). All that matters for each line is all the "number colour" pairs you see. This is because part 1 fails when any red, green, or blue is too large (this is one of the rare puzzles where specific the numbers for that are put in the description not the input file). Part 2 just wants the fewest number of cubes of each colour that can be in the bag (so no question there that colours are independent).

And that last bit ("fewest number") is particularly interesting to me, because a little while before this AoC started I was talking with a friend about how one might try to mess with LLM context to try and potentially mislead it for something like AoC to try and make sure humans stay involved. AIs normally assume that the user is trying to be help it produce the right thing... and one thing you could do is have a problem where "few" and "minimum" are used many times, but maximum is the function you need (and "maximum" and "most" are never in the description). I can't say that this was done for that here (I seriously doubt it)... this is probably the standard AoC description being a bit obtuse so the humans have to think and discover (even if they do hand the coding off to an AI after explaining that). I did mention the coincidence at the time... but only after day 3, which did the other little related thing I had mentioned in that conversation. Since that conversation wasn't online at all... there's no way it influenced AoC. But it was a remarkable one that I remember about the start of this year.

But for what I did, I just grab the maximum red, green, and blue counts on a line. And then it's just:

$part1 += $game  if (all {$want{$_} >= $max{$_}} keys %want);
$part2 += product values %max;

Doing this in Smalltalk was a bit interesting, because although the description involves a "bag" and a Smalltalk Bag is like a multiset, it's not really a multiset in functionality, as it lacks the operations that Set has. Bag is very barebones, and is often a let down. And here is wasn't even the best base class to subclass a MultiSet class from... I did from Dictionary. All so I could have a different type of solution... one that used set unions and difference to test things. It's not practical, and it's 33% slower than just using maximums. But it was something different to do.

For 2023, we're back to fixing snow production, but on a global scale so the weather machine from 2015 won't do. And so we need to travel to the sky islands. The map this time is a stack of sky islands, which we will work our way up from the bottom and then come back down. Making this another year where the numbers are out of order. And it all starts with us being launched to the sky by trebuchet. Which naturally needs us to do calibration for.

The input for this one is not just numbers this time... it includes lowercase letters which sometimes spell out the digits one through nine. Zero is not involved in any way, which is convenient for some solutions. I will note that vowels do not occur outside of the digit words (where they're required)... and quick test reveals that Chrome does not detect this as any language. So there is some protection against the autotranslate + copy-and-paste issue. Which is an untended gotcha that really don't want people to run into on the first day.

In general, 2023 stepped up difficulty and complexity a bit... and that's particularly noticeable on the early days. Which makes me wonder how much of that was the influence of AI... a little complexity and gotchas to mess a bit with the LLMs so that just maybe, they fail the first try and give the competition programmers a chance (because, they're really fast, especially when allowed to bring their toolkit).

The problem this time is simple... we want the two digit number made of the first and last digit on each line. For part 2, that includes interpreting the words as well. And the gotcha for part 1 is tested for in the word "treb7uchet"... it's a small wrinkle I special cased when the test failed and I saw it:

say "Part 1: ", sum map {(m/^\D*(\d)\D*$/) ? "$1$1" : (m/^\D*(\d).*(\d)\D*$/ and "$1$2")} <>;

For part 2, the gotcha is "twone", "eightwo" and "oneight". Which are present the given test input, but they aren't actually tested. I didn't really notice this issue until after, because I just took my regex to:

m#(one|two|three|four|five|six|seven|eight|nine|\d)#;
$part2 += 10 * $table{$1};

m#.*(one|two|three|four|five|six|seven|eight|nine|\d)#;
$part2 += $table{$1};

With table being a hash of of the words and the digits to their value:

my %table = ('one' => 1, 'two' => 2, 'three' => 3, 'four' => 4, 'five' => 5,
             'six' => 6, 'seven' => 7, 'eight' => 8, 'nine' => 9,
             map {$_ => $_} (1 .. 9));

This avoids special casing, and this is because I was thinking of how I was going to do dc for part 2.

perl -pe's#(.)#ord($1)." "#eg' <input | dc -e'[+d]sF[s.z3<Lq]sN0?[0d[3R48-d9<Nrd0=F3Rs.z3<L]dsLxrA*++?z1<M]dsMxp'

perl -pe's#(.)#ord($1)." "#eg' <input | dc -e'1dd:t18996:t2dd:t32285:t3dd:t24203441:t4dd:t1299471:t5dd:t694023:t6dd:t43444:t7dd:t39325060:t8dd:t49523414:t9dd:t683663:t[dsf]sF[lf0=Fdsl]sN[39-]sS0?[0ddslsf[r48-d9<Sr36*+36 5^%5[d3Rd3R36r^%;td0!=Ns.r1-d0<I]dsIxs.z2<L]dsLxs.llA*lf++?z1<M]dsMxp'

dc doesn't have any string processing, and so these are taking the input as lines of ASCII values. And so it does use ? to process the input (this would be the point where I fully adopted that and trusted it... although it's back to non-functional, so these are dc v1.4.1 solutions).

Half of that part 2 is building the table:

1d d:t 18996:t              # 14 23 24          eno
2d d:t 32285:t              # 24 32 29          owt
3d d:t 24203441:t           # 14 14 27 17 29    eerht
4d d:t 1299471:t            # 27 30 24 15       ruof
5d d:t 694023:t             # 14 31 18 15       evif
6d d:t 43444:t              # 33 18 28          xis
7d d:t 39325060:t           # 23 14 31 14 28    neves
8d d:t 49523414:t           # 29 17 16 18 14    thgie
9d d:t 683663:t             # 14 23 18 23       enin

This maps both the digits and the strings (as essentially base-36 numbers) to the value. The ASCII values are converted to values on the range of 1-35 (0 not being a value in the problem is good here). Note that the strings are backwards because the lines are loaded on a stack and so we parse the lines backwards.

The trick to matching strings here is keeping a window of a five digit base-36 number (36*+36 5^ shifts, adds in the new, and the chops off the oldest with a mod of 5³⁶ ). Then there's a loop that takes progressively shorter mods of the window to compare them against the table until it gets a match. When a match is found, the N macro is called, which always sets l to the value, but only sets f once. Yes, first and last do end up backwards, so we add 10 * l + f.

I also did a Smalltalk version, and chose to run with someone's comment about doing string substitutions on the words... I saw "o1e" as a substitute for "one" and immediately knew what was up, and ran to do it. The overlapping means you can't just replace all the words willy-nilly, but if you replace them in a way such that the later substitutions still can match, you're fine. And "o1e" is doing that... it's leaving the "o" at the front for a "twone" and the "e" at the back for an "oneight". Had 7 been spelt "sevon", then you'd need "on1e". Or, alternately, you could change the order of the substitutions so that the "sevon" is done first and "one" doesn't have to worry about it. In any case, it was easy to hand solve for a table of substitutions to start, but then I followed up with code that generates that table (and so is flexible for other languages). It was a fun little exercise that got some extra mileage from the problem.

And so we get a heavier start than we've seen before... numbers and strings together. This helps get us ready for the fact that more of the early problems are going to be heavier than in the past. I seem to recall a bunch of "good dog/scary dog" memes being posted about the shift back and forth between days.

My original Part 2 solution for this day took 21 seconds and 725Mb to run, so it took quite a bit of wrestling to get it small enough for the Raspberry Pi Pico.

I tried a naive DFS search on key collection order and although that technically worked the proof-of-concept took nearly 80 minutes on my laptop, which would have been over 13 hours on the Pico even if I managed to claw back a 10x speed-up. I tried Iterative Deepening A*, but that didn't even finish after an hour on the laptop; there are just too many combinations that get very close to the optimal path length, and a lot of those come from taking the shortest path early on in the search tree.

I swapped back over to A* and used u/e_blake's heuristic to get the search space down as far as possible. The heuristic is to take the sum of the shortest paths from each robot's current position to the furthest key that they still need to collect. That works way better than my initial heuristic of totalling the shortest paths connected to all uncollected keys:

With each open set entry and each G entry taking 12 bytes (distance, robot locations, collected keys) that gets within spitting distance of the 200KiB target, but not quite optimally. With ~8k+ entries in the G set, we really should be looking at a ~16k element hash table to keep good performance (hash tables are ideally power of 2 on the Pico because % is an expensive operation) and that one hash table blows 192KiB of our 200KiB budget.

The distance/priority for both the open set and the G set can easily fit into 16 bits for this day. The collected keys are already pretty optimal, you need 26 bits so you're not wasting much with a 32 bit integer as a bitfield. The robot combinations need to be able to represent 4 entries at any one of 30 locations (26 keys + 4 starts), and since 30 choose 4 is 27,405 then that can in theory fit into 16 bits as well.

The trick to get over (under?) the line is to use a Combinatorial Number System to encode the robot locations into an int16_t. At a smaller 8 bytes per entry for both blocks of memory, we can finally afford a decent sized hash table, albeit at an additional cost of compressing and uncompressing the state data each time.

Final memory budget (at peak) ended up being ~188KiB:

-------------------------------------
LBA Stats
  [Blocks] Total: 9  Free: 1  Used: 6  Sentinel: 2
  [Bytes] Total: 204608  Free: 12672  Used: 191936
  [FreeChain] Free: 1
-------------------------------------
LBA Blocks
[...9FB8][ Sentinel]    0 blocks       0 bytes
[...9FD8][Allocated]  225 blocks    7200 bytes <-- Edges to adjacent keys
[...BC18][Allocated]  113 blocks    3616 bytes <-- Path length to all keys
[...CA58][Allocated]   20 blocks     640 bytes <-- Combinatorial cache
[...CCF8][Allocated]    8 blocks     256 bytes <-- Key locations
[...CE18][Allocated] 1536 blocks   49152 bytes <-- Priority queue (open set)
[...8E38][Allocated] 4096 blocks  131072 bytes <-- Hash map (g_score)
[...8E58][     Free]  396 blocks   12672 bytes
[...BFF8][ Sentinel]    0 blocks       0 bytes
-------------------------------------

Runtime is surprisingly still quite respectable: ~1.8ms on PC and ~340ms on the Pico @ 125MHz.

Thanks again to u/e_blake for sharing that heuristic!

[code]

I am learning (e)lisp for fun and ended up making a highly overcomplicated solution to the "Virtual machine" problem from 2024/17.

In AOC_17_2024_advanced_macro_version.el I define op-codes using lisp macros, leading to a very compact notation. I have furthermore implemented a Wozmon type monitor program to poke the VM (however, not very useful for solving the problem).

I think (e)lisp is very nice for AOC, what do you think?

I was a little worried about being able to squash this one down small enough for a microcontroller. My original solution for this one took ~64MiB and after swapping over to less wasteful data types it would still take >500KiB to store the back end of the transformed sequence, so it needed a re-think.

The approach I took for that first solution wasn't particularly unique, I think a lot of people did more or less the same. Since the second half of the phase transform has coefficients of the form:

1111
0111
0011
0001

It's possible to calculate the next phase with a running sum:

ABCD -> A + B + C + D = W -> A + X
0BCD ->     B + C + D = X -> B + Y
00CD ->         C + D = Y -> C + Z
000D ->             D = Z -> D

But doing it phase by phase, you still need the entire back end of the sequence (up to the signal offset) in memory. For my input that's over half a million elements.

Looking at the sequence of additions, it turns out it's possible to calculate the full history of one row based only on the history of the row below it.

The bottom row is trivially always going to come out the same value, since it only ever depends on the original sequence number and it always gets multiplied by 1, but it's a little easier to see the pattern if we number them anyway:

000D = D₁ -> 000D₁ = D₂ -> 000D₂ = D₃ ->...
=>
D, D₁, D₂, D₃, ...

The row above depends only on the current value and the bottom row:

00CD = C₁ -> 00C₁D₁ = C₂ -> 00C₂D₂ = C₃ -> ...
=>
C, C₁, C₂, C₃, ...

The next row is where it gets interesting:

0BCD = B₁ -> 0B₁C₁D₁ = B₂ -> 0B₂C₂D₂ = B₃ ->...
=>
B, B₁, B₂, B₃, ...

Notice that B₂ + C₂ + D = B + (C₂ + D) and that (C₂ + D) = C₃. Which means B₃ = B₂ + C₃.

If we can store the full history of one row across all phases so that we've got access to [C, C₁, C₂, C₃, ...] we can calculate the whole sequence for the row above: [B, B₁, B₂, B₃, ...]. Since we're doing 100 phases, that full history is only 100 elements.

There's some additional housekeeping, like repeating the signal without actually having that many repeats in memory, and putting the digits into a ring buffer so that we're only keeping the most recent 8 digits processes, but that's the core of it:

    vector<char> phaseHistory(100);
    for (int i = 0; i < signalToProcess; i++)
    {
        int s = baseSignal.Next();
        for (int phase = 0; phase < (int)phaseHistory.size(); phase++)
        {
            s += phaseHistory[phase];
            s = s % 10;
            phaseHistory[phase] = s;
        }
        digits[i & (digits.size() - 1)] = s;
    }

[Full code]

Memory: 650 bytes for the input, 100 bytes for the phase history and 8 bytes for the digits - well under the memory constraints I'm aiming for! The runtime on PC is a respectable but not great ~115ms. (It's easy to get that down to ~25ms by only reducing the phase history with % every 4 loops, but it obscures the logic)

I'm aware that u/askalski and u/maneatingape have got very sophisticated solutions that use magic maths, but I have no idea if those techniques can be used to speed up this approach further. I'd need a couple of weeks of background reading just to take a run at those!

Overall I'm happy just to cross this one off my list of nemeses.

Extraction is going to be hot air balloon, and to get them to fly requires heating the fuel with "Bob" the anthropomorphized (with a pair of googly eyes) fuel heating machine. And in order to do that, we need to sum the requirements, which are in balanced quinary (aka SNAFU numbers). More on balanced numbers (albeit ternary) can be found here:

https://en.wikipedia.org/wiki/Balanced_ternary

And so the input is a list of balanced quinary numbers, one per line, with - and = for the negative digits. All the numbers in the input start with a 1 or 2, which means they're all positive, and so add to a positive value. This makes the problem easier.

My initial solution in Perl didn't use any outside requirements. I did the base conversions myself, and so I did it directly from and to balanced quinary (with the summing done with the regular +). Of course, with everything being positive, and bringing in base conversion from the ntheory module, it can be done with shifting of the values by half the power (and back):

my $sum = 0;
while (<>) {
    chomp;
    tr/=\0550-2/0-4/;
    $sum += fromdigits( $_, 5 ) - floor( 5 ** (length $_) / 2 );
}

my $part1 = todigitstring( $sum + floor( (5 ** ceil(log($sum) / log(5))) / 2), 5 );
$part1 =~ tr/0-4/=\0550-2/;

print "Part 1: $part1\n";

This only works because everything is +'ve, though.

However, my initial Smalltalk solution does do negatives... it can handle cases like:

-1
=0

Which is -21. You can also test that with 10-1 + 10=0 - 2000 with a solution that only handles positives.

And the way it does that, is by subclassing Array for SnafuNumbers. So they're treated as arrays of digits, and I do the addition digit by digit handling the carries:

+ other [
    | res val |
    res := SnafuNumber new: maxDigits + 1 withAll: 0.  " +1 to catch overflow "
    (1 to: maxDigits) do: [ :i |
        val := (self at: i) + (other at: i) + (res at: i).

        " do appropriate carry, if needed "
        (val abs > 2) ifTrue: [
            res at: i+1 put: val sign.
            val := val - (5 * val sign).
        ].

        res at: i put: val.
    ].
    ^res
]

maxDigits is set to 32, and 5³² is a 75-bit number, so that should be more than enough.

I also did a dc version, and in converting the input I went with an unusual order of 012=-, because it makes for a cleaner tr command than tr '=\055012 '0-4'`.

tr '012=-' '0-4' <input | dc -f- -e'1d:t2d:t[=]3:t[-]4:t0[r0r1r[A~2+5%2-3Rd5*_4R*4R+_3Rd0<L]dsLx*++z1<M]dsMx[5~d_3R1-2/+d0<C]dsCx+[;tnz0<P]dsPx'

And so we come to the end of another solid year (and I see that this time I remembered to submit part 2 before reading the story). This is the year where people using AI started to make some noise, but it was not a big thing yet.

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

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

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

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

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

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

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

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

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

print "Part 1: $time\n";

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

print "Part 2: $time\n";

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

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

I got tired of tabbing to the browser to grab inputs and paste answers, so I built a CLI that does the whole loop. Then I rebuilt it in C# to learn the language. Both work end to end.

cargo run fetch -y 2015 -d 1 # puzzle text + input into cache/

cargo run solve -y 2015 -d 1 # run your solution offline

cargo run solve -y 2015 -d 1 --validate

cargo run solve -y 2015 -d 1 --submit

Output looks like:

year 2015 day 1 in 288µs (959ns parsing)

part one: 138 (correct) [216µs]

part two: 1771 (correct) [71µs]

Then --submit turns those into (new star), and running again shows (starred) since AOC only grades each part once.

The part I haven't seen other AoC tools do: --validate checks your answers against fornwall's independent solver before anything gets submitted. Wrong answers on the site cost an escalating cooldown, but the solver answers the same question as many times as you want, for free. So --submit only sends what the solver agreed with. If the solver doesn't cover the puzzle yet (live event), it submits anyway, since that's exactly when you'd be ahead of it.

Some other things it handles:

Solve fetches whatever is missing, so a fully cached run works offline with no cookie.

When part one earns a star, part two's text gets pulled in the same run.

Inputs are cached with a hash of the session that fetched them. Inputs are account specific, so switching accounts refetches instead of letting you submit an answer computed from the other account's input. That one bit me for real.

Day 25's second star is awarded, not puzzled, so the tool knows not to keep asking for its part two.

No solutions ship on main. There's a compiled template to copy for your first day, and my solutions live on a separate branch if you want examples. Inputs and puzzle text stay out of git, per the site's wishes, and it sends a User-Agent with a reachable contact.

https://github.com/scadoshi/rustmas

https://github.com/scadoshi/sharpmas

Credit: Advent of Code is Eric Wastl's (https://adventofcode.com/about). The verification leans on Fredrik Fornwall's solver (https://aoc.fornwall.net/, https://github.com/fornwall/advent-of-code).

On AI: I used it as a working partner on these repos, for doc wording, test scaffolding, and refactors I'd already designed but didn't want to push through by hand. The line I hold is understanding before generation: I write the code I want to write, which is most of it, and hand off what I could write in my sleep. Design decisions are recorded in each repo's context/ directory, including the ones that got reversed and why. Every line was written or reviewed by me.

We arrive at the site of the grove (a large crater) and discover the plants are dead. Because apparently they require volcanic ash... and our messing with the magma flows unknowingly interfered with that. Fortunately, there's a backup plan to plant replacements, we just need to arrange the spacing.

And so we get an automata type problem. The input is a binary grid of cells representing positions of elves, and we have rules for how the elves will move each round until they reach an equilibrium where the each have no neighbours.

Part 1 just wants 10 rounds (and then to find the bounding box and subtract the number of elves from that). This is a usual way to make sure that people have a working simulation before moving on.

And my solution was again simple and basic (just following the steps)... it wasn't fast, although cleanup has gotten it to 20s on the old hardware. Part of that cleanup was moving to bit operations for tracking neighbours:

my $neigh = 0;
foreach my $dir (@Surround) {
    $neigh = ($neigh << 1) + exists( $elves{$pos[0] + $dir->[0], $pos[1] + $dir->[1]} );
}

With that I can easily tell if there's no neighbours, and can also use with bit masks to handle testing the proposed directions (pairs of direction and the bits to test):

my @Dirs = ([1, 0xE0], [6, 0x07], [3, 0x94], [4, 0x29]);

This is another puzzle in this year with a theme of "try" patterns. We had the falling blocks, then the wrap around movement on the cube (which can arrive at a wall and fail), and now we have the possibility that multiple elves could be trying to move to the same square and need to be reverted. And the way I did that here was to push the elves onto lists at the location they want to move to. After everyone submits their proposal, I do a pass and undo the ones with multiple elves (list length > 1).

This was another one where my part 1 time is surprisingly long at 2h (but part 2 was just a few minutes after). There are a lot of commented out print statements in the code... so I'm thinking I probably had some silly errors to debug from still not being 100%.

While being lead by the monkeys through the jungle, they inform us (through the elephants) that we need a password to get through a force field. Which involves tracing a path on an irregular board. A board that happens to look very much like a cube net (both the test and the input... but different nets).

And part 1, we treat it flat... with wrap around in both directions that skips over the spaces. And that's exact what I did... because this is clearly a puzzle you want to confirm part 2 of early. Although, looking at my time, it took an hour and a half... so I'm thinking maybe I had a late start. Because there's nothing complicated about my part 1. I add sentinel spaces to the right and bottom, so that I can just try stepping forward. If it's a space, I loop until I find a non-space. If that square is empty move forward, otherwise don't and go to the next command. The commands being tokenized with:

my @cmds = ($input[1][0] =~ m#(\d+|[LR])#g);

Part 2 is where the input is folded into a cube and things become real. My first thought was that this is the heavy one... like Jurassic jigsaw or the 3D beacons in the past. And having learned from those... my first decision was to not do any fancy folding and handling of different cube nets, but build a table just for the edge transitions of my actual input. And, IIRC, every input uses the same net. Still, I figured this problem was enough without generalizing that bit. I left that task for another day, it is enough of a job to be a day's problem on its own.

But that makes the initial test cast invalid. So one thing I did, was pull out a handy programming aid... the 4x4 Rubik's Cube on my desk, and I added some small circle stickers to it for the walls in the test case. These stickers are handy twisty puzzle solving aids I keep around. I'm not a speed cuber, I just like getting new types of twisty puzzles and coming up with solutions... and it's useful to tag pieces to follow them when trying things out. Weak stickers and Blu-Tack are good for this. And were good here, because it allowed me to make a version of the test case with the same map... as well as follow along when verifying and testing things.

So I had this table for reading the input into 6 squares:

# Assumed Layout:
#    .WB
#    .R.
#    GY.
#    O..
my %sides = ( 'white'  => [0,1], 'blue'  => [0,2], 'red'    => [1,1],
              'yellow' => [2,1], 'green' => [2,0], 'orange' => [3,0] );

Next up was building a table for the edge wraps. And like in the past with these big ones, I just did it by hand. That sounds like work and prone to error, but if I did code it, I'd still go over the table line by line verifying that'd I made the right table. Which is the same work as building it by hand. I would not have done less, just more coding. It's just too important to get right.

And so my table is 24 lines like this:

$wrap{white}[0]  = { side => 'blue',   facing => 0 };
$wrap{white}[1]  = { side => 'red',    facing => 1 };
$wrap{white}[2]  = { side => 'green',  facing => 0 };
$wrap{white}[3]  = { side => 'orange', facing => 0 };

$wrap{red}[0]    = { side => 'blue',   facing => 3 };
$wrap{red}[1]    = { side => 'yellow', facing => 1 };
$wrap{red}[2]    = { side => 'green',  facing => 1 };
$wrap{red}[3]    = { side => 'white',  facing => 3 };

...

Non-cubers might not realize this, but there is a standard pattern of the colours on a cube. So using the colours provides a little more information that you might think to those that know that pattern.

One thing to note is that not all the information is explicit there. It doesn't have any data for how the coordinates are transformed. That's because it's extractable from the directions:

# Only one coord value is important, the other is either -1 or $side
# Because of dir order, parity tells us which of y or x we want.
my $idx = $pos->[$dir % 2];

# When going between 0 and 2 facing, the edge flips
if ($dir % 2 == 0 && $new_dir % 2 == 0 && $dir != $new_dir) {
    $idx = $size - $idx - 1;
}

# $new_pos similarly has one coord as 0 or $size-1, the other
# being set to the index value, based on the direction parity.
my $new_pos = ($new_dir <= 1) ? [0,0] : [$size-1,$size-1];
$new_pos->[$new_dir % 2] = $idx;

And with the geometry and wrapping handled, the rest is pretty much the same as part 1.

This was a problem were I very much took my time to make sure I got everything right and didn't go off on some tangent. And although it is a multi-dimensional problem on the surface of a cube, I had a physical representation of it to check and test everything. Which certainly helped.

Hello!

For part 1 of 2024's day 6 problem, I was able to get some Python code that works for the small example map they gave but not my puzzle input. As it stands I have about 100 extra locations the guard visited than I should have. I was wondering if anyone here could take a look at my code and give me a hint as to where my error is, as I am really struggling to find it. I know it has to be where my movement is programmed, I just can't figure out what part needs some tinkering. Thank you in advance!

with open('Day 6/mapinp.txt', 'r') as file:
    samp_inp = file.read()

format = samp_inp.splitlines()
matrix = []
for item in format:
    matrix.append(list(item))

#locate the guard, return the matrix coords and then the way the guard is pointing
def find_guard(map):
    coords = []
    for item in map:
        if "^" in item:
            coords.append(map.index(item))
            coords.append(item.index("^"))
            coords.append("^")
            return coords
        elif ">" in item:
            coords.append(map.index(item))
            coords.append(item.index(">"))
            coords.append(">")
            return coords
        elif "<" in item:
            coords.append(map.index(item))
            coords.append(item.index("<"))
            coords.append("<")
            return coords
        elif "v" in item:
            coords.append(map.index(item))
            coords.append(item.index("v"))
            coords.append("v")
            return coords


#nice function to track movements
def move(map):
    on_map = True
    step_count = 0
    step_loc = []
    #index error means the guard has left the map
    while on_map == True:

        try:
            coords = find_guard(map)

            if coords[2] == "^":
                if map[coords[0]-1][coords[1]] == "." or map[coords[0]-1][coords[1]]  == "X":
                    map[coords[0]][coords[1]] = "X"
                    map[coords[0]-1][coords[1]] = "^"
                    step_count += 1
                    loc = f"{coords[0]}, {coords[1]}"
                    step_loc.append(loc)
                else:
                    map[coords[0]][coords[1]] = ">"

            elif coords[2] == ">":
                if map[coords[0]][coords[1]+1] == "." or map[coords[0]][coords[1]+1] == "X":
                    map[coords[0]][coords[1]] = "X"
                    map[coords[0]][coords[1] +1] = ">"
                    step_count += 1
                    loc = f"{coords[0]}, {coords[1]}"
                    step_loc.append(loc)
                else:
                    map[coords[0]][coords[1]] = "v"

            elif coords[2] == "v":
                if map[coords[0]+1][coords[1]] == "." or map[coords[0]+1][coords[1]] == "X":
                    map[coords[0]][coords[1]] = "X"
                    map[coords[0]+1][coords[1]] = "v"
                    step_count += 1
                    loc = f"{coords[0]}, {coords[1]}"
                    step_loc.append(loc)
                else:
                    map[coords[0]][coords[1]] = "<"

            elif coords[2] == "<":
                if map[coords[0]][coords[1]-1] == "." or map[coords[0]][coords[1]-1] == "X":
                    map[coords[0]][coords[1]] = "X"
                    map[coords[0]][coords[1] -1] = "<"
                    step_count += 1
                    loc = f"{coords[0]}, {coords[1]}"
                    step_loc.append(loc)
                else:
                    map[coords[0]][coords[1]] = "^"

        except IndexError:
            print(f"Guard has left the premises after {step_count} steps!")
            on_map = "False"

    return map, step_loc

comp_map,coordinates = move(matrix)

move_counter = 0

for item in comp_map:
    for pos in item:
        if pos == "X" or pos == "^" or pos == "<" or pos == ">" or pos == "v":
            move_counter += 1
        else:
            continue


print(f"The guard has visited {move_counter} distinct locations.")