THE PUZZLET PAGE


How_Does_It_Work


FUNCTION:  IsForwardRun().  A "Forward Run" number is an integer whose digits are all in consecutive, ascending order, left to right, such as 123, 56789, 45, etc.

When an integer is passed to IsForwardRun(), the function checks out  all of its argument's digits. If they are arranged as described above, TRUE (-1) is returned, otherwise FALSE (0).

It's up to you what kind of integer you pass to the function, as long as the function declaration has already taken this data-typing into account. See the table below for the parameter limits.

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

Here's the code:

sub IsForwardRun(f)
' if f forms a forward run, such as 567 or
' 123456, 45 etc, returns TRUE  (-1),
' otherwise returns FALSE (0)
if f < 10: 'not enough digits for a run
    return -1
endif
def flag, LSD1, LSD2: int
flag = -1
do
    LSD1 = f % 10: 'save current LSD
    f = f/10: 'chop off current LSD
    LSD2 = f % 10: 'get new LSD
    if LSD1 - LSD2 <> 1: 'not ascending
        flag = 0
    endif
until not flag | f < 10
return flag


Overview:  Variable f holds the number to be checked for consecutive, ascending orderliness.  The code copies the LSD (Least Significant, or rightmost, Digit) into variable LSD1, then chops the LSD off f, so that a new LSD exists on the end of f (what used to be the second last digit, in fact).  The new LSD is saved in variable LSD2.

If the two digits are in
consecutive, ascending order, their difference will be exactly 1. A check is made that LSD1 - LSD2 equals 1 is made. If the difference isn't exactly one, f wasn't in consecutive, ascending order, so no further checks are made.  The function quits, returning FALSE (0) to the calling routine.

If t
he difference is exactly one, ascending orderliness hasn't been disproved yet, so another round of checks as above is carried out, this time on the next available LSD.  Each time these checks are carried out, f gets a bit shorter since its LSD is being chopped off every time. 

Eventually, if no failures in orderliness are detected, f will be reduced to zero length.  When this happens, TRUE (-1) is returned to the calling routine.


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

f is the function's argument which has been submitted by the calling routine. It's asking the question "Are f's digits in consecutive, ascending order?" and expects one of two replies: TRUE (-1) or FALSE (0). IsForwardRun()'s job therefore is to determine f's consecutive, ascending orderliness and respond accordingly.

Variable flag is used to indicate f's orderliness. It's set to TRUE (-1) to begin with, and will stay that way unless f is found not to be ordered, at which point it will be reset to FALSE (0). The code picks the change up and aborts further investigation, making the function work more efficiently.

Variable LSD1 is used to hold f's current LSD (that is, the least significant, or rightmost, digit). In this function, f is repeatedly shortened by chopping off the rightmost digit. Everytime this happens, a new rightmost digit appears, and this is loaded into LSD2. So the contents of these variables change all the time.

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


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

if f < 10: 'not enough digits for a run
    return -1
endif
def flag, LSD1, LSD2: int
flag = -1
do
    LSD1 = f % 10: 'save current LSD
    f = f/10: 'chop off current LSD
    LSD2 = f % 10: 'get new LSD
    if LSD1 - LSD2 <> 1: 'not ascending
        flag = 0
    endif
until not flag | f < 10
return flag

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

1

if f < 10.  This is a preliminary check. If is less than 10, it can't fail a run check because there are no other digits which could cause it to fail. So no further checks on f will be necessary.

2

return -1.  If the code reaches this line, it means that f only has one digit.  The convention here is that this is considered to be a run, and TRUE (-1) is returned to the calling routine.

3

endif.  Housekeeping - closes IF-ENDIF clause.

4

def flag, LSD1, LSD2: int.  If the code gets this far, f has more than one digit, so a digit-by-digit check on it will be made.  This line defines the variables that will be used to make the checks.  LSD1 will hold f's last LSD.  After saving the last LSD, f's LSD is chopped off, so a new LSD appears, and this is stored in LSD2.  Variable flag is used to indicate TRUE or FALSE status of consecutive, ascending orderliness of f.

5

flag = -1.  Variable flag is preloaded with the value -1.  Thus, the assumption is made that, until evidence to the contrary is found, f's digits are in consecutive ascending order.

6

do.  Opens the main DO loop.

7

LSD1 = f % 10.  We can paraphrase this expression as "Divide f by 10 and save the remainder in variable LSD." Such a division is called integer arithmetic. 

Example:  Assume f is 12345.  Dividing by 10 gives 1234 remainder 5. The 5 is saved in LSD1.  So you can see that the effect is simply to find f's own LSD and save it in variable LSD1.

Note two important things here. Firstly, only the remainder of the division is saved. Secondly, f itself isn't changed when this line is executed, because we didn't save anything into f itself, so whatever was there remains there.  You could therefore more accurately paraphrase the line as "Find out what the remainder would be if f were to be divided by 10, and, without actually changing f, save that remainder in variable LSD1."

8

f = d/10.  To paraphrase the expression, "Divide variable f by 10 and save the result in f  itself, over-writing the original contents." 

This line performs a neat operation.  To explain it, let's assume that f has value 12345.  Normally, dividing it by 10 would give 1234.5, but something else happens here.

Remember that f was declared as an integer in the declaration? That means that it must remain an integer, no matter what we do to it. And an integer contains no decimal part. So the operation on this occasion gives f's new value as 1234 - the 0.5 has been discarded.

Thus, the operation in effect says "Chop off the rightmost digit of f."

9

LSD2 = f % 10.  This is almost identical to the action in line 7 above, except for two things.  Firstly f's LSD has been chopped off, so f % 10 will yield the new LSD, different to that stored in variable LSD1.  Secondly, this new LSD is stored in a different variable, LSD2.

10

if LSD1 - LSD2 <> 1.  Once again, a paraphrase can help us understand this expression more clearly: "Is the value of LSD1 exactly 1 greater than that of LSD2?".

Why are we making this comparison? Assume f started with value 12356. After one execution of lines  7 to 9, LSD1 contains 6, LSD2 contains 5 and f now contains 1235. So the expression
LSD1 - LSD2 will yield 1. Thus, at the moment, consecutive ascending orderliness is assumed.

The next time around the DO loop things have changed, because lines 7 and 8 have been executed again. 
LSD1 now contains 5, LSD2 contains 3, and f now contains 123. So LSD1 - LSD2 will yield 2. This proves that, although everything was ok the first time around the loop, it wan't the second time, and consecutive ascending orderliness isn't maintained throughout the whole of f.

11

flag = 0.  If the code reaches this line, it found two successive digits that weren't in consecutive ascending order. It immediately sets flag to zero so that the code will be able to quit without wasting time on further unnecessary digit checks.

12

endif.  Housekeeping - closes IF-ENDIF clause.

13

until not flag | f < 10The code now reaches the end of the DO loop. It needs to decide whether to execute the loop again, or just move on to the next instruction.

The line
until not flag | f < 10 is the decision-maker.  It can be paraphrased as "execute the DO loop again unless either flag is FALSE (0) or the value of f is less than 10."

The "
until not flag" may appear confusing, but it's actually simple. The normal phrase is "until flag" and means "execute the DO loop until flag is set to TRUE (-1)." So "until not flag" means the opposite: "execute the DO loop until flag is set to FALSE (0)."

Clearly, if flag is FALSE (0), a non-ordered digit has been found, so there's no need to look at any more of f's digits. The function can return the FALSE (0) immediately.

And the alternative for exiting the DO loop is if f is less than 10. Remember, f's length is decremented by 1 each time the DO loop executes without finding a non-ordered digit. So, eventually, if all the digits are ordered, f will be shortened to just 1 digit - obviously having value less than 10. Since there is no other digit to its left to compare to, the necessary digit checks are complete and the program can quit.

14

return flag.   One of those two alternatives will cause the last line of code to be executed: return flag. The calling routine will thus receive either a FALSE (0) or TRUE (-1), corresponding to the consecutive, ascending orderliness of the digits of argument f.

This code was originally written with a different algorithm, using strings. This version runs faster.

MAIN MENU
HOW DOES IT WORK?

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