http://en.wikipedia.org/wiki/Shortest_path_problem
----- Original Message -----
From: Dan Bron <[EMAIL PROTECTED]>
Date: Thursday, December 28, 2006 8:52 am
Subject: [Jprogramming] I know a shortcut
> I have a problem to which I'd like a beautiful J solution. I know
>
> it's out there. But I can't find it.
>
> The basic problem is a have a bunch of long "paths". Now, I know
> some
> "shortcuts" down these paths. For example, let's say I want to
> get to
> point X:
>
> $ A-B-C-D-E...-X
>
> Now, say I know shortcuts to points E, M, and T, labeled sE, sM,
> sT,
> respectively. I now have several ways to get to point X:
>
> $ A-B-C...-X
> $ sE-F-G...-X
> $ sM-N-O...-X
> $ sT-U-V...-X
>
> What I want is the shortest way to get to X. In this case, I'd
> choose
> the last path, because T is closest to X.
>
> So, given a Nx2 table of shortcut ; path-equivalent-to-shortcut
> and
> a list of target paths, I want the targets shortened as much as
> possible (if no reduction is possible, the target remains unchanged).
>
> A concrete example (somewhat) analogous to my problem would be to
> provide an inverse to jpath_z_ . The verb takes a shortcut and
>
> resolves it to a fully qualified path. What I want is the
> opposite:
> Given a fully qualified path, it should return the shortest
> possible
> shortcut.
>
> So, provide a dyadic verb shortcut such that:
>
> pathj =: (2 {."1 SYSTEMFOLDERS_j_,USERFOLDERS_j_)&shortcut
>
> eg =: <;._2 noun define
> ~Classes\plot\jzplot.ijs
> ~Main\sysenv.ijs
> ~config\recent.ijs
> ~user\labs.txt
> )
>
> eg -: pathj jpath&.> eg
> 1
>
>
> I have included an (ugly, explicit, nested-loop) model of
> shortcut
> in the postscript.
>
> It is important to note that jpath is "eached" but pathj
> isn't.
> (Of course, in the body of the model, each path is treated
> independently, but I don't think in a "beautiful" solution that
> should
> be so.)
>
> A lot of paths will be prefixes of others, and having resolved
> such a
> path once, we should be able to reuse that knowledge for an
> efficient
> solution (would M. help here?). Another way of putting it is
> that
> shortcuts can be relative to other shortcuts.
>
> Note also that file systems permit backtracking with "\..", and my
>
> model reflects this. In my real problem however, that's not
> possible,
> so you may feel free to ignore the possibility in your solution
> (you
> can treat shortcuts followed by "..\" as non-viable/infinite
> length).
> But bonus points for generality if you provide for the possibility.
>
> -Dan
>
> PS: Here is a model:
>
> shortcut =: dyad define
>
> r =. 0 $ a:
> for_file. y do.
> cutfile =. PATHSEP_j_ cut tolower^:IFWIN32 > file
>
> file_candidates =. file
> for_nick_dir. x do.
> 'nick dir' =. nick_dir
> cutdir =. PATHSEP_j_ cut tolower^:IFWIN32 dir
>
> a =. i.&0@:=/ cutdir,:cutfile
> relative =. (a~:0) # ('~',nick) ; a }. (#cutdir) # <'..'
> candidate =. ; }:,(<'\') ,.~ a: -.~ relative , a }. cutfile
>
> file_candidates =. file_candidates , <candidate
> end.
>
> r =. r , ({~ [: (i. <./) #&>) file_candidates -. a:
> end.
>
> r
> )
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
