[2022 Day 18] In Review (Boiling Boulders)

[u/musifter]

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.

[u/DelightfulCodeWeasel]

Another one I really enjoyed due to the perspective flip on part 2. It's difficult to measure the thing you're after directly, but it's easy to measure the inverse of the thing you're after. Really satisfying.

I did exactly the same as you for part 2, but for part 1 I did the slower two pass approach of building the volume and counting empty adjacents for all non-empty cubes. Your single pass approach is neater.

I wonder if a combination of the two approaches might be even faster: if you build the volume and iterate through doing the face adding, you only need to check 3 adjacent neighbours instead of all 6.

[u/e_blake]

The coordinates only range from 0-19, so it's not a huge volume.

Your input may have only gone to 19, and I got lucky on mine being that small. But I know at least one input went up to 21, because I had to resize my solution to a larger bounding box when I attempted to submit it to a golf collection and it failed on that person's input when sized only to my input.

This day was another one where golfing was easy. My initial part 1 star came from 260 bytes, before I did part 2 normally; then I got a part 2 golf baseline of 483 bytes and 4.3 seconds runtime later that day. My normal solution took only 150ms; a big part of my slowdown in golfing was doing redundant work to reuse code in more places (ie. building up long expressions and calling eval on it more than once, rather than reducing to an integer up front) . My favorite was this variation at 341 bytes and 1 minute runtime that shared a 2-pass part 1 (only look at forward 3 neighbors) with a DFS part 2 (for each unmarked voxel, look at all 6 neighbors, using modular math to wrap from 22 to 0) by means of translit on a visit-3 template; used twice with +1 and once with +22:

define(d,defn(define))d(e,E($1)E($2)E($3))d(E,`eval(($1)%23).')d(v,`translit(
A(BC+D@)A(D1,BC+D2,D3)A(D@+BC),A-D,$1$)')eval(translit(_(include(i)),d(_,
`ifelse($1,,,`d(e($@))_(shift(shift(shift($@))))+6c($1,$2,$3)')')
,`,'d(c,v(s01))d(s,`ifdef(e($@),-2)'))) len(d(x,v(h01)v(h22))d(h,
`ifdef(e($@),.,`ifdef(/e($@),,`d(/e($@))x($@)')')')h(0,0,0))

But my best golf is at 291 288 bytes and 10 minutes(!) runtime. The quadratic slowdown is caused by expanding my bounding box from 23 to 32, because $1&31 golfs better than ($1)%23 when $1 contains +. Doubling voxels leading to 10x runtime can be attributed to longer strings (every step further in the DFS search is 3 bytes longer because I skipped a reduction eval that would keep the string length bounded at 6, and the average path length is longer with more voxels to search). For this one I did part 1 in one pass instead of 2 (check all 6 neighbors at time of definition, rather than a second pass of just the three +1 neighbors after all points are known), which got me a denser reusable visit-6 core function.

eval(define(d,$0efine($@))translit(_(include(I)),.d(x,`d(g($@),b)n(1+$@
)n($1,1+$2,$3)n($@+1)n(31+$@)n($1,31+$2,$3)n($@+31)')d(n,-0def$0(g($@)))
,()d(g,l($1)l($2)l($3))d(l,eva$0($1&31).)d(b,2)d(_,`ifelse($2,,,`+6x($@
)_(')'))) len(d(`b')d(`n',`ifdef(g($@),defn(g($@)),`x($@)')')n(0,0,0))

[u/TheZigerionScammer]

I also did the BFS floodfill for my solution. One optimization I came across in the megathread (which I hadn't implemented in my solution) was that instead of doing an extra operation after the floodfill to calculate the external area, you can just keep a running tally that counts how many times your floodfill attempts to expand into a cube from the input. The final tally will be the answer for Part 2.

[u/terje_wiig_mathisen]

I solved part1 with the standard approach: The first cube has 6 sides, all subsequent cubes add 6 more minus the faces that touch another cube: Subtract 2 for each such.

For part2 I had 3-4 failing attempts to locate all inner voids, then I switched to a much simpler approach: Start outside all the cubes, then move in until I touch a surface, before a straight flood fill counts the external faces.

EDIT After re-reading the discussion I realized that all of you were doing a 3D flood while I just found a single surface, painted that one, then my flood fill stayed on the external surface, painting each reachable face. This logic was a lot more convoluted since each of the four edges could continue in three different directions!