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

Groups > comp.programming > #10276 > unrolled thread

Long winter evenings

Back to article view | Back to comp.programming

Contents

  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

#10276 — Long winter evenings

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?

(2) Is there a way to make the program shorter, without compromising its 
rigorous adherence to ISO C90? (See below.)

#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;"

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!)

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [next] | [standalone]

#10277

On 04/11/2019 18:37, Richard Heathfield wrote:
> 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?

Apart from a "newbie" award at the IOCCC?  I don't know yet.

> 
> (2) Is there a way to make the program shorter, without compromising its 
> rigorous adherence to ISO C90? (See below.)
> 
> #include <stdio.h>
> int r(int*c){int f=0;if(*c%5==1)*c/= 5,*c*=4,f=1;return f;}

Surely "f" can be eliminated and replaced with a tertiary operator 
expression?

int r(int*c){return(*c%5==1)?*c/= 5,*c*=4,1:0;}

And there is a redundant space in "*c/= 5".

> int t(int c){int f=1,i;for(i=0;f&&i<5;i++)f=r(&c);return f*!(c%5);}

The call to "r" could then be inlined

> int main(void){int n=0,d=0;while(!d)d=t(++n);printf("%d\n",n);return 0;}

And the call to "t" could be inlined.

#include <stdio.h>
int main(void){int 
n=0,d=0,c,f,i;while(!d){++n;c=n,f=1;for(i=0;f&&i<5;i++)f=(c%5==1)?c/=5,c*=4,1:0;d=f*!(c%5);};printf("%d\n",n);return 
0;}

That's 160 characters, compared to the original 221.

> 
> 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;"

And I guess this is cheating too?

#include <stdio.h>
int main(void){printf("3121\n;return 0;}

> 
> 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 still don't know what it does...

[toc] | [prev] | [next] | [standalone]

#10278

On 04/11/2019 21:39, David Brown wrote:
> On 04/11/2019 18:37, Richard Heathfield wrote:
>> 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?
> 
> Apart from a "newbie" award at the IOCCC?  I don't know yet.

Oh, it wasn't intended to be obfuscated. (You can try for obfuscated if 
you like - I'm not a genius at it like some of the IOCCC guys, but when 
I'm trying I can generally put three or four levels of obfusc in there 
somewhere.)

> 
>>
>> (2) Is there a way to make the program shorter, without compromising 
>> its rigorous adherence to ISO C90? (See below.)
>>
>> #include <stdio.h>
>> int r(int*c){int f=0;if(*c%5==1)*c/= 5,*c*=4,f=1;return f;}
> 
> Surely "f" can be eliminated and replaced with a tertiary operator 
> expression?
> 
> int r(int*c){return(*c%5==1)?*c/= 5,*c*=4,1:0;}
> 
> And there is a redundant space in "*c/= 5".

Damn! I thought I'd caught them all.

> 
>> int t(int c){int f=1,i;for(i=0;f&&i<5;i++)f=r(&c);return f*!(c%5);}
> 
> The call to "r" could then be inlined
> 
>> int main(void){int n=0,d=0;while(!d)d=t(++n);printf("%d\n",n);return 0;}
> 
> And the call to "t" could be inlined.
> 
> #include <stdio.h>
> int main(void){int 
> n=0,d=0,c,f,i;while(!d){++n;c=n,f=1;for(i=0;f&&i<5;i++)f=(c%5==1)?c/=5,c*=4,1:0;d=f*!(c%5);};printf("%d\n",n);return 
> 0;}
> 
> That's 160 characters, compared to the original 221.

An astonishing reduction. The inlining was the big win - and, bizarrely, 
I moved those bits out to functions because doing so had the effect of 
dramatically *reducing* the size! So it's quite pleasing to see them 
moved back in again and gaining a further reduction in the process.

> And I guess this is cheating too?
> 
> #include <stdio.h>
> int main(void){printf("3121\n;return 0;}

Yes! That is quite definitely cheating! :-)

And I'm surprised at you: puts("3121") is a mere 75% of the size that 
printf("3121\n would be if you'd closed it off properly with ")

The problem with printing 3121 is that it removes the calculation, which 
is intrinsic to establishing what the program is actually for.

>> 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 still don't know what it does...

Phone home and tell them you'll be late.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#10287

On 04/11/2019 22:51, Richard Heathfield wrote:
> On 04/11/2019 21:39, David Brown wrote:
>> On 04/11/2019 18:37, Richard Heathfield wrote:
>>> 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?
>>
>> Apart from a "newbie" award at the IOCCC?  I don't know yet.
> 
> Oh, it wasn't intended to be obfuscated. (You can try for obfuscated if
> you like - I'm not a genius at it like some of the IOCCC guys, but when
> I'm trying I can generally put three or four levels of obfusc in there
> somewhere.)

The code is initially incomprehensible, but not really obfuscated -
that's why you only get a newbie award :-)

> 
>>
>>>
>>> (2) Is there a way to make the program shorter, without compromising
>>> its rigorous adherence to ISO C90? (See below.)
>>>
>>> #include <stdio.h>
>>> int r(int*c){int f=0;if(*c%5==1)*c/= 5,*c*=4,f=1;return f;}
>>
>> Surely "f" can be eliminated and replaced with a tertiary operator
>> expression?
>>
>> int r(int*c){return(*c%5==1)?*c/= 5,*c*=4,1:0;}
>>
>> And there is a redundant space in "*c/= 5".
> 
> Damn! I thought I'd caught them all.
> 
>>
>>> int t(int c){int f=1,i;for(i=0;f&&i<5;i++)f=r(&c);return f*!(c%5);}
>>
>> The call to "r" could then be inlined
>>
>>> int main(void){int n=0,d=0;while(!d)d=t(++n);printf("%d\n",n);return 0;}
>>
>> And the call to "t" could be inlined.
>>
>> #include <stdio.h>
>> int main(void){int
>> n=0,d=0,c,f,i;while(!d){++n;c=n,f=1;for(i=0;f&&i<5;i++)f=(c%5==1)?c/=5,c*=4,1:0;d=f*!(c%5);};printf("%d\n",n);return
>> 0;}
>>
>> That's 160 characters, compared to the original 221.
> 
> An astonishing reduction. The inlining was the big win - and, bizarrely,
> I moved those bits out to functions because doing so had the effect of
> dramatically *reducing* the size! So it's quite pleasing to see them
> moved back in again and gaining a further reduction in the process.
> 

Sometimes inlining is a win on size, sometimes not - it applies to
source code as much as compiler optimisations.

>> And I guess this is cheating too?
>>
>> #include <stdio.h>
>> int main(void){printf("3121\n;return 0;}
> 
> Yes! That is quite definitely cheating! :-)
> 
> And I'm surprised at you: puts("3121") is a mere 75% of the size that
> printf("3121\n would be if you'd closed it off properly with ")

Ah, you spotted my intentional mistake to check you were paying
attention, /and/ my exercise left for the reader :-)

> 
> The problem with printing 3121 is that it removes the calculation, which
> is intrinsic to establishing what the program is actually for.
> 
>>> 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 still don't know what it does...
> 
> Phone home and tell them you'll be late.
> 

[toc] | [prev] | [next] | [standalone]

#10280

David Brown <david.brown@hesbynett.no> writes:

> #include <stdio.h>
> int main(void){int n=0,d=0,c,f,i;while(!d){++n;c=n,f=1;for(i=0;f&&i<5;i++)f=(c%5==1)?c/=5,c*=4,1:0;d=f*!(c%5);};printf("%d\n",n);return 0;}

When reducing code, two standard tricks are to move declarations to file
scope so you don't need the zero initialisation, and return!printf(...);

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#10279

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"?

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, ...

> (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.

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)

> #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!)

> 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.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#10281

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.

> 
> 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.).

But I love the abuse of return.

> 
>> #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.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#10283

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.

[toc] | [prev] | [next] | [standalone]

#10284

On 04/11/2019 23:59, Ben Bacarisse wrote:
> 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.?)

Oh dear...

> 
> Are we really talking about the same problem?

...I'm beginning to wonder.

> 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.

> 
> 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.

>> 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.

I so don't like them that I forgot to think of them.

>>>> 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?

Blech. :-)

<much ingenuity snipped>

> 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).

> Thanks for post, though.  I'm quibbling, but it was entertaining.

You'll find the story (or, at least, the puzzle) in Wikipedia. I first 
came across it in a Martin Gardner book in the 1970s, and I was reminded 
of it by a (rather poorly executed) Youtube explanation that I happened 
to run into earlier today.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#10285

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

> On 04/11/2019 23:59, Ben Bacarisse wrote:
>> 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.?)
>
> 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.

[toc] | [prev] | [next] | [standalone]

#10286

On 05/11/2019 04:01, Ben Bacarisse wrote:

> Did you intend to allow alternative algorithms, or was it just to be
> about code golf?

The question never occurred to me.

The original was far more legible, but I wanted to squeeze it into a 
tweet (280 characters these days). I managed it without too much 
trouble, but then it idly occurred to me to wonder whether it could be 
squeezed still further without the pips actually falling out.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#10282

On 2019-11-04, Richard Heathfield <rjh@cpax.org.uk> wrote:
>
> (1) What, *exactly*, does the program do? That is, what is the 
> significance of the printed result?

It is difficult to figure out problem from program especially since it
is a number game. So: only way is to follow program and give formulae.
Some will recognize what it is, some will not.

>
>


-- 
press any key to continue or any other to quit...
U ničemu ja ne uživam kao u svom statusu INVALIDA -- Zli Zec
Svi smo svedoci - oko 3 godine intenzivne propagande je dovoljno da jedan narod poludi --  Zli Zec
Na divljem zapadu i nije bilo tako puno nasilja, upravo zato jer su svi 
bili naoruzani. -- Mladen Gogala

[toc] | [prev] | [next] | [standalone]

#10288

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?
>
> (2) Is there a way to make the program shorter, without compromising
> its rigorous adherence to ISO C90?  [...]

There is a simple way of shortening the program that applies to
all the variations I have seen posted.

Hint: I don't make the rules, I just follow them.

(In my own defense let me say I think this idea is easier to
figure out than question (1) above.)

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web