RabbitFarm

The examples used here are from the weekly challenge problem statement and demonstrate the working solution.

Part 1

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.

Solution

:-initialization(main).

caesar([], [], _).
caesar([H|T], [C|Cypher], N):-
    C is H - N,
    C >= 65,
    caesar(T, Cypher, N).
caesar([H|T], [C|Cypher], N):-
    C0 is H - N,
    C0 < 65,
    C is C0 + 26,
    caesar(T, Cypher, N).

main:-
    caesar("ABCDEFGHIJKLMNOPQRSTUVWXYZ", C, 3),
    atom_codes(CypherText, C),
    write(CypherText), nl,
    halt.

Sample Run

$ gplc ch-1.p
$ ./ch-1
XYZABCDEFGHIJKLMNOPQRSTUVW

Part 2

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.

Solution

:-initialization(main).

substrings(BinaryString, N, SubStrings):-
    substrings(BinaryString, N, [], SubStrings).
substrings([], _, SubStrings, SubStrings).    
substrings(BinaryString, N, SubStringAccum, SubStrings):-
    length(L, N),
    append(L, X, BinaryString),
    substrings(X, N, [L|SubStringAccum], SubStrings).

count_flips(B, [H|T], Flips):-
    count_flips(B, [H|T], 0, Flips).
count_flips(_, [], Flips, Flips).    
count_flips(B, [H|T], FlipsSum, Flips):-
    number_codes(B0, B),
    number_codes(H0, H),
    X is xor(B0, H0),
    Flips0 is X + FlipsSum,
    count_flips(B, T, Flips0, Flips).
    
min_flips(SubStrings, MinFlips):-
    min_flips(SubStrings, [], Flips),
    sort(Flips,[MinFlips|_]).
min_flips([_], Flips, Flips).    
min_flips([H|T], FlipsAccum, Flips):-
    count_flips(H, T, Flips0),
    min_flips(T, [Flips0|FlipsAccum], Flips).

main:-
    substrings("101100101", 3, SubStrings),
    min_flips(SubStrings, Flips),
    write(Flips),nl,
    halt.

Sample Run

$ gplc prolog/ch-2.p
$ ./ch-2
1

References

xor

The examples used here are from the weekly challenge problem statement and demonstrate the working solution.

Part 1

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.

Solution

use strict;
use warnings;
sub caesar_cypher{
    my($s, $n) = @_;
    my @cypher = map { unless(ord($_) == ord(' ')){
                           my $x = ((ord($_) - $n) < ord('A')?(ord($_) - $n + 26):(ord($_) - $n)); 
                           chr($x);
                       }
                       else{
                           $_
                       }
                 } split(//, $s);
    return join("", @cypher);
}

MAIN:{
    my($S, $N);
    $S = "THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG";
    $N = 3;
    print "$S\n";
    print caesar_cypher($S, $N) . "\n";
}

Sample Run

$ perl perl/ch-1.pl
THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG
QEB NRFZH YOLTK CLU GRJMP LSBO QEB IXWV ALD

Notes

The basic approach here is pretty much the straightforward one: use the ascii values for the characters and subtract $n. In Perl we use the ord function to do this and the chr to go in the other direction, ascii value to character. The only thing we really need to be careful of is if subtracting $n takes us outside the ascii range for upper case letters, then we need to add 26 to get back in range.

Certain style instructions have been burned into my brain over the years and I find them almost impossible to deviate from. The one that applies here is Whenever possible do not use numeric literals. They are often poorly documented and become “magic numbers”, and make code readability and future debugging unnecessarily difficult. So it is in that spirit that I write, for example, ord(' ') instead of just 32.

Part 2

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.

Solution

use strict;
use warnings;

use feature "bitwise";

sub substrings{
    my($d, $s) = @_;
    my @substrings;
    for(my $i = 0; $i < length($d); $i+=$s){
        push @substrings, substr($d, $i, $s);
    }    
    return @substrings;
}

sub min_flips{
    my($d, $s) = @_;
    my @flips;
    my @substrings = substrings($d, $s);
    for my $digits (@substrings){
        my $flip_count = 0;
        map { $flip_count += unpack("%32b*", $digits ^. $_) } @substrings;
        push @flips, $flip_count;
    }
    return [sort {$a <=> $b} @flips]->[0];
}

MAIN:{
    my($B, $S);
    $B = "101100101";
    $S = 3;
    print min_flips($B, $S) . " flips\n";
    $B = "10110111";
    $S = 4;
    print min_flips($B, $S) . " flips\n";
}

Sample Run

$ perl perl/ch-2.pl
1 flips
2 flips

Notes

The substrings function is just a convenient wrapper around the code necessary to break the string into the right sized chunks. The assumption is that the string is evenly divisible into chunks of size $s. If we were not making this assumption we would need to add some zero padding for any unevenly sized substring.

Since use feature "bitwise"; is present the ^. is defined and the operands to ^. are taken to be bit strings and the result is itself a bit string.min_flips does a bitwise xor operation, pairwise comparing each substring in a map. Since xor is 1 only when the bits are different the result is a bit string of set bits, the ones needed to be flipped. unpack is used to sum these, and the result added $flip_count which is then pushed into an array. The minimum number of flips is determined by the smallest number in that array. The bitwise feature was introduced in Perl 5.22 and graduated from experimental status in Perl 5.28.

References

ASCII Table

xor

Perl’s xor

bitwise feature