THE PUZZLET PAGE


How_Does_It_Work


FUNCTION:  AllDiffBy2().  This function takes an integer as its argument.  If every digit of its argument differs from its neighbours by exactly 2, it returns TRUE (-1), otherwise it returns FALSE (0).

The integer can be any of the usual IBasic types, as shown below:

Type

Exponent of 2
Value

int 230 1073741824
uint 231 2147483648
int64 261 2305843009213693952
uint64 262 4611686018427387904


Declaring the function must be done like this:

declare AllDiffBy2(a: int) (or whatever type of integer you choose).

Here's the code:

sub AllDiffBy2(a)
' if every digit of argument a differs from its
' neighbour/neighbours by two, returns -1,
' otherwise returns 0
def flag, LSD: int
flag = -1
do
    LSD = a % 10: 'copy least significant digit
    a = a/10: 'divide argument by 10
    'does copied LSD differ from next by 2?
    if abs(LSD - a % 10) <> 2
        flag = 0
    endif
until flag = 0 | a < 10
return flag


Overview:  Argument a holds the number to be checked. The algorithm here is simply to compare the Least Significant (or rightmost) Digit of a with the one to its left.  If the difference is 2, remove the LSD and repeat the process.  This continues until either a difference not equal to 2 is found, or only one digit of a remains.

The code copies the LSD into variable LSD.  Now the argument a is divided by ten and the remainder discarded, effectively just removing its rightmost digit.

The newly-exposed rightmost digit can be compared with the old one, because it's still stored in variable LSD.  If the difference isn't 2, variable flag, which was initialised originally to -1, is reset to zero.

When the end of the process is reached, it is re-executed if neither flag is at value zero nor the length of a less than two digits.  When one of these conditions is met, the function simply returns the value in flag to the calling routine.  It will be at the initialised value of TRUE (-1) unless a difference between adjacent digits of other than 2 was encountered.


To make it simpler to follow a detailed code description, I've numbered the lines as shown below.  For simplicity, I have removed the comment-only line.


1
2
3
4
5
6
7
8
9
10

def flag, LSD: int
flag = -1
do
    LSD = a % 10: 'copy least significant digit
    a = a/10: 'divide argument by 10
    if abs(LSD - a % 10) <> 2
        flag = 0
    endif
until flag = 0 | a < 10
return flag

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

1

def flag, LSD: int.  Establishes local variables.  flag will be used to indicate a TRUE (-1) or FALSE (0) status for return to the calling routine.  LSD will be used to hold the least significant digit of argument a just before it's removed from a.

2

flag = -1flag is initialised to -1 (TRUE).  Thus, it's assumed that every digit of the argument is different from its neighbours by exactly 2 until evidence is found to the contrary.

3

do.  Opens main DO loop.

4

LSD = a % 10.  Line 4's purpose is to obtain and save a copy of the argument's LSD (Least-Significant, or rightmost, Digit).  It does this by using integer arithmetic.  In IBasic, the % sign means "divide by 10 and discard any remainder."  For example if a is equal to, say, 29731, the remainder after dividing by 10 would be 1.  In such a case the value saved in variable LSD would be 1.  Note that we haven't actually changed argument a at this time - it's still 29731.

Why do want to save this digit?  In a short while, the code will remove it from the argument permanently, but still want to refer to it, so it has to be saved.  You'll see below why the code has to remove it.

5

a = a/10.  Now that we have saved a copy of the LSD, it's ok to chop the original off!  Line 5 does that.  Let's use the example value introduced above, 29731.  Normally, dividing 29731 by 10 would yield 29731.  However, a is always an integer, so it truncates the result to 2973, effectively chopping off its own LSD.

Why does the code want to remove the LSD?  This is the heart of the process.  It's comparing the LSD with the one to its left all the time.  To do this, it copies the value of the LSD, then removes the LSD itself from the argument.  We now have a new LSD, which can be compared with the one stored in variable LSD.  If they differ by some other value than 2, the process is aborted; if the difference is exactly 2, the process is repeated, causing argument a to keep shortening.  When it's down to the last digit.  We're finished.

6

if abs(LSD - a % 10) <> 2.  This is where the comparison just described takes place.  It looks complicated, but can be unravelled easily.  Let's start inside the brackets.  We know that a % 10 effectively isolates the LSD of the current value of a.  And we know that the last value of LSD is stored in variable LSD.  So (LSD - a % 10) means "Subtract the new LSD from the old one."

Using the example 29731.  After lines 4 and 5 have been executed, variable LSD holds value 1 and argument a has been truncated to 2973.  Then
a % 10 yields value 3, and (LSD - a % 10) means "1 - 3", which in turn yields value -2.

Thus the two digits differ by 2 as required.  It's awkward to handle as a negative number, however.  And just to make things more difficult, the code doesn't know if it's going to be negative or positive at any one time.  To overcome this, the built-in function
abs() is deployed.  In effect, it says "take whatever value is in the brackets and, if it's negative, remove the negative sign."

So abs(LSD - a % 10) will always return a positive number, and in our example, will return 2.  The complete expression now makes sense:  if abs(LSD - a % 10) <> 2  can be paraphrased as a question: "Do the old LSD and the new one differ in value by 2, regardless of sign?"

7

flag = 0.  This line is only executed if the answer to the question in line 6 is "No."  It means two adjacent digits don't differ by exactly 2, a failure.  Variable flag is set to zero to indicate this and enable a quick exit from the function, since there's no point in further checks.

8

endif.  Housekeeping - close the IF-ENDIF clause opened in line 6.

9

until flag = 0 | a < 10.  The end of the DO loop has been reached and a decision must be made: execute it again, or move on?  If flag has been reset to zero, at least two adjacent digits don't differ by exactly 2, so there's no point in continuing. 

Alternatively, if the last removal of a's LSD reduced it to a single digit (that is, value less than 10), it has no further digits for comparison and the job is finished. Note that, in these circumstances, flag must still be at TRUE (-1).

So line 9 is effectively saying "if variable flag is set to FALSE or we've reached the end of the checks on argument a, quit the DO loop, otherwise execute it again."

10

return flag.  All that remains now is to return whatever value is in variable flag to the calling routine, and line 10 does that for us.



MAIN MENU
HOW DOES IT WORK?

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