laurent_r

These are some answers to the Week 16 of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Spoiler Alert: This weekly challenge deadline is due in several days from now (July 14, 2019). This blog post offers some solutions to this challenge, please don't read on if you intend to complete the challenge on your own.

Challenge # 1: Pythagoras Pie

At a party a pie is to be shared by 100 guest. The first guest gets 1% of the pie, the second guest gets 2% of the remaining pie, the third gets 3% of the remaining pie, the fourth gets 4% and so on. * Write a script that figures out which guest gets the largest piece of pie. (Challenge proposed by Jo Christian Oterhals)*

The first guest gets 1% of the whole pie. The second guest gets 2% of 99%, i.e. 1.98%. And so on: each guest gets in turn a larger share of what is left of the pie, but, at the same time, what is left of the pie gets smaller and smaller. So, intuitively, there must be a point where the share sizes start diminishing. If there was a 101st guest, she would get nothing, since the 100th guest took everything that is left (in fact a very tiny share).

Using a One-Liner Script to Display Each Guest's Share of the Pie

It is quite easy to write a Perl 5 one-liner to display the share of each guest. Given that the share become really minuscule after a while, I'll print the shares only for the first 50 guests. In the following one-liner script, $p represents each guest, $r the fraction of the pie that remains at any given point, and $sh is a constant representing the share. We display the guest number, what remains of the pie and the share taken by the guest:

$ perl -E '$r = 1; $sh = .01; for $p (1..50) {printf "%i\t%0.10f\t%0.10f\n", $p, $r, $r*$p*$sh; $r -=  $r*$p*$sh; }'
1       1.0000000000    0.0100000000
2       0.9900000000    0.0198000000
3       0.9702000000    0.0291060000
4       0.9410940000    0.0376437600
5       0.9034502400    0.0451725120
6       0.8582777280    0.0514966637
7       0.8067810643    0.0564746745
8       0.7503063898    0.0600245112
9       0.6902818786    0.0621253691
10      0.6281565096    0.0628156510
11      0.5653408586    0.0621874944
12      0.5031533642    0.0603784037
13      0.4427749605    0.0575607449
14      0.3852142156    0.0539299902
15      0.3312842254    0.0496926338
16      0.2815915916    0.0450546547
17      0.2365369369    0.0402112793
18      0.1963256577    0.0353386184
19      0.1609870393    0.0305875375
20      0.1303995018    0.0260799004
21      0.1043196015    0.0219071163
22      0.0824124852    0.0181307467
23      0.0642817384    0.0147847998
24      0.0494969386    0.0118792653
25      0.0376176733    0.0094044183
(Rest of the display omitted for brevity)

So, it turns out that the 10th guest gets the largest share of the pie (6.28%).

Of course, we can do more or less the same in Perl 6:

$ perl6 -e 'my $r = 1; for 1..50 -> $p {printf "%i\t%0.10f\t%0.10f\n", $p, $r, $r*$p*.01; $r -=  $r*$p*.01;}'
1       1.0000000000    0.0100000000
2       0.9900000000    0.0198000000
3       0.9702000000    0.0291060000
4       0.9410940000    0.0376437600
5       0.9034502400    0.0451725120
6       0.8582777280    0.0514966637
7       0.8067810643    0.0564746745
8       0.7503063898    0.0600245112
9       0.6902818786    0.0621253691
10      0.6281565096    0.0628156510
11      0.5653408586    0.0621874944
12      0.5031533642    0.0603784037
13      0.4427749605    0.0575607449
14      0.3852142156    0.0539299902
15      0.3312842254    0.0496926338
(Rest of the display omitted for brevity)

But we're cheating a bit with these one-liners. The challenge says: * Write a script that figures out which guest gets the largest piece of pie.* Our one-liners display the share and it is the human person reading the output that really figures out which share is the largest.

We could still do it with a one-liner, for example in Perl 5:

$ perl -E '$r = 1; $sh = .01; $max_sh = 0; for $p (1..100) { 
    ($max_p, $max_sh) = ($p, $r*$p*$sh) 
        if $r*$p*$sh > $max_sh; $r -= $r*$p*$sh
    } 
    say "$max_p\t$max_sh";'
10      0.0628156509555295

But I'm afraid this is now becoming a bit too hairy, it will be cleaner to write real scripts.

Real Scripts for Finding the Largest Share

Since we've already done it with one-liner, writing a full-fledged script in Perl 5 is not complicated:

#!/usr/bin/perl
use strict;
use warnings;
use feature qw/say/;
use constant SHARE_FACT => 0.01;

my $rest_of_the_pie = 1;
my ($max_guest, $max_sh) = (1, 0);
for my $guest_nr (1..100) {
    my $share = $rest_of_the_pie * $guest_nr * SHARE_FACT;
    ($max_guest, $max_sh) = ($guest_nr, $share) if $share > $max_sh;
    $rest_of_the_pie -= $share;
}
say "Lucky guest: $max_guest \tLargest share: $max_sh";

This prints the following output:

$ perl pythagoras_pie.pl
Lucky guest: 10         Largest share: 0.0628156509555295

We can directly translate the algorithm in Perl 6:

use v6;

constant $share-fact = 0.01;
my $rest-of-the-pie = 1;
my ($max-guest, $max-sh) = 1, 0;
for 1..100 -> $guest-nr {
    my $share = $rest-of-the-pie * $guest-nr * $share-fact;
    ($max-guest, $max-sh) = ($guest-nr, $share) if $share > $max-sh;
    $rest-of-the-pie -= $share;
}
say "Lucky guest: $max-guest \tLargest share: $max-sh";

But we can do something much more concise in Perl 6 using the sequence operator, functional programming and some built-in functions:

use v6;

my $rest = 1;
my @shares = map { my $sh = $rest * $_; $rest -= $sh; $sh}, 
    (0, .01 ... 1); 
say  map { $_, @shares[$_] }, @shares.keys.max({@shares[$_]});

which prints out:

((10 0.06281565095552947))

We start with the sequence operator ... to build a list of 101 relative shares and use a map statement to build @shares, the list of final shares of the original pie. Then we use the max routine to find the index of the largest value, and finally print the index and the value. Note that we started the original sequence with 0, although this is useless for the computations, because this makes it possible to use the array index as a rank (otherwise, the script would have printed 9, instead of 10, for the rank of the lucky guest).

Another approach is to build directly the @shares array with the sequence operator and a generator (i.e. a code block to generate the next item from the previous one):

use v6;

my ($rest, $a) = 1, .01;
my @shares = 0, .01, -> $b {$rest -= $b; $a += .01; $rest * $a} … *;
say  map {$_, @shares[$_]}, @shares[0..100].keys.max({@shares[$_]});

Validation of Bitcoin Addresses

Write a script to validate a given bitcoin address. Most Bitcoin addresses are 34 characters. They consist of random digits and uppercase and lowercase letters, with the exception that the uppercase letter “O”, uppercase letter “I”, lowercase letter “l”, and the number “0” are never used to prevent visual ambiguity. A bitcoin address encodes 25 bytes. The last four bytes are a checksum check. They are the first four bytes of a double SHA-256 digest of the previous 21 bytes. For more information, please refer [wiki]'https://en.bitcoin.it/wiki/Address) page. Here are some valid bitcoin addresses:

1BvBMSEYstWetqTFn5Au4m4GFg7xJaNVN2
3J98t1WpEZ73CNmQviecrnyiWrnqRhWNLy

I do not know anything about Bitcoins, so I just tried to apply the rules described in the challenge. But it seems that they are not complete, or maybe I missed something important.

I'll try to investigate the matter further and to come back to this later in the week (Update: see this new post).