http://qs321.pair.com?node_id=542708


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

L~R:

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 = (
        '1.2.3.3' => ['1.2.3.4'],
        '1.2.3.4' => ['1.2.3.3', '1.2.3.5', '1.2.3.7'],
        '1.2.3.5' => ['1.2.3.4', '1.2.3.6', '1.2.3.7'],
        '1.2.3.6' => ['1.2.3.5', '1.2.3.7'],
        '1.2.3.7' => ['1.2.3.6', '1.2.3.4', '1.2.3.5'],
);

my %visited=();
my @stack=();

print find_path('1.2.3.4', '1.2.3.6') || "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;
}

[download]
--roboticus

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
    roboticus,
    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('1.2.3.4', '1.2.3.6', \%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';
}

    [download]
    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

[reply]
[d/l]
      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!

      --roboticus

[reply]
        roboticus,
        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.
        Read more... (2 kB)

        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.

        Read more... (1054 Bytes)

        Cheers - L~R

[reply]
[d/l]
[select]
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 :)
[reply]

In Section Seekers of Perl Wisdom