On Wed, 10 Sep 2003 15:16:01 GMT, Tom Zych wrote:
>Bill Reed wrote:
>
>> I would never have come up with the expression in the while loop. And
>> after an hour I am giving up on discarding the last digit. I won't
>> figure this out either so I'll come back to it in the future. I'm
>> somewhat frustrated in that I can't find the solution in the text. No
>> reflection on the author, I'm sure it's me.
>
>Off the top of my head, I'd say that instead of immediately
>computing the remainder mod 7 of all digits read so far, we should
>instead save the current digit and compute the remainder of all
>previous digits. Then when you hit the newline, compare your running
>result to the last digit. Something like:
>
>mod7 = 0
>prev = 0
>while ((curr = read) != \n)
> curr -= '0' // convert from char to value
> mod7 = (mod7 * 10 + prev) % 7
> prev = curr
>check mod7 vs prev
You made it easy, but I still don't understand what's going on yet.
Give me some time and I'll follow it.
#include
int main()
{
int k = 0;
char c;
int p = 0;
printf("Enter ticket number: ");
while((c = getchar()) != '\n')
{
c -= '0';
k = (k * 10 + p) % 7;
p = c;
}
if ( k == p)
printf("\nVALID\n");
return 0;
}
Thanks again,
Bill
Oh, BTW.
kleenex.c:
Error E2209 kleenex.c 1: Unable to open include file 'kleenex'
*** 1 errors in Compile ***
Terminated with exit code 1
On Wed, 10 Sep 2003 15:40:50 +0000, Tom Zych wrote:
> Bill Reed wrote:
>
>> >#include
>>
>> In my condition you want me to go someplace else to find a kleenex?
>>
>> #include "kleenex.h"
>
> Two problems with this:
> 1. It only works if you already have a kleenex. <> sends you to a
> (reasonably accessible) place that should have one.
> 2. kleenex.h isn't a kleenex, just a description of what a kleenex
> does and how to use it. "kleenex" is the actual kleenex.
No, no, everybody knows you have to link against libkleenex.a (on
windows KLEENEX.LIB), however, that is OFF TOPIC for this group so cannot
be said here. :-)
M4
Bill Reed wrote:
> kleenex.c:
> Error E2209 kleenex.c 1: Unable to open include file 'kleenex'
> *** 1 errors in Compile ***
> Terminated with exit code 1
God...bless it!
(Stock phrase from a comic I like...)
--
Tom Zych
This email address will expire at some point to thwart spammers.
Permanent address: echo 'gbzmlpu@cbobk.pbz' | rot13
Bill Reed wrote:
> I am totally confused on this one. I've reviewed the material that
> pertains to this exercise a number of times. I don't even know where
> to start. The code below is basically my pathetic thoughts as
> expressed through the keyboard. If anyone can get me back on my feet I
> would be very grateful. Oh, BTW, does anyone have a kleenex?
>
>
Do you have to use getchar() for input? If not, here's a hint:
1. Enter the ticket number as a command line argument and convert it to
a number.
2. Get the last digit, the check digit, by division mod 10
3. Truncate the number, i.e. drop the least significant digit, with int
divsion by 10
4. Compare the truncated number % 7 to the last digit.
Hints are free, there is a charge for kleenex.
On Wed, 10 Sep 2003 09:43:29 -0400, Gary Labowitz wrote:
> "David White" wrote in message
> news:mxy7b.2728$d6.136244@nasal.pacific.net.au...
>> Jerry Coffin wrote in message
>> news:MPG.19c852f3e1f520949896a5@news.west.earthlink.net...
>> > In article , nomail@no.way
>> > says...
>> >
>> > [ ... ]
>> >
>> > > 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:
> <>
>> > IMO, this hint is highly suspect at best. First of all, it directly
>> > contradicts the requirements given above. The requirement says to do
>> > the division on the digits grouped together as a number, but the hint
>> > says to do the division one digit at a time -- the two will NOT give the
>> > same results.
>>
>> They will if done right.
>>
> Explain, please. If the modulo were 9 then the digits would calculate
> correctly one at a time.
> For 7 to be used it would require the number to in octal. Hmmm... would you
> consider it "right" to convert the decimal number to octal, do the one digit
> at a time modulo, and then check the digit?
> The statement of the problem doesn't say what to do if the check digit is 8
> or 9; presumable that can't happen!
Oh FCOL... just keep track of the remainder!
int ch;
int next;
int rem = 0;
ch = getchar();
while(isdigit(next = getchar())) {
rem *= 10;
rem += ch - '0';
rem %= 7;
ch = next;
}
puts(rem == ch - '0' ? "Valid ticket\n" ? "Invalid ticket\n");
It's just long division. Didn't everyone learn how to do this in fourth
grade?
Josh
On Wed, 10 Sep 2003 16:21:53 +0000, Jerry Coffin wrote:
> In article ,
> no@email.provided says...
>
> [ ... ]
>
>> You don't need to store any digits.
>
> Despite your cleverness, you've yet to show this.
OK, ok... you have to store two at a time.
>> > If so, it can be made to
>> > work, but this is about as _wrong_ of a way as is humanly possible --
>> > specifically, this is approximately the _slowest_ method known to man
>> > for carrying out this particular operation.
>>
>> It's a simple exercise that gave constraints on how to solve the problem.
>> Execution time is irrelevant.
>
> Says who?
Says the problem description.
> So far, you haven't solved the original problem at all.
If you're referring to his lack of accounting for the final character,
I've provided a solution, and his was capable after /trivial/ modification.
Oh, and your code is broken. You even said so when you posted it.
> Despite this,
> your code is longer and more complex than mine, which did solve the
> original problem.
For what definition of complex? Implementing your algorithm correctly
requires either a) external libraries or b) lots of non-trivial string
manipulation. His relies on a simple algorithm every nine-year-old knows.
Yours may (depending on the implementation of this library) run slightly
faster. His takes less memory.
And come on... faster? The code's speed is going to be limited by the I/O,
not the processing. Processing numbers one digit at a time isn't going to
significantly slow anything down. We can do a little test, if you like.
> By the time you modify your's so it does solve the
> real problem, it's likely to be at least half again as big, and maybe
> twice as big.
Your solution was four lines of code. My solution was about twice as long,
but only because I split up a mathematical expression into several
statements. My version could be five lines, easily. (In both cases, I did
not count declaration statements.)
> Question: does it provide any useful capabilities to compensate for
its
> extra complexity?
Again, what complexity?
> Answer: NO!
YES!
My version (which uses the same algorithm as David's) does not have any
artificial limits (such as the size of a long or the precision of a double).
IOW, mine is correct, and yours is not. Is not one line's worth of code
complexity a small price to pay for correctness?
> Bottom line: the algorithm you advocate is clever and I congratulate you
> for it. Unfortunately, for the job at hand it leads to complexity
> without utility.
Implement your algorithm without the above-mentioned artificial limits,
and then we'll compare the code complexity of the two.
Josh
Jerry Coffin wrote in message news:...
> In article ,
> no@email.provided says...
>
> [ ... ]
>
> > You don't need to store any digits.
>
> Despite your cleverness, you've yet to show this.
Each iteration of David's while loop reads a digit. The previously
read digit is not remembered. QED
> You're running into the same basic problem many people do when they
> start to learn a few cute algorithms: they want to apply those
> algorithms everywhere, whether they're applicable or not.
Didn't look that way to me.
> > The following test program finds the remainder of an integer of any length
> > divided by 7. For simplicity it does not check for non-digit characters or
> > for the last digit (as required by the exercise):
>
> So far, you haven't solved the original problem at all. Despite this,
> your code is longer and more complex than mine, which did solve the
> original problem. By the time you modify your's so it does solve the
> real problem, it's likely to be at least half again as big, and maybe
> twice as big.
Your solution can't cope if the number doesn't fit in the largest
integer type available. It's not unusual for this limit to be 32 bits
and the ticket number in the OP's example is longer than this. Is your
objection solely based on the fact that _if_ 64 bit integers are
available without resorting to a bignum class, David's algorithm is
redundant?
> Question: does it provide any useful capabilities to compensate for its
> extra complexity?
>
> Answer: NO!
Apart from being able to handle the input presented by the OP you
mean?
> Your original statement was wrong: it's not easier to process the input
> one digit at a time. While you've shown a way it COULD be done, the way
> you've shown clearly leads to MORE complex code.
Maybe not easier, just necessary.
> Bottom line: the algorithm you advocate is clever and I congratulate you
> for it. Unfortunately, for the job at hand it leads to complexity
> without utility.
After I read David's assertion that you don't need to store the digits
it took me well under a minute to work out how (I'm not a mathematical
genius and I'd never come across the algorithm before). That hardly
seems to qualify it as cute or clever. Pretty simple and effective
really.
GJD
Jerry Coffin wrote in message
news:MPG.19c8fdc6b6d426959896ad@news.west.earthlink.net...
> In article ,
> no@email.provided says...
>
> [ ... ]
>
> > You don't need to store any digits.
>
> Despite your cleverness, you've yet to show this.
Here is the conversation again, without the edits:
* * * * * *
> > > > IMO, this hint is highly suspect at best. First of all, it directly
> > > > contradicts the requirements given above. The requirement says to
do
> > > > the division on the digits grouped together as a number, but the
hint
> > > > says to do the division one digit at a time -- the two will NOT give
> the
> > > > same results.
> > >
> > > They will if done right.
> >
> > What exactly do you mean by "done right"? Are you talking about doing
> > basic long division on the stored digits?
>
> You don't need to store any digits.
>
* * * * * *
It seemed to me that you were referring only to the part of the exercise
requiring calculation of the remainder of the division. For that part, you
don't need to store any digits.
> > > If so, it can be made to
> > > work, but this is about as _wrong_ of a way as is humanly possible --
> > > specifically, this is approximately the _slowest_ method known to man
> > > for carrying out this particular operation.
> >
> > It's a simple exercise that gave constraints on how to solve the
problem.
> > Execution time is irrelevant.
>
> Says who?
Says the exercise. The requirement was to "Write a program that checks
whether or not an airline ticket number is valid:". It doesn't say to write
the fastest possible program. It doesn't say there are any bonus marks for
speed. It's just asking to get the job done.
> > It's an exericse - a problem for a student to solve. A bignum library
would
> > be completely inappropriate. A solution that satisfies the problem
> > description is ridiculously easy.
>
> Apparently it's not quite so easy as you imply, since your posted
> "solution" isn't even close to solving the problem.
It doesn't seem too far off to me. In any case, my comments and my code were
responding only to the division part of the problem, since that's what I
thought you were talking about.
> [ ... ]
>
> > That's four paragraphs now on a throwaway line I mentioned only as
> > indication of what the algorithm can handle if necessary.
>
> You're running into the same basic problem many people do when they
> start to learn a few cute algorithms: they want to apply those
> algorithms everywhere, whether they're applicable or not.
I came up with one algorithm that could be adapted for use in the presented
exercise. I haven't suggested using it anywhere else.
> > The following test program finds the remainder of an integer of any
length
> > divided by 7. For simplicity it does not check for non-digit characters
or
> > for the last digit (as required by the exercise):
>
> So far, you haven't solved the original problem at all.
I wasn't trying to. I was responding to your posts, which confined
themselves to discussion of the division part of the problem.
> Despite this,
> your code is longer and more complex than mine,
The problem does not specify a ticket-number length. Therefore, you can't
guarantee that your code will work. It also doesn't satisfy the hint given:
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
Even if you argue that this is just a hint, the exercise evidently wants the
student to solve the problem this way.
> which did solve the
> original problem. By the time you modify your's so it does solve the
> real problem, it's likely to be at least half again as big, and maybe
> twice as big.
>
> Question: does it provide any useful capabilities to compensate for its
> extra complexity?
>
> Answer: NO!
With the last-digit check included, it satisfies the exercise's
requirements, which is all I was trying to do.
> Your original statement was wrong: it's not easier to process the input
> one digit at a time. While you've shown a way it COULD be done, the way
> you've shown clearly leads to MORE complex code.
Are you sure that all airline tickets for which your code might be used will
fit into a long, or even a double? I'm not.
> Bottom line: the algorithm you advocate is clever and I congratulate you
> for it. Unfortunately, for the job at hand it leads to complexity
> without utility.
Here is the complete program. I still haven't checked for non-digit
characters, since the exercise confines the problem to numbers only. I've
also assumed that a ticket number cannot be zero digits long, which it
surely can't be.
#include
int main()
{
int k = 0;
int c2, c1 = getchar();
while((c2 = getchar()) != '\n')
{
k = (k*10 + (c1 - '0')) % 7;
c1 = c2;
}
printf("\nTicket is %s\n", (k == (c1 - '0')) ? "VALID" : "INVALID");
return 0;
}
DW
BR wrote:
> WARNING: "Kleenex" is somebody's intellectual property. Protect yourself
> from lawsuits.
What can I say but...SNORT ;)
--
Tom Zych
This email address will expire at some point to thwart spammers.
Permanent address: echo 'gbzmlpu@cbobk.pbz' | rot13
Mega Search
Sign Up 
