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
