Date:   Sun May 22 1994  05:51:09
From:   Dave Dunfield
To:     Ray Gardner
Subj:   A simple programming challenge
Attr:   
international C echo           -------------------------------
 RG> Tony, here's a possible solution:
 RG> /* solve.c -- find solution to simple programming challenge
 ... excellent, top-notch algorithm deleted for brevity ...

Ray,
You came up with virtually the same recursive algorithm I did, and
you must have posted it earlier since I got it the day I posted
mine. :-(  My only excuse is that I missed the original challange,
and was waiting around for someone to quote it completely.

To insure that I contribute something useful to the thread, here are
a couple of interesting variations on my original program (All code
below is hereby donated to the public domain):


#1 - Here the program has been converted to an iterative solution
(non-recursive):

On a system with "expensive" function calls, it could be faster, however
additional division operations to clean up after each attempt are likely
to (more than) negate any speed advantage.

Being non-recursive, it will use considerably less stack space.

It uses a pre-allocated stack to keep track of the digit attempted at
each position, so that it can properly resume from nested attempts...
This is handled much more nicely in the recursive solution, in which
the stack in inherent in local variable allocation.

Use of 'goto' avoids the necessity of an extra test following the
nested for loop, which keeps it closer to the recursive program.

#include <stdio.h>
main()
{
    long num = 0L, next;
    int i, n = 1;
    char digits[10] = { 0 };
    char lastdig[10] = { 0 };

    do {
    next:
        if(n >= 10)                             /* This number qualifies */
            printf("%ld\n", num);
        else for(i=lastdig[n]+1; i < 10; ++i) { /* Test digits 1-9 only */
            if(digits[i])                       /* Digit in use */
                continue;
            if(!((next = num*10 + i) % n)) {    /* Divides - proceed */
                digits[i] = -1;                 /* Mark digit as used */
                num = next;                     /* Proceed from here */
                lastdig[n++] = i;               /* Save continuation */
                goto next; } }                  /* Restart test */
        digits[num % 10] = 0;                   /* Release digit */
        num /= 10;                              /* Remove last attempt */
        lastdig[n] = 0; }                       /* Reset lower starts */
    while(--n);
}

#2 - This recursive version has been compressed into a single function
program.

It should operate at similar speeds to the original, two "moves" have
been added, as well as an increment and decrement. Parameter passing
and one addition have been removed.

It uses less stack space, as the parameters are not passed. On most
systems, this will translate to 6 bytes per recursion (60 total).

It is probably one of few functional recursive main() functions
that you will encounter in this echo.

#include <stdio.h>
main()
{
    int i;
    long savenum;
    static int n = 0;
    static char digits[10] = { 0 };
    static long num = 0;

    ++n;
    if(n >= 10)                             /* This number qualifies */
        printf("%ld\n", num);
    else for(i=1; i < 10; ++i) {            /* Test digits 1-9 only */
        if(digits[i])                       /* Digit in use */
            continue;
        savenum = num;                      /* Save our place */
        if(!((num = num*10 + i) % n)) {     /* Divides - proceed */
            digits[i] = -1;                 /* Mark digit as used */
            main();                         /* Try sub-combinations */
            digits[i] = 0; }                /* Release digit */
        num = savenum; }                    /* Restore place */
    --n;
}

Regards,

Dave

--- Squed 1.07
 * Origin: Dunfield Development Systems - 613-256-5820 (1:163/107.4)