RabbitFarm
2021-07-25
Average of Stream / Basketball Points
The examples used here are from The Weekly Challenge problem statement and demonstrate the working solution.
Part 1
You are given a stream of numbers, @N. Write a script to print the average of the stream at every point.
Solution
use strict;
use warnings;
sub moving_average{
my $n = 0;
my $sum = 0;
{
$n += 1;
$sum += shift;
print $sum / $n;
print ", " if @_;
redo if @_;
}
print "\n";
}
MAIN:{
my @N;
for(my $i = 10; $i < 1_000_000; $i += 10){
push @N, $i;
}
moving_average(@N);
}
Sample Run
$ perl perl/ch-1.pl
10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95,
Notes
Typically when one thinks of a stream the idea is of a virtually endless source of data. Or, at least, data which is handled as if this were the case. Here the "stream" is simulated by a long (one million items) array.
The computation of the average as the simulated stream is evaluated is done using a redo
loop. I would think it is fair to say that typically my code is somewhat verbose. I prefer
to be fairly explicit in that way to enhance readability. Here, however, I try to be more
terse. The "stream" is evaluated by shifting values off the array passed to the function.
The array argument is also used to determine if the block should be repeated, and also
to format the output.
Part 2
You are given a score $S. You can win basketball points e.g. 1 point, 2 points and 3 points. Write a script to find out the different ways you can score $S.
Solution
use strict;
use warnings;
sub basketball_points{
my($total) = @_;
my %points;
my @valid_points;
$points{"1"} = "1";
$points{"2"} = "2";
$points{"3"} = "3";
while((keys %points) > 0){
my %updated_points = ();
for my $points (keys %points){
my @points = split(/,/, $points);
for my $point (1 .. 3){
my $point_sum = unpack("%32I*", pack("I*", (@points, $point)));
push @valid_points, [@points, $point] if $point_sum == $total;
$updated_points{join(",", (@points, $point))} = $point_sum if $point_sum < $total;
}
}
%points = %updated_points;
}
return @valid_points;
}
MAIN:{
my $S;
$S = 4;
print "\$S = $S\n";
my @point_combinations = basketball_points($S);
for my $points (basketball_points($S)){
print join(" ", @{$points}) . "\n";
}
$S = 5;
print "\n\$S = $S\n";
@point_combinations = basketball_points($S);
for my $points (basketball_points($S)){
print join(" ", @{$points}) . "\n";
}
}
Sample Run
$ perl perl/ch-2.pl
$S = 4
1 3
2 2
3 1
1 2 1
1 1 2
2 1 1
1 1 1 1
$S = 5
3 2
2 3
3 1 1
2 1 2
1 3 1
2 2 1
1 2 2
1 1 3
1 2 1 1
1 1 1 2
1 1 2 1
2 1 1 1
1 1 1 1 1
Notes
The approach here borrows heavily from the solution to the triangle problem from Challenge 117. This is a dynamic programming style solution which builds and updates lists of potential point sequences. Uniqueness is guaranteed by saving the lists as hash keys, in a command separated values string format.
References
posted at: 18:53 by: Adam Russell | path: /perl | permanent link to this entry