Pythagoras Bitcoin with Raku

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

Challenge #16.1: Pythagoras Pie Puzzle

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

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

See docs.raku.org/syntax/loop for more information about loop (which can also be used as a C-style loop; eg. loop (my $i = 0; $i < 10; $i++) { say $i; }.)

$ raku 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.

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 indices (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 indices are 0..99.

Running it:

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

Challenge #16.2

1BvBMSEYstWetqTFn5Au4m4GFg7xJaNVN2
3J98t1WpEZ73CNmQviecrnyiWrnqRhWNLy

There are basically three ways to approach this:

• A procedure
• A type
• A regex

We can start with a custom type «BitcoinAddress» declared with subset 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]>+$/;

See docs.raku.org/language/typesystem#index-entry-subset-subset for more information about subset.

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 Raku 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:

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:

$ raku 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

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 Raku from Zero to 35 article, where I handled exactly that in the «Even Higher (Bonus)» section.

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 indices 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 Raku 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.raku.org/routine/polymod
• Buf: docs.raku.org/type/Buf
• eqv: docs.raku.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:

$ raku bitcoin-validator 1BvBMSEYstWetqTFn5Au4m4GFg7xJaNVN2
Valid

$ raku bitcoin-validator 1BvBMSEYstWetqTFn5Au4m4GFg7xJaNVNa
Not valid

$ raku bitcoin-validator 3J98t1WpEZ73CNmQviecrnyiWrnqRhWNLy
Valid

$ raku bitcoin-validator 3J98t1WpEZ73CNmQviecrnyiWrnqRhWNLz
Not valid

$ raku bitcoin-validator QQQQQQQQQQQQQQQQ
Not valid

And that's it.