ShareMyScreen/AdventOfCode/2022/08/TreetopTreeHouse
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