Hacker News Reader

Comment by dinesh_babu | Hacker News Reader

There should be a round in Code Jam which asks people to write the slowest possible (and correct) solution for a problem. Would be interesting to see people coming up with algos that have ridiculously large complexity classes like O(n!), O(n!!) etc.,

View on HN

How do you eliminate stuff that is slow just for the sake of being slow? For example, a find_in_list function that iterates through the list N! times to 'protect against cosmic rays' or something along those lines.

By requiring to terminate and return a result?

Of course. Just test to see if the program terminates or not.

While halting problem can't be solved, you can solve the problem by saying all programs must terminate within 20min and program must scale with input length.

And/Or you can forbid sleep and similar nop functions.

And/Or you can sit down and analyze the code.

Truth be told, it makes for a very boring competition, but a very useful exercise.

How will a code-checking engine get past infinite loops?

while(earth_has_not_blown_up) {}

"Hey, I need the earth to blow up to solve this problem!"

you'll never get the answer. when earth blows up, you lose electricity

Just before the electricity goes, an electromagnetic disturbance or a shockwave causes the CPU to skip a few instructions, printing out the answer.

It reminds of an interview question. What is the slowest program (that still terminates) it is possible to write, and how would you do it?

    sleep(10000)
    return fizzbuzz(10)

This reminds me of the busy beaver problem.

  while True:
        continue

  return solve(x)

Reply on news.ycombinator.com