RabbitFarm

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

Part 1

You are given a positive number, $n. Write a script to validate the given number against the included check digit.

Solution

use strict;
use warnings;
use boolean;

my @damm_matrix;
$damm_matrix[0] = [0, 7, 4, 1, 6, 3, 5, 8, 9, 2];
$damm_matrix[1] = [3, 0, 2, 7, 1, 6, 8, 9, 4, 5];
$damm_matrix[2] = [1, 9, 0, 5, 2, 7, 6, 4, 3, 8];
$damm_matrix[3] = [7, 2, 6, 0, 3, 4, 9, 5, 8, 1];
$damm_matrix[4] = [5, 1, 8, 9, 0, 2, 7, 3, 6, 4];
$damm_matrix[5] = [9, 5 ,7, 8, 4, 0, 2, 6, 1, 3];
$damm_matrix[6] = [8, 4, 1, 3, 5, 9, 0, 2, 7, 6];
$damm_matrix[7] = [6, 8, 3, 4, 9, 5, 1, 0, 2, 7];
$damm_matrix[8] = [4, 6, 5, 2, 7, 8, 3, 1, 0, 9];
$damm_matrix[9] = [2, 3, 9, 6, 8, 1, 4, 7, 5, 0];

sub damm_validation{
    my($x) = @_;
    my @digits = split(//, $x);
    my $interim_digit = 0;
    while(my $d = shift @digits){
        $interim_digit = $damm_matrix[$d][$interim_digit];
    }
    return boolean($interim_digit == 0);
}

MAIN:{
    print damm_validation(5724) . "\n";
    print damm_validation(5727) . "\n";
}

Sample Run

$ perl perl/ch-1.pl
1
0

Notes

Damm Validation really boils down to a series of table lookups. Once that is determined we need to encode the table and then perform the lookups in a loop.

Part 2

Write a script to generate first 20 Palindromic Prime Cyclops Numbers.

Solution

use strict;
use warnings;
no warnings q/recursion/;
use Math::Primality qw/is_prime/;

sub n_cyclops_prime_r{
    my($i, $n, $cyclops_primes) = @_;
    return @{$cyclops_primes} if @{$cyclops_primes} == $n;
    push @{$cyclops_primes}, $i if is_prime($i) && 
                                   length($i) % 2 == 1 &&
                                   join("", reverse(split(//, $i))) == $i &&
                                   (grep {$_ == 0} split(//, $i))   == 1 && 
                                   do{my @a = split(//, $i);
                                      $a[int(@a / 2)]
                                   } == 0;
    n_cyclops_prime_r(++$i, $n, $cyclops_primes);
}

sub n_cyclops_primes{
    my($n) = @_;
    return n_cyclops_prime_r(1, $n, []);
}

MAIN:{
    print join(", ", n_cyclops_primes(20)) . "\n";
}

Sample Run

$ perl perl/ch-2.pl
101, 16061, 31013, 35053, 38083, 73037, 74047, 91019, 94049, 1120211, 1150511, 1160611, 1180811, 1190911, 1250521, 1280821, 1360631, 1390931, 1490941, 1520251

Notes

I recently saw the word whipupitide used by Dave Jacoby and here is, I think, a good example of it. We need to determine if a number is prime, palindromic, and cyclops. In Perl we can determine all of these conditions very easily.

Just to add a bit of fun I decided to use a recursive loop. Out of necessity this will have a rather deep recursive depth, so we'll need to set no warnings q/recursion/ or else perl will complain when we go deeper than 100 steps. We aren't using too much memory here, but if that were a concern we could do Perl style tail recursion with a goto __SUB__ instead.

References

Challenge 177

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

Part 1

You are given a positive number, $n. Write a script to validate the given number against the included check digit.

Solution

damm_matrix(0, [0, 7, 4, 1, 6, 3, 5, 8, 9, 2]).
damm_matrix(1, [3, 0, 2, 7, 1, 6, 8, 9, 4, 5]).
damm_matrix(2, [1, 9, 0, 5, 2, 7, 6, 4, 3, 8]).
damm_matrix(3, [7, 2, 6, 0, 3, 4, 9, 5, 8, 1]).
damm_matrix(4, [5, 1, 8, 9, 0, 2, 7, 3, 6, 4]).
damm_matrix(5, [9, 5 ,7, 8, 4, 0, 2, 6, 1, 3]).
damm_matrix(6, [8, 4, 1, 3, 5, 9, 0, 2, 7, 6]).
damm_matrix(7, [6, 8, 3, 4, 9, 5, 1, 0, 2, 7]).
damm_matrix(8, [4, 6, 5, 2, 7, 8, 3, 1, 0, 9]).
damm_matrix(9, [2, 3, 9, 6, 8, 1, 4, 7, 5, 0]).

damm_validate(N):-
    number_chars(N, NChars),
    damm_validate(NChars, 0).
damm_validate([], InterimDigit):-
    InterimDigit == 0.    
damm_validate([H|T], InterimDigit):-
    number_chars(N, [H]),
    damm_matrix(N, DammRow),
    succ(InterimDigit, I),
    nth(I, DammRow, NextInterimDigit),
    damm_validate(T, NextInterimDigit). 

Sample Run

| ?- damm_validate(5727).

(1 ms) no
| ?- damm_validate(5724).

yes

Notes

The beauty of Prolog is when it's implicit features such as backtracking and unification are exclusively leveraged to obtain a beautiful solution. This is not one of those cases! This is pure recursion, more functional than logical. I can't think of a more elegant way to express this Damm Validation process, however. Essentially we are performing a series of lookups from a table. I could see this being done with a DCG, perhaps. But in that case we wouldn't really be making anything more elegant, I would argue, just removing the explicit recursion while still having to do the same sort of lookups. It would probably end up being more code than this!

Anyway, Damm Validation is pretty succinctly expressed, it's just that the algorithm doesn't seem to really lend itself to being made much more logically implemented.

Part 2

Write a script to generate first 20 Palindromic Prime Cyclops Numbers.

Solution

cyclops(X):-
    number_chars(X, XChars),
    length(XChars, XCharsLength),
    XCharsLengthMinusOne is XCharsLength - 1,
    delete(XChars, '0', XCharsNoZero),
    length(XCharsNoZero, NoZeroLength),
    NoZeroLength == XCharsLengthMinusOne,
    append(Beginning, ['0'|End], XChars),
    length(Beginning, BeginningLength),
    length(End, EndLength),
    BeginningLength == EndLength.

palindrome(X):-
    number_codes(X, C),
    reverse(C, CR),
    number_codes(X, CR).

palindrome_prime(Prime):-
    current_prolog_flag(max_integer, MAX_INTEGER),
    between(100, MAX_INTEGER, Prime),
    palindrome(Prime),
    fd_prime(Prime).

palindromic_prime_cyclops(_) --> [].
palindromic_prime_cyclops(Seen) --> [X], {palindrome_prime(X), cyclops(X), \+ member(X, Seen)}, palindromic_prime_cyclops([X|Seen]).

main:-
    length(PalindromicPrimeCyclops, 5),
    phrase(palindromic_prime_cyclops([]), PalindromicPrimeCyclops),
    write(PalindromicPrimeCyclops), nl.

Sample Run

$ gprolog --consult-file prolog/ch-2.p 
| ?- length(PalindromicPrimeCyclops, 20), phrase(palindromic_prime_cyclops([]), PalindromicPrimeCyclops).

PalindromicPrimeCyclops = [101,16061,31013,35053,38083,73037,74047,91019,94049,1120211,1150511,1160611,1180811,1190911,1250521,1280821,1360631,1390931,1490941,1520251] ? 

Notes

This borrows a quite a bit of code from previous challenges! Probably the newest thing here is the checking of the cyclops condition. In cyclops/1 we first check to see if there is a single zero. This is done by removing all zeroes with delete/3 and then confirming, by checking lengths, that only one was removed. After that we split the list around the '0' using append/3 and if the sublists before and after the '0' are of the same size we know we have a cyclops number. Notice that it only matters that they are equal. Whether they are of even length or odd length doesn't matter since we know we have just a single '0' and so the length of the entire list is necessarily of odd length, as required.

References

Challenge 177