> I tried to use your solution in my program but, I must admit, I discarded it soon.
Easy... ;-)
use strict;
use warnings;
use Data::Dump qw/pp dd/;
my @paths = find_paths
(
[0,0,'start'],
[3,1,'goal']
);
pp @paths;
sub find_paths {
my ($start,$goal)=@_;
# --- transform to easier coordinates
($start,$goal) = map old2new($_), ($start,$goal);
# --- define closure
my @results;
my ($gl,$gr) = @$goal;
my $pathfinder;
$pathfinder = sub {
my ( $last ) = @_;
# pp \@_ ;# track recursion path
my ( $l, $r ) = @$last ;
if ( $gl == $l and $gr == $r) {
push @results, [ map new2old($_), reverse @_ ];
return;
}
$pathfinder->( [$l+1,$r ,"left" ], @_ ) if $l < $gl;
$pathfinder->( [$l ,$r+1 ,"right"], @_ ) if $r < $gr;
};
# --- init recursion
$pathfinder->($start);
return \@results;
}
# --------------------------------------------------
# coordinate transformations
sub old2new { # left = level - right
my ($a_old)=@_;
my @new = @$a_old;
$new[0] = $new[0] - $new[1];
return \@new;
}
sub new2old { # level = left + right
my ($a_new)=@_;
my @old = @$a_new;
$old[0] = $old[0] + $old[1];
return \@old;
}
(
"Result:",
[
[
[0, 0, "start"],
[1, 0, "left"],
[2, 0, "left"],
[3, 1, "right"],
],
[
[0, 0, "start"],
[1, 0, "left"],
[2, 1, "right"],
[3, 1, "left"],
],
[
[0, 0, "start"],
[1, 1, "right"],
[2, 1, "left"],
[3, 1, "left"],
],
],
)
Please note, any recursion can be written as iteration. If speed matters this might be worth it.
tybalt is using the same algorithm, just starting from the end (so he doesn't need to reverse the path) and more golfy.