Given: A graph %g composed of a hash of hashes; the keys of %g are the names of the nodes of the graph, and the value of each is another hash (temporarily, call it %t); the keys of %t are other nodes in the graph that can be accessed by the current node, and the values are the distances to those nodes. So, in the case where, say "Chicago" and "Cleveland" are separated by a distance of 400, %g will look like:

%g = ( Chicago => { Cleveland=>400 },
       Cleveland => { Chicago=>400 } );
[download]

All distances are non-zero, positive values. The graph is not necessarily bidirectional (That is, if the distance from 'A' to 'B' is 1, the distance from 'B' to 'A' may not necessarily be 1, nor may it be possible to go from B to A directly.) There are no disjoint parts of the graph or dead ends, so that it is possible to go to any other point from a given point. Also, you are given two node names, $a and $b.

Find a perl golf solution that returns an array of the node names in the shortest distance route from $a to $b, including $a and $b. UPDATE as suggested by MeowChow to set the order of the sub parameters as \%g, $a, $b.

More Updating Goodness: Here's a test case for ya :-)

my %g = ( Chicago=>{ Detroit=>250,
                     Cleveland=>400,
                     Denver=>2500,
                     SF=>4000 },
          Cleveland=>{ Chicago=>400,
                       NYC=>2500 },
          Detroit=>{ Chicago=>250,
                     Cleveland=>200 },
          NYC=>{ Cleveland=>2500,
                 SF=>7500 },
          SF=>{ NYC=>6500,
                Denver=>1500 },
          Denver=>{ SF=>1500,
                    Chicago=>2500 }
        );

d( \%g, 'Detroit', 'Cleveland'); # should be ( 'Detroit', 'Cleveland' 
+)
d( \%g, 'Cleveland', 'Detroit' ); # should be 
( 'Cleveland', 'Chicago', 'Detroit' )
d( \%g, 'NYC', 'SF' ); # should be 
( 'NYC', 'Cleveland', 'Chicago', 'SF' ) OR ( 'NYC', 'Cleveland', 'Chic
+ago', 'Denver', 'SF' )
d( \%g, 'SF', 'NYC' ); # should be ( 'SF', 'NYC' )
d( \%g, 'Denver', 'Cleveland' ); # should be ( 'Denver', 'Chicago', 'C
+leveland' )
d( \%g, 'Cleveland', 'Denver' ); # should be 
( 'Cleveland', 'Chicago', 'Denver' );
[download]

Update: yea, fixed the stupid parens here....

---

Dr. Michael K. Neylon - mneylon-pm@masemware.com || "You've left the lens cap of your mind on again, Pinky" - The Brain

---

---

• Are you posting in the right place? Check out Where do I post X? to know for sure.
• Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:

  <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>

• Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
• Want more info? How to link or How to display code and escape characters are good places to start.