Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid
 
PerlMonks  

Comment on

( #3333=superdoc: print w/replies, xml ) Need Help??
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 } );
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' );
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

In reply to (Golf) Shortest Graph Distance by Masem

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    [Corion]: Nicholas Clark++ # read for a multichar block-delimiter by scanning for the last char, and only then check whether the whole delimiter was read.
    [Corion]: At least if you're appending the data read to a larger buffer, this means you avoid the situation of "a delimiter was found but the other half has not been read yet"
    choroba misses the context
    [Corion]: choroba: Optimizing how Perl reads source code on startup (and then processes it line-by-line)
    [Corion]: But in general, it seems to be an interesting approach I should think about - whenever I'm searching for something, to consider if I could search for the end of the token instead of the start of the token

    How do I use this? | Other CB clients
    Other Users?
    Others exploiting the Monastery: (12)
    As of 2016-12-06 15:00 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?
      On a regular basis, I'm most likely to spy upon:













      Results (107 votes). Check out past polls.