Yes, yes, after last week, my brain wants to hear music based on the Perl Weekly Challenge. Because I’m starting a new job this week (yay!), I’m going to hold off on the Java solution and blog about it later. I want to keep up with the process of learning Java by adding it to the “guest languages” I do PWC solutions in, but I don’t want to delay getting my primary languages (Perl, Raku, & Python) submitted because I’ve got new-job tasks to accomplish.
Though my new job does have code in a language that’s new to me—Elixir. Since Elixir’s a functional language like Lisp, I want to learn it so I can better understand how my Elixir-coding coworkers think, so that’s going to be the next guest language I add to the PWC.
Task 1: Running Sum
You are given an array of integers.
Write a script to return the running sum of the given array. The running sum can be calculated as sum[i] = num[0] + num[1] + …. + num[i].
Example 1
Input: @int = (1, 2, 3, 4, 5)
Output: (1, 3, 6, 10, 15)
Example 2
Input: @int = (1, 1, 1, 1, 1)
Output: (1, 2, 3, 4, 5)
Example 3
Input: @int = (0, -1, 1, 2)
Output: (0, -1, 0, 2)
Once again, there’s an easier way to calculate the values being asked for than the way problem is defined. See, the way the problem is defined, it would appear that the way to generate the output array would be like this:
for (my $i = 0; $i <= $#int; $i++) {
# sum the 0th through $i-th numbers in @int
my $sum = $int[0];
for (my $j = 1; $j <= $i; $j++) {
$sum += $int[$j];
}
$sums[$i] = $sum;
}
Or, if we were savvy about modules, we would use sum out of List::Util and an array slice to avoid the inner loop:
use List::Util qw(sum);
for (my $i = 0; $i <= $#int; $i++) {
# sum the 0th through $i-th numbers in @int
$sums[$i] = sum @int[0 .. $i];
}
But… note that each new number in the output array is obtained by adding the next number in the input array to the last number in the output array. So we don’t need more than one loop through the input array:
sub runningSum {
my @int = @_;
my @sums;
my $running_sum = 0;
foreach my $num ( @int ) {
# add the next number to the sum of numbers before it
$running_sum += $num;
# add the current running sum to the output array
push @sums, $running_sum;
}
return @sums;
}
View the entire Perl script for this task on GitHub.
On to the Raku solution, which really shows how closely related Perl and Raku are. The only changes I made were accepting the @int array as a defined parameter, the syntax of the for loop, and using the .push() method on @sums instead of push @sums, $running_sum;.
sub runningSum(*@int) {
my @sums;
my $running_sum = 0;
for @int -> $num {
# add the next number to the sum of numbers before it
$running_sum += $num;
# add the current running sum to the output array
@sums.push( $running_sum );
}
return @sums;
}
View the entire Raku script for this task on GitHub.
In much the same way, Python didn’t require much changes from the Raku version besides its silly syntax differences:
def runningSum(int):
sums = []
running_sum = 0
for num in int:
# add the next number to the sum of numbers before it
running_sum += num
# add the current running sum to the output array
sums.append( running_sum )
return sums
Really, I chalk this up to Python (even though it’s based off ABC) liberally borrowing syntax ideas from C-family programming languages. Which might be why I picked up Python so quickly: it feels really familiar.
View the entire Python script for this task on GitHub.
Task 2: Persistence Sort
You are given an array of positive integers.
Write a script to sort the given array in increasing order with respect to the count of steps required to obtain a single-digit number by multiplying its digits recursively for each array element. If any two numbers have the same count of steps, then print the smaller number first.
Example 1
Input: @int = (15, 99, 1, 34)
Output: (1, 15, 34, 99)
15 => 1 x 5 => 5 (1 step)
99 => 9 x 9 => 81 => 8 x 1 => 8 (2 steps)
1 => 0 step
34 => 3 x 4 => 12 => 1 x 2 => 2 (2 steps)
Example 2
Input: @int = (50, 25, 33, 22)
Output: (22, 33, 50, 25)
50 => 5 x 0 => 0 (1 step)
25 => 2 x 5 => 10 => 1 x 0 => 0 (2 steps)
33 => 3 x 3 => 9 (1 step)
22 => 2 x 2 => 4 (1 step)
This time, we want to be able to multiply all the digits in a number, and product in List::Util will be very useful!
my $step_count = 0;
while ( length($num) > 1 ) {
# split $num into its individual digits
my @digits = split //, $num;
# generate a new number by multiplying all the digits
$num = product @digits;
# add to our count of steps
$step_count++;
}
But since we need to do this for each number in our input array and then later sort based on the results, let’s make the step count a hash indexed on the number. Note that because $num is an alias to the actual value in the @int array, we should make a copy of $num so we’re not modifying the values in @int.
my %step_count;
foreach my $num ( @int ) {
$step_count{$num} = 0;
my $num_copy = $num; # copy the num so we can modify it
while ( length($num_copy) > 1 ) {
# split $num_copy into its individual digits
my @digits = split //, $num_copy;
# generate a new number by multiplying all the digits
$num_copy = product @digits;
# add to our count of steps
$step_count{$num}++;
}
}
Once we have a %step_count hash containing how many steps were needed for each number, sorting the input array as requested becomes trivial:
my @sorted = sort {
# sort by step count
$step_count{$a} <=> $step_count{$b}
||
# then sort numerically
$a <=> $b
} @int;
Once I added code to generate the verbose step explanations seen in the examples, we have the following :
use List::Util qw( product );
sub persistenceSort {
my @int = @_;
my %step_count;
my $steps;
# first, calculates the steps for each number
foreach my $num ( @int ) {
$step_count{$num} = 0;
$steps .= "\n$num"; # our starting number
my $num_copy = $num; # copy the num so we can modify it
while ( length($num_copy) > 1 ) {
# split $num_copy into its individual digits
my @digits = split //, $num_copy;
# generate a new number by multiplying all the digits
$num_copy = product @digits;
# show the multiplication in the steps for this num
$steps .= ' => ' . join(' x ', @digits);
$steps .= " => $num_copy";
# add to our count of steps
$step_count{$num}++;
}
# put the step count in the steps for this num
$steps .=
sprintf " (%d step%s)", $step_count{$num},
$step_count{$num} == 1 ? '' : 's';
}
# now, sort by steps/numeric value
my @sorted = sort {
# sort by step count
$step_count{$a} <=> $step_count{$b}
||
# then sort numerically
$a <=> $b
} @int;
return \@sorted, $steps;
}
View the entire Perl script for this task on GitHub.
With Raku, there are a few differences:
- I didn’t need to pull in a module to get the product of the digits, because that’s something built into the language with Raku’s Reduction Metaoperator:
[ ]. So, what in Perl was$num_copy = List::Util::product @digits;became$num_copy = [*] @digits;in Raku. - When counting the number of digits in
$num_copy, we need to pass it through theIntclass’.Strmethod to get a string representation of the number. - Perl’s
length()function becomes Raku’sStrclass’ .chars routine. - As I noted back in PWC 334, when splitting a string into its component characters, make sure you add the
:skip-emptyparameter, otherwise you’ll get leading and trailing empty character entries. - And one of the tricky things I’ve noticed is if you’re returning a List from a subroutine, if you try to capture it in a variable with the @ sigil, the list is assigned to the first element of the variable.
sub persistenceSort(*@int) {
my %step_count;
my $steps;
# first, calculates the steps for each number
for @int -> $num {
%step_count{$num} = 0;
$steps ~= "\n$num"; # our starting number
my $num_copy = $num; # copy the num so we can modify it
while ( $num_copy.Str.chars > 1 ) {
# split $num_copy into its individual digits
my @digits = $num_copy.split('', :skip-empty);
# generate a new number by multiplying all the digits
$num_copy = [*] @digits;
# show the multiplication in the steps for this num
$steps ~= ' => ' ~ @digits.join(' x ');
$steps ~= " => $num_copy";
# add to our count of steps
%step_count{$num}++;
}
# put the step count in the steps for this num
$steps ~=
sprintf " (%d step%s)", %step_count{$num},
%step_count{$num} == 1 ?? '' !! 's';
}
# now, sort by steps/numeric value
my @sorted = @int.sort({
# sort by step count
%step_count{$^a} <=> %step_count{$^b}
||
# then sort numerically
$^a <=> $^b
});
return @sorted, $steps;
}
sub solution {
my @int = @_;
say 'Input: @int = (' ~ @int.join(', ') ~ ')';
# if we attempt to capture the returned array in
# @sorted, the array becomes the first ELEMENT in
# @sorted (and the $steps Str becomes the second
# element) so we capture it in $sorted
my ($sorted, $steps) = persistenceSort(@int);
say 'Output: (' ~ $sorted.join(', ') ~ ')';
say $steps;
}
View the entire Raku script for this task on GitHub.
With Python, I initially encountered a problem because I had defined the input parameter to persistenceSort to be the variable int… but that shadowed the Python function int() that I needed to convert individual characters back to integers and caused TypeError: 'list' object is not callable when I tried to execute lambda a, b: int(a) * int(b). Quickly renaming the variable to int_list solved the problem.
Edit: Initially, I had a custom sort function to handle the multi-factor sorting, but then I was reading some more and I discovered that if the key function returned a tuple, Python would do what we want: sort by the first element of the tuple, but if the first elements are equal, sort by the second element of the tuple.
from functools import cmp_to_key, reduce
def persistenceSort(int_list):
step_count = {}
steps = ""
# first, calculates the steps for each number
for num in int_list:
step_count[num] = 0
steps += f"\n{num}" # our starting number
num_copy = str(num) # copy the num so we can modify it
while len(num_copy) > 1:
# split num_copy into its individual digits
digits = list(num_copy)
# generate a new number by multiplying
# all the digits
num_copy = str(
reduce(
lambda a, b: int(a) * int(b),
digits
)
)
# show the multiplication in the steps for this num
steps += ' => ' + ' x '.join(digits)
steps += ' => ' + num_copy
# add to our count of steps
step_count[num] += 1
# put the step count in the steps for this num
step_word = 'step' if step_count[num] == 1 else 'steps'
steps += f" ({step_count[num]} {step_word})"
# now, sort by steps/numeric value
sorted_list = sorted(int_list,
key=lambda x: (step_count[x], x))
return sorted_list, steps
View the entire Python script for this task on GitHub.
Here’s all my solutions in GItHub: https://github.com/packy/perlweeklychallenge-club/tree/master/challenge-238/packy-anderson