RabbitFarm

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

Part 1

Write a script to figure out if the given number is Palindrome. Print 1 if true otherwise 0.

Solution

:-initialization(main).

palindrome_even([]).  
palindrome_even([H|T]):-
    last(T, Last), 
    H == Last, 
    append(L, [Last], T), 
    palindrome_even(L).   

palindrome_odd([_|[]]).  
palindrome_odd([H|T]):-
    last(T, Last), 
    H == Last, 
    append(L, [Last], T), 
    palindrome_odd(L).   

palindrome(N):-
    N > 0, 
    number_chars(N, C), 
    length(C, Length), 
    M is Length mod 2,
    M == 0,
    palindrome_even(C).   
palindrome(N):-
    N > 0, 
    number_chars(N, C), 
    length(C, Length), 
    M is Length mod 2,
    M == 1,
    palindrome_odd(C).  

is_palindrome(N):-
    palindrome(N),
    write(1), nl.
is_palindrome(N):-
    \+ palindrome(N),
    write(0), nl.

main:-
    is_palindrome(1221),
    is_palindrome(-101),
    is_palindrome(90),
    halt.  

Sample Run

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

Notes

This is a Prolog version of Perl code I wrote for the same problem. The basic approach is roughly the same as the Perl implementation: starting at both ends of the number work inwards comparing one pair of digits at a time. Here we define all negative numbers as being non-palindromic due to the inherent asymmetry of the ‘-’.

It is slightly odd in Prolog to print out a 0 or 1 as asked in this problem statement. In languages like Perl doing so is really just as simple as printing out a boolean value returned from some comparison or function call. Although odd it is not unheard of, however, and the best advice I have seen on the matter is to define a small predicate to wrap the predicate(s) doing the real work and print whatever is needed. That job here is done by is_palindrome/1

Part 2

Demonstrate Stack operations.

Solution

:-initialization(main).

new_stack([]).

push(Stack, Value, [Value|Stack]).

pop([H|T], H, T).

top([H|_], H).

min(Stack, Min):-
    min_list(Stack, Min).

main:-
    new_stack(Stack),
    push(Stack, 2, NewStack0),
    push(NewStack0, -1, NewStack1),
    push(NewStack1, 0, NewStack2),
    pop(NewStack2, Top0, NewStack3),
    write(Top0), nl,
    top(NewStack3, Top1),
    write(Top1), nl,
    push(NewStack3, 0, NewStack4),
    min(NewStack4, Min),
    write(Min), nl,
    halt.

Sample Run

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

Notes

Just writing this code made me feel like I was committing a crime against Prolog! Implementing this sort of data structure in Prolog is really just writing some small predicates which wrap otherwise ordinary list operations. Then again, implementing Stacks in Prolog is not entirely unheard of. This sort of thing is done as an exercise when studying data structures. The excellent text by Luger and Stubblefield describes a Stack implementation, among other Abstract Data Types, in Prolog.

References

Challenge 095

AI Algorithms, Data Structures, and Idioms in Prolog, Lisp, and Java