11
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Related: codegolf.meta.stackexchange.com/q/2280/45941 \$\endgroup\$ – Mego Oct 17 '19 at 20:42
  • 4
    \$\begingroup\$ Any answer that would be disqualified under this rule abuses native number types to trivialize the challenge, and is therefore already disgualified for violating standard loopholes. \$\endgroup\$ – pppery Oct 17 '19 at 20:57
  • 5
    \$\begingroup\$ @pppery I disagree. Some answers to the linked challenge don't abuse any number types, yet are unable to take inputs larger than \$2^{52} - 1\$ \$\endgroup\$ – caird coinheringaahing Oct 17 '19 at 21:00
  • \$\begingroup\$ How about "the maximum possible value the data type can hold"? \$\endgroup\$ – S.S. Anne Oct 19 '19 at 23:22
  • \$\begingroup\$ @JL2210 while that would work for most challenges, it doesn't cover challenges where the input may be greater than the maximum value for that data type, but should still theoretically work, regardless of the data type limitations \$\endgroup\$ – caird coinheringaahing Oct 20 '19 at 1:15
  • \$\begingroup\$ could you provide an example? \$\endgroup\$ – S.S. Anne Oct 20 '19 at 1:17
  • 1
    \$\begingroup\$ @JL2210 The linked question for example. With your wording, answers that only handle inputs up to \$2^32 - 1\$ for instance, and fail algorithmically for larger inputs would be perfectly acceptable, whereas with the current wording would not be \$\endgroup\$ – caird coinheringaahing Oct 20 '19 at 1:21
11
\$\begingroup\$

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

\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ "A float will always be 4 bytes" Actually, there are single floats (4-bytes), double floats (8 bytes), and apparently quadruple-precision floats too. One could conceivably think of hypothetical floats with more bytes and thus more precision \$\endgroup\$ – Luis Mendo Oct 18 '19 at 9:10
  • \$\begingroup\$ @LuisMendo Most languages implement their float type as single precision with other precisions being implemented in types like double. \$\endgroup\$ – Ad Hoc Garf Hunter Oct 18 '19 at 13:30
-1
\$\begingroup\$

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.
\$\endgroup\$
  • 1
    \$\begingroup\$ Maybe the downvote is for not directly answering the question, but this has my upvote because I see this as an XY question (the best solution is to step back and solve an underlying problem). Rather than trying to prove solutions work for arbitrary inputs, I'd rather see advice on how to choose a required range that will ensure that tailoring to just that range is not competitive with making a general solution. \$\endgroup\$ – trichoplax Oct 21 '19 at 21:19
  • 1
    \$\begingroup\$ (I also like challenges where only a small range of inputs has to work, so there is competition between general solutions and those that take advantage of the limited range, but where the challenge author wants to see only general solutions, setting the range deliberately too large to allow for taking advantage of it should ensure this) \$\endgroup\$ – trichoplax Oct 21 '19 at 21:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .