Pythagoras Bitcoin
with Perl 6

by Arne Sommer

Pythagoras Bitcoin with Perl 6

Published 13. July 2019

This is my response to the Perl Weekly Challenge #16.

Challenge #16.1

Pythagoras Pie Puzzle, proposed by Jo Christian Oterhals.

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.

We can start with the numbers (the size of the pieces), which is suitable job for a sequence with «gather/take»:

File: pythagoras-pie-all
my $pythagoras-pie := gather  # [1]
{
  my $remainder = 100;        # [2]
  my $position  = 1;          # [3]
  loop                        # [4]
  {
    my $part = $remainder * $position / 100; # [5]
    $remainder -= $part;                     # [6]
    $position++;                             # [7]
    take $part;                              # [8]
  }
}

say "{ $_ + 1 } ->  $pythagoras-pie[$_]%" for ^100; [9]

[1] We set up the sequence with binding (:=) to ensure that it stays lazy (as evaluating an inifinite list doesn't work out).

[2] The size of the pie (in %), starting with 100.

[3] The position in the sequence. We need this as the portion is defined related to this variable.

[4] An infinite loop.

[5] The size of the part given to the current guest.

[6] The remainder of the pie, after the current guest has been served.

[7] Increase the position, ready for the next iteration of the loop (#4).

[8] Return the current size.

[9] Print the 100 first values from the sequence. (Any values after this are all zero.)

Running it (with just some of the lines shown):
$ perl6 pythagoras-pie-all
1 ->  1%
2 ->  1.98%
3 ->  2.9106%
4 ->  3.764376%
5 ->  4.5172512%
6 ->  5.149666368%
7 ->  5.64746745024%
8 ->  6.002451118541%
9 ->  6.21253690768973%
10 ->  6.281565095552947%
11 ->  6.21874944459741773%
12 ->  6.037840369845492849%
13 ->  5.75607448591936984904%
14 ->  5.392999018345995%
15 ->  4.969263381190237%
...
96 ->  3.7330486177577654e-34%
97 ->  1.5087738163437654e-35%
98 ->  4.572984556753267e-37%
99 ->  9.239295328950519e-39%
100 ->  9.332621544394437e-41%

We can see that the answer is 10; i.e. guest number 10 gets the largest piece of cake. But the task was for the program to figure it out, so let's do just that.

Finding the largest value is easy, as long as we chop off the sequence after the first 100 elements. (The rest of them, ad infinitum, are zero. Trying to access all elements in an infinite list is not a good idea.)

say $pythagoras-pie[^100].max; # -> 6.281565095552947

But this doesn't tell us the position (or index), and thus which guest.

File: pythagoras-pie
my $pythagoras-pie := gather
{
  my $remainder = 100;
  my $position  = 1;
  loop
  {
    my $part = $remainder * $position / 100;
    $remainder -= $part;
    $position++;
    take $part;
  }
}

my $largest = $pythagoras-pie[^100].max;                          # [1]

for (^100).grep({ $pythagoras-pie[$_] == $largest }) -> $guest    # [2]
{
  say "Guest #{ $guest + 1 } got the largest piece of cake ({ $largest }%).";
}                # [3]

[1] Get the highest value in the first 100 elements of the sequence. (We had to get rid of the infinite sequence, as «max» obviously cannot reach the end.)

[2] Iterate over the indeces (0 to 99), select the ones (with «grep») where the value in the list is equal to the highest value. Note that this would give all matches, if there had been more than one (but there isn't).

[3] Compensate for the numbering discrepancy; the guests are given as 1..100, but the indeces are 0..99.

Running it:

$ perl6 pythagoras-pie
Guest #10 got the largest piece of cake (6.281565095552947%).

Challenge #16.2

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 page.

Here are some valid bitcoin addresses:

1BvBMSEYstWetqTFn5Au4m4GFg7xJaNVN2
3J98t1WpEZ73CNmQviecrnyiWrnqRhWNLy

There are basically three ways to approach this:

  • A procedure
  • A type
  • A regex
I'll start with the type, and see where that leads us.

We can start with a custom type «BitcoinAddress» that validates the address for us. The challenge says that «Most Bitcoin addresses are 34 characters», which is pretty vague. The Bitcoin wiki page is more helpful, as it states that a Bitcoin address «is an identifier of 26-35 alphanumeric characters». Then we add the legal characters (as given in the challenge):

subset BitcoinAddress of Str where 26 <= .chars <= 35
  && /^<[123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz]>+$/;

Now we can just use that type when we assign a new Bitcoin Address, and the program will do the validation for us, automatically:

my BitcoinAddress $a = '1BvBMSEYstWetqTFn5Au4m4GFg7xJaNVN2';
my BitcoinAddress $b = '3J98t1WpEZ73CNmQviecrnyiWrnqRhWNLy';

Trying an illegal value gives an error:

> my BitcoinAddress $c = '4J98t1WpEZ73CNmQviecrnyiWrnqRhWNLy';
Type check failed in assignment to $c; expected BitcoinAddress but got
  Str ("4J98t1WpEZ73CNmQviec...)

Using a character class is tempting, but as Perl 6 is Unicode compliant the notion of a character and digit doesn't work out here (as e.g. «ß» and «Å» are characters).

But we can use subtraction like this:

subset BitcoinAddress of Str where .chars == 34
  && /^<[1..9 A..Z a..z]-[IOl]>+$/;

This is easier to read than the complete list I used above, as it clearly marks out the missing values.

The Bitcoin wiki page states that the first character(s) must be one of «1», «3» or «bc1», so we add that as well to the type:

subset BitcoinAddress of Str where .chars == 34
  && /^<[1..9 A..Z a..z]-[IOl]>+$/
  && /^[1|3|bc1]/;

We haven't looked into the validation part yet, but let us write the program first:

File: bitcoin-validator-dummy
subset BitcoinAddress of Str where 26 <= .chars <= 35
  && /^ <[1..9 A..Z a..z]-[IOl]>+$/
  && /^[1|3|bc1]/;

multi MAIN (BitcoinAddress $bca)
{
  say "Valid";
}

multi MAIN (Str $string)
{
  say "Not valid";
}

Running it:

$ perl6 bitcoin-validator-dummy 1BvBMSEYstWetqTFn5Au4m4GFg7xJaNVN2
Valid

The program is quite simple as multiple dispatch removes the problem with illegal values that would have terminated the program (with a type check error, as shown previously).

The Validation

Validation is the hard part.

The challenge isn't clear about the difference between characters (there are 34 of them in an address) and bytes (there are 25 of them in an address), but the Technical background of version 1 Bitcoin addresses Bitcoin wiki page gives the clue; «Base58» and «Base58 encoding». Then it is simply a case of digging up my Perl 6 from Zero to 35 article, where I handled exactly that in the «Even Higher (Bonus)» section.

File: bitcoin-validator
use Digest::SHA;                                     # [1]

subset BitcoinAddress of Str where 26 <= .chars <= 35
  && /^ <[1..9 A..Z a..z]-[IOl]>+$/
  && /^[1|3|bc1]/;

my @alphabet = (1..9, "A".."H", "J".."N", "P".."Z", "a".."k", "m".."z").flat;
                                                     # [2]
						   
my %values = @alphabet.map( { $_ => $++ } );         # [3]
					 
my $alphabet-length = @alphabet.elems;               # [4]

multi MAIN (BitcoinAddress $bca)
{
  my @values = from-baseX($bca, $alphabet-length).polymod(256 xx 24).reverse;
  # [5] ###### # [6] ############################ # [5a] ########### # [5b]
					 
  my @check  = @values[21..24];                      # [7]
					 
  my @sha    = sha256(sha256(Buf.new(@values[^21]))).list[^4];
  # [8] ###### # [8a] ###### # [8b] # [8c] ######### # [8d] #  
      
  @sha eqv @check                                    # [9]
    ?? say "Valid"
    !! say "Not valid";
}

multi MAIN (Str $string)
{
  say "Not valid";
}

sub from-baseX (Str $value, Int $base = 42)  # [6]
{
  my $return = 0;
  my $exp    = 0;

  for $value.flip.comb -> $digit
  {
    $return += %values{$digit} * $base ** $exp++;
  }
  return $return;
}

[1] Install the «Digest» module with «zef install Digest» if it hasn't been installed already. It provides «sha256» for us.

[2] Note the repetition. We already have this as a regex (in the line above), but we also need it as a list - as BaseX uses the indeces to calculate the values.

[3] The reverse of the above; give it a letter and get the index in the array, which is the baseX value.

[4] The length of the alphabet, which is 58.

[5] The 25 bytes, by applying Base58 on the string. The result of [6] is a number, and we use «polymod» [5a] to chop if into 24 bytes (values in the range 0-255; or Base256). The result is in reverse order, courtesy of «polymod» and we fix that by applying «reverse» [5b].

[6] See my Perl 6 from Zero to 35 article for a detailed description of «from-baseX» (and «polymod»).

[7] The 4 checksum bytes.

[8] We apply «sha256» twice [8a] on the first 21 bytes [8c]. «sha256» works on «Buf» objects, so we must generate one [8b]. The result is also a «Buf» object, and we use «list» on it to get a list [8d] and finally we save the first four bytes only.

[9] Compare the two arrays, with «eqv» which can compare complex structures.

See the following documentation pages for more information:
• polymod: docs.perl6.org/routine/polymod
• Buf: docs.perl6.org/type/Buf
• eqv: docs.perl6.org/routine/eqv

Note the hybrid approach. The actual validation (the sha-magic) is done in the procedure, and not in the type validation code. This may look messy (and we end up with two «say "Not valid"» lines), but it works.

Testing it:

$ perl6 /bitcoin-validator 1BvBMSEYstWetqTFn5Au4m4GFg7xJaNVN2
Valid

$ perl6 bitcoin-validator 1BvBMSEYstWetqTFn5Au4m4GFg7xJaNVNa
Not valid

$ perl6 bitcoin-validator 3J98t1WpEZ73CNmQviecrnyiWrnqRhWNLy
Valid

$ perl6 bitcoin-validator 3J98t1WpEZ73CNmQviecrnyiWrnqRhWNLz
Not valid

$ perl6 bitcoin-validator QQQQQQQQQQQQQQQQ
Not valid

And that's it.