Re: Programming Challenge

From: Tim Rentsch (txr_at_alumnus.caltech.edu)
Date: 11/05/04 

Date: 04 Nov 2004 21:09:00 -0800

dj3vande@csclub.uwaterloo.ca (Dave Vandervies) writes:

> In article <kfnu0s68lji.fsf@alumnus.caltech.edu>,
> Tim Rentsch <txr@alumnus.caltech.edu> wrote:
> >dj3vande@csclub.uwaterloo.ca (Dave Vandervies) writes:
> >
> >> What's the shortest set of characters you can put between the "Do not
> >> modify..." lines to make this program print the correct answer to a
> >> problem of the form "Find the smallest nonnegative N such that N%m_i=r_i
> >> for all appropriate i" (where in this case r_i is 1 for m_i in {2,3,4,5,6}
> >> and r_6=0,m_6=7)?
> >
> >Excellent suggestion.
> >
> >Alas, the key problem that the output is a constant remains.
>
> That's why the problem statement says "problem of the form..." and not
> "this problem". I should probably have said added a requirement that
> calc() compute the answer rather than simply return it, but there's
> nothing wrong with the result being computed being constant.

If there's nothing wrong with the computed result being constant, the
shortest text is almost certainly 'i=%d;' where for %d is substituted
the numerical value of "Find the smallest nonnegative N such that
...". Programs that evaluate constants usually aren't very interesting
(IMO, anyway).

> (I had almost asked for the more general:
> int calc(int *m,int *r,int N)
> returning the smallest number R such that R%m[i]==r[i] for 0<=i<N, but
> decided that most of the interesting source-code-crunching opportunities
> come from having fixed N, m[], and r[].)

There's an old graduate level CS question that goes something like
this: Is it possible to write a program that tells you whether
Goldbach's Conjecture is true? (Note: Goldbach's Conjecture says
that every even (integer) number greater than 6 is the sum of two
primes.) The answer is, Yes There Is, and it is either the program
that prints "It's true" or the program that prints "It's false";
the point is that one of those two programs answers the question,
even though you might not know which program does.

Similarly, having the N, m[], and r[] be fixed might lead to the most
interesting mathematics, but the resulting program would still be just
setting 'i' to a constant (for 'int' that is any reasonably finite
number of bits, that is).

> >May I suggest this related problem instead:
> [snip]
> >What's the shortest set of characters you can put between the "Do not
> >modify..." lines to make this program print the correct answer to a
> >problem of the form "Find the smallest nonnegative N such that N%i=1
> >for all i with 2 <= i < n, and N%n=0".
>
> Do you have a good reason for degeneralizing it to m[i] being consecutive
> integers and r[i]==1 for all but the last m[i],

I was trying to follow the provisions of the original problem
statement. No other motivations than that.

> or is it just to avoid
> letting a sufficiently clever compiler from optimizing the (carefully
> crunched) source code away? If it's the latter, the whole point of this
> is that it's crunching the source code that's interesting, so your change
> is worse than pointless.

As long as the number of moduli computed is variable, I don't think it
makes much difference if the residues or residue classes requirements are
fixed or variable. If the interface requirement were as your generalized

    int calc(int *m,int *r,int N)

described above, it would probably lead to a program text that is
basically isomorphic to the program text were the m's and r's are
fixed as in the original problem statement.

What I was looking for was a simple clean problem statement that
addresses a class of input questions rather than just a single input
question instance. If there is only a single input instance, it's
more about the single input instance than about programming. It
just seems to me that in comp.programming more people would like
it to be about the programming.

======================================================================

Incidentally, here's a problem that's kind of related.

We have an integer number N with N between 50 and 500.
We have an integer number k with 1 <= k <= N, with the
property that

    sum(i) for 1 <= i < k == sum(j) for k < j <= N

Verbally, the natural numbers less than k add up to the natural
numbers greater than k and less than or equal to N. What is
k (or equivalently, N)?

Example: if N is 8, k is 6: 1 + 2 + 3 + 4 + 5 == 7 + 8.

The great mathematician Ramanujan heard this problem, and almost
immediately dictated a solution to the general solution (where the
bounds on N are not confined to 50 and 500 as above).

The shortest program to solve the specific problem here
(with 50 < N < 500) will just output a constant. :)