' Puzzlet #059
' Find all denary numerical palindromes
' which, when converted to binary,
' still produce numerical palindromes.
' Example:  33 converts to 100001.
' Limit your search to denaries less
' than 10,000.
' By Dave Ellis.

declare DecToBin(d: int)
declare IsPalindrome(p$: string)
declare PrintResults(d: int, b$: string)
def denary: int
def denary$: string
def binary$: string
openconsole
print "Searching ...": print
denary = 1

do
    denary$ = ltrim$(str$(denary))
    if IsPalindrome(denary$)
        binary$ = DecToBin(denary)
        if IsPalindrome(binary$)
            PrintResults(denary, binary$)
        endif
    endif
    denary = denary + 1
until denary > 9999

print: print "No More!"
print: print "Press any key ... ",
do: until inkey$ <> ""
closeconsole
end

sub DecToBin(d)
' converts integer d into its binary
' equivalent and returns it as a string
def num: int
def bin$: string
num = d
bin$ = ""
do
    if num % 2 > 0
        bin$ = "1" + bin$
    else
        bin$ = "0" + bin$
    endif
    num = num/2
until num = 0
return bin$

sub IsPalindrome (p$)
' if p$ is a numerical palindrome,
' returns -1, else returns 0
def flag, i, j, L: int
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 PrintResults(d$, b$)
' pretty printer
def format$: string
format$ = string$(16, "#")
print using ("####", denary),
print using(format$, val(binary$))
return

PROGRAM NOTES

The code is straightforward. In order to make these notes simpler, I have applied line numbers to the main routine. This is a top-down program, so everything is controlled by these ten lines.

1  2  3  4  5  6  7  8  9 10

do     denary$ = ltrim$(str$(denary))     if IsPalindrome(denary$)         binary$ = DecToBin(denary)         if IsPalindrome(binary$)             PrintResults(denary, binary$)         endif     endif     denary = denary + 1 until denary > 9999

Line 1:  Opens the main DO loop.

Line 2:  Converts variable denary into a string, denary$, ready for string-slice processing. When the loop runs for the first time, it uses the pre-initialised value of 1 for denary. Later, it picks up  values set in line 9.

Line 3:  Passes  denary$ as the parameter to function IsPalindrome(). The returned value will always be 0 (FALSE) or -1 (TRUE).

Line 4:  If Line 3 returned TRUE, we at know that denary's value is a numerical palindrome, so we can go ahead and check if the binary equivalent is also a palindrome. Variable denary is passed as the parameter to function DecToBin(), which returns the binary value of denary in string form.  Why do we pass a string to IsPalindrome() yet supply DecToBin() with an integer?  Because IsPalindrome() is one of my library functions and always requires a string input, since it relies on string-slicing, while DecToBin(), another library function, depends on integer arithmetic to work and thus requires an integer input.  Note also that DecToBin() returns its result in string form.  There are two reasons for this. Firstly, the function accumulates its result in a string. Secondly, the returned value will have to passed to IsPalindrome(), which requires a string input.

Line 5:  Passes  binary$ as the parameter to function IsPalindrome(). The returned value will always be 0 (FALSE) or -1 (TRUE).

Line 6:  If Line 5 returned TRUE, both binary and denary forms of the same value were palindromes, and we have a valid result.  The two are sent to the subroutine PrintResult() for printing to the screen. The fact that one of the arguments is in string form and the other in integer form is simply to assist formatting for output.

Lines 7 and 8: Housekeeping - closes the nested if-endifs.

Line 9:  Increments denary ready for the next test.

Line 10: If denary's newly-incremented value is still less than 10,000 the program executes the DO loop again.  If not, it moves on to the terminating code.

Both IsPalindrome() and DecToBin() have been used in several previous Puzzlets.  If you want to know more about how they work, please refer back via the archives, or e-mail me at the address below.

When you run the code, it generates the screen shown inset, with  twelve solutions. You may find it easier to understand in this format:        1                   1        3                  11        5                 101        7                 111        9                1001       33              100001       99             1100011      313           100111001      585          1001001001      717          1011001101     7447       1110100010111     9009      10001100110001

Searching ...      1                          1      3                        11      5                      101      7                      111      9                    1001     33                100001     99              1100011   313           100111001   585         1001001001   717         1011001101 7447    1110100010111 9009  10001100110001 No more! Press any key ...