THE PUZZLET PAGE


How_Does_It_Work


FUNCTION:  Is10Pandigital().  A pandigital is an integer which comprises all the digits less than 10 in any order. Sometimes this omits the digit 0, so I call that a 9-digit pandigital. Otherwise I use the term 10-digit pandigital, and it is the latter this function tests for.

10-digit pandigitals can be regular integers (int) up to a maximum value of 2147398650, but above that they are long integers. For convenience, I have therefore designed this function to work with a long integer (int64) argument.


Declaring the function must be done like this:

declare Is10Pandigital(p: int64)

Here's the code:


sub Is10Pandigital(p: int64)
' if argument p is a 10-digit
' pandigital, returns TRUE (-1),
' otherwise returns FALSE (0).
' Note: this algorithm is about
' four times faster than one
' using string manipulation.
def a[10]: int
def flag, i, r: int
' initialise array
a = 9,8,7,6,5,4,3,2,1,0
' load array
do
    r = p % 10
    a[r] = r
    p = p/10
until p = 0
flag = -1
i = 0
' array contents pandigital?
do
    if a[i] <> i
        flag = 0
    endif
    i = i + 1
until flag = 0 | i = 10
return flag

Let's look at the variables before we begin on the code detail.

Variable p is the function's argument, passed from the calling routine for investigation.

Array A[] is created to hold all the digits of p. Note: although p is an int64 type, A[] is of type int. This is because A[] is only called on to hold the individual digits of p one at a time in its cells, and a single digit is only an int.

Variable flag is used to flag the state of the investigation. It's initially set to TRUE (-1), making the assumption p is a 10-digit pandigital. If it's reset to FALSE (0) at any time, no further checks are made on p, increasing efficiency by avoiding unnecessary further testing. It is then used to give a replay to the calling routine.

Variable r is used to hold the remainder of integer arithmetic operations, and also as a pointer to A[] in the first part of the function.

Variable i is used as an iterator on A[] in the second part of the function.

To make it simpler to follow detailed code description, I've number the lines as shown below.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

a = 9,8,7,6,5,4,3,2,1,0
do
    r = p % 10
    a[r] = r
    p = p/10
until p = 0
flag = -1
i = 0
do
    if a[i] <> i
        flag = 0
    endif
    i = i + 1
until flag = 0 | i = 10
return flag

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

1












a = 9,8,7,6,5,4,3,2,1,0.  This line pre-loads array A[] in a very specific way. It contents become:

Cell number
0
1
2
3
4
5
6
7
8
9
Cell contents
9
8
7
6
5
4
3
2
1
0

These assignments are very important. It means that, if every single cell is now loaded with the digit corresponding to the cell number, no cell will remain unchanged. The second part of the function will exploit this fact.

2

do. Opens first DO loop. This part of the function will break down p into its separate digits and load them array A[], each digit going to the cell corresponding to its value.

3

r = p % 10. This says in effect "Divide p by 10 and store the remainder in variable r. For example, if p equals 4352167498, after the operation r will contain 8. Thus, we have separated out just the last digit. Note that, if p ends in zero, r will also contain zero. This is crucial to the correct operation.

4

a[r] = r. Whatever is currently in r is now stored in the array cell with the corresponding number. So, if r contains, say, 6, A[6] will be loaded with a 6.

5

p = p/10Having looked at the right-most digit of p, we want to look at the one to its left. To do this, we simply lop off the last digit and then repeat line 4.

Now, p is an integer type, albeit a long integer (int64). So dividing it by 10 will produce another integer, regardless of the result. For example, when p is
4352167498, you might have expected p to become 435216749.8, but it simply becomes 435216749, the desired result.

6

until p = 0.  This is the end of the DO loop, so it's time to make a decision. Execute it again, or move on the next piece of code. This is easy! We just need to check if the last time we did p = p/10 produced a zero. If it did, all of the digits of p have now been processed, and we can move on. If not, go around and execute the DO loop again.

7

flag = -1.  Now we're moving on to the second part of the function. In preparation, flag is set to TRUE (-1). Its use will be seen once we get into the next DO loop.

8

i = 0.  Variable i is the iterator the DO loop which is about to opened, and its initialised to zero here in readiness.

9

do.  Opens the second  DO loop containing the A[]  contents pandigital checks.

10

if a[i] <> i. In the first part of the function, we loaded every digit of p into the A[] cell corresponding to its value. Because A[] was preloaded, any pandigital digit missing from p will result in the corresponding cell of A[]  containing the wrong value.  For example, assume p is 4352167491. The table below shows the contents of A[] the preload and then after the first DO loop.

Cell number
0
1
2
3
4
5
6
7
8
9
Contents after preload
9
8
7
6
5
4
3
2
1
0
Contents after first DO loop
9 1
2
3
4
5
6
7
1
9

Because p's contents (4352167491) didn't contain either a 0 or an 8, cell numbers 0 and 8 will have incorrect values after the first DO loop has finished. Look at the last line of the table.  Every cell now has the value in it which corresponds to the cell number except cells 0 and 8.

11

flag = 0.  If the code reaches this line, a cell of A[] was found to have a value not corresponding to the cell number, so flag is set to FALSE (0). In the example given above,  this would occur when the checks reached cell 1.

12

endif.  Housekeeping - closes the IF-ENDIF clause

13

i = i + 1. Variable i is incremented ready for the next check.

14

until flag = 0 | i = 10.  Decision time again. If the last check set flag to zero, there's no point in continuing. Also, if the last increment of i set its value past 10 (that is longer than a 10-digit pandigital), all checks are complete. In the latter case, flag will still be in its original state, TRUE (-1). If either of these conditions are met, the DO loop is exited, otherwise it is executed again.

15

return flag.  The function has finished.  Variable flag holds the value TRUE (-1) or FALSE (0), and this is returned to the calling routine.

Earlier versions of this function used strings, but I have found this method, using integer arithmetic and arrays, is around four times faster.


MAIN MENU
HOW DOES IT WORK?

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