# RabbitFarm

### 2021-01-31

The Weekly Challenge 097 (Prolog Solutions)

*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

posted at: 18:48 by: Adam Russell | path: /prolog | permanent link to this entry

#### Perl Weekly Challenge 097

*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

posted at: 11:11 by: Adam Russell | path: /perl | permanent link to this entry