THE PUZZLET PAGE

PUZZLET 053 - THE SOLUTION


I should begin by saying that it's not too hard to solve this Puzzlet manually  It goes like this:

Case 1:  First digit is a 2. In order to keep to odd numbers, the last digit can only be a 1, 3, or 5. In each of these three scenarios, the remaining four digits can be permutated.  Taking four things in any order yields 24 permutations (You can use your calculator to confirm that 4P4 = 24).  So the three scenarios yield 3 x 24 = 72 acceptable numbers.


Case 2:  First digit is a 3. In this case, the last digit can only be a 1 or a 5. It can't be a 3, since this would duplicate the first digit.  In each of these two scenarios, as for case 1, there are 24 permutations.  2 x 24 = 48.  
So the two scenarios yield 2 x 24 = 48 acceptable numbers.

Now just add the numbers from cases 1 and 2.  72 + 48 = 120.


In spite of the ease of developing this result manually, we have no generic method that will work for other ranges etc.  So it's worth developing the code as it will have a much wider range of use.  It's also an interesting exercise, since the instructions were to "count" the acceptable numbers, and the program does exactly that.


' Puzzlet #053
' Count the odd numbers between 200,000
' and 400,000 which use all the digits 1 to 6
' inclusive, in any order, just once.

' By Dave Ellis.


declare One2Six(n$: string)
declare AllDigitsDifferent(n$: string)
def count, number: int
def num$: string
openconsole
print
"Counting ...": print
print
"Found:  ",
count = 0
num = 213463


do
    num$ = ltrim$(str$(number))
    if number % 5 = 0
        number= number + 6
    else
        number = number + 2
    endif
    num$ = ltrim$(str$(number))
    if One2Six(num$)
        if AllDigitsDifferent(num$)
            count = count + 1
            locate 3, 9
            print count
        endif
    endif
until
number > 365421


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


sub One2Six(n$)
' if the numerical value of every digit
' in n$ is between 1 to 6 inclusive,
' returns 1, otherwise returns 0.

def flag, i, m: int
i = 1
flag = 1
do
    m = val(mid$(n$, i, 1))
    if m < 1 | m > 6
        flag = 0
    else
        i = i + 1
    endif
until
flag = 0 | i = 7
return flag

sub AllDigitsDifferent(n$)
' if all the characters of n$ are mutually
' different, returns 1, otherwise returns 0

def flag, i, j: int
def p$, q$: string
i = 1
flag = -1
do   
    j = i + 1
    do
        p$ = mid$(n$, i, 1)
        q$ = mid$(n$, j ,1)
        if q$ = p$
            flag = 0
        else
            j = j + 1
        endif
    until
flag = 0 | j > 6
    i = i + 1
until flag = 0 | i > 5
return flag


PROGRAM NOTES

To make the explanation of this code simpler, I've repeated the lines that control the program with line numbers.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
count = 0
num = 213463

do
    if number % 5 = 0
        number= number + 6
    else
        number = number + 2
    endif
    num$ = ltrim$(str$(number))

    if
One2Six(num$)
        if AllDigitsDifferent(num$)
            count = count + 1
            locate 3, 9
            print count
        endif
    endif
until
num > 365421



Line 1:  Variable count is used to hold the number of acceptable integers (that is, those odd numbers between 200,000 and 400,000 using all digits below 7 once and once only) found by the program so far.  Here it's initialised to zero.

Line2:  The variable number is used to hold the number currently being investigated.  Here it's being initialised to its lowest possible value. It has to begin with a 2. The next digits must utilise 1, 3, 4, 5, and 6, giving 213456. However, the final digit must be odd, leading to 213465.  A minor complication is that the code always increments this value by two before doing anything else, so it's initialised to a value lowered by two to compensate.  We end up with 213463.  Don't worry that this is an illegal value (it contains two 3's and no 5).  That first increment will take care of it.

Line 3:  
Opens the main DO loop.

Line 4:  If the rightmost digit of number is 5, we make an increment of six to bring it back to a 1 while rolling over the preceding digit in the normal manner. This prevents illegal digits appearing in the rightmost position. 6 isn't allowed, as this would make an even number. 7, 8, and 9 aren't allowed since they're all greater than 6. 0 isn't allowed because, once again, it would create an even number.

Line 5:   Makes the actual increment determined in Line 4.

Line 6:  If it turned out in the Line 4 test that the rightmost digit of number wasn't a 5, it could only be a 1 or a 3 due to the initialised value in Line 2 and the rules deployed in Lines 5 and 7.  For a 1 or a 3, an increment by two is called for to keep the number odd.

Line 7:  
Makes the alternate increment determined in Line 6.

Line 8:  Housekeeping - closes the if-endif clause.

Line 9:  Converts number into a string, storing it in variable num$. A string is much easier to manipulate for our purposes than an integer.

Line 10:  Now that we have a value for number, we need to ensure it contains only digits with values from 1 to 6 inclusive. This test is performed by the function One2Six().  If the conditions are met, a -1 for TRUE is returned, otherwise a 0 for FALSE is returned.

Line 11:  If a TRUE is returned from Line 10, we still need to make sure that each of the digits 1 to 6 inclusive is used once and once only - a number such as 234151 will pass that test but is still illegal because it contains two 1's. So num$ is now submitted to the function AllDigitsDifferent(), which follows the same return rules as One2Six().

Line 12:  This line is only every executed for numbers that have passed all tests, so it must be valid for count purposes.  To record it, count is incremented by one.

Lines 13/14:  In order to show the user something is happening, a running total of acceptable numbers is printed to the screen.  To make it appear in the same place, the locate command is used.

Line 15/16:  Housekeeping - closes the nested 
if-endif clauses.

Line 17:  The maximum legal value for number is 365421, since it is the highest possible odd number using all the digits 1 to 6 inclusive. This line looks at number's value.  If it hasn't reached 365421 yet, it will be ok to execute the main loop again.  If it has, further increments will make it illegal, so the loop is exited and the program stops.



When you run the code, it generates the screen shown inset, and you can see that the answer agrees with that worked out manually.

Counting ...

Found:  120

No more!

Press a key ...


MAIN MENU
DOWNLOAD CODE
ARCHIVES


Site design/maintenance: Dave Ellis E-mail me!
Last Updated: February 22nd, 2004.