ShareMyScreen/AdventOfCode/2022/18/Boiling Boulders

From J Wiki
Jump to navigation Jump to search

The Problem

I won't even need a script for this.

Two cubes share a face normal to z if their x and y positions are the same and the z positions differ by one. To count those cases I sort the cubes on xyz and see where neighbors differ by just 1 in z

   cubes =. ".;._2 LF ,~ wd 'clippaste'
   +/ 0 0 1 -:"1 (2) -/\ \:~ cubes
3

To find all the shared faces normal to x I repeat the computation sorting on yzx. Likewise for y. I do this by giving an argument that indicates which axis to put at the end. I need to execute that sequence repeatedly, so I need to roll it up into a tacit fork with a rank. The tacit fork looks much like the right-to-left form; the difference is that all the verbs are rolled up into one jumbo verb before being applied to the arguments. The roll-up is performed right to left:

  • the rightmost verb will be executed first when the tacit fork is executed
  • other verbs are processed in pairs and can be of 3 forms:
arg-verb between-verb arg-verb will be executed on the overall argument(s) to the fork, and then (arg-verb-result between-verb result-from-verbs-to-the-right) is executed
[: monadic-verb (monadic-verb result-from-verbs-to-the-right) is executed
noun between-verb (noun between-verb result-from-verbs-to-the-right) is executed

The upshot of this is that I have to put [: in front of any monadic verbs.

   0 1 2 ([: +/ 0 0 1 -:"1 (2) -/\ [: \:~ |."1)"0 _ cubes
3 2 2

The number of visible faces is 6 for each cube, minus 2 times the number of shared faces.

   (6*#cubes) - +: +/ 0 1 2 ([: +/ 0 0 1 -:"1 (2) -/\ [: \:~ |."1)"0 _ cubes
64

In part 2 I have to exclude faces on the interior of the rock. I will treat this as a maze follower: I'll start outside the rock and diffuse in all directions until all empty cells that connect to the outside have been touched. Then I'll count the number of faces that connect to the outside.

I peek at my test data and see that the cubes are contained within a 20x21x21 area. The diffusion will be fast and I still won't need a script. I define a couple of things I will need:

   faces =. (, -) 0 1 2 |."0 1 (0 0 1)   NB. the 6 ways to move to a new face
   ib =. ((_1 > <./"1) +: (22 < >./"1))  NB. y is nx3 cube locations; result is 'in bounds', true if cube is in the playing area

Now I'll write the verb for diffusion. I will start at a point outside the rock and move to neighbors. At each step I want to have

(coordinates of all cubes found to be in the air) ; (frontier: the coordinates first entered in the previous step)

Each step advances one cube from the frontier:

  • find neighbors of the frontier
  • discard any that
    • have been previously visited
    • move to an area filled by the rock
    • are outside the playing area
  • add the surviving neighbors to the list of cubes in the air, and make the surviving neighbors the frontier for next time
   (;   [: ,/ faces&(+"1/))&>/ 2 # < ,: _1 _1 _1
+--------+--------+
|_1 _1 _1|_1 _1  0|
|        |_1  0 _1|
|        | 0 _1 _1|
|        |_1 _1 _2|
|        |_1 _2 _1|
|        |_2 _1 _1|
+--------+--------+

This a stripped-down version of the verb for diffusion. It is a hook executed between the two opened boxes of the argument (because of the &>/). The right side of the hook ([: ,. faces&(+"1/)) operates on yalone, finding the neighbors and joining the first two axes to form a table; the left side of the hook, stubbed out as (;), operates between x and the result of the right side. The argument is a cell outside the rock, as both the frontier and the total cell-to-date.

   (([ (, ; ]) -.~)   [: ,/ faces&(+"1/))&>/ 2 # < ,: _1 _1 _1
+--------+--------+
|_1 _1 _1|_1 _1  0|
|_1 _1  0|_1  0 _1|
|_1  0 _1| 0 _1 _1|
| 0 _1 _1|_1 _1 _2|
|_1 _1 _2|_1 _2 _1|
|_1 _2 _1|_2 _1 _1|
|_2 _1 _1|        |
+--------+--------+

The left side of the hook is replaced by its final version (([ (, ; ]) -.~)) which is a fork that removes items from the frontier that have been visited already, and then creates the result which is (all cubes in the air including new frontier;new frontier)

   (([ (, ; ]) -.~)   [: (#~ ib) cubes -.~ [: ~. [: ,/ faces&(+"1/))&>/ 2 # < ,: _1 _1 _1
+--------+--------+
|_1 _1 _1|_1 _1  0|
|_1 _1  0|_1  0 _1|
|_1  0 _1| 0 _1 _1|
| 0 _1 _1|        |
+--------+--------+

3 more steps have been added: discarding out-of-bounds cubes ([: (#~ ib)), discarding cubes inside the rock (cubes -.~), and discarding duplicate cubes ([: ~.). That's the final version.

   diffuse =: (([ (, ; ]) -.~)   [: (#~ib) cubes-.~ [: ~. [: ,/ faces&(+"1/))&>/
   diffuse^:2  (2) # < ,: _1 _1 _1
+--------+--------+
|_1 _1 _1|_1 _1  1|
|_1 _1  0|_1  0  0|
|_1  0 _1| 0 _1  0|
| 0 _1 _1|_1  1 _1|
|_1 _1  1| 0  0 _1|
|_1  0  0| 1 _1 _1|
| 0 _1  0|        |
|_1  1 _1|        |
| 0  0 _1|        |
| 1 _1 _1|        |
+--------+--------+

diffuse^:2 executes diffuse twice, first on the y argument and then again on the result returned by the first execution. All I have to do is execute diffuse repeatedly until the result stops changing, and I will have the complete list of cells that are in the air. Then I just need to count the number of neighbors of cells in the rock that are in the air.

   # (,/ faces +"1/ cubes) ([-.-.) 0 {:: diffuse^:_ (2 # < ,: _1 _1 _1)
58

diffuse^:_ executes diffuse repeatedly until the result stops changing. Set intersection ([-.-.) gives all the items of x that are also cells of y.