Jan-Pieter, The use of shifting and padding to produce multiple tables and then operating on those tables was illuminating to me. I often find myself writing verbs to process lists and then applying them to tables by transposing or fiddling with the rank conjunction. For example, this was my solution to part 1 of day 9, which uses the same idea as Raul's solution:
lows1 =: ([: 2&(</\) ,&9) *. ([: 2&(>/\) 9&,) lows =: lows1&.|: *. lows1 risk =: [: +/@:, lows ([ + *) ] For part 2, how did you arrive at the insight to repeatedly apply max to the indices until convergence in your basins verb? I confess that I had to take your solution apart and use the power conjunction with 1, 2, 3, 4, 5, 6, 7 (solution), and 8 (convergence) to understand how it worked. I would never have arrived at that solution on my own. I learned a lot from your code. Thank you! Mike -- Michael P. Manti [email protected] > On Dec 30, 2021, at 10:01, 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
