ShareMyScreen/AdventOfCode/2022/08/TreetopTreeHouseJP
Entire solution
i8=: "."0;._2 freads '08.txt'
NB. Part 1: how many trees are visible from outside
ou =: [.+.&. NB. u +. u&.v i.e. or-under
part1=:[: +/@, ({:>>./@}:)\ ou |. ou |:
NB. Part 2: scenic scores: from each tree, how many other trees of equal or shorter length can be seen? product of 4 directions
to=:<. + i.@(+_1+2*0&<:)@:-~
NB. take line of trees with current tree first, count seen trees (monad)
see =: ((1-~#) <. 1 >:@i.~ {. <: }.)
NB. left and right take array of trees as x and return y to 0 and y to #, resp.
left =: {~ ] to 0: NB. C to 0
right =: [{~ ] to <:@#@[ NB. C to N
vis =: left *&see right NB. product of visible distances left/right
row =: {~ {. NB. a row of trees (horizontal), taking x: wood, y: rownum
col =: {"1~{: NB. a column of trees (vertical) taking x: wood, y: colnum
NB. lr and ud take: x: forest ; y: current tree loc
lr =: row vis {:@]
ud =: col vis {.@]
part2 =: [: >./ ((lr*ud)"_ 1 >@,@{@;&i./@$)
(part1;part2) i8
The data
We get a matrix of numbers representing tree heights as input. As each tree is a single character, we know they are between 0 and 9. The matrix is also not too big:
$i8 99 99
Let's have a look using Viewmat:
load 'viewmat' viewmat i8 NB. output see "Input of Day 8"
Part 1
Part 1 asks how many trees are visible when looking from outside inwards across the four edges of the wood.
I reasoned like this: looking from the top side of the wood, for the last tree of a row of the trees to be seen, it has to be higher than the highest preceding tree. In J, this translates rather directly to:
( {: > >./@}: ) \
NB. last > max of preceeding for all prefixes
Although J automatically does this for all columns at once, I bet in terms of computation this is sub-optimal, but for this size of problem, clarity is more important than shaving off some hundredths of a second. It's handy to check our assumptions on this code, again using viewmat:
viewmat ({:>>./@}:)\ i8 NB. output see "Top down"
We see the top line of trees are all seen, which makes sense, but there's a strange bowl shape... Can we see also the tree height in the same picture? Sure we do, because this line of code returns a matrix of the same size as i8:
viewmat i8 * ({:>>./@}:)\ i8 NB. output see "Top down, colors"
This looks good, tree heights always increase from the edge inwards.
To apply the same from the bottom up, I initially wrote it as (but will come back to it shortly):
({.>>./@}.)\.
That is, replacing {. and {: with {. and }., and \ with \. . Now, a tree can be seen if it is visible from top or bottom. Doing the same from left and right is straightforward: transpose (now left and right are at the top and bottom) do topbottom and transpose back. This last one is important: if not, the right trees don't correspond anymore when or'ing them together, possibly counting some trees double.
topbottom =: ({:>>./@}:)\ +. ({.>>./@}.)\
leftright =: topbottom&.|:
visible =: topbottom +. leftright
part1 =: [: +/@, visible
viewmat visible i8 NB. output see "Trees that can be seen and their height"
When going through this solution to do this write-up, it occurred to me I could also define visible using a custom adverb:
visible=: topbottom {{u+.u&.|:}}
visible
topbottom +. topbottom&.|:
Just for fun, can I condense this even more? Yes! In j903, modifier trains were reintroduced, after a long absence. This is the first time I came across a problem where they made sense, and were not mindbogglingly complex. First step is seeing what we need to combine:
- u , which is equivalent to Lev, [. ;
- the +. verb;
- u&.|:;
- the result should be an adverb.
Well, after looking for a solution in the table (linked in the modifier trains page above), there does not appear to be an adverb-producing train that does what I want. Second try: &.|: is an adverb, but if, instead of trying to produce an adverb, I aim for a conjunction, and give |: as right argument, I do find the following train: C0 V1 C2, which produces (u C0 v) V1 (u C2 v). The conjunction to be created is thus [.+.&.. As conjunctions can be partially applied to a verb to form an adverb, the adverb I was looking for is ([.+.&.)|:.
Can I get rid of the parentheses? Yes, because that's (apparently, had to try it out myself) how parsing works for J. A nice way to see how parsing works is using the trace tool:
load 'trace' trace '[.+.&.|:' --------------- 5 Trident ---- [. +. &. [. +. &. --------------- 6 Bident ----- [. +. &. |: ([. +. &.)|: ==============================
And now for the real beauty of J: By not allowing me to write the adverb (maybe by accident?), I ended up with a broader conjunction that I named ou or, "or-under":
ou=:[.+.&.
After having defined this, it occurred to me that the SAME mechanism also applies to my topbottom verb, combining ou with reverse (|.): Instead of manually exchanging {:, }: and \ with {. , }. and \., I could use ou |. instead, and write topbottom as:
topbottom =: ({:>>./@}:)\ ou |.
NB. or for part 1 as a whole:
part1=: [: +/@, ({:>>./@}:)\ ou |. ou |:
Just as a note: if you're starting exploring J, I'd keep modifier trains for last...
Part 2
Part 2 asks for finding the highest scenic score from all trees. The scenic score is defined for each tree as the product of how far one could see, including the first tree that blocks the sight, in each of the 4 directions.
Here I took a fairly straightforward blunt-knife approach, and simulate all positions from each tree (which would be 99*99*2*99, only about 2 million comparisons.).
For this we need all grid coordinates, i.e. the Carthesian product, { on the boxed lists of indexes covering the entire wood:
($ ; 5&{. , _5&{.) >@,@{@;&i./@$ i8
┌──────┬─────┐
│9801 2│ 0 0│
│ │ 0 1│
│ │ 0 2│
│ │ 0 3│
│ │ 0 4│
│ │98 94│
│ │98 95│
│ │98 96│
│ │98 97│
│ │98 98│
└──────┴─────┘
Now I feed the wood as left argument, and the coordinates one by one. For each coordinate we'd want to know the product of all sides, and I happened to group them as left-right and up-down similarly as before. This returns the scenic score for each tree, after which we should simply take the maximum:
part2 =: [: >./ ((lr*ud)"_ 1 >@,@{@;&i./@$)
Off to write lr and ud: we need to get the right row from the wood with the hook
row =: {~ {.
with its x being the wood, and y being a pair of coordinates. Having this row, we need to get the trees on the left and on the right of the current tree, i.e. if y is the column of the current tree, on the left we see trees y-1 to 0 (decreasing) and on the right y-1 to the last. For doing this, I define this little helper function, that implements literally "to" as in "numbers from 0 to 10". The part between parentheses was slightly harder than expected to get right, because it has to deal with inverted ranges (see the left range below) and also ranges where the end points are the same (e.g. 1 to 1 equals ,1).
to=: <. + i.@(+_1+2*0&<:)@:-~
With this verb, the left and right ranges of all possible trees become (left argument is row, and right is coordinate):
left =: [{~ ] to 0: NB. y to 0
right =: [{~ ] to <:@#@[ NB. y to N
Now we need a verb that, given a range of trees, can determine how far we can see (let's call it see). Note that in the definition of left and right, I included the tree at the current column y? That's because it is needed for the comparison: like this, see can be written as a monad, making it easy to apply using compose (&). The length of our sight is the position of the first tree that's higher, or the edge of the wood:
see =: (1-~#) <. 1 >:@i.~ {. <: }.
NB. edge min 1 index(+1) tree <: others
All parts needed for lr have been defined. I define vis because I'm going to reuse it for ud:
vis =: left *&see right
lr =: row vis {:@]
Defining up-down (ud) boils down to defining col to replace row, and keep all the rest the same:
col=: {"1~ {:
ud =: col (left *&see right) {.@]