| This Puzzlet has a potential problem
- running time. We need to look at all 6-digit palindromes, convert
them to their hex format, then check to see if the hex version is also
a palindrome. Easy-peasy, you'd think. But the "brute force and ignorance" approach means running through all 900,000 6-digit integers and checking each one for palindromicity. This would be a very slow business indeed. Obviously, something much faster is needed. I've used an idea which, as far as I know, is Denis Borris's brainchild. All that's needed is to take every 3-digit integer, reverse it, add the original and its reverse together, and each iteration produces a palindrome. None are missed, and none duplicated. The total number of iterations is simply the number of 3-digit integers, 900 in all - a saving of 899100/900000 = 99.9%. This is really significant - just try code using both algorithms, and you'll see what I mean! Needless to say, I follow the quicker method in the following code. |
| ' Puzzlet #091 ' Find 6-digit denary palindromes which ' remain palindromic when converted to ' hexadecimal. ' By Dave Ellis. declare ReverseInteger(n: int) declare IsPalindrome(p$: string) def i, denPal: int def hexValue$: string openconsole print "Searching ...": print print "Denary Hex": print i = 100 do denPal = 1000*i + ReverseInteger(i) hexValue$ = hex$(denPal) if IsPalindrome(hexValue$) print denPal, hexValue$ endif i = i + 1 until i > 999 print: print "No More!" print: print "Press a key ... ", do: until inkey$ <> "" closeconsole end sub IsPalindrome(p$) ' if p$ is a palindrome, returns 1, ' otherwise returns 0 def flag, i, j, L: int def q$, r$: string L = len(p$) j = int(L/2) i = 1 flag = 1 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 sub ReverseInteger(n) ' returns the reverse of integer n ' example: n = 1234 returns 4321 def i, L: int def n$, rev$: string n$ = ltrim$(str$(n)) L = len(n$) rev$ = "" for i = L to 1 #-1 rev$ = rev$ + mid$(n$, i, 1) next i return val(rev$) |
| PROGRAM NOTES The usual top-down approach is applied to this program. The main routine tells you everything you need to know. In the following extract, the lines are numbered to make it easier to follow the description. |
| 1 2 3 4 5 6 7 8 |
do denPal = 1000*i + ReverseInteger(i) hexValue$ = hex$(denPal) if IsPalindrome(hexValue$) print denPal, hexValue$ endif i = i + 1 until i > 999 |
| Now for an exegesis of the code, using the above line numbers: |
| 1 |
do. Opens the main DO-LOOP. |
| 2 |
denPal = 1000*i + ReverseInteger(i). Variable denPal will hold the processed value of i, the 6-digit integer currently being investigated. Here's how the code forms that value. First it's reversed by the function ReverseInteger(). For instance, 123 becomes 321. Then the two are added together, to form 123321, one of the required 6-digit palindromes. |
| 3 |
hexValue$ = hex$(denPal). Converts denPal to string form and saves it in hexValue$. |
| 4 |
if IsPalindrome(hexValue$). Submits hexValue$ as parameter to IsPalindrome(), whose function is named in the title. If its argument is a palindrome,it returns -1 (TRUE), otherwise 0 (FALSE). Note that this function works whatever characters are involved. This is necessary, since hexadecimal numbers can contain alpha as well as numerical characters. |
| 5 |
print denPal, hexValue$. If line 4 returned TRUE, we have a solution, and it's printed out. |
| 6 |
endif. Housekeeping - closes the IF-ENDIF clause. |
| 7 |
i = i + 1. Increments i ready to look at the next value. |
| 8 |
until i > 999. If the newly-incremented value of i is less than 1,000, its new value is processed by executing the DO-LOOP again. Otherwise, the program ends. |
| The
functions called by the main routine have all been used in previous
Puzzlets, and are just about
self-explanatory. If you
want to know more about them please either refer back, or e-mail me
directly. |
| When
you run the program, you'll see the inset printed out onto your
computer's screen. There are five solutions, only one of which doesn't use alpha characters in its hexadecimal part. |
|
Searching
... Denary Hex 333333 51615 512215 7D0D7 666666 A2C2A 749947 B717B 845548 CE6EC No More! Press a key ... |