Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?

Re^2: traversing a hash looking for path?

by roboticus (Chancellor)
on Apr 11, 2006 at 23:55 UTC ( #542708=note: print w/replies, xml ) Need Help??

in reply to Re: traversing a hash looking for path?
in thread traversing a hash looking for path?


Since you asked in the ChatterBox for a recursive version, I thought I'd take up the challenge. Here's my take on a recursive solution:

#!/usr/bin/perl use strict; use warnings; my %net = ( '' => [''], '' => ['', '', ''], '' => ['', '', ''], '' => ['', ''], '' => ['', '', ''], ); my %visited=(); my @stack=(); print find_path('', '') || "no solution!"; sub find_path { my ($beg, $end) = @_; return $end if $beg eq $end; $visited{$beg}=1; for my $try (@{$net{$beg}}) { if (!defined($visited{$try})) { push @stack, $beg; my $t = find_path($try, $end); return $beg.'=>'.$t if $t; pop @stack; } } undef; }

Replies are listed 'Best First'.
Re^3: traversing a hash looking for path?
by Limbic~Region (Chancellor) on Apr 12, 2006 at 14:29 UTC
    Thank you. I have a real hard time thinking recursively for some reason. There are some things that I would want to change. For instance, letting the call stack be handled automatically by the recursion and not relying on lexicals visible at the package level. Here is my take on satisfying those two changes:
    my %net = (...); # shortened for brevity sake print find_path('', '', \%net); sub find_path { my ($beg, $end, $net, $seen, $stop, $node, $path) = @_; if (! defined $stop) { ($node, $path) = ($beg, $beg); $stop->{$_} = 1 for @{$net->{$end}}; } return $path if $node eq $end; return "$path=>$end" if $stop->{$node}; return undef if $seen->{$node}++; for (@{$net->{$node}}) { my $found = find_path($beg, $end, $net, $seen, $stop, $_, "$pa +th=>$_"); return $found if $found; } return 'path not found'; }
    I liked the iterative solution better because I could alter the search process by adjusting the shift/unshift and push/pop. I thought recursive solutions were supposed to be more elegant. Perhaps it is just because I don't know what I am doing.

    Cheers - L~R


      For some problems, recursion can be more elegant. For some other problems, it's just another way to do the job. For the remaining few problems, it's just a harder way to do things.

      In fact, for this problem, it may be that recursion could be more elegant. My implementation, however, makes no such claim! Especially as you've made a few improvements! 8^)

      (In Perl, I'm not very skilled (yet), so you'd be agog at how much time I spent debugging it before posting. I was happy enough to get it done! Once there, I was afraid to touch it in persuit of elegance. We need to get a good golfer in here for that...)

      Regarding the altering of the search process: I'd imagine that you may be able to get there with a recursive solution, as well--not that one comes to mind for this task!

      I've been meaning to beat Lisp into my brain, but after learning a few programming languages, I've adopted the policy: No learning a new language until I get paid for it! It's too bad I can't convince my boss to let me write anything in Lisp..... So, I'm trying to learn some Lisp-like Perl idioms, but I've got quite a way to go!


        The problem with a recursive BFS is that you have to pass forward your nodes. You want to first check all your nodes of a distance of 1, then 2, etc until you find your destination.

        It turns out that the only real difference between this and my iterative solution is that you have 2 stacks. The first is the current work load (nodes at current distance) and the second is you future work load (nodes at the next distance) which you pass forward.

        While the find_path() sub that follows is quite elegant, the remainder of the code isn't.

        This isn't the result of recursive BFS being all that ugly or intention obfu. I was just experimenting. It can be brought back into a single sub that looks quite reasonable (which is what I started with). Since working backwards to clean code is easier, I thought you might enjoy seeing the things I played with.

        Update: Since others besides roboticus might be interested, I am providing the relatively clean version as well.

        Cheers - L~R

Re^3: traversing a hash looking for path?
by Anonymous Monk on Apr 12, 2006 at 01:41 UTC
    Both of these are great examples and have opened a few doors for me.
    Thanks for all the help :)

Log In?

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

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (6)
As of 2022-01-21 22:43 GMT
Find Nodes?
    Voting Booth?
    In 2022, my preferred method to securely store passwords is:

    Results (59 votes). Check out past polls.