It's nice to see another take on the same problem.
Differences with Raul's solution: for part A, I used shifted and padded
versions of the array to find the minima's. For the basins, I did not use
the lowest points, but just gave all points (not being edges = 9) a unique
id, then assigned the max index amongst each point and its neighbors and
repeated until convergence. The scoring is similar.
My code was as follows:
in=: [: freads '.txt' ,~ _2 {.!.'0' ": NB. input verb
NB. Day 09: local minima lava-tube field
i09=: "."0;._2 in 9
NB. Part A:
NB. find sum of scores of local minima (score=val+1) in 4 connected
neighbors
NB. shifts in principal directions
sh4=: 0 1,1 0,_1 0,:0 _1
NB. pad with 11 (>9+1) to detect minima on edges
a09=: [: +/@, (] * ] *./@:(<"2) sh4 |.!.11 ])@:>:
NB. Part B:
NB. find 3 largest basins separated by edges of 9's, multiply their sizes
NB. basins returns map with edges (0) and basins having unique id's (>0)
NB. non-edge * max self&neigbors repeat point indices
basins=: 9&~: (* [: >./ ] , sh4 |.!.0 ]) ^:_ >:@i.@$
NB. sizes: takes basins result, count how many (excluding edges = 0)
sizes=: [: #/.~ -.&0@,
NB. final solution
NB. prod 3 largest sized basins
b09=: [: */ 3 {. \:~ @ sizes@:basins
(a09;b09)i09
}} dod 09''
On Thu, Dec 30, 2021, 02:52 Raul Miller <[email protected]> wrote:
> 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
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
