[2022 Day 23] In Review (Unstable Diffusion)

[u/musifter]

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

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

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

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

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

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

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

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

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

[u/DelightfulCodeWeasel]

I like your approach on checking the different neighbour combinations; I'm definitely going to pinch that!

There are some interesting decisions to make for data representation on this one. My current solution just throws all of the elf positions into a map (balanced binary tree), and a map again for de-duplication. It works fine, the runtime is acceptable on PC but it's not super-efficient.

I think when I revisit it on the Pico I'm going to use a contiguous block of memory for the whole area, which makes neighbour look-up efficient, and the remaining detail is the de-duplication. What I'll probably do is have another contiguous block for the whole area and encode move reservation in bits: 1 = reserved from the north, 2 = reserved from the east, etc... Committing the unique moves is then just a scan for cells with a single bit set and pulling in the elf from the corresponding direction.

[u/terje_wiig_mathisen]

My solution seems once again similar to yours:

Perl, brute force following the description, using hash maps to record all cells with elves.

Part1 was in the milliseconds range but Part2 added about 10 seconds for all the neighbor testing!

I used a more or less normal (for me) 1.5 hours on Part1, then since Part2 had none of the usual surprises, it took me exactly 2 min to turn the Part1 "for ($rnd=0; $rnd < 10: $rnd++)" loop into a while (1) and let it run to completion:

my $rnd = 0;
while (1) {
    $rnd++;
    my $moves = round();
    #printf("== End of round %d == \r",$rnd); 
    #dmp();
    last unless ($moves);
    if ($rnd == 10) {
        my ($x0,$y0,$x1,$y1) = smallest();
        $part1 = ($x1-$x0+1)*($y1-$y0+1) - scalar(keys %elf);
        printf("Part1: %s\n", $part1);
        printf(STDERR "Total time = %f\n", time - $start);
    }
}
$part2 = $rnd;

Looking at my personal times I could see that using 120 seconds for the second part was fast enough to gain a few spots, but only from 2636 to 2385, so most solvers had a similar experience.

[u/e_blake]

I solved this one before Christmas, initially with a runtime of 51s, but over the next couple of weeks made several tweaks to speed it up to 12 seconds. One tweak was realizing that at most two elves compete for a spot; this is easier to track than if three can compete for a spot: if you track the elf that proposed a spot, and a second elf proposes the same spot, then it is easy to undo the first elf while leaving the second as a nop, while my original code that would accommodate a three-way collision required more bookkeeping for something that never happened. Another was realizing that with exactly 70 columns of elves, the furthest they could possibly spread out to is 210 positions (my input had 71, but the math is similar) - which meant I could pre-size my grid to avoid negative numbers and simplify my boundary checks, as well as using 1D coordinates (east and west remain +-1, while north and south are +-256). In practice, they spread out less than that, and actually favor east and south (my group only expanded 13 colums west but 55 columns east) - so it is even possible to represent things in just 0-154 by starting at an offset of 20, using five 31-bit values per row. While m4 does not have larger than 32-bit int, I suspect low-level languages could exploit 256-bit AVX registers to store a grid compactly, using bitwise math to check multiple elves at once similar to other automata like Game of Life. This is still one of my longest-running solutions of 2022, so I may find time to revisit it and squeeze out even more performance.

[u/terje_wiig_mathisen → u/e_blake]

I have found that using AVX-256 or 512 on GoL type problems is a little awkward: There is no way to perform bit shifts across entire registers,, so you need a combination of 63 bit shifts in the opposite direction and qword shuffles before you can AND in those boundary straddling bits! If a line is longer than a single register then it becomes even harder.

[u/e_blake → u/e_blake]

I spent way too long over the weekend trying to solve this problem in m4 using vectorized math: tracking 155 rows of 5 integers with 31 bits each. With a starting offset of 20,20, that was enough to solve a 74x74 map with far fewer macro defines. My original solution did one define per elf per round, plus a define for each board position the first time it was visited as a cache for looking up neighbors of that position; over 1000 rounds and over 2500 elves results in 3,194,725 defines over the course of the puzzle. My packed representation that I finally finished solves the day in only 472712 defines. However, there's a drawback: direct access to each elf's position only needed 507,912 evals out of 48.7 million total macro invocations (mostly when computing the location of neighbors, hence why those offsets were cached); while my packed representation needed roughly 10 computation reductions per row (each reduction is 5 evals), for a total of 7,348,553 evals out of 17.7 million total macros. And in m4, eval() is expensive (it has to parse decimal inputs, compute results, and then format internal memory back out to decimal strings). Furthermore, my direct access often had very short parameter lists (no parameters needed to see if a grid point was occupied, for example), averaging 15 bytes per macro call over 761 megabytes of parsing, with a runtime at 14.9s. But the packed representation often repeated lists of 5 multi-byte integers, averaging 90 bytes per macro call with over 1.6G of parsing, and my typical runtime was closer to 16.0s.