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 }