r/adventofcode

Having discovered that obsidian is forming, we decide to use it to crack some geodes by building geode-cracking robots. To get the obsidian we need obsidian-collecting robots, which need clay-collecting robots, which need ore-collecting robots. Fortunately, we start with an ore bot, so we have initial production, but the rest requires building additional robots which cost varying amounts of materials, and can only be built one per turn.

And so we get to this problem. This one I managed part 1 in under two hours, but part 2 took 3 more hours and is still not very good. Part of that might have been still not feeling to great. And cleaning it up now has made it faster (just over a minute for part 1, and half that for part 2), but I haven't had time to really work on it this month.

My initial solution was a job queue one. With the mining at Saturn, I remembered making a mess with a recursive approach, and scrapping it for a queue. So I decided to start there this time. One thing I did do as part of clean up was to do a recursive version... it's not any faster, but I wanted it anyways in case I got any ideas that could use that.

In trying to get a solution, I applied heuristics. Basically using a couple decades of German board game experience with building economic engines. First up was realizing that you don't need to build robots past the the maximum cost for that material... because you can only build one thing a turn. If you're producing enough ore to cover any ore cost and recoup it every turn, you don't need more... it will stack up and be worthless. Although it's not necessary the best to max things out, in part 2, blueprint #3 in my input only wants 3 ore miners to be able to build geode crackers every turn (every other robot costs 4 ore... so this is an impact on the engine building for efficiency on the end game).

Another heuristic was a little less safe... I did some estimating on how long it would take to set up an engine to start producing geodes, and came to the conclusion that the game is probably too short to really catch up if you fall 2 geode crackers behind. Because it could be better to be behind for a little bit to build a stronger engine... but that engine needs to be strong enough to get ahead with enough time left to make up and exceed the amount you fell back. And going from -2 to +1 crackers with still enough time to make up all the geodes (all while the "opponent" is also building more crackers, so it's probably not just 3 you need) really doesn't seem likely. It is a bit like flexible version of the greedy algorithm... of always just build a cracker when you can (which IIRC some people used). And adding that to mine, I get a tiny improvement with having both.

The one other thing I did was that if you don't build a robot in a turn, any that you could have built are removed as options on the next turn. That sounds like greedy, but that's standard board game strategy. If you're saving up for something you can't buy yet, that's okay (and you should buy it as soon as possible), but completely passing a turn and then turning around to build something you could have built a turn earlier... that's a mistake.

So, this one is one where I can do any of the searches reasonably fast with my solution, it's just that it asks for doing so many of them. Which adds up. And although my recursion has memoization (although I'm not sure how much benefit it really gives)... when the blueprints change, it needs to be reset.

Having reach the exit of the cave, we shelter there while the lava continues to rain down. Watching the lava fall into a pond and cool, we decide to measure its cooling rate to see if it could be making obsidian. And to do that we need to calculate the surface area.

The input is a list of 3D coordinates of cubes that make up the drop. The coordinates only range from 0-19, so it's not a huge volume.

And for part 1, my thoughts were along the lines of an inductive solution. One cube has 6 sides, for a surface area of 6. Add a second and you add another 6, but if it's adjacent to the first, you need to subtract 2 (one from each cube). And assuming you have the correct surface area after n cubes, the next cube is going to add 6 new faces, and subtract 2 for each adjacent. So we can just iterate over the list in one pass doing that. That makes for a nice simple solution even for dc:

tr ',' ' ' <input | dc -f- -e'0[6+_4R1+5C5*_3R1+1F*r++d2r:tddddd1+;tr1-;t+r1F+;t+r1F-;t+r5C5+;t+r5C5-;t+-z1<L]dsLxp'

Just converting the 3D coordinates into a flat array index. To mark a cell as occupied we put a 2 in the array. This means we don't need to test for the existence of a neighbour, just to subtract the values of all the neighbours.

For part 2, we realize that the surface area for cooling is just the outside that's in contact with the water. And so what I visualized was casting/molding around the drop. So I extended the bounding box by one on each side (to guarantee a path all the way around), picked a corner of it, and BFS flood filled it. The result being a visited list that was a molding of the outside of the drop. It has an internal surface (which is the outer surface of the drop) and an external one (which is a cube and easily calculated). So I applied part 1 to those cells and subtracted the outer cube surface.

my $encase_surface = &get_surface( values %encase );
my $outer_surface  = 6 * (($max - $min + 1) ** 2);

print "Part 2: ", $encase_surface - $outer_surface, "\n";

The values of the encase table (which is the visited list) are the same as a key, but the key is converted to a string by Perl and would need converting back, so we might as well use the value to avoid that.

I really liked this one. Part of that is probably because I came to quick revelations (this was my fastest part 1 time since day 6) that allowed me to avoid having to really work with the 3D structure. There was a bit of extra incentive in that I still didn't feel 100%, and so was going to try for anything simple before moving on to mapping 3D surfaces.

Having found an alternate exit, we find ourselves at the bottom of a tall shaft with boulders falling down it. And so we need to simulate them to avoid being crushed... but the "real" task is apparently proving the accuracy of the simulation to the elephants.

And so we get this Tetris inspired problem. The shapes aren't just the set of tetrominos. a couple pentominos are also included in the set. And there's no rotation, just side to side movement and falling.

The input is a list of left and right moves for the pieces as they fall. Mine is 10091 long, which is a prime number. And both it and the list of 5 blocks cycle.

For part 1 we just want the height of the tower after 2022 rocks (and it is not a very efficient packing at all).

My first choice was to store the block shapes in a table of relative indexes of the squares:

my @Blocks = ([[ 0,0], [ 0,1], [ 0,2], [ 0,3]],              # —
              [[-2,1], [-1,0], [-1,1], [-1,2], [0,1]],       # ✚
              [[-2,0], [-2,1], [-2,2], [-1,2], [0,2]],       # ⅃
              [[-3,0], [-2,0], [-1,0], [ 0,0]],              # |
              [[-1,0], [-1,1], [ 0,0], [ 0,1]]);             # ⬜

Then the plan is essentially to stream over this list and the input list. In the case of Smalltalk, that literally involved BlockStream and MoveStream classes with a stream interface. But in Perl, it's just indices being incremented mod the size of their list.

Then for dropping the blocks, I went with a simple "try" pattern (this is using a Vector class for the coordinates and directions):

do {
    my $move = $Input[$Inptr = ($Inptr + 1) % $Input_len];

    # Try sliding
    my @try = map { $_ + $Dirs{$move} } @squares;
    @squares = @try if (all {0 <= $_->[1] < 7 and !$Grid{$_}} @try);

    # Try dropping
    @try = map { $_ + $Down } @squares;
    @squares = @try if ($dropped = all {!$Grid{$_}} @try);
} while ($dropped);

# Place piece:
$Grid{$_} = '#' foreach (@squares);

Nothing fancy... attempt the operation and accept if it succeeds. There are multiple ways to do this sort of thing, try-catch blocks are another one.

Part 2 tells us that the elephants are not impressed yet and want more... a lot more:

my $Num_rocks = 1_000_000_000_000;

But of course, iterating a trillion times is out of the question, so we want to find when this loops (and then do the calculations to jump to the solution). This is one of the two problems in 2022 that I broke into the top-1000. I wasn't that fast for part 1, but part 2 only took me 14 minutes... so I wasn't amazingly fast on the second part, but it gained a lot of positions. So my code was apparently better positioned for doing part 2 than many.

For finding the loop, I went a hash table with the state being:

my $key = "$Inptr:$blk:" . join( ',', @tops );

Where $Inptr and $blk are the indexes of the moves and blocks, and @tops is the highest point in each of the 7 columns (relative to the highest point). This involved simply changing the subroutine for doing the dropping to return the final resting squares of the new rock (instead of just the highest point), which I then use to update the @tops array. I figured this was probably safe... and it worked.

But in regular Tetris, you can slide a piece under an overhang. And so, with that unease, and a desire to do different things for the Smalltalk solution, I went for being a bit more robust. First off, I represented the shaft with bytes there... 7 bits wide and using bit operations to place things. Which I can treat as characters (ASCII ones even, although often not printable ones). And so for detecting a repeat of the the position of the shaft what I did was build a string (starting from the top) while also ORing the characters into a mask... when the mask hits 127, all bits set, so we've seen a rock in every column. And so we have a map of the full structure at the top, not just the tops. So the elephants get to be a little more confident.

This is was a really fun one. It's another in the category of game inspired problems, and those always tend to stand out.

I need help finding where my understanding is off because my answer agrees with the test case but doesn't give the right answer for the real input. I'm also using AOC to learn Rust so there's probably something I'm missing about the language itself as well.

The main idea is to add up the differences of the quotients of the before and after positions of the dial for each rotation. I've included my main.rs:

use std::env::args;
use std::fs::File;
use std::io::{BufRead, BufReader, Lines};
use std::path::Path;

const DIALSIZE: i16 = 100;

fn parse_input(path: &Path) -> impl Iterator<Item = i16> {
    let file: File = File::open(path).unwrap(); // open the file
    let lines: Lines<BufReader<File>> = BufReader::new(file).lines(); // iterator to the reader of the lines of the file
    // iterator over the lines but with L replaced with - and R replaced with nothing to be positive
    let rot_strs = lines.map(|line| -> String { line.unwrap().replace("L", "-").replace("R", "") });
    rot_strs.map(|rot_str| -> i16 { rot_str.parse::<i16>().unwrap_or_default() })
}

fn print_dial(dial: i16) {
    println!(
        "Dial at {}",
        (dial % DIALSIZE) + DIALSIZE * i16::from(dial.is_negative())
    );
}

fn main() {
    // open the file
    // read line into buffer
    // replace L with -1 or R with nothing
    // parse into integer
    // only work in raw position, never mod
    // count += abs(div(old_pos + rotation, DIALSIZE) - div(old_pos, DIALSIZE))
    // repeat
    let args: Vec<String> = args().collect();
    let path: &Path = Path::new(&args[1]);
    let roterator = parse_input(path); // iterator over input lines that gives integers
    let mut pre_rot: i16 = 0;
    let mut post_rot: i16 = 50;
    let mut pre_div: i16 = 0;
    let mut post_div: i16 = 0;
    let mut hits: i16 = 0;

    roterator.for_each(|rot| {
        // update dial position
        pre_rot = post_rot;
        post_rot += rot;
        print_dial(post_rot);
        // update zero hits
        // div_euclid rounds toward negative infinity for negative lhs and postive rhs
        // if postive or zero add zero, if negative add 1
        pre_div = pre_rot.div_euclid(DIALSIZE) + 1 - i16::from(pre_rot.is_negative());
        post_div = post_rot.div_euclid(DIALSIZE) + 1 - i16::from(post_rot.is_negative());
        hits += (post_div - pre_div).abs();
    });
    println!("Final zero count: {}", hits);
}
    

Arriving at the distress signal we find a herd of elephants, one of which has figured out how to turn on the distress signal. Because they are in distress (as are we now)... this cave is a volcano that's about to erupt. And our task is to take advantage of the conveniently installed pressure release system to get time to escape.

And so we have a network of pipes and valves, most of which aren't functional (and thus essentially empty corridors between interesting rooms). My input has 61 valves, and only 15 are functional. The input is in sentence format, so I did my usual of grabbing a line and turning it into a regex to parse:

my ($room, $flow, $lead) = m#^Valve (\w\w) has flow rate=(\d+);.*valves? (.*)#;

First step was the usual... turn the map into a weighted graph between the interesting things. I just threw BFS at it, as there's not that many interesting nodes (and it's also easy to code correctly from scratch). You could through something like Floyd-Warshall if you want.

Then I did a simple recursive search of it... track which interesting spots you've been, and wander to new ones. Collect the maximum total pressure release on the returns. The trick is that when you enter a room (and open the valve), you add all the pressure that will be released for the remaining time.

$total += $valve{$room}{flow} * (31 - $time);  # Add pressure released

No need to simulate with ticks and process the valves again and again. Turning a valve off would clearly be a mistake, any valves that you open you want to remain open.

And looking at my personal scoreboard times, I was still not in good shape. It took a while to get part 1 done, and then I clearly went to bed. The next afternoon I picked it up, and I remember having slept on things I had some ideas how to add the second actor (an elephant) to the search.

Basically, what I went for was doing the full recursive search as before (on the shorter time), but building a table along the way of the best total seen for every open valve combination (we do it at every level because we have no idea what the elephant is doing yet). This gives a table of the best possible results from opening any set of valves that can be opened in the allotted time.

With that, I can just double loop to cover all pairs of those... finding maximum of the pairs that don't overlap on any open valve. And initially I just used lists to track what was open, and it's plenty fast. There is one little optimization I did to this O(n^2 ) search, which was to sort the sets (paths) from most to least pressure. This way I can end things early when no remaining pairs can possible beat the best we've seen already.

But I did follow up with one using bit operations. Which really didn't improve the speed (because it was already very fast)... it just felt a bit cleaner. Tracking the interesting rooms with bits, so that my recursion just becomes:

$ret = max($ret, &recurse_path($tun, $time + $turns, ($left ^ $bit), ($open | $bit), $total));

XOR removes the move (bit) from the remaining options (left), OR adds it to the set of open values, and AND comes in to check for the intersection in the final bit:

next if ($paths[$i] & $paths[$j]);

This was a rather interesting little search problem. We've done these before, even with multiple actors. But the valves and getting to the right spots as soon as possible to get the most of the them is an interesting angle... more so that just the usual of minimizing steps.

In order to track the distress signal we engage a system of sensors and beacons. Much like day 19 of 2021, but simpler. Unlike that one we don't have to find the actual coordinates... we get those for each sensor and the closest beacon we can see. The unlisted information we need is simple the distance between the two (which is Manhattan), which will be useful for establishing the exclusion zones needed to find the answers.

I remember this one because I had a Doctor's appointment early the net morning. So I did part 1 very quickly... I went though and filled a hash with all the points in a scanner range:

$hash{$_}++  foreach ($x - $dist .. $x + $dist);

This involved some ugly copy past code to handle the cases for above, below, and on the line. And after running through everything:

delete $hash{$_}  foreach (keys %beacons);
print "Part 1: ", scalar %hash, "\n";

The problem description nicely showed a beacon on the test case line not being counted, so I knew that I should probably assume that the input has that too.

This takes about 8 seconds to run... 4 of which are after it's printed out the result. That's system clean up of a big a hash for you.

The thing about part 2 is that there was an ice storm that night, and still freezing rain that morning. And the result was that I took a fall shortly after exiting the house. I still went to the appointment... I didn't really know how banged up I was until I got there. There was some nasty bruising, possibly a concussion, and some pain for the next few days. So when I finally got home, I wasn't really in the best shape to do a good solution. I had had some ideas on what I wanted to do, involving rotating the diamonds in some way to deal with squares instead. But I wasn't really in the condition to do that, so I went with the thing that wouldn't require any thought and definitely would work. I just merged ranges on the raster lines and then looked for the hole. It takes over 2 minutes to run, but it was simple, and allowed me to submit an answer, and take the rest of the day off.

So this one had been on the TODO list for a long time, and I got to finally do something better with it at the end of July. So I started just by coding the better scanline just with the diamonds... they change every line of 4 million, but a few are active at any time (moving out and then in), and that results in things only taking about 13 seconds.

But the real solution that I had made the TODO for back on the initial day was to square the diamonds. Rotate them so the scanline will work effectively (and skip most of the lines). The problem being that the rotation matrix involves 1/sqrt(2) (the sin and cos of 45 degrees). And I don't like going outside of integers for AoC. So the result is using a rotation matrix multiplied by sqrt(2) (and so it scales by that in each direction):

sub rot { my ($x,$y) = @_; return( [$x + $y, $y - $x] ) }

The trick being that by doing a second one (ie the inverse rotation), results in a scale factor of 2 in each dimension, which is a nice integer that can be divided out then:

sub rot_inv { my ($x,$y) = @_; return( [($x - $y) / 2, ($y + $x) / 2] ) }

And so I use these to rotate the initial diamonds into squares. Then I can do a scanline vertically to track the active squares, and then did similar for the horizonal (pretty much exactly what I did for Firewall Rules in 2016, where we also needed to find the missing values in a set of ranges).

And so this one finally has a decent solution.

The distress signal lead to a waterfall, and as the trope goes, there's a large hidden cave behind it. Following the signal into the cave, we find ourselves threatened by falling sand. And we have a sand physics simulation to go along with the water simulation from 2018 (Reservoir Research).

The general idea is similar... sand is falling down from a point at (500,0) like before. There are a bunch of walls that going to form obstacles to redirect the flow. The format of the input this time is different, in that the lines cover chains of walls, and it's up to us to spot which way the walls go,

As for the simulation, it's actually a bit simpler. Sand falls straight down, then diagonally to the sides, and eventually when it comes to rest, the sand piles back up. The description was very suggestive of a stack to me so that's the first solution I did... push the locations to fall down, and when things are blocked, fill and pop back up. For part 1 you need to know where go below the max Y coordinate, and for part 2 you put a floor there and run it again... it was one of the faster part 2s in this year (and I didn't gain that many positions for it, so it looks like many people were similarly well positioned for part 2). Of course, that's just the stack version of the recursive approach, so I followed up with the actual recursive version later that day. Which would be the first solution in 2022 that required turning off deep recursion warnings in Perl (it spawns about 200 of them). The recursive version is actually a little bit faster. It's certainly a lot simpler than the mutually recursive functions I did for the water in 2018.

I have never struggled with a Day1 like this before, so I'm a little embarrassed to have to ask for help. Here is the code I have tried:

Part2

The definition of a 'Turn' is:

class Turn {
public:
  int clicks;
  Direction dir;
  Turn(char d, int c) {
    switch (d) {
    case 'L':
      dir = Direction::Left;
      break;
    case 'R':
      dir = Direction::Right;
      break;
    }
    clicks = c;
  }
};

My solution for Part1 worked so I am reasonably confident the input is parsed correctly, and my part2 solution (pasted above) works on the example provided. Where have I gone wrong?

Edit: I needed an abs() call. Thanks for the help!! Updated code: Part2 Corrected

Don't code on an empty stomach!

In order to get a better signal for our communication device, we use it to find a nearby hill. And so we're tasked with finding an efficient path up to the top (that doesn't require going up more than two levels on any step).

The input is a relief map in landscape (mine is 41 lines of 154 characters). Where elevation is represented by the letters a-z... with S and E used to mark the start (elevation a) and end (elevation z). The left column is all a (including the start), followed by a column of b, followed by a large plain of c with many large holes of depth a. At the right there's a hill with a spiraling path up it to the end.

One thing I remember about this one is that it has spawned threads of people that missed that you can always go down as much as you want (the only limit is that you cannot go two higher). And the map has a check that you've implemented that correctly on the spiral (on mine you need to go back to j from l in order to continue up the path).

The nature of the map and final path means that BFS is fine for this. Using A* can direct you to cross the plain quicker if you want. But then part 2 shows up. And for it, it wants the shortest path from an a to the E... which is clearly best done by searching from E with a BFS (which is going to whip around that mountain) until you find you find the first a. And with that, you can easily include part 1 in that solution, by continuing until you get to S as well.

And so we get a search problem that isn't that heavy. The map presents opportunities for people that want fast times to specialize the search based on knowledge of the map structure. But using heuristics like that can also allow a beginner programmer to get a solution, because with the structure and blockiness of the map, you could even do this problem by hand if you wanted to.

Having reached the top of the hill, we receive a distress signal. But since the device is still malfunctioning, the packets are out of order.

The input for this one is like that of Snailfish numbers. Lists of lists using a common syntax for such things, so some popular languages don't have any parsing to do. Writing a parser for this one is slightly more complicated than the one for Snailfish numbers... empty lists exist, as does the two digit number 10.

Once you have the packet structures loaded, the problem asks essentially for a comparator and provides a nice description of what it wants. And for part 1 it just to test it on pairs, and for part 2 it wants the position of two markers in the full list.

So, I just treated is as coding to a spec, and then:

$part1 += $i  if (cmp_packet( $left, $right ) < 0);

$part2 = product inc indexes {$_ == $markers[0] or $_ == $markers[1]} sort cmp_packet @input;

I didn't really spend anymore time thinking about it. I believe the markers [[2]] and [[6]] do occur at the start of the sections that start with a 2 and 6 respectively. And I recall some people did use that to shortcut. But with the comparator already in hand, just using it to sort and then grabbing the indexes is so programmer efficient, that doing anything else felt like more work. It's not like the problem is that intensive... I have a Smalltalk solution that returns almost immediately and it's just using:

part2 := ((allPackets count: [:p | p <= pack2]) + 1) * ((allPackets count: [:p | p <= pack6]) + 2).

IE, comparing everything in the list against each of the markers and counting.

The bulk of this problem for any beginner is going to be getting that spec right (and maybe doing a parser). And the description does include step-by-step comparisons of the test cases to verify your code against.

While making our way upriver, some monkeys grab some of the stuff from our backpack and we need to get it back (while they keep away), while trying not to worry too much.

The input describes 8 monkeys, each with a starting list of items (with 2-digit worry levels), an expression for how to modify the worry level for an item for that monkey, and a section that describes a divisibility test (using the first 8 prime numbers) with the monkeys to throw to if it passes or fails. And so the input requires a bit of parsing... although for the most part you can ignore everything but the numbers. The exception being the "Operation" line which has a simple arithmetic expression: either adding/multiplying with a constant or squaring the old worry level.

And so, I naturally turned the input into code (hello, Bobby Tables):

my %p = map { (m#(\w+):#) => [m#(\d+)#g] } @desc;

$desc[1] =~ s#new = (.*)#$1#;
$desc[1] =~ s#old#\$_[0]#g;
$monkeys[$n]{op} = eval "sub { $desc[1] }";

$monkeys[$n]{pass} = eval "sub {(\$_[0] % $p{Test}[0] == 0) ? $p{true}[0] : $p{false}[0]}";

For part 1, we get a rule to reduce the worry levels by dividing by 3. For part 2, that's removed. And the description mentions multiple times that this means "ridiculous levels" of worry and the need to "find another way to keep your worry levels manageable". And it means it.

Because this isn't one where you can just invoke "bignums"... the fact that one monkey squares the worrying means that the worry levels quickly exceed the number of protons in the observable Universe (not a problem), and soon after they have a number of digits that exceeds the the number of protons in the observable Universe (which is very much a problem). So the numbers cannot be stored... this is a case where it's very good to have limits set on how much resources your processes can use.

But not being able to store all the digits isn't a problem, because we can easily describe how to compute the number, and so we can use that to extract information about the number. And that's what we need to do to keep the worry level manageable.

As for how... well, it's divisibility and so the answer is pretty much always LCM (Least Common Multiple) and modular arithmetic. And since I was using anonymous subroutines for other parts, I did that here too:

print "Part 1: ", &run_monkeys(    20, sub { floor( $_[0] / 3 ) } ), "\n";
print "Part 2: ", &run_monkeys( 10000, sub { $_[0] % $modulus   } ), "\n";

Where $modulus is just the LCM of all the test values (which, since the values in the input are all different primes, is just the multiplication of them). Which for the first 8 primes, is 9699690. I do remember someone doing this problem on a C-64 with 16-bit integers, and IIRC, they broke it into two parts covering 4 monkeys each. Although, you could also just track all 8 modular values for each number.

In coming back to it, I was curious how big my worry levels get... and so I quickly modified it to also track the log of the length of the numbers. And the answer I got was about 9 * 10^504 bits in length.

This probably is definitely a memorable one... maybe not for the job that needing doing, but for the size of the bomb the input contains.

Having plunged into the river and separated from the rest of the expedition, we pull out our communication device to find it in need of repair again. This time we need to work on the clock circuit for the display.

And so we get what's marginally an assembly problem. Two instructions, one of which is noop, and the other is addx. For part 1 we want to collect the values at times 20 mod 40. For part 2, we use the timing of the values with the raster beam to produce an image.

For my initial solution I just parsed the input as text and added a noop for the extra cycle that addx took. But in doing that, and thinking about how to do this in dc (I do like to do these ASCII art problems in dc), it immediately became apparent how to turn the opcodes into numbers that dc can parse. Namely, noop has one word and takes one cycle, addx V has two words and takes two cycles... so just turning all the opcodes into 0s provides the correct timing when we just treat the result as a list of 1-cycle adds to the register. In Perl, that looks like:

foreach (map {tr/a-z/0/; split} <>) {
    $display .= (abs($regX - $time % 40) <= 1) ? '#' : ' ';
    $part1 += $time * $regX  if (++$time % 40 == 20);
    $regX  += $_;
}

And for dc I did this:

tac input | tr -s -- '-a-z' '_0' | dc -f- -e '[d3Rd3R*ls+ssr]sS1d[1+d40%20=Sr3R+rz2<L]dsLxlsp'

tac input | tr -s -- '-a-z' '_0' | dc -f- -e '[AP]sR[d3Rd3R*ls+ssr]sS33P1d[d40%d0=R3Rd3R-d*v2r-d.1-/32+Pr1+d40%20=Sr3R+rz2<L]dsLxlsp'

So it wasn't a typical assembly/VM machine problem, but still quite fun.

Back when we looked at this one, about a week ago, I said that I would like to write a proper bleeding edge (unsafe{}) AVX intrinsic version, well I finally got it done and I'm quite amazed:

        for b in 0..blocks {
            let bl = input.as_ptr().add(b*64) as *const __m256i;
            let b1 = _mm256_loadu_si256(bl);
            let b2 = _mm256_loadu_si256(bl.add(1));
            let b1h = _mm256_and_si256(b1, xyz_mask);
            let b2h = _mm256_and_si256(b2, xyz_mask);
            let b1l = _mm256_and_si256(b1, abc_mask);
            let b2l = _mm256_and_si256(b2, abc_mask);
            let b1h = _mm256_srli_epi32(b1h, 14);
            let b2h = _mm256_srli_epi32(b2h, 14);
            let b1hash = _mm256_or_si256(b1l, b1h);
            let b2hash = _mm256_or_si256(b2l, b2h);
            let b16 =_mm256_packus_epi32(b1hash, b2hash);
            let inc1 = _mm256_shuffle_epi8(part1shuffle, b16);
            let inc2 = _mm256_shuffle_epi8(part2shuffle, b16);
            part1 = _mm256_add_epi16(part1, inc1);
            part2 = _mm256_add_epi16(part2, inc2);
        }

These 15 AVX ops are the full solver that handles a block of 16 input lines, I pad the input with 48 space chars (10048 is divisible by 64) so that I don't have to worry about the tail end.

It is probably clear, but the algorithm starts with u/ednl's packing (AND both chars with 3, shift the second one down 14 bits and merge, that's the first 10 AVX ops.

Next I pack together the two 32-bit arrays into a single 16-bit one (b16 above), before I use that variable twice to directly lookup the 8 part1 and part2 results for these lines.

So, with a single AVX op/cycle this should take a fraction less than a clock cycle per input line, right?

I do measure 3 us on my Acer, but now we get to the interesting part:

When I instead run u/maneatingape on my input file, I get 2.3 us, for much simpler and shorter integer only code!

That time is broken down into 1.2 us to convert all 2500 lines into a 0..8 index, using code like this

pub fn parse(input: &str) -> Vec<u8> {
    input.as_bytes().chunks_exact(4).map(|c| 3 * (c[0] - b'A') + c[2] - b'X').collect()
}

(The original code generates an array of usize, when I switched to u8 the parsing stage dropped to 1.1 us and the total from 2.3 to 2.2 us)

In order to manage this, the CPU has to convert two lines per nanosecond, probably using code somewhat like this, which has a minimum latency of 4 cycles. The CPU must internally unroll the code over a bunch of iterations, enough to gain back the AVX advantage and then beat it!

movzx rax,[rsi]
movzx rbx,[rsi+2]
sub rax,'A'
sub rbx,'X'
lea rax,[rax+rax*2]
add rax,rbx
;; push into vector

We get to the rope bridge on the map, and decide to model rope physics as we cross. Even while falling after the bridge breaks.

The input is a list of absolute direction moves for the head of the rope to take (UDLR and a number of steps, at most 19). The rest of the rope follows along... moving when it has to (Chebyshev distance > 1 from the piece ahead), and otherwise staying at rest (as Newton says it should). For part 1, we only have one piece in the tail, for part 2 we extend it to 9. And we want to track how many different locations those end up in.

So I just did the very basic thing of a straight simulation. Since we want all the in-between spots the tails rest on, not just those at the end of the move, that's a pretty good reason to just do the moves stepwise... iterating for the number of steps and pulling the rope along, and throwing the tail into a set/hash to record the unique places it lands.

There are a few little things to work out from the description, like the vector for movement. But just looking at the examples and reading it... I immediately thought "roach movement from DROD". That's not the first or best example of it, but I'd played a lot of DROD. And DROD looks like a hack-and-slash dungeon crawler, but is perfectly deterministic hand designed puzzle game (most of the time). Where puzzles often require you to keep monsters alive and manipulate them into positions. Which means that the movement patterns get really ingrained. So I did end up calling the subroutine to calculate the vector (which just uses <=>) "roach_move".

So this was another one of just doing the thing and staying away from any potential chaos that the rope movement might bring. The problem is small so it's fine (2000 lines, 19 steps max, 10 knots).

We come across a grove of trees that were planted as a reforestation effort. And the Elves decide to think about building a tree house, and so we're tasked with finding a good spot.

This problem is a bit like the Skyscraper/Tower pencil and paper puzzle. Only there the goal is to fill in the grid based on how many can be seen from the outside (with an added Latin square restriction to provide enough constraints). Here we're going the other way for part 1... we've got the grid, we want how far in we can see. And for part 2, it's how far can we see in the 4 directions from a tree.

The input is a square grid of numbers, and just looking at it you can see that there is a pattern. The numbers generally increase up to a circular plateau in the middle.

And looking at my initial Perl solutions... it's really ugly brute force copy-pasta to do all four directions. For the Smalltalk I did a little better, using a state machine approach on the scan that did forwards and back in the same pass. I've done a Perl transcode of that that's slightly better to look at:

for (my $y = 0; $y < $MAX; $y++) {
    my @fore = ([$y, 0]);
    my @back = ([$y, $MAX - 1]);

    for (my $x = 1; $x < $MAX; $x++) {
        my $height = $Grid[$y][$x];

        push( @fore, [$y,$x] )  if ($height > &grid_at( $fore[-1] ));
        shift( @back )          while (@back and &grid_at( $back[0] ) <= $height);

        unshift( @back, [$y,$x] );
    }

    $vis{$_->[0], $_->[1]}++  foreach (@fore, @back);
}

And copy paste for the other axis. The basic idea is that fore does the easy scan of just adding each higher tree as we go. The back scan removes lower trees from the front that the current tree will block before inserting it. It's not great by any means, but it is at least more interesting.

So, in revisiting things. I did that transcode, and for part 2, I decided to do a little state machine there too. Basically using the idea of tracking what we can see behind us. So I keep an array of size 10 that's the count of the number of trees backwards we can see from that height. The idea being that when I look at the next tree in the row, I take it's height and look it up and multiply that in. Then I reset lower heights to 1 (as this tree will block all but itself from the next), and increase the higher heights (that this tree doesn't block). And since I didn't much have much time to do more today, I copy pasted that 4 times for each direction. Again, it's just the start of something more interesting. When looking at puzzles at the end of July to fix up, I had completely missed this one, because the run time was so fast with brute force anyways and it's so early.

The next step in fixing the communication device we've been given is finding enough space to do an update (complete with an INTERCAL Easter Egg). And to do that we get a log of browsing around the system with ls and cd... the filesystem apparently lacks better tools for doing this job, so we make do.

The input is a log, and it's a nicely ordered walk. It starts with a cd / to establish that it begins at the root, no other cd has a / in it... so there's no down-two, up-two, up-and-over stuff to worry about. And the ls is only done once in each directory. So support for that stuff and sanity checks are optional.

I did this with a recursive decent parser in Perl to start... it really fits because we're doing a tree walk, with a very standard collection of the results going back up... recurse down and return the size back up, collecting the sum of them for the current directory. Here we also want to keep those intermediate values, so we can just add them to a hash table on the current working directory string. Then at the end we can just extract what we need with:

say "Part 1: ", sum grep { $_ <= 100_000 } values %dirs;

my $needed = NEED - (DISK_SIZE - $dirs{'/'});
say "Part 2: ", min grep { $_ >= $needed } values %dirs;

I also did another version which was iterative, because the recursion only has the parameter of the current working directory. Which is basically a stack... you append (push) directories on the end when you cd down, and remove (pop) the last directory when you cd ...

And for Smalltalk I did a nice class to represent the system and make queries. That's in line with the fact that this is a "work" problem. It's a real task... I wouldn't do this specific job this way, but there have been times were I've written scripts to follow logs like this and extract information.

I suppose the cutest thing in my solutions is with the Perl, where I did this:

$/ = '$ ';          # break input on cmd prompts

# read input, throwing out the cmd prompts
my @Input = map { [grep { $_ ne '$ ' } split /\n/] } <>;

... to read in the input. Basically chopping it up with the command prompts as the delimiter. So that I get an array of arrays where the first element is the command, and the rest is the response. It does require a bit of mess to chop out the $ delimiters, but it does the job and it means that the code that does the work doesn't need that mess. Up here is the perfect place for such ugliness.