4 ms·
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 com
by dinesh_babu 12y ago
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.,
- hueving 12y agoHow 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.
- Ygg2 12y agoBy requiring to terminate and return a result?
- minikomi 12y agoOf course. Just test to see if the program terminates or not.
- Ygg2 12y agoWhile 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.
- anirudh24seven 12y agoHow 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!"
- yen223 12y agowhile True: continue return solve(x)
- yodsanklai 12y agoIt reminds of an interview question. What is the slowest program (that still terminates) it is possible to write, and how would you do it?
- one-more-minute 12y agosleep(10000) return fizzbuzz(10)
- jskonhovd 12y agoThis reminds me of the busy beaver problem.