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

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