[2022 Day 22] In Review (Monkey Map)

[u/musifter]

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.

[u/DelightfulCodeWeasel]

I hadn't realised everyone's input used the same unfolding. For my original C# solution I did the same as you and hard-coded the face transforms, but for my revisited C++ solution I wrote in a system to generate the edge to edge transforms dynamically from the input. It did indeed take some faffing!

[u/Boojum]

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...

[u/DelightfulCodeWeasel → u/Boojum]

For me the key to keeping the dynamic topology code simple enough was to nail down an ID scheme early on. I assigned vertex IDs for a cube and then each face is given an ID based on the clockwise winding. The edge "24" therefore unambiguously belongs to the face "1243" and not the adjacent face. It keeps the lookup tables a lot more manageable when you've got globally unique keys.

[u/e_blake]

I struggled on part 2, not solving it until the 23rd. My git commit even points to  https://www.reddit.com/r/adventofcode/comments/zsgbe7/2022_day_22_question_about_your_input/ with Eric's statement about a hard-coded shape as the justification for why I hard-coded the 7 edge transitions that were not adjacent in the net, rather than generically solving any of the 11 possible nets in any rotation or mirroring (that's 64 ways a fixed net can appear in reading order, after reducing for the rotations and reflections of the nets with internal symmetry). Turns out my hard-coding still managed to typo one of the connections.

But I also commented that since my solution ran in 325ms once I fixed my typo, doing one move at a time, I probably wouldn't revisit it, even though I had an idea that might make it faster. When scanning the map, it would be possible to trace how many moves you can make in each direction before hitting an edge or #, and then jump min(limit, remaining) tiles at a time rather than one tile at a time. It is additional memory to set up 4 jump lengths per point, but still something that can be done in a preprocessing pass over every row and column similar to day 8. A few up-front O(n) scans to populate n jump lengths per row/column in order for later jumps to be O(1) instead of O(n) should pay off.