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.
Really, who couldn't love code like this:
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.
Also, as long as I am on a rant, Tetris is NOT NP-Hard, since the arrival of the blocks is probabilistic. It is only if the entire sequence of blocks is known in advance that it becomes NP-Hard. But that doesn't happen in actual play.
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.
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."
And here we get to the core of the problem. The presenter passes off information in an incorrect light, so only the audience that cares to accept it will continue accepting his later statements.
One of those statements is that code coverage tells you what to test. It doesn't. It tells you what you haven't bothered to test. What you need to test is driven by the user stories, customer requirements, and other bits of development documentation. Testers writing tests for permutations of non-important functionality are wasting company resources, especially if the important functionality was treated with a light "get the coverage up" style of testing.
A real test doesn't make the lines of code tested the goal. It makes corner cases, edge conditions, unexpected value selection, illegal parameter passing, etc. of the methods most likely to be used the point. Then, if there is extra time, it extends those tests to the next highest set of code, ordered by business value.
Stating that lines of code is the goal is a metric we have proven to be useless again and again (since the 1980's); so, where is the compelling evidence that it suddenly became valuable in the realm of unit testing? Not covering code with any tests is a red flag, if the code matters. Covering all code with the lightest battery of tests to get the line count up is money spent without much value.