How can we clearly define "Must work for theoretically large values"?

Question

This doesn't seem immediately like an issue, but I've encountered it once in a challenge already, and recently again in a Sandboxed challenge, and is getting tiring to find the correct wording. For example, for this challenge, the biggest struggle in the Sandbox was making it clear that programs only had to work in theory for large inputs, and currently, the rules take up 2/3 bullet points just to define this. So:

What wording would be best to imply that your program must work theoretically for an arbitrarily large value, but it is acceptable from your program to fail due to practical limitations, such as memory or time?

For instance, if your algorithm for computing \$x^n\$ is sound, but fails for inputs \$x, n \ge 2^{52}\$, this is a perfectly valid answer, but if the program fails because of the algorithm behind it, it is not acceptable.

Answer 1

This is what I use in my challenges (with slightly different wordings):

The algorithm should theoretically work for arbitrarily large input values. In practice, it is acceptable if the program is limited by time, memory, or data-type size.

Small variations may be needed in each challenge:

• The arbitrarily large input values part may be tailored to the specific problem. For example,

  for arbitrarily large M and N

  if M and N are the variables used to refer to the input in the challenge text; or

  for any input size

  if the input is say a string that can be arbitrarily large in theory.

• The limited by part may also need tweaking. For example, for ASCII-art challenges that could in theory produce arbitrarily large output:

  limited by time, memory, data-type size, or screen size

Answer 2

I don't this cannot be defined in in an objective and satisfactory way.

We can talk about the behavior of a program as more memory is added to a computer, or more computing time is given. Since we actually contruct proofs about behavior based on the semantics of the language, this is entirely objective. (note that this is not computable, so it cannot be checked entirely autonomously by a computer, but it is still objective and a computer could verify a proof artifact.)

However when it comes to things like floating point precision regardless of how much memory you have a single precision float will always be 4 bytes. This is a semantic property of the language. And even variable length floating point numbers can never represent values beyond binary fractions. If we want to talk about the idealized version of the program we need to decide what semantic changes can be made.

Ideas of the algorithms at play behind any piece of code are inherently subjective. It is up to the humans involved to decide if a correct algorithm is actually represented or if something funny is going on.

If you don't want this subjectivity you can state the ranges required (possibly infinite) that must be supported in the challenge. But I do think that it is okay to let a little subjectivity in. I don't think it is likely that two people in good faith will disagree over the algorithm behind a piece of code. And at that point it is better to take it on a case by case basis instead of trying to create a general rule.

Answer 3

Simple answer: don't.

Computers are precise, discrete, and limited. Most programming languages are no different. You either have to limit defined behavior within the bounds of what can be done with the built-in numeric types of whatever language a solution happens to be written in (with a few patches for strange edge cases), or...

Set explicit precision/accuracy limits

Like the other answers have said, I don't think there's really a clean way to set "theoretical" boundaries without opening up gaping loopholes and weird edge cases. I think you're much better off setting explicit boundaries of defined behavior. Good challenges intentionally allow some undefined behavior; if it isn't really relevant to the challenge, let it be undefined.

In general, I would suggest avoiding challenges that require numbers larger than \$2^{52}\$ unless you have a really good reason (i.e. the challenge would be significantly altered by using smaller values e.g. generating RSA keys, SHA digests, etc...). Even better, avoid requiring anything bigger than the signed 32-bit integer range \$[-2^{31}, 2^{31} - 1]\$

Rather than working around theoretical limits, my challenges usually specify a range of values that must work to be considered valid solutions. Anything outside that precision and accuracy is undefined. Make limits tight enough that almost any programming language or architecture could solve the problem without excessive effort that's not really relevant to the challenge itself- I usually aim for what fits in an int16, a float32, or 4 decimal digits since these are common denominators to almost every language/architecture made since 1990.

Addendum: I think the way you handled it in the challenge you linked is fine, but these sorts of challenges that map numbers to something should be avoided if that something has more than \$2^{52}-1\$ possible states since that encloses a common denominator of distinct integer limits.

---

A few examples from my challenges:

From Heavy Box Stacking

• You must support weights up to 9,999 kg, at minimum.
• You must support up to 9,999 total boxes, at minimum.

From Compound Interest... With Wizard Money

• Input and output may be in any convenient format. You must take in Knuts, Sickles, Galleons, interest rate, and time. All but interest rate will be whole numbers. The interest rate is in increments of 0.125%. ...snip...
• Totals owed, up to 1,000 Galleons, should be accurate to within 1 Knut per year of interest when compared with arbitrary precision calculations.
• You may round down after each year of interest or only at the end. Reference calculations can take this into account for accuracy checks.

From Arrays Start at \$\pi\$

• Your result must have at least two decimal points of precision, be accurate to within 0.05, and support numbers up to 100 for this precision/accuracy. (single-precision floats are more than sufficient to meet this requirement)

From Intersection Point of Two Line Segments

• A minimum of 2 decimal places (or equivalent) precision is required.
• Final results should be accurate to within 0.01 when at a scale of -100 - +100. (32-bit floats will be more than accurate enough for this purpose)

From Length of the Longest Descent

• You may assume the height map is perfectly rectangular, is nonempty, and contains only positive integers in the signed 32-bit integer range.