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

Groups > comp.programming > #10285

Re: Long winter evenings

Show all headers | View raw

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.

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