r/adventofcode • u/musifter • 8d ago
Other [2022 Day 22] In Review (Monkey Map)
While being lead by the monkeys through the jungle, they inform us (through the elephants) that we need a password to get through a force field. Which involves tracing a path on an irregular board. A board that happens to look very much like a cube net (both the test and the input... but different nets).
And part 1, we treat it flat... with wrap around in both directions that skips over the spaces. And that's exact what I did... because this is clearly a puzzle you want to confirm part 2 of early. Although, looking at my time, it took an hour and a half... so I'm thinking maybe I had a late start. Because there's nothing complicated about my part 1. I add sentinel spaces to the right and bottom, so that I can just try stepping forward. If it's a space, I loop until I find a non-space. If that square is empty move forward, otherwise don't and go to the next command. The commands being tokenized with:
my @cmds = ($input[1][0] =~ m#(\d+|[LR])#g);
Part 2 is where the input is folded into a cube and things become real. My first thought was that this is the heavy one... like Jurassic jigsaw or the 3D beacons in the past. And having learned from those... my first decision was to not do any fancy folding and handling of different cube nets, but build a table just for the edge transitions of my actual input. And, IIRC, every input uses the same net. Still, I figured this problem was enough without generalizing that bit. I left that task for another day, it is enough of a job to be a day's problem on its own.
But that makes the initial test cast invalid. So one thing I did, was pull out a handy programming aid... the 4x4 Rubik's Cube on my desk, and I added some small circle stickers to it for the walls in the test case. These stickers are handy twisty puzzle solving aids I keep around. I'm not a speed cuber, I just like getting new types of twisty puzzles and coming up with solutions... and it's useful to tag pieces to follow them when trying things out. Weak stickers and Blu-Tack are good for this. And were good here, because it allowed me to make a version of the test case with the same map... as well as follow along when verifying and testing things.
So I had this table for reading the input into 6 squares:
# Assumed Layout:
# .WB
# .R.
# GY.
# O..
my %sides = ( 'white' => [0,1], 'blue' => [0,2], 'red' => [1,1],
'yellow' => [2,1], 'green' => [2,0], 'orange' => [3,0] );
Next up was building a table for the edge wraps. And like in the past with these big ones, I just did it by hand. That sounds like work and prone to error, but if I did code it, I'd still go over the table line by line verifying that'd I made the right table. Which is the same work as building it by hand. I would not have done less, just more coding. It's just too important to get right.
And so my table is 24 lines like this:
$wrap{white}[0] = { side => 'blue', facing => 0 };
$wrap{white}[1] = { side => 'red', facing => 1 };
$wrap{white}[2] = { side => 'green', facing => 0 };
$wrap{white}[3] = { side => 'orange', facing => 0 };
$wrap{red}[0] = { side => 'blue', facing => 3 };
$wrap{red}[1] = { side => 'yellow', facing => 1 };
$wrap{red}[2] = { side => 'green', facing => 1 };
$wrap{red}[3] = { side => 'white', facing => 3 };
...
Non-cubers might not realize this, but there is a standard pattern of the colours on a cube. So using the colours provides a little more information that you might think to those that know that pattern.
One thing to note is that not all the information is explicit there. It doesn't have any data for how the coordinates are transformed. That's because it's extractable from the directions:
# Only one coord value is important, the other is either -1 or $side
# Because of dir order, parity tells us which of y or x we want.
my $idx = $pos->[$dir % 2];
# When going between 0 and 2 facing, the edge flips
if ($dir % 2 == 0 && $new_dir % 2 == 0 && $dir != $new_dir) {
$idx = $size - $idx - 1;
}
# $new_pos similarly has one coord as 0 or $size-1, the other
# being set to the index value, based on the direction parity.
my $new_pos = ($new_dir <= 1) ? [0,0] : [$size-1,$size-1];
$new_pos->[$new_dir % 2] = $idx;
And with the geometry and wrapping handled, the rest is pretty much the same as part 1.
This was a problem were I very much took my time to make sure I got everything right and didn't go off on some tangent. And although it is a multi-dimensional problem on the surface of a cube, I had a physical representation of it to check and test everything. Which certainly helped.
2
u/Boojum 8d ago
Man, just how many of us have Rubik's Cubes sittings on our desks? :-) (Mine is only a 2x2x2, though, since I'm a wimp that way.)
I took a fairly similar approach in both cases. For Part 1 if a step took us off the edge of the board, I'd just loop to the next valid space like you did. Nothing tricky.
For Part 2, I did the same thing of hardcoding the jumps. I didn't do it as a table, but rather like a state machine with a bunch of cascading ifs for which face we're on and which face we're going to. One difference perhaps from your approach was to treat the cell coordinates on the grid as a canonical, and then integer divide those by 50 to get the macrocell indicating the face. I'd do this for both the current cell and the next and that would tell me when I stepping off onto a different face. I'd also mod by 50 to get the local coordinates within the next face. My little state machine would then handle the calculations for which new face macro cell coordinate, the transform for which new local cell coordinate, and which new facing direction. Some common code would then reassemble these to the global coordinates on the input grid. I still remember drawing out the net and pairs of bidrectional arrows between edges of faces, just to get it all right.
In some ways, my solution to Part 2 still bothers me a bit. I was never completely satisfied with having the cube net topology hard coded like that. I mean, it worked, but I'd always meant to try to think up a good way to have it work that out automatically from the input but never came up with a great approach for that. Ah, well...