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
The Weekly Challenge 122 (Prolog Solutions)
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
:-initialization(main).
moving_average(N):-
moving_average(0, N, 1).
moving_average(Sum, N, I):-
I \== N,
Sum0 is Sum + (I * 10),
Average is Sum0 / I,
write(Average), nl,
I0 is I + 1,
moving_average(Sum0, N, I0).
moving_average(_, N, I):-
I == N.
main:-
moving_average(10),
halt.
Sample Run
$ gplc prolog/ch-1.p
$ prolog/ch-1
10.0
15.0
20.0
25.0
30.0
35.0
40.0
45.0
50.0
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 generated sequence of numbers. For each recursive call to
moving_average/3
we increase the simulated "stream" by 10 and compute the moving
average.
(The idea of a stream in Prolog is fairly specific. My preferred Prolog is Gnu Prolog, which has a very nice write up of the subject.)
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
:-initialization(main).
points --> [].
points --> point, points.
point --> [0]; [1]; [2]; [3].
basketball_points(Points, Goal):-
length(Points, Goal),
phrase(points, Points),
sum_list(Points, Goal).
zero_remove([], []).
zero_remove([H|T], [ZR_H|ZR_T]):-
delete(H, 0, ZR_H),
zero_remove(T, ZR_T).
main:-
findall(Ps, basketball_points(Ps, 4), Points),
zero_remove(Points, PointsZR),
sort(PointsZR, PointsZR_Unique),
write(PointsZR_Unique), nl,
halt.
Sample Run
$ gplc prolog/ch-2.p
$ prolog/ch-2
[[1,1,1,1],[1,1,2],[1,2,1],[1,3],[2,1,1],[2,2],[3,1]]
Notes
This is almost exactly identical to a solution for Challenge 112. The only difference is that I changed the predicate and variable names to match the current problem statement!
References
posted at: 18:09 by: Adam Russell | path: /prolog | permanent link to this entry