10
\$\begingroup\$

An awkward question comes up in code golf specs as to whether answer code is to be judged as running on a theoretical machine, an actual one with finite precision and memory, or somewhere in between. For example, see feersum's comments on Find the simplest value between two values that two posted answers arguably fail for large values due to limits of float representation.

For my question, I edited the spec afterwards to try to handwave away such limits, but I'd like to ask the community opinion on how and if to do this. It would also be nice to have a general agreement or standard options to avoid disagreements and avoid fiddly boilerplate in specs.

What are your thoughts on:

  • Should questions specify bounds and precisions for inputs?
  • Can and should questions handwave-away overflow and precision issues?
  • Is it OK to submit answers that "eventually" give the answer, like one that loops through all 2^64 machine-representable integers regardless of input size?
  • Should answers have to handle extreme cases like inputs 1 away from overflow?
  • Are answers responsible for machine-precision failures like 21.0/7.0>3.0?
  • What about stack-overflows for recursive code without tail-recursion?
\$\endgroup\$
  • 9
    \$\begingroup\$ There are too many questions there. If an answer addresses all of them then people may want to upvote three of the subanswers and downvote the other three. \$\endgroup\$ – Peter Taylor Oct 2 '14 at 6:53
  • \$\begingroup\$ This question start wrong, because "Theoretical machine" NOT EXIST. Exist one implementation, one compiler or better, one Os + compiler system. The problem it is the ambiguity in the answer. What it is easy to say for remove all these ambiguity: "the answer code function f has to return the right result in the input range for example 0..10000 for the online compiler in http:/someone.it in less of 1 minute for each number of input in its range." Otherwise this is the C answer to all question: main(){for(;;);} Because all you accept solution that never return one result. (except me) \$\endgroup\$ – RosLuP Oct 20 '17 at 21:21
12
\$\begingroup\$

I’d say that the asker is free to set (objective) rules and limits as they like. If any issues like overflow or precision are particularly relevant to the question, it would be good to specify what’s acceptable. Otherwise, I think it’s fine to ignore them.

Regardless, the solution should always produce the correct output for all test cases. As mentioned here, you shouldn’t post the answer until after it has successfully completed these. This is a nice way to weed out ridiculous or unverifiable answers.

But I think we should be lenient with extreme cases and slow solutions. There is often a tradeoff between length and efficiency when it comes to code golf, and every solution, language and system will have its limits (especially some of the more esoteric languages). So we shouldn’t rule out the clever recursive solution that has memory limitations, or the super-short FizzBuzz answer that overflows after 2^32, et cetera.

\$\endgroup\$
  • \$\begingroup\$ "we should be lenient with extreme cases and slow solutions" -- but enumerating all 2^64 integers is kinda overboard, isn't it? \$\endgroup\$ – John Dvorak Oct 5 '14 at 2:19
  • 2
    \$\begingroup\$ @JanDvorak Yeah, I don't think anyone will be waiting around for the test cases to pass with a solution like that. But if they do, I can't see any reason to stop them posting it. You don't need to upvote their answer of course. \$\endgroup\$ – grc Oct 5 '14 at 2:37
5
\$\begingroup\$

All of your questions seem to me like they're pretty much asking the same thing: "A computers can screw up, even if you programmed it correctly, because there are limitations on what you can do that stem from how the technology works. How (and should) we account for this?"

This answer is one suggestion that I think applies to every question you asked except 4. I'll answer that one separately.


Unless the question specifies otherwise, golfers should be allowed to assume exactly one of the following:

  • Their machine is a real, physical computer that runs code.

  • Their machine is theoretical. It lacks limitations of a real computer like stack overflows or lost precision. It runs your code flawlessly, even if no real computer in the universe ever could. It also runs it instantly.

Write a program that works by abusing integer overflows? Great! That's the first option.

Write a program that works by assuming that integers will never overflow, you can recurse as deep as you like, and precision is infinite? Great! That's the second.

There are so many great programs that have been written, but never run to completion, because the technology holds us back. At the same time, restrictions breed creativity, and great programs have been written abusing technological failure. I believe this proposal would allow both kinds of program to live in harmony on this site.

\$\endgroup\$
  • \$\begingroup\$ A computers can screw up, even if you programmed it correctly -- I would disagree. Most language documentations clearly state the language's limits. Expecting -- for example -- arbitrary precision is therefore unreasonable. \$\endgroup\$ – Jonathan Frech Aug 27 '18 at 14:13
-4
\$\begingroup\$

I'm just addressing question 4 (and to a lesser extent, 1) here. I gave my opinion about the others in my other answer.


Should answers have to handle extreme cases like inputs 1 away from overflow?

I don't think so. But how do we define "extreme"? That's exactly the issue. We can't exactly have rules about objective questions if we have the word "extreme" floating around.

If a question specifically includes input boundaries then your program must work for the every specified input. Note that saying "an integer" doesn't count as boundaries. It might technically mean -2^31 < n < 2^31-1 but that's usually not what people mean when they say it. If those are the bounds you want answers to work for, specifically say it.

If a question does not include boundaries, things get tricky. Here's my proposal. I think we, as a community, should decide on boundaries to default to for different archetypes of problems. It doesn't need to be comprehensive, but over time it could grow into something that could be relied on when the OP doesn't supply limits.

For example, something like this:

Problem Type: One integer input n. Guaranteed non-negative. More computationally intensive as n increases.

Default Boundaries: 0 < n < 21474

Or this:

Problem Type: Some number n of input strings.

Default Boundaries: 1 < n < 10, each string's length < 15

At the moment this is just an idea, I haven't even really fleshed it out. But does it seem feasible?

\$\endgroup\$
  • 8
    \$\begingroup\$ There's no realistic way that we can come up with some generic default limits which work for everything. And IMO we should push people to specify their questions properly (which includes specifying the range of input which needs to be handled, and ideally including test cases which cover all the corners of that range) rather than try to cover for them. (Before anyone else says anything: I don't see this as quite the same as standard loopholes). \$\endgroup\$ – Peter Taylor Oct 3 '14 at 15:35
  • 1
    \$\begingroup\$ My example: "find the sum of digits in the decimal expression of 2^n". Then n=21474 is way over the top for a naive implementation using 32-bit arithmetic (or even 64-bit arithmetic) but it works just fine for n=30. E \$\endgroup\$ – John Dvorak Oct 5 '14 at 2:25
  • 1
    \$\begingroup\$ Another classic: TSP: find the shortest route through 10 cities? Sure, just enumerate all paths. Shortest route through 30 cities? Let me learn how branch&bound works, or maaaybe a* the visited-set space will suffice. Route through 21474 cities? I'd throw a closest-first at it, and perhaps add random restart or 2-opt (crossing elimination) if the time constraints allow. Add a kD tree to speed up if necessary. \$\endgroup\$ – John Dvorak Oct 5 '14 at 2:30
-6
\$\begingroup\$

on the unambiguous answers

This question start wrong, because "Theoretical machine"

DOESN'T EXIST.

Exist one implementation, one compiler or better, one Os + compiler system + cpu and hardware. If one question request calculate in one programming language f(x) with x in [0, 8000] it has not significance until they specific, for example "in all more 2 widely used know compiler + Os in their default installation".

What it is easy to say for remove all ambiguity:
"the answer code function f has to return the right result
in the input range for example 0..10000 for the online compiler in   
http:/someone.it in less of 1 minute for each number of input
in its range."

Otherwise this is the C answer to all question:

main(){for(;;);}

Because all you accept solution that never return one result.

Op xnor is •

•What are your thoughts on: •Should questions specify bounds and precisions for inputs?

Yes and yes

•Can and should questions handwave-away overflow and precision issues?

No and no

•Is it OK to submit answers that "eventually" give the answer, like one that loops through all 2^64 machine-representable integers regardless of input size?

No the answer has to print its right result in the real machine, 
in the specified time the question assign to that calculus
for example in Tio web interface compilers. It can be 1 minute
if it is not specified (or one rationally good chose time)

•Should answers have to handle extreme cases like inputs 1 away from overflow?

I Don't understand 

•Are answers responsible for machine-precision failures like 21.0/7.0>3.0?

Yes yes and yes

•What about stack-overflows for recursive code without tail-recursion?

If stack end in the real machine of test in Tio, 
for some value of the range request in the question
the answer 
is invalid or not determinate 
\$\endgroup\$
  • \$\begingroup\$ So where I make wrong? Where would be my error? Only a downvote they all run away... \$\endgroup\$ – RosLuP Oct 21 '17 at 13:53
  • 4
    \$\begingroup\$ This is absolutely unintelligible gibberish. \$\endgroup\$ – Mego Oct 21 '17 at 17:25
  • 1
    \$\begingroup\$ @Mego I disagree. While probably due to translation issues not every sentence is clearly understandable, the main point seems pretty clear to me: xnor asks how programs should be judged and this answer states that they should not be treated as running on a theoretical unlimited machine, but instead the actual implementation should be taken into account. \$\endgroup\$ – Laikoni Oct 26 '17 at 20:09
  • 1
    \$\begingroup\$ The biggest error is the argument that accepting answers which will produce a correct solution after the heat death of the universe is equivalent to accepting answers which have an infinite loop and don't attempt to do any work. There is nothing reasonable about that argument. \$\endgroup\$ – Peter Taylor Nov 11 '17 at 9:17
  • \$\begingroup\$ @PeterTaylor if the function not return the result in the required time(1 second, 1 minutes, 1 year etc) that function it is the same of a void loop, for me and for each observer \$\endgroup\$ – RosLuP Nov 11 '17 at 9:27
  • \$\begingroup\$ Where did "required time" come from? That's not in the question or the answer. As it stands, the answer claims that (using linear temporal logic) ¬A ⇒ □¬A is a tautology, when in actual fact ¬A ∧ ⋄A is not a contradiction. \$\endgroup\$ – Peter Taylor Nov 11 '17 at 15:40
  • \$\begingroup\$ @PeterTaylor ¬A ⇒ ¬A is ok only if A is followed from axioms; ¬A /\ A can not be written even if A followed from axioms (because it means theory collapse) i not understand the connection with previous discussion... \$\endgroup\$ – RosLuP Nov 11 '17 at 16:10

You must log in to answer this question.

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