THE PUZZLET PAGE

 FUNCTION:  Is9Pandigital().  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. It is the former this function tests for.

 Declaring the function must be done like this: declare Is9Pandigital(p: int) Here's the code: sub Is9Pandigital(p: int) ' if argument p is a 9-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 = 0,9,8,7,6,4,5,3,2,1 ' load array do     r = p % 10     a[r] = r     p = p/10 until p = 0 flag = -1 i = 1 ' 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. Variable flag is used to flag the state of the investigation. It's initially set to TRUE (-1), making the assumption p is a 9-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 = 0,9,8,7,6,4,5,3,2,1 do     r = p % 10     a[r] = r     p = p/10 until p = 0 flag = -1 i = 1 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 = 0,9,8,7,6,5,4,3,2,1.  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 0 9 8 7 6 4 5 3 2 1

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 352167498, 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 - a zero isn't permitted in a 9-digit pandigital, and this part of the code detects such a case.

 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/10.  Having 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, so dividing it by 10 will produce another integer, regardless of the result. For example, when p is 352167498, you might have expected p to become 35216749.8, but it simply becomes 35216749, 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 = 1.  Variable i is the iterator the DO loop which is about to opened, and its initialised to 1 here in readiness.

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

10

if a[i] <> i. To paraphrase: "If the contents of the cell in array A[] pointed to by i are not equal to the value of i itself . . ." 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 435216249. The table below shows the contents of A[] after the preload and then after the first DO loop.

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

Because p's contents (435216249) didn't contain either a 7 or an 8, cell numbers 7 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 7 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.  This can be paraphrased as: "Execute the DO loop again unless either variable flag equals zero or  variable i equals 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 to 10 (that is, greater than a 9-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, 2005.