Thanks to Raul's very accurate observations, I patched two of my previously
posted solutions (The array based tacit one and the explicit one).
The approach based on </. is less trivial to fix, as it destroys previously
visited nodes' states by using insert (/) between anti-diagonals.
Indeed, my approamh assumed that once visited, nodes would no longer
change. This is disproven with a very simple example:
ts=: 0 1 0 0 0, (3#3 5$0 1 0 1 0), 0 0 0 1 0
the previous approach,
a15awrong=: [: {:@, ] (+ >:&max <.@:* <./@sh5)^:(max +./@:<: ,@])^:_ start
was wrong because: it stops when no more maxes are present, i.e. does not
consider paths not found at the first go. Also summation with current score
is wrong, should be max instead.
NB. now better:
max=: 2e9 NB. integer "inf"
NB. start with an 100 100$10000{.!.max 0 array repeat with steps
start=: ($ 0 {.!.max~ */)@$
NB. at each step: new shortest path length is minimum of the current with
the sum of the risk + the min shortest path to any of its neighbors
(represented by shift42)
a15a=: {:@,@(] (] <. [ + <./@sh4@])^:_ start)
sh4=: (4 2$0 1 1 0 0 _1 _1)&(|.!.max)
NB. Map is actually a lot larger, 5 times replicated as follows:
ka=: [: ,./^:2 +/ NB. kronecker addition (analogous to kronecker product)
rep=: 10 |&.<: (5 ]\ i. 9)&ka
b15a=: a15a@rep NB. recoded because slow (+-32s)
NB. Trying more vanilla Dijkstra, keeping shortest path lengths of all
nodes to (0,0) (spl), and keeping a list of active nodes, that have at
least one neighbor that changed at the last iteration.
NB. shift in 4 direction for getting neighbors (could make it a torus if
needed by removing !. in sh4).
NB. verb to construct a boxed array of neighbors
getneigh=: <@(-.&max"1)@|:@:(,"2)@sh4@i.@$
a15b=: {{
NB. neighbors for input array
neigh=. getneigh y
NB. risk values of y (,y)
val=. ,y
NB. array of shortest path lengths for every id. unvisited nodes are
initialised to max. Initially 0 is considered visited, value 0.
spl=. (#neigh) {.!.max] 0
act=. 0 {:: neigh NB. list of active nodes (nodes of which one or more
neighbors changed), initially the neighbors of 0
it=. 0 NB. #iterations: debug, see echo it below
whilst. #act do.
NB. minimum spl of the neighbors of each active node (which will be the
new candidates for being active next turn)
minneigh=. spl ((<./@:{~ >)"_ 0) cand =. act { neigh
NB. mask of active nodes which are changed because their current
shortest path length is higher than the sum of their risk and minneigh
mask =. (act{spl)>nv=.minneigh+act{val
NB. update shortest paths to active nodes in that change (i.e. decrease)
spl=. (mask#nv) (mask#act)} spl
NB. uncomment for diagnostic output (on small sample!)
NB. prints locations of act, shortest path lengths and risks
NB. echo (($y)$1 (mask#act)} 0#~#val);(($y)$spl);t
NB. echo it=. >:it
act=. mask (~.@;@:#) cand NB. new active nodes are those that changed
end.
{:spl NB. shortest path length of last node.
}}
I'm quite happy with this, as it manages part B in about 3 s on my rather
crappy phone :).
Jan-Pieter
On Thu, Jan 6, 2022, 02:15 Raul Miller <[email protected]> wrote:
> 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
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
