I think that you have assumed that because a location on the grid has been visited that you have found the lowest cost path to that location on the grid.
This ignores the possibility that you visited it through a "high risk path" where another, longer path would have lower risk. The structure of the second part suggests that they designed the puzzle such that the lowest cost path was circuitous like that. I hope this helps, -- Raul On Wed, Jan 5, 2022 at 3:23 PM Jan-Pieter Jacobs <[email protected]> wrote: > > I started out with a classic J approach of shifting the array around, and > keeping score in an array, having non-visited nodes set to max (2e9, rather > than _ to keep the solution in the integer domain). > > NB. Day 15: Chiton navigation > in=: [: freads '.txt' ,~ _2 {.!.'0' ": NB. read input of day y (given as > num) > i15=: "."0;._2 in 15 > NB. Part A: path with least risk (risk counts when moved to, not start) > NB. test output: 40 > t=: "."0;._2 {{)n > 1163751742 > 1381373672 > 2136511328 > 3694931569 > 7463417111 > 1319128137 > 1359912421 > 3125421639 > 1293138521 > 2311944581 > }} > max=: 2e9 NB. integer "inf" > NB. idea: start with an 100 100$10000{.!.max 0 array to keep risk of > minimum risk path to each grid node. > NB. start creates the risk array,given y:input array > start=: ($ 0 {.!.max~ */)@$ > > NB. verb shifting array in 4 principle directions, + original, padding with > max > sh5=: (5 2$0 0 0 1 1 0 _1 0 0 _1)&(|.!.max) > > NB. shortest path algorithm based on shifting the score array around at > every step. This results in computing the result for all positions at once, > also before they are reached by a path with risk<max. This is very > inefficient, but good enough for part A. > a15a=: [: {:@, ] (+ >:&max <.@:* <./@sh5)^:(max +./@:<: ,@])^:_ start > > a15 t > 40 > > This worked fine but was too slow to my taste on part b, aside of giving > the wrong result on part B, while the result on test data is correct: > > NB. Map is actually a lot larger, 5 times replicated as follows: > NB. Kronecker addition (analogous to kronecker product), see > https://code.jsoftware.com/wiki/Essays/Kronecker_Product . > ka=: [: ,./^:2 +/ > NB. repliction happens as Kronecker addition with 5]\i. 9, but wrapping > around from 9 to 1. > rep=: 10 |&.<: (5 ]\ i. 9)&ka > > NB. First implementation; slow, but simple. > b15a=: a15a@rep > timespacex 'r=:b15a t' > 0.030089 329952 > r NB. correct test result > 315 > timespacex 'b15a i15' NB. slow, and wrong result on actual input data. > 34.1406 2.5168e7 > > So I implemented a pretty literal Dijkstra algorithm (b15b) which was a lot > faster, worked on the test data, but not on my actual input :/ (same result > as b15a). > > NB. Trying more vanilla Dijkstra, keeping state of current and done nodes > NB. shift in 4 direction for getting neighbors (_1 for edges) > sh4=: (([:(,-)],:|.)0 1)&(|.!._1) > NB. verb to construct array of neighbors (_1 indicates missing neighbor; > edge) > getneigh=: |:@:(,"2)@sh4@i.@$ > > a15b=: {{ > NB. neighbors for input array > neigh=. getneigh y > NB. values (risks) of y (,y) > val=. ,y > NB. visited nodes is an array of shortest path lengths for every node id. > Unvisited nodes are initialised to max. Initially 0 is considered visited, > value 0. > vis=. (#neigh) {.!.max] 0 > NB. list of current nodes, initially the neighbors of 0 > cur=. _1 -.~ 0{neigh > while. #cur do. NB. nodes left to process? > NB. minimum values of current node's neighbors which were previously > visited > NB. min visited non-edge (note, since initialised as max, > non-visited nodes do not influence the result) > minneigh=. ([:<./vis{~ _1-.~])"1 cur { neigh > NB. update shortest paths to current nodes > vis=. (minneigh+cur{val) cur} vis > NB. set new current nodes, i.e. non-visited neighbors of current nodes > NB. unique list sel non-visited , edges removed from current node's > neighbors > cur=. ~.,([: (#~ max=vis{~]) _1 -.~ ])"1 cur {neigh > end. > NB. one step visits current nodes (i.e. finds score+<./neighbor path > length), adding the current nodes to the visited ones; and adds the > neighbors of current nodes not yet in the visited nodes to the visited > nodes, along with all their neighbors. > {:vis > }} > b15b=: a15b@rep > > b15b t NB. result on test data correct, but still not one actual input > i15 > 315 > 10 timespacex 'b15b i15' > 1.73428 1.15361e7 > > So, this approach, although a lot wordier, is almost 20 times faster, but > is still "wrong" on the actual input. > While debugging the explicit Dijkstra approach, I noticed the current nodes > and previously visited nodes are, given the geometry of the problem, all on > anti-diagonals, which can be conveniently gotten to using </ instead of > explicitly constructing the neighbor array neigh, and doing all operations > based thereon. So I thought to try that approach and gave it a go. > > The idea is that in a rectangular grid, w=th starting node 0 0, doing > Dijkstra's algorithm involves anti-diagonals exactly as done with <./ . > current weights (i.e. current anti-diag) are added to pairwise minimum > between shortest path lengths of previous neighbors, all located on the > previous anti-diagonal. This maps exactly to an operation inserted between > anti-diags (see u&.>) reversed, to start from the top left, rather than > from the bottom right. Not that it actually matters for the symmetric > problem at hand. Amend is needed to zero the weight of the start tile. The > only thing needing taking care of is padding for the first antidiagonals > (until the corners are reached); this is done by padrifshort, which pads > the right (shortest paths) with a high number (max) such that it does not > influence the minimum. > > NB. open cur + p. min padded right between antidiags with 0 0 set to 0 > a15c=: [: > [: ([ + 2 <./\ padrifshort)&.>/@|. [: </. 0 (<0 0)} ] > NB. pad right argument with max if it's shorter than the left. > padrifshort=: ]`(max (,,[) ])@.(>&#) > > b15=: b15c=: a15c@rep > > I was very satisfied with this find, but frustrated with it being a *third* > solution working on the test data, but not on the actual input (which > agrees, moreover with both b15a and b15b): > > b15c t > 315 > timespacex every 'b15a i15';'b15b i15';'b15c i15' > 42.3583 2.5168e7 > 3.18975 1.15361e7 > 0.169335 4.58714e6 > 2 =/\ (b15a,b15b,b15c) i15 NB. all the same result > 1 1 > > So at this point, with test data giving the right result, for 3 entirely > different implementations, that all agree on the "wrong" result, I start > wodering whether the result that Advent of Code expects is the right one. > Could you please tell me whether my code works on your input? > > Otherwise, I invite all the smart people here to call out my mistake(s), > and liberate me of this nagging feeling of having to skip a problem. > > This is also the last I solved so far, so I sign off of this thread for now! > > Thanks, > Jan-Pieter > > > On Wed, Jan 5, 2022, 03:55 Raul Miller <[email protected]> wrote: > > > https://adventofcode.com/2021/day/15 > > > > For day 15, we had a cave with a "risk level map" and our task was to > > find the least risk path through the cave (from the top left corner to > > the lower right corner of the map). > > > > The provided example map looked like this: > > > > sample=: {{)n > > 1163751742 > > 1381373672 > > 2136511328 > > 3694931569 > > 7463417111 > > 1319128137 > > 1359912421 > > 3125421639 > > 1293138521 > > 2311944581 > > }} > > > > I didn't have any really great approach here, so I just used > > Dijkstra's shortest path algorithm (with connections horizontally and > > vertically and risk being the "path length" to enter a point on the > > map). > > > > unpack=:{{ > > _&".@>;._2 y > > }} > > > > dir=: 1 0,0 1,_1 0,:0 _1 > > > > NB. extend each path y in each of the available directions (limited by x) > > NB. discard "usless" paths which immediately return to its previous > > location > > extend=:{{ > > if.1=#y do. > > NB. Hack: avoid length error from uselessness test when starting > > 0 0,:1 _<.x return. > > else. > > next=. (x #: {:y)+"1/dir > > paths=. ,/(|:y),"1 0"_1 x#.next > > tolow=. ,/next +./ .< 0 > > tohigh=. ,/next +./ .>: x > > useless =. =/"1 (_3 _1){"1 paths > > |: paths #~ -.tolow+.tohigh+. useless > > end. > > }} > > > > a15=:{{ > > i=. 0 > > 'gridshape movecosts'=. ($;,) unpack y > > mincosts=. 0,_#~1-~#movecosts > > newpaths=. i.1 1 > > while. #newpaths do. > > NB. find all 'newly' reachable locations > > newpaths=. gridshape&extend newpaths > > newcosts=. ((_2 { newpaths) { mincosts) + ({: newpaths) { movecosts > > NB. discard everything which is not an improvement > > k=. +/keep=. newcosts < ({: newpaths) { mincosts > > if.0=k do. break.end. NB. done? > > newpaths=. keep #"1 newpaths > > newcosts=. keep # newcosts > > loc=. {: newpaths > > costbyloc=. loc <.//. newcosts > > NB. pick best of each of the new competing paths > > k=. +/keep=. newcosts = costbyloc {~ (i.~ ~.) loc > > if. k~:#keep do. > > newpaths=. keep#"1 newpaths > > newcosts=. keep#newcosts > > loc=. {: newpaths > > end. > > NB. pick arbitrarily when we have multiple new same-cost > > NB. paths leading to the same place > > k=. +/keep=. (i.@# = i.~) loc > > if. k~:#keep do. > > newpaths=. keep#"1 newpaths > > newcosts=. keep#newcosts > > loc=. {: newpaths > > end. > > NB. record results > > mincosts=. newcosts loc} mincosts > > NB. show progress > > echo (i=.i+1),($newpaths),{:mincosts > > end. > > {: mincosts > > }} > > > > I threw the echo statements in there so that I could watch the > > algorithm's progress. This is basically an exhaustive search. > > > > I could have achieved some efficiency here by discarding older parts > > of the paths, and generally speaking this could have been tighter > > code. I should have been able to merge the "lowest cost" by location > > step and the "pick arbitrarily when multiple paths lead to the same > > location" step. And, some lines might wrap here in this email message > > (hopefully not). > > > > But this worked, and I can understand the code. > > > > For part B, it turns out that our map was a map of one of 25 tiles of > > the actual cave. We add each value from +/~i.5 to this map (and wrap > > values greater than 9 back to 1) to get the "real map". Which mostly > > means it takes on the order of 25 times longer to find the shortest > > path (probably a little longer than that because of inefficiencies in > > my code). > > > > a15 sample > > spits out 18 lines of progress reports and then returns the value 40 > > > > In other words, my part B looked like this: > > > > tile=:{{ > > ,LF,.~' '-."1~":>:9|<:>,.each/,each/(+/~i.5)+each<unpack y > > }} > > > > b15=: {{ > > a15 tile y > > }} > > > > b15 sample > > spits out 98 lines of progress reports and then returns the value 315 > > > > FYI, > > > > -- > > 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
