That's a good point.
For the second part, I could have used
basins=:{{
base=. i.$y
whilst. -. b-:base do.
b=.base
base=. ((|:y)&extend&.|: b) >. y extend b
end.
}}
instead of my
http://jsoftware.com/pipermail/programming/2021-December/059487.html
implementation
In the context of aoc scoring, this simplification would have been a
significant advantage.
Thanks,
--
Raul
On Thu, Dec 30, 2021 at 10:01 AM Jan-Pieter Jacobs
<[email protected]> wrote:
>
> 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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
