Perl Weekly Challenge 97.

My solutions (task 1 and task 2) to the The Weekly Challenge - 097.

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

I obtain the arguments from @ARGV; the first argument is the string to encode and the second is the displacement which must be numerical.

# Perl weekly challenge 097
# Task 1: Caesar Cipher
#
# See https://wlmb.github.io/2021/01/25/PWC097/#task-1-caesar-cipher
use warnings;
use strict;
use v5.12;
use Scalar::Util qw(looks_like_number);

sub usage {
    say <<END;
    Usage:
	./ch-1.pl S N
    to encode string S using Casear's cipher with displacement N
END
    exit 1;
}

usage() unless @ARGV==2;
my $string = uc shift @ARGV; # Allow lower case but convert to uppercase
my $displacement=shift @ARGV;
usage() unless looks_like_number($displacement);

I build a translation table from the set of allowed characters. Note the sign of the $displacement.

my @plain="A".."Z";
my %translation_of=map {($plain[$_]=>$plain[($_-$displacement)%@plain])} 0..@plain-1;

Finally, I apply the translation table to print the results. I keep untranslated characters unmodified, so that punctuation and spaces go through.

my $translated=join '', map {$translation_of{$_}//$_} split '', $string;
say "Input:  \"$string\" $displacement\nOutput: \"$translated\"\n";
say "Plain:\t", @plain, "\n",
    "Cipher:\t", join '', @translation_of{sort keys %translation_of}, "\n",
    "Displacement:\t$displacement\n",
    "Plaintext:\t$string\n",
    "Ciphertext:\t$translated",

Results:

./ch-1.pl "The quick brown fox jumps over the lazy dog" 3

Results:

Input: "THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG" 3
Output: "QEB NRFZH YOLTK CLU GRJMP LSBO QEB IXWV ALD"

Plain:	ABCDEFGHIJKLMNOPQRSTUVWXYZ
Cipher:	XYZABCDEFGHIJKLMNOPQRSTUVW
Displacement:	3
Plaintext:	THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG
Ciphertext:	QEB NRFZH YOLTK CLU GRJMP LSBO QEB IXWV ALD

Check that the degenerate case works.

./ch-1.pl "" 3

Results:

Input:  "" 3
Output: ""

Plain:	ABCDEFGHIJKLMNOPQRSTUVWXYZ
Cipher:	XYZABCDEFGHIJKLMNOPQRSTUVW
Displacement:	3
Plaintext:
Ciphertext:

Check that negative displacements work.

./ch-1.pl "The quick brown fox jumps over the lazy dog" -23

Results:

Input:  "THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG" -23
Output: "QEB NRFZH YOLTK CLU GRJMP LSBO QEB IXWV ALD"

Plain:	ABCDEFGHIJKLMNOPQRSTUVWXYZ
Cipher:	XYZABCDEFGHIJKLMNOPQRSTUVW
Displacement:	-23
Plaintext:	THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG
Ciphertext:	QEB NRFZH YOLTK CLU GRJMP LSBO QEB IXWV ALD

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"

Receive the two arguments in @ARGV.

# Perl weekly challenge 097
# Task 1: Binary substrings
#
# See https://wlmb.github.io/2021/01/25/PWC097/#task-2-binary-substrings
use warnings;
use strict;
use v5.12;

use List::Util qw(all reduce);
use Scalar::Util qw(looks_like_number);
use Memoize; # Just for fun
# Check arguments
usage() unless @ARGV==2;
my $string = shift @ARGV;
my $length=shift @ARGV;
usage() unless looks_like_number($length) && $length>=1;

Check that the string contains only 1’s and 0’s.

my %binary=("0"=>1,"1"=>1); # Binary characters
usage() unless all {$binary{$_}} split '', $string;

Split into substrings using split and keeping only substrings of the correct length, i.e., throwaway the last substring if incomplete.

my @substrings=grep {length $_ == $length} split /(\d{$length})/, $string;

Choose the best target substring to minimize flips.

memoize('cost'); # Don't duplicate effort
my @total_costs=map {total_cost($substrings[$_], @substrings)} 0..@substrings-1;
my $best_index=reduce {$total_costs[$a]<=$total_costs[$b]?$a:$b} 0..@total_costs-1;
my $target=$substrings[$best_index];
my @costs=map {cost($target, $_)} @substrings;

Finally, print results.

say "Input:\t\"$string\"\t$length\n",
    "Output:\t$total_costs[$best_index]\n\n",
    "Binary substrings\n",
    map {"\"$substrings[$_]\": $costs[$_] flips to convert it to \"$target\"\n"}
	0..@substrings-1;

Calculate the cost to flip a set of strings to the first one

sub total_cost {
    my $first=shift;
    my $cost=0;
    $cost+=cost($first,$_) foreach @_;
    return $cost;
}
sub cost {
    my @first=split '',shift;
    my @second=split '',shift;
    my $cost=0;
    $cost += $first[$_]!=$second[$_]?1:0 foreach 0..@first-1;
    return $cost;
}

Results: Finally, the usage message.

sub usage {
say <<END;
 Usage:
   ./ch-1.pl B S
   to split binary string B into substrings of size S>=1
   and then enumerate changes to make them the same
END
   exit 1;
}

Example 1:

./ch-2.pl 101100101 3

Results:

Input:	"101100101"	3
Output:	1

Binary substrings
"101": 0 flips to convert it to "101"
"100": 1 flips to convert it to "101"
"101": 0 flips to convert it to "101"

Example 2:

./ch-2.pl 10110111 4

Results:

Input:	"10110111"	4
Output:	2

Binary substrings
"1011": 0 flips to convert it to "1011"
"0111": 2 flips to convert it to "1011"

Another couple of examples to check if it actually minimizes flips.

./ch-2.pl 0001101111 2
./ch-2.pl 0001101100 2

Results:

Input:	"0001101111"	2
Output:	4

Binary substrings
"00": 2 flips to convert it to "11"
"01": 1 flips to convert it to "11"
"10": 1 flips to convert it to "11"
"11": 0 flips to convert it to "11"
"11": 0 flips to convert it to "11"

Input:	"0001101100"	2
Output:	4

Binary substrings
"00": 0 flips to convert it to "00"
"01": 1 flips to convert it to "00"
"10": 1 flips to convert it to "00"
"11": 2 flips to convert it to "00"
"00": 0 flips to convert it to "00"
Written on January 25, 2021