Keeping Up the Average Number of Trips From the Line

Wherein we learn to maintain the balance; every shot adds up in the end, but some shots are harder than others.

THE WEEKLY CHALLENGE – PERL & RAKU #122

---

episode one:
“You cannot step in the same river twice“

---

Task 1

Average of Stream

Submitted by: Mohammad S Anwar

You are given a stream of numbers, @N.

Write a script to print the average of the stream at every point.

Example

Input: @N = (10, 20, 30, 40, 50, 60, 70, 80, 90, ...)
Output:      10, 15, 20, 25, 30, 35, 40, 45, 50, ...

Average of first number is 10.
Average of first 2 numbers (10+20)/2 = 15
Average of first 3 numbers (10+20+30)/3 = 20
Average of first 4 numbers (10+20+30+40)/4 = 25 and so on.

Method

I do find the use of the word “stream” in the title to be a bit confusing, was we’re not apparently dealing with a continuous flow of information but rather a list of data that starts at a certain point, gets kept and is loaded into an array. So I think what’s really only being asked for here is the running average of an array of values at each of its indices. Keeping a running average of, say, the last five values of a stream, with new data being added and old being erased, would be a different, more complex problem and quite interesting in its own right.

The input here, though, is a Perl array, and without a window specified we can only interpret the count as from the head of the array. Even though the end of the array is appended with an ellipsis we can only assume it will grow intact as new elements are added.

Now, from a study of the examples, as I understand things we are being requested to produce a single report of the average of the the array values at each index. I suppose the descriptives could be interpreted in other ways but that’s what I got.

So how do we go about this? One of the first things to note is that rather than maintaining a separate count of the values summed to create an average, we already have this value, or something like it, as we’re always counting elements from the first index.

By calling each on the @stream array we get tuples of index and value for each element. We then establish a running $sum value that is kept up-to-date with even new element; dividing this by $idx, which always contains one less than the number of elements summed, will give us an average value of everything seen up to that point.

PERL 5 SOLUTION

use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';



my @stream = (10, 20, 30, 40, 50, 60, 70, 80, 90);

my $sum = 0;
while ( my ($idx, $val) = each @stream ) {
    $sum += $val;
    $_ = sprintf "%.2f", $sum / ($idx+1);
    s/\.0*$//;
    say "average of first ", $idx+1, " numbers is ", $_;
}

raku solution

unit sub MAIN ( *@stream ) ;

@stream.elems == 0 && @stream = (1..10).map: * × 10;

say @stream.WHAT;
my $sum;
for @stream.kv -> $idx, $val {
    $sum += $val;
    given sprintf $sum/($idx+1) {
        s/ \.0* $//;
        say "average of first ", $idx+1, " numbers is ", $_;
    }
}

Ok, we could always do it this way, mirroring the Perl solution. Not much changes, and it gets the job done — at least the job as we defined it earlier. That’s all well and good.

On the other hand, in deference to the idea of an input stream, the word originally used in the task description, well, Raku has all this built-in functionality for asynchronous programming.

In other words, we could, you know, in theory actually build an input stream, start sampling it and counting, and provide a running average report.

Infinitely.

To be clear I did not know how to do this when I started, and have something workable now. I have no idea if this is the best way to to this, but it does seem to do what I want. It’s pretty cool, no wait, very cool. I do want to spend more time in the sandbox trying things out but what I have is up and working so we’ll start with this.

Here’s what I ended up needing to do: What I wanted was an infinite list of data points coming in, preferably over time. This time I’d need to count them as the arrived and keep a running sum to compute the average, as they would end up consumed when no longer needed. We want to use an infinite list, but not keep it.

But with an infinite list, the next problem was how to stop the process, more elegantly than control-C.

So I ended up with the need to listen to two sources and respond to them differently, and also keep moving forward and listening to both if data didn’t come.

I ended up with an abstraction known as a Channel, a sort of data pipe that can be added to to synchronize asynchronous data in a FIFO fashion. Things can get added to the pipe from one end, in one or several threads, and are taken out at the other, by one or more consumers in one or more different threads. It’s a sort of common thread pipe, you might say. In this case there’s only one consumer, our report generator.

I seem to have created four threads here: one to consume the data, one to wait for keyboard input, another to send it, when found, into the Channel, and another to send our simulated stream data into the same Channel.

For that data stream, I copied the style of the example input: 10, 20, 30, 40, 50, 60, … This trick ended up being done with a Supply, a type of data-source abstraction, the sort of thing that can feed a Channel. A Supply with a call to .interval() will produce a never-ending steam of digits, at specified times — here at one-second intervals: 0, 1, 2, 3, 4, 5, … A little massaging transforms this data into the expected values and they are, when created, pushed into the Channel. We have simulated our stream perfectly.

Getting an event-loop for the keyboard was more indirect: I ended up creating a new thread that would sit waiting for getc to produce a value. If one showed up another thread stood waiting to send the value into the Channel pipe. I still feel I’m missing something on the concepts around await, but when viewed another way this seems nice and clean, albeit quite indirect. Implementing “press q to exit” proved unexpectedly complicated, and the solution still requires a return key press. But it’s a toy so I took the win and moved on.

At the other end of the pipe, another thread calls react, reacting to new data being found on the Channel with whenever; if this is a single character it’s taken as a cue to stop looking for new data and exit. Otherwise it’s data from the stream and a new average is computed.

Is this the best way to do this? Possibly, no probably not. Two Channel-s would be conceptually cleaner but I found it hard to keep the event loop from stalling, waiting for new data at one or the other. Combining all the data into a single Channel pipeline fixed that. And yes, using any single key character to exit when we know that stream data will always have two digits is definitely a hack but hey, it is a hack and the details don’t matter to the demonstration. It took a while to get up and running from zero but what I have here finally does what I set out to do; now that I’ve got this far I’ll keep at it and see where we end up. It started very foreign but it’s all beginning to make sense to me now. As I heard said from multiple sources trying to figure this stuff out — “Concurrency is hard”. Now that I have a limited handle on it the tools provided seem to address that problem pretty well.

unit sub MAIN () ;

my $stream = Channel.new;
my $i;
my $sum;

my $p = start {
    say "stream started. Enter any value to exit";
    
    react {
        whenever $stream {
            done() if $_ !~~ /\d ** 2..* /;
            $sum += $_;
            $i++;
            say "received value $_ from stream, cumulative average now {$sum/$i}";        
        }
    }
    exit;
}

start {
    await $*IN.getc.map: -> $c {
        start {
            $stream.send( $c );
        }
    }
}
 
await Supply.interval(1).map: -> $r {
    start {
        $stream.send(($r+1)*10);
    }
}

$stream.close;
await $p;

[colincrain@boris:~/Code/PWC]$  raku 122-1-crossing-the-stream.raku 
stream started. Enter any value to exit
received value 10 from stream, cumulative average now 10
received value 20 from stream, cumulative average now 15
received value 30 from stream, cumulative average now 20
received value 40 from stream, cumulative average now 25
received value 50 from stream, cumulative average now 30
received value 60 from stream, cumulative average now 35
q

---

episode two:
“A Basketball Jones Oh Baby Oo-oo-ooo…“

---

task 2

Basketball Points

Submitted by: Mohammad S Anwar

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.

Example

Input: $S = 4
Output: 1 1 1 1
        1 1 2
        1 2 1
        1 3
        2 1 1
        2 2
        3 1

Input: $S = 5
Output: 1 1 1 1 1
        1 1 1 2
        1 1 2 1
        1 1 3
        1 2 1 1
        1 2 2
        1 3 1
        2 1 1 1
        2 1 2
        2 2 1
        2 3
        3 1 1
        3 2

Method

What we have here is an integer partition problem, of sorts, where we only allow the partitions the maximum value of 3. I say “of sorts” but we’ll get to that. We want all combinations of 1, 2 and 3 that add to the given sum.

I thought up a way to do this — just me and my facilities out on a walk — so I sez to myself: “Let’s start with an empty list of lists, and just keep adding lists of partial partitions to it as long as the sum is less than the final score”.

Ok.

And yes, I probably did say it to myself in pretty much those words. Such is life being me.

We would work through this list, shifting off the next working instance of a partial from one end, adding each of either a new 1, 2 or 3 to the end of it and, if the new instance still summed less than the total, pushing it on the backside of the queue to come around again. On the other hand, if the sum came out exact, we’ve found one partition and that list is moved over to another list of solutions and not recycled. And if we’re over with the total, well, we just forget about that instance and move on. Lots of lists-of-lists going on here, but when we’re done our solutions will be a list of lists of every valid partition.

The first time around I put in a clause: that any new number cannot be less than the last number placed. This avoids repetitions by keeping the new patterns ordered, and we won’t get either (1, 2, 1, 2) or (2, 1, 2, 1), but only one instance of that set, (1, 1, 2, 2).

However, after I got this up and running I realized that what was being requested in fact did want these repetitions counted as separate variations, in variance to what we normally consider integer partitions. Hence my earlier clause “of sorts”. So be it; this only involved stripping out a single grep filtering the @points options, so now at each juncture the full gamut of adding a new 1, 2 or 3 was considered. We now have a list of lists of every conceivable way of accumulating a given number of points in a basketball game. The technical term for this is an S-restricted composition of N. Compositions are to partitions as permutations are to combinations: compositions are ordered, partitions are not.

And one more thing…

Now I have that amazing groove stuck in my head. Basketball Jones, I got a basketball jones… Let’s see… Nikki Hopkins on piano, Carol King on electric piano, Billy Preston on organ, wait, George Harrison on guitar?… Backup singers? How about Darlene Love, Ronnie Spector and Michelle Phillips? The whole big-show thing was unplanned; Cheech and Chong were there to cut a silly track, and Tommy Chong knew George Harrison who was in the studio next door… and as the day went on everybody wanted to get in on it. Just a bunch of folks who happened to be hanging out at Herb Alpert’s studio that day, abetted by whoever they wanted to give a call. What a weird, wonderful, singular musical document. Reached #15 on the Billboard charts, too, with good reason.

Because it’s amazing, that’s why.

PERL 5 SOLUTION

================================================================================
Jul 24, 2021 at 3:43:06 AM
~/Code/PWC/122-2-trip-from-the-line.pl
--------------------------------------------------------------------------------
2 3
3 2
1 1 3
1 2 2
1 3 1
2 1 2
2 2 1
3 1 1
1 1 1 2
1 1 2 1
1 2 1 1
2 1 1 1
1 1 1 1 1

The code:

use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';
use List::Util qw( sum );

my $score = shift @ARGV // 5 ;      ## default value
my @points = ( 1, 2, 3 );

my @queue = map { [$_] } grep { $_ <= $score } @points;
my @solutions;

while ( my $seq = shift @queue ) {
    for my $next (  @points ) {
        my $sum = sum $seq->@*, $next;
        if ( $sum <= $score ) {
            $sum == $score ? push @solutions, [$seq->@*, $next]
                           : push @queue,     [$seq->@*, $next] ;
        }
    }
}

say "$_->@*" for @solutions;

Raku Solution

I’m really starting to fall in love with the elegance of a nicely crafted piece of Raku. I hope Perl will forgive me. Here we have some nice examples of “whatever” code, and slips to dereference the values of an array container used to construct a new list. Creating the kernel list-of-lists was interesting; we use grep to filter the list of possible points to find those under the requested value, and map each of those values to a new Array object. It’s the same as in Perl but just looks a little different.

unit sub MAIN (Int $score = 5) ;

my @points = 1, 2, 3 ;
my @queue  = @points.grep( * <= $score )
                    .map(  *.Array ) ;
my @parts;

while @queue.shift -> @seq {
    for @points {
        my @new = |@seq, $_ ;
        next if @new.sum > $score;
        @new.sum == $score ?? @parts.push: @new
                           !! @queue.push: @new;
    }
}

put $_ for @parts;