Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

Re: compute paths in Pascal's triangle (aka Tartaglia's one) (2 updates)

by LanX (Saint)
on Mar 22, 2018 at 12:23 UTC ( [id://1211514]=note: print w/replies, xml ) Need Help??


in reply to compute paths in Pascal's triangle (aka Tartaglia's one)

The confusing "problem" is the coordinate system, it's trivial if you change it to left-down and right-down moves

0-0 1-0 0-1 2-0 1-1 0-2 3-0 *2-1 1-2 0-3 4-0 3-1 2-2 1-3 0-4 5-0 4-1 3-2 2-3 1-4 0-5

You see in your system:

  • the left coordinate is the "level", which is the sum of left-down and right-down moves
  • the right coordinate is the right-down move
So your goal needs 2 left and 1 right move in any order, because this is just a distorted rectangle with 2 down and 1 right move

0-0 0-1 0-2 0-3 0-4 0-5 1-0 1-1 1-2 1-3 1-4 2-0 *2-1 2-2 2-3 3-0 3-1 3-2 4-0 4-1 5-0

This algorithm is fixing it by recalculating the remaining left-down moves

use strict; use warnings; use Data::Dump qw/pp dd/; my $goal = [3,1]; my ($gl,$gr) = @$goal; my @results; pathfinder( [0,0,"start"] ); # start pp \@$_ for @results; sub pathfinder { my ( $last ) = @_; my ( $l, $r ) = @$last ; if ( $gl == $l ) { if ($gr == $r) { push @results,[ reverse @_]; } else { warn "wrong",pp [reverse @_]; return } } # left pathfinder( [$l+1,$r ,"left"], @_ ) if $l < $gl - ($gr - $r); # right pathfinder( [$l+1,$r+1,"right"], @_ ) if $r < $gr; }

C:/Perl_64/bin\perl.exe d:/tmp/pascale_path.pl [ [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"], ] Compilation finished at Thu Mar 22 12:41:53

update

in hindsight it's probably better implemented in the new coordinate system and only the results are transformed back.

The code is much easier then.

Cheers Rolf
(addicted to the Perl Programming Language and ☆☆☆☆ :)
Wikisyntax for the Monastery

Replies are listed 'Best First'.
Re^2: compute paths in Pascal's triangle (aka Tartaglia's one)
by LanX (Saint) on Mar 22, 2018 at 15:12 UTC
    > in hindsight it's probably better implemented in the new coordinate system and only the results are transformed back.

    > The code is much easier then.

    Yep!

    use strict; use warnings; use Data::Dump qw/pp dd/; my $goal = [3,1,'goal']; my $start = [0,0,'start']; pp "OLD: ",[$start,$goal]; ($start,$goal) = map old2new($_), ($start,$goal); pp "NEW: ",[$start,$goal]; my ($gl,$gr) = @$goal; my @results; pathfinder( $start ); pp \@$_ for @results; sub pathfinder { my ( $last ) = @_; 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; } # -------------------------------------------------- # 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; }

    Compilation started at Thu Mar 22 16:09:33 C:/Perl_64/bin\perl.exe d:/tmp/pascale_path.pl ("OLD: ", [[0, 0, "start"], [3, 1, "goal"]]) ("NEW: ", [[0, 0, "start"], [2, 1, "goal"]]) [ [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"], ] Compilation finished at Thu Mar 22 16:09:33

    Cheers Rolf
    (addicted to the Perl Programming Language and ☆☆☆☆ :)
    Wikisyntax for the Monastery

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others pondering the Monastery: (5)
As of 2024-03-28 13:19 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found