1 #!/usr/bin/perl 2 # 3 # https://theweeklychallenge.org/blog/perl-weekly-challenge-201/#TASK2 4 # 5 # You are given an integer, $n > 0. 6 # 7 # Write a script to determine the number of ways of putting $n pennies in a row of piles of ascending heights from left to right. 8 # 9 ## Example 10 ## 11 ## Input: $n = 5 12 ## Output: 7 13 ## 14 ## Since $n=5, there are 7 ways of stacking 5 pennies in ascending piles: 15 ## 16 ## 1 1 1 1 1 17 ## 1 1 1 2 18 ## 1 2 2 19 ## 1 1 3 20 ## 2 3 21 ## 1 4 22 ## 5 23 # 24 ###################################################################### 25 ## 26 ## discussion 27 ## 28 ###################################################################### 29 # 30 # we can find all ways of stacking $n pennies by creating the right-most 31 # pile first, going from 1..$n 32 # then we create all solutions for the remaining pennies but with the constraint 33 # that the biggest pile can only be as big as the one we already built. To each 34 # of all these solutions we add our right-most pile and return them. 35 # 36 37 use strict; 38 use warnings; 39 use feature 'say'; 40 41 my @examples = (1, 2, 3, 4, 5, 10, 20); 42 43 foreach my $example (@examples) { 44 my @solutions = find_solutions($example); 45 say scalar(@solutions) . " solutions found:"; 46 foreach my $solution (@solutions) { 47 say join(" ", @$solution); 48 } 49 } 50 51 # our recursive function 52 sub find_solutions { 53 my ($n, $max_pile_size) = @_; 54 # if no maximum pile size was given use $n as fallback 55 $max_pile_size //= $n; 56 # limit $max_pile_size to $n 57 $max_pile_size = $n if $max_pile_size > $n; 58 my @solutions; 59 # There is only an empty solution if $n is 0 60 return ([]) unless $n > 0; 61 # now create the last pile 62 foreach my $last (1..$max_pile_size) { 63 # create all piles left to the last one 64 my @sub_solutions = find_solutions($n - $last, $last); 65 # add the last pile to each of these solutions and add 66 # the solutions to our return array 67 foreach my $sub_solution (@sub_solutions) { 68 push @$sub_solution, $last; 69 push @solutions, $sub_solution; 70 } 71 } 72 return @solutions; 73 }