Perl Weekly Challenge 201.

My solutions (task 1 and task 2 ) to the The Weekly Challenge - 201.

Task 1: Missing Numbers

Submitted by: Mohammad S Anwar
You are given an array of unique numbers.

Write a script to find out all missing numbers in the range 0..$n where $n is the
array size.


Example 1
Input: @array = (0,1,3)
Output: 2

The array size i.e. total element count is 3, so the range is 0..3.
The missing number is 2 in the given array.
Example 2
Input: @array = (0,1)
Output: 2

The array size is 2, therefore the range is 0..2.
The missing number is 2.

I make a hash of seen values and filter out unseen ones. This makes a short oneliner:

perl -E '@s{@ARGV}=(1)x@ARGV; say join " ", @ARGV, "->", grep {!$s{$_}} 0..@ARGV' 0 1 3
perl -E '@s{@ARGV}=(1)x@ARGV; say join " ", @ARGV, "->", grep {!$s{$_}} 0..@ARGV' 0 1

Results:

0 1 3 -> 2
0 1 -> 2

The full code is essentially the same. I just add a usage message and check the input for unique values.

 1  # Perl weekly challenge 201
 2  # Task 1:  Missing Numbers
 3  #
 4  # See https://wlmb.github.io/2023/01/23/PWC201/#task-1-missing-numbers
 5  use v5.36;
 6  my %seen;
 7  die <<~ "FIN" unless @ARGV;
 8      Usage: $0 N1 [N2...]
 9      to find the missing numbers from the sequence N1 N2...
10      FIN
11  @seen{@ARGV}=(1)x@ARGV;
12  die "Expected unique values" unless 0+@ARGV==0+keys %seen;
13  say join " ", @ARGV, "->", grep {!$seen{$_}} 0..@ARGV;

Example:

./ch-1.pl 0 1 3
./ch-1.pl 0 1

Task 2: Penny Piles

Submitted by: Robbie Hatley
You are given an integer, $n > 0.

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.

Example
Input: $n = 5
Output: 7

Since $n=5, there are 7 ways of stacking 5 pennies in ascending piles:

1 1 1 1 1
1 1 1 2
1 2 2
1 1 3
2 3
1 4
5

I can solve this problem recursively. To make an ascending row of piles with $n pennies with at most $m pennies in each pile (with $m≤$n), I can make a single rightmost pile of $p pennies with $p≤$m, and I’m left with $n-$p pennies to make a row of piles with no more than $p pennies in each (so that the resulting row is ascending). This fits a longish oneliner:

perl -MList::Util=sum -E '
say "$_->", f($_, $_) for @ARGV; sub f($n,$m){return 1 if $n==0; sum map{f($n-$_,$_)} 1..($m<=$n?$m:$n)}
' 1 2 3 4 5 6

Results:

1->1
2->2
3->3
4->5
5->7
6->11

The full code is almost identical. I just add a test, some minimal optimization and memoization to reduce the cost of recursion.

 1  # Perl weekly challenge 201
 2  # Task 2:  Penny Piles
 3  #
 4  # See https://wlmb.github.io/2023/01/23/PWC201/#task-2-penny-piles
 5  use v5.36;
 6  use List::Util qw(min sum);
 7  use Memoize;
 8  memoize "rows";
 9  die <<~"FIN" unless @ARGV;
10      Usage: $0 N1 [N2...]
11      to obtain the number of ascending rows of piles of Ni coins.
12      FIN
13  say "$_->", rows($_, $_) for @ARGV;
14  sub rows($coins,$max){
15      return 1 if $coins==0;
16      return sum map{rows($coins-$_,min($_, $coins-$_))} 1..min($coins, $max)
17  }

Example:

./ch-2.pl `seq 6`

Results:

1->1
2->2
3->3
4->5
5->7
6->11

Other examples:

./ch-2.pl -1 0 100

Results:

-1->
0->1
100->190569292
Written on January 23, 2023