THE PUZZLET PAGE


How_Does_It_Work


FUNCTION:  NoDigitsIncluded().  Pass two integers, whose lengths can differ if required, to this function and it will inspect their digits. If they're all mutually exclusive (that is, none of the digits in the first appears in the second, and vice versa) the function returns TRUE (-1), otherwise it returns FALSE (0).

Example:  the integer pair 237, 8165 return TRUE (no repeated digits) while the integer pair 84361, 589 return FALSE (the 8 is repeated).

It's up to you what data type you make the argument, depending on the type of integer you want to process.


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 NoDigitsIncluded(p: int) (or whatever integer type you want).

Here's the code:


sub NoDigitsIncluded(d1, d2)
' if any of the digits in argument d1
' are included in argument d2, returns
' FALSE (0) otherwise returns TRUE (-1)
def str1$, str2$: string
def flag, i, L: int
str1$ = ltrim$(str$(d1))
L = len(str1$)
str2$ = ltrim$(str$(d2))
i = 1
flag = -1
do
    if instr(str2$, mid$(str1$, i, 1)) > 0
        flag = 0
    endif
    i = i + 1
until flag = 0 | i > L
return flag

Overview:  each argument is converted to string format so that the tests can be applied using string-slicing.  They are stored in local variables str1$ and str2$.

Using variable i as iterator, each character of str1$ is searched for in str2$ in order.  If a match is found, there's no point in searching any further, since at least one character of one argument clearly appears in the other argument.  Variable flag, initialised to TRUE (-1) is now set to FALSE (0).

When the code reaches the end of the DO-LOOP in which the search was being carried out, it sees the flag status and exits the loop.  Now it simply returns the flag status to the calling routine.

If no repeated digits existed, the DO-LOOP would eventually quit anyway, when it had checked every digit of str1$. This point is indicated when the number of checks equals the length of str1$, stored in variable L.  In this case the flag status is still at TRUE, and this is what would be returned to the calling routine.

In the description of the code which follows, I have applied line numbers to make it easier to follow. Here they are:

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

def str1$, str2$: string
def flag, i, L: int
str1$ = ltrim$(str$(d1))
L = len(str1$)
str2$ = ltrim$(str$(d2))
i = 1
flag = -1
do
    if instr(str2$, mid$(str1$, i, 1)) > 0
        flag = 0
    endif
    i = i + 1
until flag = 0 | i > L
return flag

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

1

def str1$, str2$: string.  Create two local variables to hold the function's arguments in string format.

2

def flag, i, L: int.  Create the rest of the local variables.

Name
Useage
flag

If two identical digits are found during the search, flag is set to FALSE. When the code sees this at the end of the current search, it doesn't bother to search any more.
i
Used to iterate over the digits of str1$. At every pass it looks for duplicates in str2$.
L
Stores the length of str1$.  Used to terminate the search when no digit matches have been found.

3

str1$ = ltrim$(str$(d1)).  Converts argument d1 into string format and stores it in str1$.

4

L = len(str1$). Uses inbuilt function len() to find the length of str1$ and stores the result in variable L.

5

str2$ = ltrim$(str$(d2)).  Converts argument d2 into string format and stores it in str2$.

6

i = 1.  Initialises variable i to 1.  This will be used to control the DO-LOOP which follows.

7

flag = -1.  Variable flag is initialised to TRUE (-1). This means the code is going to assume all of d's digits are different unless it discovers otherwise.

8

do.  Opens the  DO-LOOP.

9

if instr(str2$, mid$(str1$, i, 1)) > 0.  This looks complicated, but it's really very simple.  To understand it, start on the inside and work outwards.

From str1$, pull out the single digit pointed to by variable i.
Look right through str2$, checking every digit for a match with the one just extracted from str1$.
If a match is found, return TRUE, else return FALSE.

So we can paraphrase this line as: "Is there a digit anywhere in str2$ which matches the i'th digit of str1$?"

10

flag = 0.  This line is only executed if the answer to the question in line 9 is "yes." In such a case, flag is set to zero. You'll see how this change in flag's status is used in line 13.

11

endif.  Housekeeping - closes the IF-ENDIF clause.

12

i = i + 1.  Increments variable i so that it points to the next digit in str1$, ready for further comparison checks if necessary.

13

until flag = 0 | i > L.  The code has reached the end of the DO-LOOP, and it's time to make a decision: should the loop be executed again, or exited?  It's saying "if variable flag has been set to FALSE (0), or the newly-incremented variable i is now greater than the length of variable str1$, quit the DO-LOOP, otherwise execute it again."

If flag has been set to zero, at least one digit in str1$ matches one in str2$, so there's no point in making further digit checks.

14

On the other hand, if i has been incremented right up to the point of exceeding the length of str1$ as stored in variable L, it must mean that every single digit of str1$ has been examined without a match being found.

So three conditions could exist:  no match has been found, but there are still some digits to look at; no match has been found, but all digits have been checked; or a match has been found.

If the first condition is met, the DO-LOOP is executed again. If either of the other two have been met, the DO-LOOP will be executed.  Whatever happens, flag will accurately reflect whether a match exists or not.

14
return flag.  All that remains is to return the status of flag to the calling routine, and this line takes care of that.


MAIN MENU
HOW DOES IT WORK?

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