RabbitFarm

The examples used here are from the weekly challenge problem statement and demonstrate the working solution. Also, the challenge statements are given in a Perl context although for Prolog solutions some adjustments are made to account for the differing semantics between the two languages.

Part 1

You are given a positive integer $N. Write a script to generate all Rare Numbers of size $N if any exist.

Solution

:-initialization(main).

perfect_square(N):-
    A is floor(sqrt(N)), 
    N is A * A.

rare(N, N, Rares, Rares). 
rare(Lower, Upper, RareAccum, Rares):-
    number_codes(Lower, C),
    reverse(C, CR), 
    number_codes(R1, CR),
    X0 is Lower + R1,
    X1 is Lower - R1,
    perfect_square(X0),
    perfect_square(X1),
    Next is Lower + 1,
    rare(Next, Upper, [Lower|RareAccum], Rares).
rare(Lower, Upper, RareAccum, Rares):-
    Next is Lower + 1,
    rare(Next, Upper, RareAccum, Rares).

rare_numbers(N, Rares):-
    Lower is 10 ^ (N - 1),   
    Upper is (10 ^ N) - 1,
    rare(Lower, Upper, [], Rares). 

main:-
    rare_numbers(2, Rares2),
    write(Rares2), nl, 
    rare_numbers(6, Rares6),
    write(Rares6), nl, 
    rare_numbers(9, Rares9),
    write(Rares9), nl,
    halt.

Sample Run

$ gplc prolog/ch-1.p
$ prolog/ch-1
[65]
[621770]
[281089082]

Notes

This is maybe straightforward bit of Prolog with arithmetic. One might say that I missed an opportunity to use between/3 but, in fact, I was happy to terminate the recursion of rare/4 by identifying the case where the first two arguments (Lower and Upper) are equal.

Part 2

You are given a positive integer $N. Write a script to produce hash counting string of that length.

Solution

:-initialization(main).

hcs(0, String, String).
hcs(1, StringAccum, String):-
    hcs(0, [35|StringAccum], String). 
hcs(N, StringAccum, String):-
    number_codes(N, C),
    append(C, "#", Accum), 
    length(Accum, L),
    N0 is N - L, 
    append(Accum, StringAccum, StringAccum0), 
    hcs(N0, StringAccum0, String). 

hash_counting_string(N, String):-
    hcs(N, [], S),
    atom_codes(String, S).

main:-
    hash_counting_string(1, String1), 
    write(String1), nl,
    hash_counting_string(2, String2), 
    write(String2), nl, 
    hash_counting_string(3, String3), 
    write(String3), nl, 
    hash_counting_string(10, String10), 
    write(String10), nl, 
    hash_counting_string(14, String14), 
    write(String14), nl,
    halt.

Sample Run

$ gplc ch-2.p 
$ prolog/ch-2
#
2#
#3#
#3#5#7#10#
2#4#6#8#11#14#

Notes

As mentioned elsewhere I first wrote a solution to this in Perl. This code, follows pretty directly from that, a clean bit of recursion. Probably we should prefer a more prological piece of code versus this which is more …what should we call it…procursive? That is, recursive fairly functional style code which does not make much use of the power of Prolog backtracking.

Time is running out to submit solutions for Weekly Challenge 102, but I can imagine a solution which uses DCGs perhaps? The hash counting string being assembled by processing a list of success numbers which in turn generate the appropriate characters. I’ll update this article if I get a chance.

References

Challenge 102 Rare Numbers