Hi Mike, I'm glad my code was useful. If I recall correctly, I picked up the connected component approach from how it's implemented in Matlab ( https://nl.mathworks.com/help/images/ref/bwconncomp.html), although I don't exactly recall whether that uses the shifting. The (excellent) Learning J book also mentions the padding and shifting approach for implementing Conway's game of life, which is also based on considering neighbors, noting it's far faster than using Cut (u;._3). Anyhow, it's not exactly "my" insight ;). I have previously used the same approach a few times in codegolf (here: https://codegolf.stackexchange.com/questions/40798/square-circle-triangle-gear/41107#41107 and here: https://codegolf.stackexchange.com/questions/32015/are-you-in-the-biggest-room/40205#40205 ).
A lot of these array minded ways of thinking can be picked up from the excellent documents on the J website (e.g. the Essays). Jan-Pieter On Sat, Jan 1, 2022, 19:17 Michael P. Manti <[email protected]> wrote: > 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 > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
