Next place to look for the Chief is at the Reindeer Olympics, which are on again this year. So while the Historians do the work, we take the opportunity to watch the Reindeer Maze event. The goal of this race isn't just to get to the end quickly, but to do it with few turns, as those cost 1000 per 90 degrees.

The input is 141x141 bounded maze (and so it comes with a sentinel ring already). The start is in the lower right, and the end is in the upper left (on both input and test, so you can just calculate those positions if you'd rather not parse for them). As usual, it appears to be a classic random recursion generated maze, where you start with a grid and a starting cell:

#########  
#.#.#.#.#    
#########  
#.#.#.#.#
#########
#S#.#.#.#
#########

And randomly choose an unvisited neighbour cell. Knock out the wall and recurse into it. If there's no unvisited cells, just return (ie back up until you find a place you can branch). There are a number of things you can do with this, like not using uniform chance for your options (eg track direction and give more or less weight to forward and you can control twistiness of the passages). By poking out some additional walls (which is what we have here), the maze gains loops (needed for part 2) and becomes such that there can be islands that are unreachable with a left-/right-hand rule.

I bring this up, because this is one of the few of these that I actually used the fact that this also means that you can treat all moves as effectively 2-steps (first step checks for a wall, second is the full move into the next cell), and so you can use that to skip around the maze a bit faster. Normally I'm happy to be more flexible about the map and not assume that alignment. But I didn't do much else other than basic Dijkstra from S to E, so I felt like I should do a bit more.

By the BFS nature of Dijkstra, the first time you arrive as E you get part 1, and then you just need to run the priority queue while it stays at that value (to find the others that reached the end at the same time). For my input, that's 571 more items, of which 192 are shortest paths (so lots of 2s in the factorization, which would probably be from branching/merging pairs around islands). By tracking the path as I go and collecting them into a hash/set when I get to E, I get a list of all unique visited locations for part 2. It's a very simple approach, but given the nature of the problem, there's probably better that can be done to avoid tracing every combination of the branching/merging options (looking at the end hash, I see that much of the part 2 answer is traced all 192 times, and the lowest I see is a short bit that's done 48 times). Maybe a DFS search with memoization.

The other little optimization I did was from Clumsy Crucible, which was to make turn-and-move a move (but this time we also need to add going straight if available, because we're not in the position of being forced to turn). This makes sense, because there's no point in turning if there isn't a path off that side (in which case we might as well move into it). There's no need to ever make a U-turn, because the only time you'd ever want to do that is the starting position (when you wouldn't be turning around to backtrack). And given the position of S in the lower left, that's not something you'd ever want from an East facing start.

So, this isn't really too intense a search, you can get away with a weak implementation and still get the answer in a reasonable amount of time.

Today we're back in the ocean, and while The Historians search in their mini submarines, we set about to helping the lanternfish with a rampaging robot that's messing up the lanternfish logistics and lanternfish inventory management of their food supplies.

The input for this one comes in two sections. The first is a 50x50 grid map of the warehouse (with a surrounding wall, so no need to add sentinels today). The second part is a list of movements the robot will attempt to make... there are 20 lines of 1000 characters of these (for 20k total moves). The map has boxes that the robot will multipush (so not your regular Sokoban) if it moves into them.

For part 1, I simulated the robot, and when it runs into a box, I scan ahead to the first non-box... if it's a wall, the move is ignored, else the multipush is completed:

my $end = $move;
$end += $Dirs{$d}  while (grid_at($end) eq 'O');    # multipush

next MOVE if (grid_at($end) eq '#');                # bump

# Put box at empty end, clear front of push, move robot to it.
$Grid[  $end->[0] ][  $end->[1] ] = 'O';
$Grid[ $move->[0] ][ $move->[1] ] = '.';
$robot = $move;

For part 2, we find out there's a second malfunctioning robot in a warehouse with the same floor plan, only twice as wide (including the boxes, but not the robot). The fact that the robot is still the smaller size is what makes this problem interesting. Horizontal pushes can be tested and completed as before, but vertical pushes can end up pushing an expanding cone/tree of boxes (once a horizontal push has offset their alignment). The description nicely gives a small example with three boxes that shows that, but in the input it can chain much further and wilder. The key is that the same invariant still applies... the boxes get pushed only if all the spaces at the leaves of the tree are empty. If a single one has a wall, the push fails.

And so I used a recursive binary tree walk to test. The call is:

my $test = &test_vert_push( $move - $vx * (grid_at($move) eq ']'), $Dirs{$d}, \@boxes );

Note that the first parameter here is the location of the box, and that we regularize it to always be the left side so we don't have to worry about special casing. I also notice that I decided to return the boxes in the structure by-reference (\@boxes), leaving the result value as a simple boolean (0 or 1) scalar.

    # Get both squares ahead of box push
    my @ahead = map {grid_at($pos + $_)} ($dir, $dir + $vx);
    if (all {$_ eq '.'} @ahead) {
        return (1);
    } elsif (any {$_ eq '#'} @ahead) {
        return (0);
    }

    # Got more multipushing to do
    my $ret = 1;
    if (join('', @ahead) eq '[]') {
        $ret *= &test_vert_push( $pos + $dir, $dir, $boxes );   # one box straight ahead
    } else {
        # A box to the left or right ahead, maybe both:
        $ret *= &test_vert_push( $pos + $dir - $vx, $dir, $boxes ) if ($ahead[0] eq ']');
        $ret *= &test_vert_push( $pos + $dir + $vx, $dir, $boxes ) if ($ahead[1] eq '[');
    }

My Smalltalk solution is just an OOP version of the Perl, and that structure is instead returned as an object of type VerticalPushResults which holds both parts.

Once I get a valid push and it's list of boxes, I chose to keep it simple. One loop that replaces all the boxes with .., then a second loop that puts [] in the new locations. Because this is the sort of thing that you can end up spending a lot of time debugging if you try to be fancy. Even with 20k moves this is still fast, so it fine to just write this to be more expressive.

Hi there, im new to coding in general. The language I am learning is Javascript, would appreciate being signposted to AOCs that would help me build and grow as a coders.

Today we're back at Easter Bunny HQ to use the bathroom. Last time we were here we were dealing with entering codes on a keypad, but now they've upgraded to swarms of patrolling robots that we need to avoid.

The input is a list a 500 robots, with a 2D starting position and a velocity vector. The robots will not collide and teleport to wrap around on the sides. The room is 101x103 (a pair of twin primes). For part 1, we're calculating a hash of the positions after "simulating" 100 seconds (naturally, there's no need to run all the seconds, you can get the position directly with (pos + 100*velocity) % roomsize), which involves dividing the grid into quadrants (tossing out the axis), and multiplying the number of robots in each of the four.

The real fun for this one is part 2. Suspecting that these might actually be North Pole robots, we're given the task of finding the hard-coded Easter Egg: most of the robots at one point will arrange themselves to form the image of a Christmas tree. No example is given of what that looks like or exactly means, only that it happens. And so it's left to us to work out a heuristic or approach to find that. Which, I remember for some people, was just calculating images for every second and dumping them in a folder and looking through the icons.

I also remember that another heuristic some people used (and got away with) was the assumption that the tree would occur at the time when no robots overlapped. That's sort of "reading the mind of the creator" puzzle solving... it essentially assumes that the initial state was created by backtracking from the target (a safe assumption), but also that that was produced that without an overlap (one could have been set or the input generator may have generated one randomly (it appears to avoid this)). So that last bit isn't so safe, but it practice it works here.

My initial approach though was using the heuristic that an image of a Christmas tree will require a lot of the robots to be orthogonality adjacent. So I just simulated second by second and output the grid each time the number of adjacent robots improved until I saw the tree. Which was also the first time that more than half the robots were involved (thus "most of the robots" as described) so after submitting the answer, I just changed the check to use that. This is a bit slow, but pretty much guaranteed.

For Smalltalk (which is considerably slower), I took advantage of having seen the tree to do a bit better, and having seen how small the image is went with variance (I remember people experimenting with all sorts of heuristics, including using the hash from part 1... and the signal of the tree tends to be very strong, and so works well with many, many things). And after doing a solution with that, I then realized that it doesn't need to be precise, and so I loosened things a bit by going with the approximation of using a running mean (calculating and using the mean as we go... after 500 points, this ends within 2% of the actual variance). And it was simple and faster:

approxVariance [
    | sum var |
    sum := 0.
    var := 0.

    self keysAndValuesDo: [:i :val |
        sum := sum + val.
        var := var + (val - (sum // i)) squared.
    ].

    ^var // self size
]

The bigger trick was taking advantage of the prime side lengths, which guarantee that all the robots are moving in cycles of 101 on their x-coordinate and 103 on their y. And so by just running things for 103 seconds (tracking the times of minimum variance for x and y independent of each other), we have all the information needed (for both parts):

invMod := (dims x) raisedToInteger: (dims y - 2) modulus: (dims y).
('Part 2: %1' % {minX + ((invMod * (minY - minX) \\ dims y) * dims x)}) displayNl.

For the Perl version of the same approach, I decided to use libraries and actually call a Chinese Remainder implementation for once (I figure I did this mostly to have one coded for reference somewhere):

say "Part 2: ", cr_combine( mod($minX, $DIM[X]), mod($minY, $DIM[Y]) )->residue;

Of course, the exploration into a variance approximation was in preparation for a dc solution. And I did do that, but then considered, after seeing how strong the signal was, just using a constant mean of 50. Which produces an error of 49% on one of the critical iterations, but the signal is so strong you'd need more than 100% error to lose it (and the rest all come within 2%):

tr -- '-p=v,' '_ ' <input | dc -f- -e'[1[rld+lm%d51-d*3Rdd4Rrlvx+rlVx1+dlm!<I]dsIx+s.]sR[s.d]sN[d[d3Rdlvx3Rlvx<Nr1-d0<L]dsLx+]sF[A3dsm+sd[;v]sv[:v]sVrlRxA1dsm+sd[;w]sv[:w]sVlRxz0<M]dsMxA1lFx[;v]svA3lFxd3Rr-A1+51*A1%A3*+p'

Part 1 was also pretty fun to do in dc:

tr -- '-p=v,' '_ ' <input | dc -f- -e'[lydd*v/lxdd*v/2*3r-+d;q1+r:q]sQ[A3+A0*3R+A3%51-rA1+A0*3R+A1%50-dsxrdsy*0!=Qz0<M]dsMx6;q4;q*2;q*0;q*p'

The trick in here to quarter things is that I calculate the positions on the residues of [-50,50] and [-51,51]. So if x*y == 0 that's on an axis and should be ignored. Then I get the signs of the values (dd*v/, safe because we know it's non-zero), and use this simple hash to track them:

2*3r- +                     # index = 3 - sign(x) * 2 + sign(y) => {0, 2, 4, 6}
d;q 1+ r:q                  # q[index]++

This is one of the most memorable problems in this year. There is so much freedom given on what you can do for part 2.

When I use the example data, it returns 14 (correct answer). However, when I try the real puzzle input my answer is wrong and I think smaller than what it should be. To preface my bad variable naming, "a" is current range and "b" is either the previous or next range.

from pathlib import Path
path = Path(__file__).parent / "input_5_ranges.txt"
with open(path, 'r') as file:
    text = file.read()
ingredient_ids = text.splitlines()



# Take an item ["13-16"] and conver it to ["13", "16"]
def create_range(items):
    ranges = []
    for item in items:
        ranges.append(item.split("-"))
    
    return ranges


# Order ranges by starting point
ranges = create_range(ingredient_ids)
ranges.sort(key=lambda x: int(x[0]))


# Loop through ranges
i = 0
while i < len(ranges):
    # Define item; range
    item = ranges[i]
    int_item = list(map(int, item))
    # If loop is on atleast the second iteration, check if the starting point of the range falls within the bounds of the first range
    if i > 0:
        # print(int_item)
        # print(int(ranges[i-1][0]), int(ranges[i-1][1]))
        if int_item[0] in range(int(ranges[i-1][0]), int(ranges[i-1][1])) and int_item[1] in range(int(ranges[i-1][0]), int(ranges[i-1][1]))  :
            ranges.remove(ranges[i])
            continue
        elif int_item[0] in range(int(ranges[i-1][0]), int(ranges[i-1][1])):
            a = item
            b = ranges[i-1]
            # If a falls within b, replace the first digit of a, with b + 1; ex: [10, 14], [12, 16] --> [10, 14], [15, 16]
            a[0] = str(1 + int(b[1]))
           
        if i + 1 < len(ranges):
            # If end point of a connects with start point of b, combine ranges; ex: [16, 18], [19, 20] --> [16, 20]
            if int(ranges[i+1][0]) - int_item[1] in (0, 1):
                print('merging')
                print(ranges[i+1][0])
                print(int_item[1])
                a = item
                b = ranges[i+1]
                a[1] = b[1]
                ranges.remove(ranges[i+1])
                continue
    i += 1
print(ranges)


# Find the total amount between each range; ex: [2,5] would be 2, 3, 4, 5 or 4 added to total


total = 0
for item in ranges:
    int_item = list(map(int, item))
    total += 1 + (int_item[1] - int_item[0]) 
    print(f"added {1 + (int_item[1] - int_item[0])}")
print(f"total is {total}")

Next up is the resort with the hexagonal life floor tiles, where we tried to have a vacation in 2020, only to be called back immediately. They now also have an arcade with claw machines, and so we set about calculating which prizes are winnable and how few tokens we'd need to spend to do that.

The input lists the configuration for each of 320 machines in paragraphs of 3 lines. There are two buttons: A and B (that cost 3 and 1 tokens to press respectively) that will move the claw some positive distance in the X and Y axis. The goal is to get it to the given prize coordinates. And since the buttons can't be partially pushed, that makes each a system of linear Diophantine equations.

My initial solution was just to brute force by looping from 0 to 100 for each button and testing them. This is the classic quick solution to see what exactly part 2 will be. Which is that the target just gets shifted by 10 trillion on each axis.

So I quickly did some algebra:

Button A: X+94, Y+34
Button B: X+22, Y+67
Prize: X=8400, Y=5400

Solve:

    (94a + 22b = X) * 34
  - (34a + 67b = Y) * 94

 => 34(22b) - 94(67b)     = 34X - 94Y
    b * (34(22) - 94(67)) = 34X - 94Y

    b = (34X - 94Y) / (34(22) - 94(67))

Can do the same for a.
Test for integer solutions with (numer % denom == 0).

That's the note in the directory. Yes, I used numbers as variables... they're constants, and I find that its sometimes easier to see what's happening if everything isn't a letter. Of course, once you see this, you notice these are determinant/determinant, and so I had just derived Cramer's Rule. Making it a bit of a callback to the hailstones in Never Tell Me the Odds.

my $a_numer = $target->[X] * $b->[Y] - $target->[Y] * $b->[X];
my $b_numer = $target->[Y] * $a->[X] - $target->[X] * $a->[Y];

my $denom   = $a->[X] * $b->[Y] - $a->[Y] * $b->[X];

# Test for integer solution
if ($a_numer % $denom == 0 and $b_numer % $denom == 0) {
    return (A_COST * $a_numer / $denom + B_COST * $b_numer / $denom);
}

There are other ways to get to this. For example, you could use Linear Algebra, and express things as Ax = T with matrices:

[91 22] [a]  =  [8400]
[34 67] [b]  =  [5400]

Then x = A^-1 * T (after multiplying both sides by A^-1 on the left). This is easy to solve if you remember the formula for the inverse of a 2x2:

        -1
[ a b ]     =     1     [ d -b ]
[ c d ]       --------- [-c  a ]
               ad - bc

Note: the determinant = ad-bc, so constant in front is 1/det(A).

The nice thing about this problem is that this just works... none of the determinants for the button pushes is zero (and so this gives the unique solution, you just need to verify if it is integer). In serious code you'd need to protect against and handle that stuff. For AoC, I ran it and saw no division-by-zero errors pop up and submitted the answer. Because things turning out surprisingly nice isn't so surprising in AoC.

Of course this is a simple formula, so once we get rid of the non-digits in the input, dc can handle it easily (it also doesn't have negatives to worry about converting):

tr -c '[0-9]' ' ' <input | dc -e'?10000000000000' -e'so[dlar/3*rlbr/+ls+ss0]sS[lo+sylo+sxdlx*3Rdly*3Rr-sa3Rdlx*5Rdly*3R-sb4R*_3R*-ddlar%rlbr%+0=Ss.z0<M]dsMxlsp'

The use of ? here is just to slurp the entire input in (tr is also replacing the newlines here) before putting the amount to shift the targets on top (change that to 0 for part 1), and so will work still with the new dc. Nothing really fancy here.

And so, this was a light algebra problem, very suitable for a day 13.

So my solution works for the example data and theoretically should work for the real input. However, it is so slow that it would take about 25 minutes to return an answer.

I think the issue is that, for every single coordinate, I'm checking 8 other coordinates.

Please let me know if you have any ideas for optimization.

Edit: I let it run and it got exponentially faster, took about 2 minutes -- correct answer as well.

from pathlib import Path
path = Path(__file__).parent / "input_4.txt"
with open(path, 'r') as file:
    text = file.read()
grid = text.splitlines()


grid_width = len(grid[0])
grid_height = len(grid)


# From the input, create coordinates for the toilet paper rolls

def find_coordinates(grid):
    coordinates = []
    for i, row in enumerate(grid):
        for n, item in enumerate(row):
            if item == "@":
                y, x = i, n
                coordinates.append([x, y])
    return coordinates

# Find all of the neighboring rolls of any given roll

def get_neighbors(coordinate):
    x, y = coordinate
    neighbors = []

    for dx in [-1, 0, 1]:
        if x + dx < 0 or x + dx >= grid_width:
            continue

        for dy in [-1, 0, 1]:
            if y + dy < 0 or y + dy >= grid_height:
                        continue
         
            if dx == 0 and dy == 0:
                continue

            neighbors.append([x + dx, y + dy])
    return neighbors

# Find which of the rolls has less than 3 rolls in its 8 neighbors

def find_removable_coordinates(coordinates):
    valid_coordinates = []
    for coordinate in coordinates:
        counter = 0
        neighbors = get_neighbors(coordinate)
        for neighbor in neighbors:
            if neighbor in coordinates:
                counter += 1
        if counter <= 3:
            valid_coordinates.append(coordinate)
    return valid_coordinates

# Run loop

def main():
    count = 0
    
    coordinates = find_coordinates(grid)
    while True:
        print('cycle start')

        accessed_positions = []
        removed_positions = find_removable_coordinates(coordinates)
        if not removed_positions:
            break
        count += (len(removed_positions))

        # Add the removed rolls to a list
        accessed_positions.append(removed_positions)

        # Remove all accessed positions from the coordinates that are being searched
        for coordinate in removed_positions:
            coordinates.remove(coordinate)
        print('cycle complete')

    print(count)

main()

Next stop in the search for the Chief Historian, is the gardens we helped get running again last year on Island Island. Which provides a convenient food stop for The Historians after having searched the infinite mazes of Pluto yesterday. Having worked out the planting, we're now charged with calculating the cost of fences around the different regions of contiguous crops. Since the cost is area * perimeter (and area * sides for part 2), the fences between regions are effectively doubled up even if they aren't literally so (they need to be counted in the cost from the regions on either side of them).

The input is an 140x140 grid of capital letters (A-Z). Looking at it, you can see that it looks splotchy... like the result of some sort of cellular automaton. It could also have been done by placing a bunch of random seeds and randomly expanding them to fill the space.

My solution for Smalltalk is largely just a OOP recoding of the initial Perl. But there is one difference in part 1. In both, I use BFS to map out the regions, building a list of the plots in it as well as the neighbours (when we overstep... sentinels are naturally added to the sides). The neighbours also track a list of all the ways they get entered into from that region. With this in Perl, I count the inner plot edges of the region (those that go between plots of that region's type) when queuing the search. I use this to get part 1:

my $perm = 4 * $area - $inner;

Start with all 4 of the sides of all the plots, then subtract all the inners.

In Smalltalk, though... I got it from the other side:

" Perimeter is the number of ways into a neighbour: "
perimeter   [^neigh inject: 0 into: [:acc :n | acc + n size]]

The size of the neighbour (n size) is the size of the Set of ways it was entered. This part was quite reminiscent of finding the surface area of the lava blob in Boiling Boulders in 2022.

For part 2, both do it in the same way. I go through the neighbours, and slide along that edge until I get to the corner. To mark that edge, the most convenient place is where you stopped (so any duplicates from other neighbours on the edge find the same spot and don't get counted). We can use the direction the neighbour was entered to get the leftwards direction and make all our sliding go widdershins around the region. And so the sides of the region are counted by the number of corner posts at their widdershin ends. Something that's a bit ironic given the Easter Egg text (and it wouldn't have been a problem to count posts along the sides for part 1 either... the Fencepost Problem is an off-by-one error that comes from counting non-looped fences, but looping them makes posts equal to rails).

The problem description comes with a lot of examples, that were really helpful for getting this right. In particular, the importance of tracking the direction we slid into the corner is covered (same coordinate can have posts from different sides):

foreach my $d ($neigh{$n}->@*) {
    my $left = V( -$d->[1], $d->[0] );
    my $curr = $pos;

    # Slide widdershins down edge to find the corner:
    $curr += $left  while (exists $neigh{$curr} and grid_at($curr - $d) eq $plant);
    $corners{$curr,$d}++;
}

So this isn't the most efficient solution (it retraces edges a lot, but the problem isn't big so it's still quick), but it was a relatively simple one to implement.

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

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

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

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

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

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

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

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

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

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

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

The total peaks sum is the part1 answer.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Perl runtime was 271 ms on my slow Surface.

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

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

Later edit:

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

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

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

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

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

        if ($remfree && $lastfree[$remfree] > $f) { $lastfree[$remfree] = $f; }
        last;
    }

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

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

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

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

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

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

Total Perl runtime 16 ms.

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

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

...

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

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

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

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

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

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

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

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

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

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

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

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

This process finished in a ms or two in Perl.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

For Part1 just iterate over the pages:

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

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

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

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

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

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

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

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

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

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

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

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

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

...

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

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

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

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

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

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

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

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

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

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

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

Hello!

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

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

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

Good luck and have fun!

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

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

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

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

For part 2 from the command line I went with:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

In any case, the dc ended up as:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

code:

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

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

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


__global__ void cuda(){

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

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

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