On Sat, 13 Sep 2003, Jerry Coffin wrote:
>
> m@rtij.nl.removefromhere.invalid says...
> > On Thu, 11 Sep 2003 23:40:29 +0000, Jerry Coffin wrote:
> >
> > Guys, try to meet each other in the middle.
>
> I've tried to.

It really doesn't look that way to the observers.
Let's see if maybe I can produce a *good* program
so we can stop this dumb thread.

> > - If there is a simple algorithm without some limitations on size,
> > it is more often than not better than one that does.  The assignment
> > said nothing about the size, so you have to think about it. The only
> > reasonable answer is 'ask the one who wrote these incomplete specs'.

Absolutely.

> > If the algorithm is size independent, that's OK too, but you'll
> > probably encounter the same problem somewhere else.
>
> And I've never said there was anything really terrible about the
> algorithm per se.  I've only said that it's more complex (and I'll
> openly admit that it's only marginally so, but more complex nonetheless)
> and for the job at hand does not seem to provide any real benefit.
>
> My real problem all along has been with the "hint" that was offered. If
> you follow that hint, you're more or less stuck writing this code about
> as badly as possible.

But see, you just said that there's nothing really terrible about this
algorithm that you're calling "about as [bad] as possible."  'Sides, I
could come up with a terribler algorithm in my sleep. ;-)

> For better or worse, I normally
> assume that even when working on toy problems that people posting here
> are interested in learning to program at least reasonably well so they
> can work toward solving real problems.  With that in mind, recommending
> techniques that have been proven (repeatedly) to fail even when solving
> small problems seems short-sighted at best.

The recommended algorithm does *not* fail, not even on medium-sized
inputs that stop your algorithm dead.  Or are you referring to the
"technique" of writing spaghetti-type code, that fails to produce
maintainable code for big algorithms?  In that case, I don't think
the recommended algorithm is very spaghetti-like at all.  It's pretty
elegant.

> > So a good solution would be to use the size-independent algorithm on a
> > string (or an iterator of course). Solves all points made.
>
> As I said above, I find this only marginally objectionable at worst, but
> I don't think it provides any real benefit, and I don't think anybody's
> shown a shred of evidence that my position is indefensible.

Famous last words?


> Consider that airline tickets are NOT the only system like this by any
> means -- there are also things like UPCs, ISSNs, ISBNs, and even
> Ethernet MAC addresses.  In every one of these cases (and quite a few
> more besides) a long long has a greater range than is demanded by the
> job at hand (though with both ISBNs and ISSNs, the check "digit" may be
> an "X" intead of a digit, so putting it into a long long may not be an
> option).

Right.  So let's try writing an actual program to solve the stated
problem:

/*
Airline tickets are assigned lengthy identifying numbers, such as
47715497443. To be valid, the last digit of the number must match
the remainder when the other digits--as a group--are divided by
7. (For example, 4771549744 divided by 7 yields a remainder of 3.)
Write a program that checks whether or not an airline ticket
number is valid:

Enter ticket number: 47715497443
VALID

Hint: Don't attempt to read the number in a single step. Instead,
use getchar to obtain its digits one by one. Carry out the
division on its digits one at a time, being careful not to include
the last digit in the division.
*/

#include 
#include 

#define MODULUS 7

int main(void)
{
    int c, nextc;
    int ndigits;
    int rem;

    printf("Enter ticket number: ");
    fflush(stdout);

    /* remove leading spaces, if any */
    while (isspace(c = getchar()) && c != '\n')
      ;

    rem = 0;
    for (ndigits = 0; isdigit(c); )
    {
        int nextc = getchar();

        ++ndigits;

        if (!isdigit(nextc))
        {
            /* c is the last digit */
            break;
        }
        else {
            rem = 10*rem + (c-'0');
            rem %= MODULUS;
            c = nextc;
        }
    }

    if (ndigits) {
        if (c-'0' == rem)
          printf("VALID\n");
        else
          printf("INVALID\n");
    }
    else {
        printf("No digits entered.\n");
    }

    return 0;
}


Conclusion: This is indeed a lengthier solution than the simple


#include 

int main(void)
{
    long long int number;
    if (scanf("%lld", &number) != 1)
      printf("No digits entered.\n");
    else
      printf((number/10 % 7 == number % 10)? "VALID": "INVALID");
    return 0;
}


However, given that it does not work in *all* cases, but only in
a few where the 'number' has fewer than 19 digits, I think that
an instructor would probably give less than full credit to the
"simple" solution.

I infer that the point of the problem is not to teach modularization.
It's teaching extensibility and robustness -- the idea that you must
really be prepared to handle "absurd" inputs, even if it makes the
program logic a bit convoluted.

I also note, in passing, that the OP's instructor may not have easy
access to a C99 compiler on which to compile Jerry's "long long"
solution.  The robust algorithm works in C89.

In short, having written out the code for the two approaches, I see
that Jerry's algorithm is less robust but much more conducive to
clever compression.  Heck, it's five lines long!  But the recommended
algorithm actually solves the problem as stated, with no assumptions
about line length or anything; so it should get the higher marks.

-Arthur

In article , ajo@andrew.cmu.edu says...

[ ... ]

> > And I've never said there was anything really terrible about the
> > algorithm per se.  I've only said that it's more complex (and I'll
> > openly admit that it's only marginally so, but more complex nonetheless)
> > and for the job at hand does not seem to provide any real benefit.
> >
> > My real problem all along has been with the "hint" that was offered. If
> > you follow that hint, you're more or less stuck writing this code about
> > as badly as possible.
> 
> But see, you just said that there's nothing really terrible about this
> algorithm that you're calling "about as [bad] as possible."  'Sides, I
> could come up with a terribler algorithm in my sleep. ;-)

It appears you haven't understood what I'm saying.  The algorithm itself 
(i.e. the piecewise calculation of the remainder) is pointless for the 
job at hand, but basically innocuous.

If he'd implemented that algorithm in a function of its own that worked 
from data in a string (or whatever), then I'd really have no _major_ 
problem with the code (it's still pointlessly complex, but to a degree 
that I agree is trivial).

> The recommended algorithm does *not* fail, not even on medium-sized
> inputs that stop your algorithm dead.

The algorithm he used doesn't fail, that's true.  The correct phrase for 
20+ digit serial numbers for something like this is not "medium-sized" 
but, "stupidly ridiculous" or something on that order.  To reiterate the 
example I used before, UPCs have been getting by quite nicely with only 
13 digits for close to 30 years now.  There's been talk of extending 
this to something like 16 digits (still within the range of a long long) 
with the figuring that doing so will allow it to be used for something 
like 50 more years before it needs changing again (but so far, they've 
been talking about this for at least 5 years, and it doesn't seem to 
have happened yet -- anybody and everybody who cares is getting _lots_ 
of warning before it happens).

His code, however, fails under basically _all_ circumstances.  You can't 
take his algorithm and use it with ANY sort of GUI, or have it get input 
from an OCR program, or much of anything else without _totally_ 
rewriting absolutely EVERY bit of it.  IOW, the code is absolutely, 
positively, 100% useless except as an example, mostly of things to 
avoid!

> Right.  So let's try writing an actual program to solve the stated
> problem:

[ most code elided ... ]

>     printf("Enter ticket number: ");
>     fflush(stdout);
> 
>     /* remove leading spaces, if any */
>     while (isspace(c = getchar()) && c != '\n')
>       ;
> 
>     rem = 0;
>     for (ndigits = 0; isdigit(c); )
>     {
>         int nextc = getchar();

You seem to have entirely ignored every point I made in my previous 
post.  Here you're mixing the I/O into the algorithm proper, rendering 
the code useless.

>         if (c-'0' == rem)
>           printf("VALID\n");
>         else
>           printf("INVALID\n");

and here you're putting character literals directly into the printf's, 
substantially increasing the difficulty of localization.

> Conclusion: This is indeed a lengthier solution than the simple

Length is the least of its problems.  Its major problem is that it's 
BAD!  It's yet another example of things to avoid.
 
>       printf((number/10 % 7 == number % 10)? "VALID": "INVALID");

In this case, you've also put the "VALID" and "INVALID" directly into 
the printf, so this code is substantially worse than what I posted.
 
> I infer that the point of the problem is not to teach modularization.
> It's teaching extensibility and robustness -- the idea that you must
> really be prepared to handle "absurd" inputs, even if it makes the
> program logic a bit convoluted.

You can infer anything you want.  The fact is, that code should not 
_crash_ (or anything similar) on absurd inputs, but there's also no need 
to attempt to "properly" process bad input.

By contrast, there's no excuse whatsoever for asking students to produce 
code that's downright bad.
 
> I also note, in passing, that the OP's instructor may not have easy
> access to a C99 compiler on which to compile Jerry's "long long"
> solution.  The robust algorithm works in C89.

Mostly true (though using a double is still technically an option).
 
> In short, having written out the code for the two approaches, I see
> that Jerry's algorithm is less robust but much more conducive to
> clever compression.  Heck, it's five lines long!  But the recommended
> algorithm actually solves the problem as stated, with no assumptions
> about line length or anything; so it should get the higher marks.

As I've said all along: the algorithm gets high marks -- but the code 
should not.  Worse is the hint to write such code in the first place; it 
is more than sufficient grounds for the instructor to be fired 
immediately.

Now, since you seem to want a piece of code to put the thread to an end:

#if __STDC_VERSION__ >= 199901L
typedef bool boolean;
#else
typedef int boolean;
#endif

boolean check_ticket_number(int (*next)(void **), void *pos) {
    int count, c, last_c, rem = 0;

    while (isspace(c=next(&pos)) && c!='\n')
        ;

    for (last_c=c, count=0; isdigit(c=next(&pos)); count++, last_c=c )
        rem = (10*rem+(last_c-'0'))%7;

    return (count > 0) && (last_c-'0' == rem);
}

// What's above is real, usable code.  From here down is a minimal
// unit test.
#ifdef TEST
#include 

int get_a_character(void **x) {
    return getchar();
}
    
int main() {
    // cheat and use literals, but at least keep them separate:
    char prompt[] = "Please enter ticket number: ";
    char *validity[] = {"INVALID", "VALID"};
    boolean is_valid;

    printf("%s", prompt);
    
    is_valid = check_ticket_number(get_a_character, NULL);

    printf("%s\n", validity[(unsigned)is_valid]);
    return 0;
}
#endif

A few notes:

1) Since concern has been voiced over C89, I've allowed for it instead 
of using bool or _Bool directly (I believe _Bool was defined in C95 as 
well, but I don't remember for sure -- if it was, the '#if' should be:
#if __STDC_VERSION__ >= 199409L
instead).

2) Using a #define for the modulus doesn't really do a lot of good -- 
just for example, a modulus greater than 10 would require other changes. 
Most other choices less than 10 have simpler solutions.

3) Since some people seem to think it means something, I've attempted to 
follow the original "hint" as closely as possible, processing each 
character as it's "read".  At the same time, I want to maintain 
independence from a particular input model.

As is often the case, a level of indirection is useful here -- instead 
of using I/O directly, the algorithm is passed an input function that 
gets the next character to be processed.  To allow it to work in a 
variety of situations, the caller passes it a pointer, a pointer to 
which is then passed to the function that retrieves the next character 
-- for example, if you were processing input from a string, you could 
pass the pointer to the beginning of the string, and the callback 
function would increment the pointer with each iteration (note that the 
call-back function does not get the address of the original pointer, but 
the address of the parameter containing a copy of it).

4) IMO, this still isn't particularly wonderful: with a decent spec, the 
minimum and maximum length of the ticket number will be known and should 
be checked.  OTOH, at least it's not particularly terrible.

-- 
    Later,
    Jerry.

The universe is a figment of its own imagination.

In article , 
jcoffin@taeus.com says...

[ ... ]

> Now, since you seem to want a piece of code to put the thread to an end:
> 
> #if __STDC_VERSION__ >= 199901L

I'm not sure how, but a line got cut off there -- the first line should 
be:

#include 

My apologies.

-- 
    Later,
    Jerry.

The universe is a figment of its own imagination.

"Jerry Coffin"  wrote in message
news:MPG.19cd3afc373433d79896c3@news.west.earthlink.net...
> The algorithm itself
> (i.e. the piecewise calculation of the remainder) is pointless for the
> job at hand, but basically innocuous.

The job at hand is to complete the exercise as instructed, which was to
write a simple piece of code that uses getchar and implements the
one-character-at-a-time algorithm.

> If he'd implemented that algorithm in a function of its own that worked
> from data in a string (or whatever), then I'd really have no _major_
> problem with the code (it's still pointlessly complex, but to a degree
> that I agree is trivial).

I would consider taking marks off for this. It's not what the question
asked. In the case of the Computer Science exam it would be really stupid.
You have limited time to get through all the questions, and no student
deserving of a degree would be silly enough to waste any time on it. There's
nothing wrong with, indeed there is much merit in, a quick and dirty program
that gets the job done. If you are writing a library, then design it
carefully, but if you are writing a throwaway program for purely academic
purposes, then a quick, short, simple program that addresses the question
that was _asked_ is the best answer.

> > The recommended algorithm does *not* fail, not even on medium-sized
> > inputs that stop your algorithm dead.
>
> The algorithm he used doesn't fail, that's true.  The correct phrase for
> 20+ digit serial numbers for something like this is not "medium-sized"
> but, "stupidly ridiculous" or something on that order.

You are still placing undue, to say the least, emphasis on the irrelevant
setting of the question. The heart of the question is the algorithm, and any
student that can't see that and gets hung up on airline-ticket number
lengths deserves to fail. Nobody but computer programmers who work for
airlines, security services, and you, knows or cares about how many digits
are in an airline-ticket's number. I would take enormous pleasure in placing
a nice big zero on your exam paper, Lawrence.

Somebody has to write bignum libraries, division algorithms for
microprocessors and countless other algorithms that most of us take for
granted. Programming isn't as simple as using a language's built-in
facilities for everyone. Someone has to learn this stuff.

DW

In article , 
no.email@provided says...

[ ... ]

> I would consider taking marks off for this. It's not what the question
> asked. In the case of the Computer Science exam it would be really stupid.
> You have limited time to get through all the questions, and no student
> deserving of a degree would be silly enough to waste any time on it. There's
> nothing wrong with, indeed there is much merit in, a quick and dirty program
> that gets the job done.

This seems (to me) to clarify the situation: your either can't or won't 
see any point I'm trying to make.  IMO, your last sentence is just plain 
wrong: you say there's nothing wrong with a quick and dirty program that 
"gets the job done".  I, by contrast, say there's nothing right with it!

-- 
    Later,
    Jerry.

The universe is a figment of its own imagination.

On Sun, 14 Sep 2003 17:24:13 +0000, Jerry Coffin wrote:

> This seems (to me) to clarify the situation: your either can't or won't 
> see any point I'm trying to make.  IMO, your last sentence is just plain 
> wrong: you say there's nothing wrong with a quick and dirty program that 
> "gets the job done".  I, by contrast, say there's nothing right with it!

I could not disagree more with this. Know what gets the job done. Know
when to refactor. Don't overdesign.

M4

"Jerry Coffin"  wrote in message
news:MPG.19ce523d240785909896d4@news.west.earthlink.net...
> In article ,
> no.email@provided says...
>
> [ ... ]
>
> > I would consider taking marks off for this. It's not what the question
> > asked. In the case of the Computer Science exam it would be really
stupid.
> > You have limited time to get through all the questions, and no student
> > deserving of a degree would be silly enough to waste any time on it.
There's
> > nothing wrong with, indeed there is much merit in, a quick and dirty
program
> > that gets the job done.
>
> This seems (to me) to clarify the situation: your either can't or won't
> see any point I'm trying to make.  IMO, your last sentence is just plain
> wrong: you say there's nothing wrong with a quick and dirty program that
> "gets the job done".  I, by contrast, say there's nothing right with it!

Not even that it works? Not even that, by your own arguments in other posts,
you are highly unlikely to use it again? It would be the quintessential
waste of time to write a neat little program in which the algorithm is in a
reusable form, and then throw it away.

DW

In article , m@rtij.nl.removefromhere.invalid 
says...
> On Sun, 14 Sep 2003 17:24:13 +0000, Jerry Coffin wrote:
> 
> > This seems (to me) to clarify the situation: your either can't or won't 
> > see any point I'm trying to make.  IMO, your last sentence is just plain 
> > wrong: you say there's nothing wrong with a quick and dirty program that 
> > "gets the job done".  I, by contrast, say there's nothing right with it!
> 
> I could not disagree more with this. Know what gets the job done. Know
> when to refactor. Don't overdesign.

Of course overdesign (by definition) is a bad thing -- but Quick and 
dirty (also by definition) isn't good either. 

-- 
    Later,
    Jerry.

The universe is a figment of its own imagination.

In article , 
no.email@provided says...

[ ... ]

> Not even that it works? Not even that, by your own arguments in other posts,
> you are highly unlikely to use it again? It would be the quintessential
> waste of time to write a neat little program in which the algorithm is in a
> reusable form, and then throw it away.

If, as you've been emphasizing, this was being used as a question on a 
test, then even if IT is not intended for real use, it should be written 
as if it was -- bad design is something that hardly needs to be taught.

-- 
    Later,
    Jerry.

The universe is a figment of its own imagination.

"Jerry Coffin"  wrote in message
news:MPG.19ceb94927203d1e9896d6@news.west.earthlink.net...
> In article ,
> no.email@provided says...
>
> [ ... ]
>
> > Not even that it works? Not even that, by your own arguments in other
posts,
> > you are highly unlikely to use it again? It would be the quintessential
> > waste of time to write a neat little program in which the algorithm is
in a
> > reusable form, and then throw it away.
>
> If, as you've been emphasizing, this was being used as a question on a
> test, then even if IT is not intended for real use, it should be written
> as if it was -- bad design is something that hardly needs to be taught.

Oy, vay. This wandered off into fantasy land, as far as I'm concerned. It
reminds me of a puzzle that was published once:
If a race car goes around the track once at X miles per hour, how fast must
it travel on the second lap to make its average speed 1/2 the speed of its
first lap?
The answer, of course, is infinite speed, and therefore is an unreal problem
with no solution on this planet. But the discussion of it wandered off to
the question: Where is the racetrack?
The answer, of course, is Italy.
-- 
Gary