Merge pull request #361 from dmanto/branch-for-challenge-016

my proposed solutions for challenge-016, p5 1 & 2

2 files changed, 159 insertions, 0 deletions

diff --git a/challenge-016/daniel-mantovani/perl5/ch-1.pl b/challenge-016/daniel-mantovani/perl5/ch-1.pl
new file mode 100644
index 0000000000..9734423343
--- /dev/null
+++ b/challenge-016/daniel-mantovani/perl5/ch-1.pl
@@ -0,0 +1,42 @@
+# 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.
+
+use strict;
+use warnings;
+
+# we start by reading total number of guests, or 100
+# by default
+
+my $total_guests = shift // 100;
+
+# we assume that each guest get his or her part of the pie
+# according with the following formula:
+
+# guest_part = remaining x guest_ordinal / total_guests
+
+# as you can see, is exactly as the Pie Puzzle states, when total_guests
+# is 100
+
+my $remaining    = 100;    # this is 100% of the pie
+my $biggest_part = 0;
+my $biggest_part_guest;
+
+for my $guest_ordinal ( 1 .. $total_guests ) {
+    my $part = $remaining * $guest_ordinal / $total_guests;
+    $remaining -= $part;    # because $part is what $guest_orinal gets
+    next unless $part > $biggest_part;
+
+    # here we have a bigger part than any other before
+    $biggest_part       = $part;
+    $biggest_part_guest = $guest_ordinal;
+}
+
+printf
+"On a Pitagoras Pie Party of %u, %u-th guest gets the biggest part of the pie (%.4f%%)\n",
+  $total_guests, $biggest_part_guest, $biggest_part;
diff --git a/challenge-016/daniel-mantovani/perl5/ch-2.pl b/challenge-016/daniel-mantovani/perl5/ch-2.pl
new file mode 100644
index 0000000000..025076a8a4
--- /dev/null
+++ b/challenge-016/daniel-mantovani/perl5/ch-2.pl
@@ -0,0 +1,117 @@
+# 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
+
+use strict;
+use warnings;
+use Digest::SHA qw/sha256 sha256_hex/;
+
+# we start by defining an array with the ordered symbols of the
+# base 58 representation
+# note the "holes" left to highlight the non existing characters
+# (number "0", upper case letter "I", upper case letter "O", and
+# lower case letter "l"
+
+my @base58 = qw {
+  1 2 3 4 5 6 7 8 9
+  A B C D E F G H   J K L M N   P Q R S T U V W X Y Z
+  a b c d e f g h i j k   m n o p q r s t u v w x y z
+};
+
+# whith this list we can build part of a regexp to
+# check matchings for these chars only
+# like 1|2|3..y|z
+
+my $ored_chars = join( '|', @base58 );
+
+# we can also build a hash to convert each symbol
+# to its code value, like
+
+my %base58_codes = map { $base58[$_] => $_ } 0 .. 57;
+
+# now we can define the decode58 function. That is,
+# given a string encoded with our base58 representation,
+# we return an array of 25 decoded integers (bytes)
+
+# as we don't want to use a BigInt module and the binary
+# result will indeed represent a big integer, we are going to take
+# care of the internal math manually, just adding byte by
+# byte and taking care of carrying values
+
+sub decode58 {
+
+    # we assume that the input is a valid base58 encoded string
+    my $in = shift;
+    my @out;    # here is where the end result is calculated
+    for my $c ( split '', $in ) {
+
+        # first we multiply all @out values by 58
+        # (this will be no operation on first pass).
+        # Note also that by doing this, we will end with a non
+        # very well formated integer represented array, in the
+        # sense that we will probably have values > 255
+        # in several of its elements.
+        # But this is not going to be a problem because we will
+        # normalyse the array after adding the new char code
+        # below, taking care of elements greater than 255
+        $_ *= 58 for @out;
+
+        # and now we add code value char by char.
+        # Note that $out[0] will be the least significant
+        # byte of the result
+        $out[0] += $base58_codes{$c};
+
+        # now we do the carry on every value of @out, starting
+        # with $out[0], when it exceeds byte max value (255)
+        # this is the "normalization" process we refered above
+        for my $i ( 0 .. $#out ) {
+            my $v = $out[$i];
+            next unless $v > 255;
+
+            # here we need to carry excess of 256 to $out[$i+1]
+            $out[ $i + 1 ] += int( $v / 256 );
+
+            # and adjust $out[$i] accordingly
+            $out[$i] = $v % 256;
+        }
+    }
+
+    # we now left-pad calculated @out, to always return a 25 bytes
+    # array
+    $out[$_] //= 0 for 0 .. 24;
+
+    # now we return calculated @out, just taking care of
+    # the right order, wich is most significant byte first
+    return reverse @out;
+}
+
+# with that decode58 function, we just write the script according
+# to valid bitcoin address definitions
+
+my $address_to_check = shift;
+
+die "Invalid format address"
+  unless $address_to_check =~ /^($ored_chars){26,35}$/;
+
+my @decoded = decode58($address_to_check);
+my $double256 = sha256( sha256( pack 'C*', @decoded[ 0 .. 20 ] ) );
+
+# note that pack 'C*', @decoded[0..20] will be the first 21 bytes
+# of the decoded result properly concatenated to be hashed by sha256
+
+my $check256 = pack 'C*', @decoded[ 21 .. 24 ];
+
+die "Checksum verification error on address"
+  unless $check256 eq substr( $double256, 0, 4 );
+
+printf "%s is a valid bitcoin address\n", $address_to_check;