Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #10283

Re: Long winter evenings

Show all headers | View raw

Richard Heathfield <rjh@cpax.org.uk> writes:

> On 04/11/2019 22:19, Ben Bacarisse wrote:
>> Richard Heathfield <rjh@cpax.org.uk> 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 <stdio.h>
>> 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 <stdio.h>
>>> 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 "<stdio.h>";
>>> 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.

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Long winter evenings Richard Heathfield <rjh@cpax.org.uk> - 2019-11-04 17:37 +0000
  Re: Long winter evenings David Brown <david.brown@hesbynett.no> - 2019-11-04 22:39 +0100
    Re: Long winter evenings Richard Heathfield <rjh@cpax.org.uk> - 2019-11-04 21:51 +0000
      Re: Long winter evenings David Brown <david.brown@hesbynett.no> - 2019-11-05 10:42 +0100
    Re: Long winter evenings Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-04 22:24 +0000
  Re: Long winter evenings Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-04 22:19 +0000
    Re: Long winter evenings Richard Heathfield <rjh@cpax.org.uk> - 2019-11-04 22:30 +0000
      Re: Long winter evenings Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-04 23:59 +0000
        Re: Long winter evenings Richard Heathfield <rjh@cpax.org.uk> - 2019-11-05 01:03 +0000
          Re: Long winter evenings Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-05 04:01 +0000
            Re: Long winter evenings Richard Heathfield <rjh@cpax.org.uk> - 2019-11-05 07:42 +0000
  Re: Long winter evenings Melzzzzz <Melzzzzz@zzzzz.com> - 2019-11-04 23:00 +0000
  Re: Long winter evenings Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-06 04:58 -0800

csiph-web