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
