RabbitFarm

Palindromic Numbers

Suppose we are asked the following, as was the case for The Weekly Challenge 095.

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

Here is my original solution to this.

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

I wrote a short description of this code before.

To repeat a little here: 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.

Let’s ignore is_palindrome/1, though, and consider something else.

This code works fine, as is shown, but it is unsatisfying from the perspective in that it only works one way. If we have defined the validation of palindromic numbers correctly then in fact Prolog should also be able to generate palindromic numbers as well! That is,
a bimodal predicate that used in one mode will validate palindromic numbers and in another mode create them.

Trying the existing code out with an uninstantiated variable this is the result

?- palindrome(N).
uncaught exception: error(instantiation_error,(>)/2)

Of course it does not take a Prolog genius to see pretty quickly why this does not work. A couple of things that jump out right away:

• We are assuming that palindrome/1 is being given a valid integer
• N > 0 requires an instantiated number variable N, as shown in the error message.
• The list of digits we evaluate to be a palindrome is created by number_chars/2 which, for our purposes, also requires an instantiated number variable.

To adjust this code to work both ways need to handle whether N is in fact instantiated or not. But here we need to be careful, we need to create one in such a way that when a non-palindromic number is created a new one is created upon backtracking. We want to be as general as possible.

Also, we already have two instances of palindrome/1 predicates to handle the two cases of even/odd number of digits. Let’s take care to not write more code than necessary when modifying this code.

So, taking all this into account, what is to be done? Well, it turns out we can make this code work both ways by adding adding two lines (and removing 1 existing line) from palindrome/1.

The changes are:

• Check to see if N is between 1 and the largest possible integer available using between/3. Here I am using Gnu Prolog on a 32-bit platform (NetBSD/macppc) and this value is 268435455.
• When the third argument to between/3 is uninstantiated it will be instantiated to be an integer in the range given by the first two arguments.
• The check if N is positive is no longer necessary and can be removed.

The updated code looks like this.

palindrome(N):-
    current_prolog_flag(max_integer, MAX_INTEGER),
    between(1, MAX_INTEGER, N),
    number_chars(N, C), 
    length(C, Length), 
    M is Length mod 2,
    M == 0,
    palindrome_even(C).   

From the Gnu Prolog top level we can see this in action. The output is truncated to just show some of the solutions generated upon backtracking.

| ?- palindrome(1200021).

true ? 

yes
| ?- palindrome(X).      

X = 11 ? ;

X = 22 ? ;
    .
    .
    .

How many palindromic numbers are there between 1 and MAX_INTEGER?

| ?- findall(X, palindrome(X), Xs), length(Xs, L).
L = 36842.

36842 palindromic numbers is about 0.01% of all integers in this range.

The full code for this is below. I’ve left the main/0 predicate alone as it demonstrates what was necessary for the original problem. Output showing the bimodal functionality was run in the Gnu Prolog top level. If this code interests you the palindrome/1 predicate can be used directly as shown.

:-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):-
    current_prolog_flag(max_integer, MAX_INTEGER),
    between(1, MAX_INTEGER, N),
    number_chars(N, C), 
    length(C, Length), 
    M is Length mod 2,
    M == 0,
    palindrome_even(C).   
palindrome(N):-
    current_prolog_flag(max_integer, MAX_INTEGER),
    between(1, MAX_INTEGER, N),
    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).      

References

Challenge 095

Previous work on the same problem

Gnu Prolog