Path: csiph.com!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail From: Ben Bacarisse Newsgroups: comp.programming Subject: Re: Long winter evenings Date: Tue, 05 Nov 2019 04:01:18 +0000 Organization: A noiseless patient Spider Lines: 129 Message-ID: <87wocfhsz5.fsf@bsb.me.uk> References: <87k18fjnd0.fsf@bsb.me.uk> <878sovjiq1.fsf@bsb.me.uk> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: reader02.eternal-september.org; posting-host="7691906a65019f668b19b4e9b8d0bca5"; logging-data="9739"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18uS5DKzzrm3dBVXE2kv0bu0YhrxXk6Yps=" Cancel-Lock: sha1:qAsS/NF2+69wXbNjzD2SG0JyHjk= sha1:R5HH3zcLrZLMF3PsMPlyUEyZeZE= X-BSB-Auth: 1.dce3ed34a04fc9be0585.20191105040118GMT.87wocfhsz5.fsf@bsb.me.uk Xref: csiph.com comp.programming:10285 Richard Heathfield writes: > On 04/11/2019 23:59, Ben Bacarisse wrote: >> Richard Heathfield writes: >> >>> On 04/11/2019 22:19, Ben Bacarisse wrote: >>>> Richard Heathfield writes: >>>> >>>>> I have just written a program in C, which for reasons that will remain >>>>> shrouded in the mists of wossname I wanted to be as short as >>>>> possible. The program solves a highly specific and relatively >>>>> antiquated problem. >>>>> >>>>> Now that the nights are drawing in, some of you might be at a loose >>>>> end and wish for something to help you pass the time. >>>>> >>>>> So here's the puzzle, which is in two parts: >>>>> >>>>> (1) What, *exactly*, does the program do? That is, what is the >>>>> significance of the printed result? >>>> >>>> These are rather odd questions. I know the answer you want, but if >>>> someone can find some other significance for the output, you'd have to >>>> accept that answer. I think you mean something along the lines of "what >>>> is the significance of the output that explains the method of >>>> calculation"? >>> >>> That's a better way of stating it, yes. >>> >>>> I won't say what I think you intend the answer to be, but I will say >>>> that the output is the first number in a infinite sequence that >>>> continues 18746, 34371, 49996, 65621, 81246, ... >>> >>> You are Martin Gardner And I Claim My Five Pounds. >>> >>> (In other words, absolutely right!) >>> >>>> >>>>> (2) Is there a way to make the program shorter, without compromising >>>>> its rigorous adherence to ISO C90? (See below.) >>>> >>>> Yes. Again, a bit odd. How much can we change? Preserving the logic >>>> and method of your calculation I can get the size down from 220 >>>> characters to 157, but I'm sure that is not the lowest. >>> >>> David Brown's reduction was very impressive. >> >> Yes, though mine (admittedly un-posted) was two characters shorter! But >> then his can be made a couple shorter two than what was posted. >> However, was that really the question? I thought it was a more general >> one.. >> >>>> Changing the logic, but sticking with the "purpose" (rather than just >>>> printing the answer), there are endless choices... For example: >>>> >>>> #include >>>> int n;int main(void){while((++n*1024l-8404)%15625);return!printf("%d\n",n);} >>>> >>>> (96 characters) >>> >>> Impressive, but I can't help thinking that it's something of a cheat, >>> since it assumes a considerable amount of knowledge not present in the >>> original problem statement (well, not quite original, but the >>> statement as modified by B.A.W.). >> >> (Who is B.A.W.?) > > Oh dear... Why oh dear? Now that I know who that is, I am confused by your statement. What is the original problem statement and how what it modified by Williams? >> Are we really talking about the same problem? > > ...I'm beginning to wonder. No, it seems it is indeed the same problem... >> I don't want to give too >> much away, but a bit of algebra shows that >> >> (4/5 * (4/5 * (4/5 * (4/5 * (4/5 * (n - 1) - 1) - 1) - 1) - 1)) / 5 >> = (1024 * n - 8404) / 15625 >> >> so why go to all the bother of your loops? > > I don't want to give too much away either now, but I can answer your > question easily enough: I scribbled out an easy couple of loops > because I didn't want to go to all the bother of doing a bit of > algebra. That answers the detailed question, but not the big one. You seemed to rule out (or were at the least unhappy with) a solution that used a different algorithm. Were you really only looking for minor textual changes that reduced the program size? >> By the way, if I got it, I only got it because I am familiar with this >> class of problems. Had I not been, I doubt I would be able to retro-fit >> a story to the calculation. > > There is very much a story to this - quite literally, in fact. Ben > Ames Williams wrote a short story for the 9 October 1926 edition of > the Saturday Evening Post, containing a puzzle that rapidly became > notorious, and which my program solves. I'm not familiar with his writing (not my kind of thing) so I would never have pulled that name up from the initials. The puzzle, on the other hand, is well known in mathematical/computing circles because it requires finding integer solutions which is usually not easy by hand but trivial by computer. The Williams version used coconuts (I now see), but there are other versions with different stories. I think I came across it as an inheritance problem -- dividing coins between children and a servant. >> There are a lot of micro-reductions like this, but changing the >> algorithm is the biggest win, and there I am left not knowing what will >> get past "the judges" (OK, past you!). > > Not a well-formed puzzle, then, so I'm glad I chose comp.programming > rather than rec.puzzles (where they prefer a little more rigour in > their puzzles). Did you intend to allow alternative algorithms, or was it just to be about code golf? -- Ben.