Thank you for the explanation and the reading material. In the case of Learning J and some of the essays, it's *re-reading" material.
Mike -- Michael P. Manti [email protected] > On Jan 1, 2022, at 15:42, Jan-Pieter Jacobs <[email protected]> > wrote: > > 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
