#!env perl
#
# ex_tartaglias_triangle.pl
#
# Find all paths any node R-C to the root (0-0), only moving upwards:
#
#                  0-0
#               1-0   1-1
#            2-0   2-1   2-2
#         3-0   3-1   3-2   3-3
#      4-0   4-1   4-2   4-3   4-4
#   5-0   5-1   5-2   5-3   5-4   5-5
#
use strict;
use warnings;

for my $r (0 .. 5) {
    for my $c (0 .. $r) {
        my $N = aNode->new($r, $c);
        print "\n*** ", $N->to_str, ", # paths to root: ", $N->cnt_paths, " ***\n\n";
        for my $rp ($N->paths) {
            print "\t", join(" -> ", map { $_->to_str } reverse @$rp), "\n";
        }
        print "\n";
    }
}


{
    package aNode;

    sub new {
        my ($cl, $r, $c) = @_;
        my $t = bless { r=>$r, c=>$c, root=>$r==0 }, $cl;
        return $t;
    }

    sub is_root { return $_[0]->{root}; }

    sub moves {
        my $self = shift;
        my @rv;
        push @rv, aNode->new($self->{r}-1, $self->{c}-1) if $self->{r} and $self->{c};
        push @rv, aNode->new($self->{r}-1, $self->{c})   if $self->{c} < $self->{r};
        return @rv;
    }

    sub paths {
        my $self = shift;
        return [$self] if $self->is_root;
        my @rv;
        for my $m ($self->moves) {
            push @rv, [ $self, @$_ ] for $m->paths;
        }
        return @rv;
    }

    sub cnt_paths {
        my $self = shift;
        return 1 if $self->is_root;

        my $rv = 0;
        for my $n ($self->moves) {
            $rv += $n->cnt_paths;
        }
        return $rv;
    }

    sub to_str {
        my $self = shift;
        return "$self->{r}-$self->{c}";
    }
}