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

Challenge 122

Dynamic Programming

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

Challenge 122

posted at: 18:09 by: Adam Russell | path: /prolog | permanent link to this entry