Was not in shape to implement the shortest path algorithm, therefore
searched for a graph package and found igraph.org which offers an R
interface. Together with the Rserver addon this reduced the task to create
the edge list for the graph with the risk levels as weights - note that
igraph needs the nodes to be greater than 0. Here's the J session:
rd=: "."0;._2
d=: rd 0 : 0
1163751742
1381373672
2136511328
3694931569
7463417111
1319128137
1359912421
3125421639
1293138521
2311944581
)
load'stats/r/rserver'
Rcmd'library(igraph)'
Attaching package: 'igraph'
The following objects are masked from 'package:stats':
decompose, spectrum
The following object is masked from 'package:base':
union
es=: ,@}: ,. ,@}. NB. Edges utility to be applied on i.$d
ltr=: 3 : 0 NB. Lowest total risk
'e' Rset >: (, |."1) (es, [: ,/ es"1) i.$y NB. Edge list
'r' Rset (([:,}.), ([:,}."1), ([:,}:), [:,}:"1) y NB. Risk levels
Rcmd'g <- graph_from_edgelist(e)'
Rcmd'E(g)$weight <- r'
+/ }. (,y){~ <: Rget'unlist(shortest_paths(g,1,', ')$vpath)',~ (, ':'&,)":
#,y
)
ltr d NB. (*)
40
mm=: {{ u/ (i.5) (9&|@+)&.(a:`<:)"0 _ y }} NB. Multiply matrix adverb
ltr ,.mm ,mm d NB. (**)
315
On Wed, Jan 5, 2022 at 3:55 AM 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
