https://adventofcode.com/2021/day/9
The day 9 puzzle dealt with a height map, with heights represented as digits.
sample=: "."0;._2 {{)n
2199943210
3987894921
9856789892
8767896789
9899965678
}}
The first part of the puzzle asked for us to find the "lowest" points
on the heightmap. "Lowest" here meant that horizontally or vertically
adjacent locations on the heightmap were higher. (And then we sum
1+the heights of those locations.)
There's several ways to solve this problem. One approach would use
tessellation ((1,:3 3)F;._3 ...). This isn't a very good approach,
though, because it's rather inefficient for this problem.
Another approach, uses a pair of scans to find the lowest along one
dimension (and then using transpose to use the same code against the
other dimension.
low=: (2 </\ (,1+{:)) * (2 >/\ (>:@{.,]))
Another approach would use *2 -/\ and then look for _1 1 pairs. Also,
I could have padded with 9, instead of computing a value, since any
lowest point will be lower than 9.
Anyways, finishing this up:
lowest=: low&.|: * low
aoc9a=: {{
+/1+(#~&, lowest) y
}}
For the second part we needed to find the size of (number of locations
within) the three largest basins. A basin is a region surrounded by 9s
in the heightmap.
For this, we can start with the lowest points, and give them positive
numeric id, and then repeatedly extend that id to adjacent points
(excluding points marked with a height of 9). When this stops changing
the representation of the map, we ravel that, take take the nub
(excluding the locations which had a height of 9 -- these will have a
height of zero). Then count the occurences of each id, downsort (\:~)
and sum the first three values.
extend=: {{
(x~:9) * (_1&(|.!.0) >. ] >. 1&(|.!.0))y
}}
I left the x~:9 in here rather than after extending both horizontally
and vertically to hopefully speed things up a bit (each horizontal
extend was after each vertical extend) without leaking across
diagonals. But I didn't benchmark this to see if it made a significant
difference for the puzzle data.
basins=:{{
l=. lowest y
k=. 1+i.+/,l
base=. ($l)$(,l)#inv k
whilst. -. b-:base do.
b=.base
base=. ((|:y)&extend&.|: b) >. y extend b
end.
}}
I probably should have used base=. ($l)$,l*1+i.$y but that's a minor
issue. Also, this approach lets me do:
(basins sample){'.abcd'
aa...bbbbb
a.ccc.b.bb
.ccccc.d.b
ccccc.ddd.
.c...ddddd
aoc9b=:{{
*/3 {. \:~ #/.~0 -.~,basins y
}}
aoc9b sample
1134
And that's about it for day 9. This is still relatively
straightforward, but you can see that it's already more involved than
day 1.
Thanks,
--
Raul
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
