Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister
 
PerlMonks  

Re: (Golf) Shortest Graph Distance

by chipmunk (Parson)
on May 12, 2001 at 00:15 UTC ( #79834=note: print w/ replies, xml ) Need Help??


in reply to (Golf) Shortest Graph Distance

Here's a solution, which I'm fairly certain works as intended (but we saw where that got me last time ;)

sub path { (*g,$f,$t)=@_;@s=map[$f,$_,$r{$_}],keys%{*r=$g{$f}}; push@s,map[@p,$_,$d+$r{$_}],keys%{*r=$g{$n}} while(@s=sort{$b->[-1]<=>$a->[-1]}@s),$d=pop@{*p=pop@s}, ($n=$p[-1])ne$t;@p }
170 characters... Yikes! I'm sure someone can do better than that!

Update: Hey, I don't need to do that complicated initialization of @s!

sub path { (*g,$f,$t)=@_;@s=[$f,0]; push@s,map[@p,$_,$d+$r{$_}],keys%{*r=$g{$n}} while(@s=sort{$b->[-1]<=>$a->[-1]}@s),$d=pop@{*p=pop@s}, ($n=$p[-1])ne$t;@p }
142 characters!

Update:

This solution will be very slow on the NYC to SF test case, because it gets stuck moving back and forth between Chicago, Cleveland, and Detroit for a while, because SF is so far away. However, it will find the solution eventually.

Of course, this could be fixed by preventing the code from moving back to a node that has already been visited, but we're optimizing for character count, not for speed of execution! ;)


Comment on Re: (Golf) Shortest Graph Distance
Select or Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://79834]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (9)
As of 2015-07-28 23:36 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (260 votes), past polls