ShareMyScreen/AdventOfCode/2022/08/TreetopTreeHouse

From J Wiki
Jump to navigation Jump to search

The Problem << >>

Back to an easy one. For each of the 4 directions, I want the running maximum of the heights before each position, i. e. not including the position itself. To get that I shift the running maximum one position, either before or after the maximum calculation. To check trees to the left, I would use

   ] trees =. (0&"."0) onaoclines
3 0 3 7 3
2 5 5 1 2
6 5 3 3 2
3 3 5 4 9
3 5 3 9 0
   (_1 |.!._1 >./\)"1 trees  NB. |.!._1 shifts in _1, to make all edge trees visible
0 3 3 3 7
0 2 5 5 5
0 6 6 6 6
0 3 3 5 5
0 3 5 5 9

I check all 4 directions with

   ((_1 |.!._1 >./\)"1 <. (1 |.!._1 >./\.)"1 <. (_1 |.!._1 >./\) <. (1 |.!._1 >./\.)) trees
_1 _1 _1 _1 _1
_1  0  2  2 _1
_1  3  3  2 _1
_1  3  3  5 _1
_1 _1 _1 _1 _1   

and count the number of visible trees with

   +/ , trees > ((_1 |.!._1 >./\)"1 <. (1 |.!._1 >./\.)"1 <. (_1 |.!._1 >./\) <. (1 |.!._1 >./\.)) trees
21

For Part 2, I must find the visibility in each of 4 directions and multiply them together, reporting the largest product. I don't want to calculate visibility from scratch at each point - that would possibly have O(n3) running time. Instead I will write a verb that will find the visibility of each point in a list, looking toward the beginning of the list. I'm not sure this is fast but it's easy.

This is a new one for me - a chance to use Fold. As I move along the list, I will keep track, for each height h, of the index in the list of the last value h or higher. The result at each position is the index value before the update.

The value going into each position in Fold is the list of indexes for each h and the result value at the previous position. The v operand to Fold will calculate that. The u operand will extract the result value so that the final result is a list. The input for each position will need to be the height of the tree and its index, so I'll append the index to the height.

I'll need a verb to calculate the result for each step, and another to update the h-indexes. I'll start by writing them.

   th10 =. 9 8 7 7 6 6 6 6 4 2  NB. A possible value of the h-index list, for testing
   res =. {.@[ { ]  NB. x is (height,index), y is h-index list, result is position of last visible index
   5 10 res th10
6
   upd =. {:@[`(i.@>:@{.@[)`] }    NB. x is (height,index), y is h-index list, this modifies y for this tree
   5 10 upd th10
10 10 10 10 10 10 6 6 4 2

res merely selects the h-index for the given height.

upd stores the index into leading positions of the h-indexes, storing for each value ffrom 0 to height inclusive. In the example the height 10 is stored into the first 6 positions.

Now I can put the Fold together.

   ('';10$0) (0&{::) F:. ((res ; upd) 1&{::) (,. i.@#) 4 7 4 5 8 2
0 0 1 1 0 4

The v operand to Fold takes a left argument of (height,index) and a right argument of (previous result;h-indexes). The first thing it does, 1&{:: , discards the previous result and brings out the h-indexes. The other components, res and upd, create the result and update the h-indexes. For each of these the left argument is (height,index) and the right argument is h-indexes. height can be had by {.@[ and index by {:@[.

The result on the test data shows that indexes 0-1 can see back to index 0, 2-3 back to index 2 where the 7-high tree is, 4 all the way back to 0, and 5 back to 4.

To get the visibility, I subtract the Fold result at each position from the index at that position. That makes the full verb

   vis =. ((] - ('';10$0) (0&{::) F:. ((res ; upd) 1&{::) ,.)   i.@#)"1
   vis 4 7 4 5 8 2
0 1 1 2 4 1

That's correct.

With vis in hand the solution is easy. I apply vis in the 4 directions, take the products. For each application of vis I transpose/reverse the array so that vis can operate on rows left-to-right, and then undo the reordering. This operation-then-inverse is done by dual (u&.:v) where I use &.: rather than &. so the reordering is done at infinite rank.

   (vis * vis&.:(|."1) * vis&.:|: * vis&.:((|."1)@:|:)) trees
0 0 0 0 0
0 1 4 1 0
0 6 1 2 0
0 1 8 3 0
0 0 0 0 0

That's right for the example data. All that's left is to find the maximum:

>./ , (vis * vis&.:(|."1) * vis&.:|: * vis&.:((|."1)@:|:)) trees
8