THE PUZZLET PAGE


How_Does_It_Work


FUNCTION:  IsPalindrome().  A palindrome is a word which reads the same backwards and forwards, like Anna, motor, etc. A palindromic number has similar properties, such as 1221, 937739,  12521, etc.

You can say that all its symmetrically opposite pairs are identical. For instance, the symmetrically opposite pairs from the number 937739 are: First pair, 9 and 9 (1st and 6th digits); second pair 3 and 3 (2nd and 5th digits); third pair 7 and 7 (3rd and 4th digits). If just one of these symmetrically opposite pairs aren't "identical twins" the number can't be a palindrome. This principle is used in the IBasic function below.

This code will only find palindromes up to the maximum possible value of p. If p is declared as an integer (int), that means 1073741824. See the table below for the limits.

Type

Exponent of 2
Value

int 230 1073741824
uint 231 2147483648
int64 261 2305843009213693952
uint64 262 4611686018427387904

Declaring the function must be done like this:

declare IsPalindrome(p: int)

With those constraints in mind, here's the code:

sub IsPalindrome(p)
' if p is palindromic returns TRUE (-1),
' otherwise returns FALSE (0)
def flag, i, j, L: int
def p$, q$, r$: string
p$ = ltrim$(str$(p))
L = len(p$)
j = L/2
i = 1
flag = -1
do
    ' get symmetrically opposite pairs
    q$ = mid$(p$, i, 1)
    r$ = mid$(p$, L + 1 - i, 1)
    if q$ <> r$: 'not a palindrome
        flag = 0
    endif
    i = i + 1
until flag = 0 | i > j: 'either failed or finished
return flag


Let's begin by looking at the variables.

The function's argument, p, holds the integer we wish to investigate. It is passed to the function by the calling routine.

p is converted into its string format and stored in variable p$ by the line
p$ = ltrim$(str$(p)). This makes it easier to manipulate p. Why do we need to use ltrim$ here? When you make a string in IBasic, and in any other Basic, it always pads out the front of the new string with a space. This would cause a failure of this particular program (which is expecting to deal with numerals only, not spaces), so we remove the space. ltrim$ just means "trim off the space at the left end of the string."

We're going to need to know the length of p$. It's found by the expression
L = len(p$) and thus stored in variable L.  We're also going to be continually referring to the half-length of p$. To save time later, this is calculated just once and stored in variable j by the line j = L/2.

j has already been declared to be an integer, so, even if L is an odd number, j will be even. For example, assume L is 7.  j will hold the value 3. This rounding down is important, as we will see shortly.

Variable i is used as an iterator to help us step through the characters of p$ for individual assessment.

Variable flag is a flag used to store the code's result.  It can hold -1 or 0, corresponding to TRUE or FALSE. Ultimately, it is this value which must be returned to the calling routine. 

So the sequence is: the calling routine sends a message to the function, accompanied by its parameter p. The question is asked "is p a palindromic integer (reading the same backwards as forwards)?". It will receive one of two possible replies from the function: TRUE or FALSE (-1 or 0).

I'm going to add line numbers to the rest of the code to make the description simpler.


1
2
3
4
5
6
7
8
9

do
    q$ = mid$(p$, i, 1)
    r$ = mid$(p$, L + 1 - i, 1)
    if q$ <> r$
        flag = 0
    endif
    i = i + 1
until flag = 0 | i > j
return flag

Now for a line-by-line exegesis of the code.

1

do.  Opens main DO loop.

2

q$ = mid$(p$, i, 1)i was already initialised to 1 before the DO loop was opened. So, first time around, the first character of p$ is sliced out and stored in variable q$. On subsequent executions of the DO loop, i's value will have changed, so a different character will be sliced out.

3

r$ = mid$(p$, L + 1 - i, 1).  This expression picks out the symmetrically opposite character to q$ and slices it out, saving it in variable r$.  For example, let's assume p$ contains "12477421".  The slicing process works like this:


Value of i
q$
r$
            Comments





1
1
1
   1st and 8th characters

2
2
2
   2nd and 7th characters

3
4
4
   3rd and 6th characters

4
7
7
   4th and 5th characters


Now when i is run through all its values, q$ and r$ are always the same as each other, or "identical twins." We'll see the significance of this shortly.

You may wonder how the code manages to pick the characters in this symmetrically opposite way. Shown below is a "y = mx + c" type of graph which makes things clearer.


Compare the graph to the third  line  of  code, which is r$ = mid$(p$, L + 1 - i, 1). r$ is the equivalent of y. Using mid$ means it will pick out a character from p$ to order.

The exact character to be selected will be L + 1 - i, equating to L + 1 - x in the graph. The final "1" at the end of the expression simply means "pick out just one character."

graph

4

if q$ <> r$. We have seen in the explanation above how q$  and r$ always hold symmetrically opposite pairs of characters from the number being investigated. It is a characteristic of palindromes that such pairs are always identical. So this line is asking "are the latest pair selected from the number being investigated not an indentical pair?"

5

flag = 0. If they're not identical, there's no point in looking further, and variable flag is set to FALSE (0) to warn the program.

6

endif. Housekeeping - closes the IF clause.

7

i = i + 1. Local variable i is incremented by 1, ready to look at the next symmetrically opposite pair of characters.

8

until flag = 0 | i > j. Decision time! Should the DO loop be executed again or not? There are two conditions which signify NO. One, if the flag is at 0, meaning the last symmetrical pair looked at didn't comprise identical twins. Two, variable i has been incremented to the point of being greater than half the length of the number being investigated.

Remember, variable j holds this value. If the number's length was an even number, like 12477421, it means that the following pairs would be investigated in order: 1st and 8th, 2nd and 7th, 3rd and 6th, 4th and 5th. If the number's length was an odd number, like 314292413, the same rule would apply. j in this case would still have a value of 4, as explained in the introductory section on variables above. So the central figure, 9, wouldn't be investigated. This is fine, because in a palindrome consisting of an odd number of digits the centre digit doesn't affect palindromicity.


9

return flag. When the DO loop was quit, flag would be in one of two states. It was initialised to TRUE (-1) before the loop was started. If the loop is executed because i is greater than j, the flag must have been unaffected and remained at TRUE. If the loop is executed because the flag had changed, it must be at FALSE. Either way, this final line of the function returns that value to the calling routine.

Of course, you don't have to go through all that just to use the function. Add it into your program. Then, anytime you want to know if a given integer really is a palindrome, just include the line if IsPalindrome(number) etc.

MAIN MENU
HOW DOES IT WORK?

Site design/maintenance: Dave Ellis E-mail me!
Last Updated: February 5th, 2010.