- Added solutions by Colin Crain.

4 files changed, 391 insertions, 0 deletions

diff --git a/challenge-097/colin-crain/perl/ch-1.pl b/challenge-097/colin-crain/perl/ch-1.pl
new file mode 100644
index 0000000000..4cefa7c3fc
--- /dev/null
+++ b/challenge-097/colin-crain/perl/ch-1.pl
@@ -0,0 +1,173 @@
+#! /opt/local/bin/perl

+#

+#       et-tu-brute.pl

+#

+#         TASK #1 › Caesar Cipher

+#         Submitted by: Mohammad S Anwar

+#         You are given string $S containing alphabets A..Z only and a number $N.

+# 

+#         Write a script to encrypt the given string $S using Caesar Cipher with

+#         left shift of size $N.

+# 

+#         Example

+#             Input: $S = "THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG", $N = 3

+#             Output: "QEB NRFZH YOLTK CLU GRJMP LSBO QEB IXWV ALD"

+#     

+#             Plain:    ABCDEFGHIJKLMNOPQRSTUVWXYZ

+#             Cipher:   XYZABCDEFGHIJKLMNOPQRSTUVW

+#     

+#             Plaintext:  THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG

+#             Ciphertext: QEB NRFZH YOLTK CLU GRJMP LSBO QEB IXWV ALD

+

+#         method:

+#             Left shift? Right shift? I'll mimic the example.

+

+#             The Caesar cypher is a near trivial translation cypher, shifting

+#             the alphabet as written a certain number of characters to the left

+#             or right and wrapping around should the letter to be written fall

+#             above "z" or below "a".

+# 

+#             The reassignment can be done with two lists, shifting one reletive

+#             to the other and restarting the lists as required:

+#             

+#                 A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z 

+#          +5      | | | | |A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z  

+#                  | | | | | | | | | | | | | | | | | | | | | | | | |     

+#         -->     V|W|X|Y|Z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U

+

+#             After shifting, those letters beyond "Z" are moved to start the

+#             list at "A", completing the translation. To encode, one looks up

+#             the letter on the top list, then scans downward to find its

+#             shifted encoding. To decode, the same operation is done in

+#             reverse.

+

+#             Although this simplest of ciphers can hardly even be called

+#             cryptographic, there is reason to believe it may have been

+#             effective in Caesar's time. With the reletively consistent

+#             declension in Latin grammer it would have been relatively easy to

+#             spot recurring word endings, and from there to work out the

+#             offset, but there are no contemporanious accounts from anyone

+#             figuring this out. Letter frequency analysis, used to attack less

+#             regular cryptograms, would not be invented until the 9th century.

+# 

+#             It has also been suggested that most people in the position to

+#             intercept a courier's message would be illterate anyway, including

+#             the courier.

+# 

+#             As such the cypher functions more as an obsticle than a vault,

+#             making a message require an effort to be read, akin to sealing an

+#             envelope to turn away prying eyes.

+

+#             In Perl, a straight rendition of the visual encoding method above

+#             would be to use the translation operator, `tr/abc/xyz/`. Given a

+#             string of characters and a matching association, the operator

+#             reroutes one letter for another efficiantly and extremely quickly.

+#             The problem with this is the operator works its magic building its

+#             routing table at complile time, as so no variable interpolation is

+#             allowed. So somehow we'd have to already know what our encoding

+#             alphabet looks like even before we compute it, so we can

+#             explicitly write out

+ 

+#                 tr/ABCDEFGHIJKLMNOPQRSTUVWXYZ/FGHIJKLMNOPQRSTUVWXYZABCDE/

+

+#             There's an obvious chicken-and-egg problem here, which is

+#             generally solved using a string `eval` statement to interpolate

+#             and then spin off a new Perl context to compile it in. There are

+#             security concerns about turning `eval` loose on random user input,

+#             so we're not going to do that today.

+# 

+#             The next best plan is to use a hash table, with each letter used

+#             as a key pointing to a translated replacement. This requires some

+#             calculation upfront to create the hash but once that is done its

+#             smooth sailing. The difficulties, as they are, come from deriving

+#             the pattern of the character offsets.

+# 

+#             A good way to do this would be by constructing an array comprised

+#             of the letters in the alphabet repeated twice. For input the

+#             letters would be indexed 0-25, and encoded we could add any offset

+#             up to 26. The wrap around is taken care of by restarting the

+#             letters with A at postion 26.

+# 

+#             I like this approach, but ultimately decided to pursue a more

+#             mathematical solution. You see, letters as computer text already

+#             have a numerical mapping built in to them, being the ASCII codes

+#             that are actually recorded in memory for each character. With a

+#             numerical association to the numbers 0 through 25, we can then use

+#             modulo arithmetic to seamlessly loop around when shifting the

+#             values.

+

+#             The only complication to using ASCII codes being that the

+#             numbering doesn't start at 0. For the upper-case letters, the

+#             numbering goes from 65 to 90. But this is no mind, we only need to

+#             upper case the text, get its number, subtract 65, add or subtract

+#             the offset as determined, run the result modulo 26 and then add 65

+#             again, then view the code as a number again.

+# 

+#             Well in Perl we have the functions `ord` and `chr` to shift back

+#             and forth between charaters and ascii, and the rest is just some

+#             arithmetic. 

+

+#             To do the actual translation, I'd rather not break the text up

+#             into an array. Sure that would work, but it would be nice to not

+#             have to recopy the text. To this end we can unleash the regular

+#             expression engine on the input string in a grand substitution

+#             scheme, matching any letter. When any single lower- or uppercase

+#             letter is matched, it is captured and handed off to a helper

+#             translation routine that performs the numerical massaging magic

+#             we've outlines above, returning the new character which is

+#             substituted in for the original using the `/e` switch. Adding the

+#             global `/g` swithc and we're streaming away.

+

+#             If we wanted to the expression easily fits into one long line, but

+#             having a helper is much easier on the eyes.

+

+#             Whitespace will be preserved as that is the way it works in the

+#             example. This is contrary to elementary rules of cyphering, as

+#             word boundries reveal short words, which are limited in their

+#             possiblities an provide a opportunity to attack the script.

+#             Cyphers are normally broken into equal sized segments of

+#             characters to confound this attack.

+# 

+#             I find it interesting that weak as this cypher may be now, as

+#             Caesar would have used it it would have been a bit stronger, as

+#             spacing between words date from only the Early Medieval era, with

+#             Irish monks transcribing and illuminating Latin texts. It turns

+#             out that reading fluency makes word gaps somewhat superfluous; the

+#             reletive consistancy of Latin words and their declensions would

+#             make it easy to identify the start and stopping of individual

+#             words, and the grammar rules would dictate phrases. It was only

+#             when early medieval scribes, at the time primarily Irish monks,

+#             began to copy the Latin text that they began inserting additional

+#             space to help keep the more unfamiliar texts straight. The

+#             original Latin-language writers would always have had the option

+#             of using an interpunct dot between words but this was not normally

+#             done in common communications. Likewise spacing, which only worked

+#             itself in on a paragraph level. Without word boundries to orient

+#             the reader decyphering would be more difficult.

+# 

+# 

+# 

+# 

+#        

+#             

+#             

+#       © 2021 colin crain

+## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##

+

+

+

+use warnings;

+use strict;

+use feature ":5.26";

+

+

+my $n   = shift // 3;

+my $str = shift // "THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG";

+

+say $str;

+$str =~ s/([a-zA-Z])/encode($1,$n)/ge;

+say $str;

+

+sub encode {

+    my $out = chr(((ord(uc $_[0])-65-$_[1])%26)+65);

+}

diff --git a/challenge-097/colin-crain/perl/ch-2.pl b/challenge-097/colin-crain/perl/ch-2.pl
new file mode 100644
index 0000000000..561b312419
--- /dev/null
+++ b/challenge-097/colin-crain/perl/ch-2.pl
@@ -0,0 +1,140 @@
+#! /opt/local/bin/perl

+#

+#       flippenbitter.pl

+#

+#         TASK #2 › Binary Substrings

+#         Submitted by: Mohammad S Anwar

+#         You are given a binary string $B and an integer $S.

+# 

+#         Write a script to split the binary string $B of size $S and then find

+#         the minimum number of flips required to make it all the same.

+# 

+#         Example 1:

+#             Input: $B = “101100101”, $S = 3

+#             Output: 1

+#     

+#             Binary Substrings:

+#                 "101": 0 flip

+#                 "100": 1 flip to make it "101"

+#                 "101": 0 flip

+# 

+#         Example 2:

+#             Input $B = “10110111”, $S = 4

+#             Output: 2

+#     

+#             Binary Substrings:

+#                 "1011": 0 flip

+#                 "0111": 2 flips to make it "1011"

+# 

+#         method:

+#             I rather enjoy these odd little puzzles with a lot of small moving

+#             parts working towards some exotic goal. In this one we need to

+#             segment the initial string, making sure it divides out evenly,

+#             then compare the bits in each segment against those in all of the

+#             remaining segments, calculating the changes required to alter the

+#             other to match the first, then sum the results for the list.

+#             Finally, after comparing each section the minimum sum among all

+#             the sections, representing the most efficiant way to go about

+#             things, will be the result requested. The given goal, the number

+#             of bits flipped to equalize the segments to one of the values

+#             without specifiying which, does not serve any obvious practical

+#             purpose in itself. It could be a widget in a longer chain of data

+#             processing, but who knows? This robs us the opportunity to provide

+#             background and commentary on the context, but on the other hand

+#             allows us to focus on the quiltwork: stiching together smaller

+#             disparate ideas to form a cohesive whole. 

+# 

+#             Whew!

+# 

+#             Ok so let's break that down again:

+#             - make sure the division is even (or it makes no sense)

+#             - for each segment:

+#                 - convert to decimal

+#                 - xor with other segments to find bit differences

+#                 - sum different bits for entire list

+#                 - compare aginst and possibly replace a running minimum of flips required

+

+#             There are a couple of implementation notes to go along with this

+#             sequence of actions. One is in identifying which bits between two

+#             binary strings are different. We can cut straight to the meat of

+#             the matter by using a binary XOR on the two strings; identical

+#             bits either 0 or 1 will produce a zero, differences will produce a

+#             1. As we want the *number* of differences and don't care about the

+#             structure, we can get this by summing the bits in the XOR result.

+# 

+#             This seems much more efficiant that breaking apart the binary

+#             strings and directly comparing bits, but there's a caveat: the

+#             bitwise operators work on *decimal* numbers, necessatating a

+#             conversion to base-10, and to sum the bits it's easiest to work in

+#             binary. Fortunately it's easy to switch back and forth.

+# 

+#             Another refactoring we can make is that once we have originally

+#             produced the bitstring segments we no longer ever need to see them

+#             in binary notation, so we can immediately convert the list of

+#             values to base-10. This cleans up the code underneath, at the

+#             expense of easily debugging exactly what's happening in the binary

+#             notation. But, as I said, a refactor move. We've eliminated

+#             printing some internal variables to peek in on the action, and

+#             we're honing a process that's vetted.

+# 

+#             

+#

+#       © 2021 colin crain

+## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##

+

+

+

+use warnings;

+use strict;

+use feature ":5.26";

+

+sub minflips {

+## given a segment length and binary bitstring,

+## segment the binary string and determine the minimum flips required to 

+## produce consistency among sections, using any section as the model

+    my ($size, $bin) = @_;

+    return undef if length($bin)%$size;

+    my @sections;

+    

+    ## section into equal sized parts and convert to decimal

+    push @sections, oct('0b'.substr($bin, 0, $size, '')) while length $bin > 0;

+

+    my $min = "Inf";

+    for ( 0..$#sections ) {

+        my $flips = bitflips($_, @sections);

+        $min = $flips if $flips < $min;

+    }

+

+    return $min;

+}

+

+sub bitflips {

+## given a list of decimal numbers and an index,

+## compute the number of flipped bits to transform all numbers in the list

+## to the value indicated at index $idx

+    my ($idx, @sections) = @_;

+    my $flips = 0;

+    for my $sect (@sections) {

+        my $xored = sprintf "%b", $sections[$idx] ^ $sect;  ## sections are decimal here

+        $flips += $_ for split //, $xored;

+    }

+    

+    return $flips;   

+}

+

+use Test::More;

+

+is(minflips(3, "101100101"), 1, 'ex-1');

+is(minflips(4, "10110111"),  2, 'ex-2');

+

+is(minflips(3, "110001011101010"), 6, '5 sections');

+is(minflips(3, "110001011101010111001010101010010000111101111110"), 21, 'many sections');

+is(minflips(3, "000000"), 0, 'no work done - 0s');

+is(minflips(2, "010101"), 0, 'no work done - mixed');

+

+is(minflips(2, "0101010"), undef, 'not divisible');

+

+

+done_testing();

+

+

diff --git a/challenge-097/colin-crain/raku/ch-1.raku b/challenge-097/colin-crain/raku/ch-1.raku
new file mode 100644
index 0000000000..c6d90cc1d4
--- /dev/null
+++ b/challenge-097/colin-crain/raku/ch-1.raku
@@ -0,0 +1,19 @@
+#!/usr/bin/env perl6
+#
+#
+#       et-tu-brute.raku
+#
+#
+#
+#       © 2021 colin crain
+## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
+
+
+
+unit sub MAIN (Int $shift = 3, Str $str = "THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG") ;
+
+$_ = $str;
+s:g/ (<[a..zA..Z]>) /{ chr(((ord(uc $0)-65-$shift)%26)+65) }/;
+
+$str.say;
+.say;
diff --git a/challenge-097/colin-crain/raku/ch-2.raku b/challenge-097/colin-crain/raku/ch-2.raku
new file mode 100644
index 0000000000..102e92db47
--- /dev/null
+++ b/challenge-097/colin-crain/raku/ch-2.raku
@@ -0,0 +1,59 @@
+#!/usr/bin/env perl6
+#
+#
+#       flippenbitter.raku
+#
+#         TASK #2 › Binary Substrings
+#         Submitted by: Mohammad S Anwar
+#         You are given a binary string $B and an integer $S.
+# 
+#         Write a script to split the binary string $B of size $S and then find
+#         the minimum number of flips required to make it all the same.
+# 
+#         Example 1:
+#         Input: $B = “101100101”, $S = 3
+#         Output: 1
+# 
+#         Binary Substrings:
+#             "101": 0 flip
+#             "100": 1 flip to make it "101"
+#             "101": 0 flip
+#         Example 2:
+#         Input $B = “10110111”, $S = 4
+#         Output: 2
+# 
+#         Binary Substrings:
+#             "1011": 0 flip
+#             "0111": 2 flips to make it "1011"
+# 
+#
+#       © 2021 colin crain
+## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
+
+
+
+unit sub MAIN (Int $size = 3, Str $bin = "110001011101010111001010101010010000111101111000") ;
+
+die "$size does not evenly divide length of $bin" unless $bin.chars %% $size;
+
+## section into equal sized parts and convert to decimal
+my @sections = $bin.comb($size).map({.parse-base(2)});
+
+## establish flips required to equalize to each value in list
+my @flips.push( bitflips($_, @sections) ) for 0..@sections.end;
+
+## report minimum
+say qq:to/__END__/;
+    binary string : $bin
+    segment size  : $size
+    bits flipped  : { @flips.min }
+    __END__
+
+sub bitflips( Int $idx, @sections ) {
+## xor each pair with indexed value and sum
+    my $flips = 1;
+    @sections.map({ ($_ +^ @sections[$idx]).base(2)
+                                           .comb 
+                                           .sum })
+             .sum;
+}