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