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;
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";
print join(" ", @{\$points}) . "\n";
}
\$S = 5;
print "\n\\$S = \$S\n";
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

Challenge 122

Dynamic Programming

posted at: 18:53 by: Adam Russell | path: /perl | permanent link to this entry