Puzzlet Solution 098

THE PUZZLET PAGE

PUZZLET 98 - THE SOLUTION

When I first published the IBasic solution to Puzzlet #098 on July 18th, I mentioned that the code ran very slowly and invited responses. Kirk Bresniker wrote in and suggested using recursion. He developed a routine of his own for permutations. He spoke about levels of checks.

This set me thinking, and I came up with my own routine. It runs about five times faster. Of course, it's a little more complicated, using double recursion, but there's no such thing as a free lunch. Here's the revised version.

' Puzzlet #098
' Take a 6-digit integer, abcdef, all of
' whose digits are different. Process it
' as a*b^c + d*e^f to generate a 4-digit
' unidigital integer (that is, one whose
' digits are all the same). For example,
' with 237954 this process yields 9999.
' Are there any other 6-digit integers
' which can be processed in this way to
' yield 4-digit unidigitals?
' By Dave Ellis.

declare LoadArray()
declare IncArray(digNr: int)
declare NoRepeats()
declare GetDerivedNr()
declare AllDigitsSame(n: int)
declare PrintArray()
declare PrintResult()
def numArray[7]: int
def derivedNr: int

color 11,0: cls
openconsole
print "Searching ...": print
color 14, 0

LoadArray()
'main routine
do
    IncArray(6): 'get next legal number
    derivedNr = GetDerivedNr(): 'apply a*b^c+d*e^f
    if derivedNr > 999 & derivedNr < 10000: 'in range?
        if AllDigitsSame(derivedNr): 'all digits same?
            PrintResult()
        endif
    endif
until numArray[1] = 0

color 11,0
print: print "No more!"
print: print "Press any key to exit ... ",
do: until inkey$ <> ""
closeconsole
end

sub LoadArray
' initialises start nr to 123456
def i: int
for i = 1 to 6
    numArray[i] = i
next i
return

sub IncArray(digNr)
' This recursive subroutine gets the next legal
' nr. First it applies rollover (eg, 145639
' rolls over to 145640). Next it looks for
' repeated digits and increments, this time by
' rolling over the repeated digit, until there
' are no repeated digits. So after 145640 you'll
' get 145670.
' digit 6 is LSD, digit 1 is MSD
' numArray[6] holds LSD
' numarray[1] holds MSD
def rptDigNr: int
' this part just increments digNr. If the specified
' digit is a 9, it will be rolled over to 0. In such a
' case, recursion is used to increment the next
' more significant digit. If this is also a 9, another
' recursive call is made for the next digit, and so
' on.
numArray[digNr] = numArray[digNr] + 1
if numArray[digNr] > 9
    numArray[digNr] = 0
    digNr = digNr - 1
    IncArray(digNr): 'recursive call
endif
' this part deals with the case of repeated digits.
'no matter what the position of the repeat, the
'least significant of the repeated digits will be
'incremented using recursion.
do
    rptDigNr = NoRepeats()
    if rptDigNr > -1
        IncArray(rptDigNr): 'recursive call
    endif
until (rptDigNr = -1)
return

sub NoRepeats
' returns -1 if cells 1 to 6 in numArray[]
' are all unique, otherwise returns 0
def i1, i2: int
for i1 = 1 to 5
    for i2 = i1 + 1 to 6
        if numArray[i1] = numArray[i2]
            return i2
        endif
    next i2
next i1
return -1

sub GetDerivedNr
' applies a*b^c + d*e^f to cells 1 to 6 of
' numArray[] and returns resultant integer
def num: int
num = numArray[1]* numArray[2]^numArray[3]
num = num + numArray[4]* numArray[5]^numArray[6]
return num

sub AllDigitsSame(n)
' if all digits in n are identical, returns -1,
' otherwise returns 0
def flag, i, L: int
def n$: string
n$ = ltrim$(str$(n))
f$= left$(n$,1)
L = len(n$)
i = 2
flag = -1
do
    if mid$(n$,i,1) <> f$
        flag = 0
    endif
    i = i + 1
until flag = 0 | i > L
return flag

sub PrintArray
' prints cells 1 to 6 of numArray[] out
' as a single integer
def i: int
for i = 1 to 6
    print numArray[i], chr$(8),
next i
print " ",
return

sub PrintResult
' pretty printer
PrintArray()
print "--> (",
print numArray[1], "x ",
print numArray[2], chr$(8), "^",
print numArray[3], chr$(8), ") + (",
print numArray[4], "x ",
print numArray[5], chr$(8), "^",
print numArray[6], chr$(8), ") = ",
print derivedNr
return

PROGRAM NOTES

Variable derivedNr holds the result of applying the specified formula, derivedNr = a*b^c + d*e^f.

Array numArray[] is used to hold the 6-digit integers we will be manipulating. Each cell's job is shown below.

Cell Number	Useage

numArray[0]	Not used
numArray[1]	Holds MSD (most significant digit
numArray[2]	digit 2
numArray[3]	digit 3
numArray[4]	digit 4
numArray[5]	digit 5
numArray[6]	Holds LSD (least significant digit)

This program uses the top-down approach, so the whole thing can be understood at overview level from just the short main routine. I've numbered the lines in the extract below to make the following explanation easier to understand.

1
2
3
4
5
6
7
8
9

do
    IncArray(6): 'get next legal number
    derivedNr = GetDerivedNr(): 'apply a*b^c+d*e^f
    if derivedNr > 999 & derivedNr < 10000: 'in range?
        if AllDigitsSame(derivedNr): 'all digits same?
            PrintResult()
        endif
    endif
until numArray[1] = 0

Here is an exegesis of the code, using the above line numbers:

do. Opens the main DO loop.

IncArray(6). Calls subroutine IncArray(), which increments numArray[] to make it hold the next higher legal number (that is, it must contain no repeated digits). See below for a more detailed explanation of how inCarray() works.

derivedNr = GetDerivedNr(). The contents of numarray[] have just been incremented ready for the next investigation. The formula a*b^c+d*e^f is applied by function GetDerivedNr(), which returns the result. This is stored in variable derivedNr.

if derivedNr > 999 & derivedNr < 10000. Checks whether derivedNr is the required four digits in length.

if AllDigitsSame(derivedNr). If the length is ok, Line 5 passes derivedNr as parameter to the function AllDigitsSame(). This function returns TRUE (-1) if its argument's digits are all identical, otherwise it returns FALSE (0).

PrintResult(). If all the digits were the same, subroutine PrintResult() is called to print the solution neatly to the computer screen.

endif. Housekeeping - closes nested IF-ENDIF clauses.

endif.

until numArray[1] = 0. Checks the status of the number currently held in numArray[1]. If it's 999999 or less, the main DO loop is executed again. If it's greater than 999999, the MSD will have rolled over to 0, and this is the sign that all legal numbers have been executed. When this occurs, the DO loop is executed and the program stops.

Subroutine IncArray().

This subroutine is really the heart of the whole program. It uses a form of double recursion, and takes care of the complicated task of finding all possible permutations of any six digits from 0 to 9 which do not begin with zero and do not contain any repeated digits.

The number being permutated is held in numArray[]. When IncArray() is called, the digit of the number to be incremented must be passed as a parameter, such as IncArray(6). When called from the main routine, digit 6 (the LSD) is always the parameter, but when IncArray() repeatedly calls itself recursively, the parameter changes all the time.

If it were dealing were a number such as 183479, it would know to rollover digit 6 to 183470 (notice that digit 5 still hasn't changed, and it needs to). Then, by recursion, the subroutine calls itself again using IncArray(5) to increment the fifth digit. This would return 183480, a correct rollover. If there had been more 9's to the left, it would rollover as often recursively as necessary until the next legal number was reached.

It doesn't end there. IncArray() will now recognise that 183480 is no good - it's got a repeated digit. It will also know there's no point in incrementing through 183481, 183482, ... 183489 to reach a legal number: everything after the fifth digit will still leave an illegal number. So, still using recursion, it calls itself again to increment in one jump to 183492. If this created another repeated digit elsewhere another, deeper layer of recursion would be triggered.

This really speeds up program execution. Imagine the case of trying to roll over 220000. It's 10,000 rollovers to the next legal number, but IncArray() does it in one step, going directly to 230000.

The REMs of the subroutine are well commented in case you want to take a closer look at its mechanics.

When you run the program, you'll see the inset solutions printed out to your computer's screen.

Notice that while the first and last three digits of each integer could be transposed succes-

sfully, but doesn't easily lead to a shorter runtime due to the result 645873: both triplets are above mid-point.

MAIN MENU
DOWNLOAD CODE
ARCHIVE

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