Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

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

by LanX (Sage)
on Mar 22, 2018 at 10:43 UTC ( #1211500=note: print w/replies, xml ) Need Help??


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

an hour later oO

I don't like that there are still wrong moves possible*, probably because I din't follow my own concept...

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

[[0, 0], [1, 0], [2, 0], [3, 1]] [[0, 0], [1, 0], [2, 1], [3, 1]] [[0, 0], [1, 1], [2, 1], [3, 1]]

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

*) i.e. the else branch with the warning should never be reached.

update

solution here

Replies are listed 'Best First'.
Re^3: compute paths in Pascal's triangle (aka Tartaglia's one)
by hdb (Monsignor) on Mar 22, 2018 at 11:48 UTC

    Well, for any given target node you build a string of the correct number of left and right moves (or zeroes and ones) and then any permutation is one of the admissible solutions (and all of them).

    UPDATE: Just as illustration, using a module, and having to filter out duplicates in the permutations, it could work like this:

    use strict; use warnings; use Algorithm::Permute; my $node = '5-2'; my ($all, $right) = split /-/, $node; my @path = ((0) x ($all-$right),(1) x $right); my %pathes; Algorithm::Permute::permute { my $key = join '', @path; if( not exists $pathes{$key} ) { $pathes{$key} = 1; my ($l, $r) = (0,0); my $path = "($l-$r) ".join( " ", map{ "(".(++$l)."-".($r+=$_). +")" } @path); print "$path\n"; } } @path;

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others about the Monastery: (7)
As of 2022-06-28 08:56 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    My most frequent journeys are powered by:









    Results (90 votes). Check out past polls.

    Notices?