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: Mon, 04 Nov 2019 23:59:50 +0000 Organization: A noiseless patient Spider Lines: 136 Message-ID: <878sovjiq1.fsf@bsb.me.uk> References: <87k18fjnd0.fsf@bsb.me.uk> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: reader02.eternal-september.org; posting-host="7691906a65019f668b19b4e9b8d0bca5"; logging-data="12618"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18Ck753wfPxxth/6lkvh8zxe2W0Cab6mp0=" Cancel-Lock: sha1:1VkZaxxVySmUh5pLrsn8eUgGM+M= sha1:hCYVLigGMcbiWd0F5hEIl9y/yFc= X-BSB-Auth: 1.c0c1d4137832402d5c80.20191104235950GMT.878sovjiq1.fsf@bsb.me.uk Xref: csiph.com comp.programming:10283 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.?) Are we really talking about 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? 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. > But I love the abuse of return. Thanks! Me too. On the flip-side, I /don't/ like the abuse of file-scope definitions just to save =0, but them's the rules. >>> #include >>> int r(int*c){int f=0;if(*c%5==1)*c/= 5,*c*=4,f=1;return f;} >>> int t(int c){int f=1,i;for(i=0;f&&i<5;i++)f=r(&c);return f*!(c%5);} >>> int main(void){int n=0,d=0;while(!d)d=t(++n);printf("%d\n",n);return 0;} >>> >>> Four obvious shortenings are excluded: >>> A. Lose the space between "#include" and ""; >>> B. Lose the second and third newlines; >>> C. Lose "void"; >>> D. Lose "return 0;" >> >> (Everyone can answer yes to Q2 if they spot the space between /= and 5!) > > ...which I didn't. I got most of them out, but I obviously missed that one. > >>> If nobody gets it within a week or so, I'll post the solution to >>> (1). (If I could think of a solution to (2), I'd have written it that >>> way to start with!) >> >> I find that second part hard to believe. > > Alas, it's true. I may be smarter than some people think I am, but I'm > not as smart as some other people think I am. Not even "typedef int N;" to save 2 characters? Or take int f=1,i;for(i=0;f&&i<5;i++)f=r(&c);return f*!(c%5); flip the operands of * and you can remove a space int f=1,i;for(i=0;f&&i<5;i++)f=r(&c);return!(c%5)*f; Initialise i in declaration and you can remove i=0 from the for int f=1,i=0;for(;f&&i<5;i++)f=r(&c);return!(c%5)*f; Post increment i in i<5 and you can remove i++. The for(;E;) could then (for readability) become while(E) int f=1,i=0;while(f&&i++<5)f=r(&c);return!(c%5)*f; But why not count down to avoid the <5: int f=1,i=5;while(f&&i--)f=r(&c);return!(c%5)*f; 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!). Thanks for post, though. I'm quibbling, but it was entertaining. -- Ben.