Slashdot Mirror
Tetris Is Hard To Test
New submitter JackDW writes: Tetris is one of the best-known computer games ever made. It's easy to play but hard to master, and it's based on a NP-hard problem. But that's not all that's difficult about it. Though it's simple enough to be implemented in one line of BBC BASIC, it's complex enough to be really hard to thoroughly test.
It may seem like you can test everything in Tetris just by playing it for a few minutes, but this is very unlikely! As I explain in this article, the game is filled with special cases that rarely occur in normal play, and these can only be easily found with the help of a coverage tool.
It may seem like you can test everything in Tetris just by playing it for a few minutes, but this is very unlikely! As I explain in this article, the game is filled with special cases that rarely occur in normal play, and these can only be easily found with the help of a coverage tool.
In BBC BASIC, a colon is a statement terminator, much like a semicolon in languages with C-style syntax. The linked code is therefore not a one-liner by any meaningful definition of the term. One could replace all of the linefeeds in Linux kernel source with semicolons and other appropriate terminators. That wouldn't make the kernel a one-liner.
A BBC BASIC line is limited to 256 bytes, including the line number. It is impressive to squeeze the whole game into that space. There's also a 140-byte Javascript version, also very impressive, though it has fewer features and doesn't have all the block types.
You're an immobile computer, remember?
It's simple enough to implement in a shell script. At least three or four of us have done it over the years.
Check out my sci-fi/humor trilogy at PatriotsBooks.
Except that is not "one line". It is six lines. Any program can be a "one-liner" if there is no limit on the line length. Well, unless you writing it in Python.
The line length limit is 256 bytes, of course. And these hacks are the basic-equivalent of the C obfuscation contest.
As the authors say: "I'd like to think it is self documenting. The code speaks for itself; even if what it has to say is not very nice."
Socialism: a lie told by totalitarians and believed by fools.
In ASCII, but many BASICs will reduce keywords down to a single byte.
All those moments will be lost in time, like tears in rain.
I disagree.
For a stochastic process your greedy "take the option with the best chance" algorithm may work, it may fail completely, just depending on the random numbers. If you have an stochastic polynomial algorithm, you have a chance to get the same or better expectation value than your "optimize global then choose greedy" algorithm. Both approaches may win or fail, but in the deterministic game the np-complete version always wins, while the "shortcut" version cannot compete. In the stochastic version, the shortcut may be as good as the optimal solution, because you cannot get the global optimum anyway so choosing a local one may be a good choice.