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.

Comments

One line?

[GrahamCox]

If anybody wrote code like that for me, they'd be made to sit on the naughty step and think very, very hard about what they'd done.

Re:One line?

[phantomfive]

You're no fun. If I worked for you, I'd quit as soon as possible.

Really, who couldn't love code like this:
0d=d:IFdVDUd:a=POINT(32*POS,31-VPOS<<5):RETURNELSEMODE9:GCOL-9:CLG:O FF:d=9:REPEATVDU30:REPEATGOSUBFALSE:IFPOS=28VDUPOS,15,VPOS,24;11,26:IF0E LSEIFa=0PRINT:UNTIL0ELSEUNTILVPOS=25:v=ABSRNDMOD7:i=0:VDU4895;3:REPEATm= 9-INKEY6MOD3:FORr=TRUETO1:t=rANDSGNt:IFt=rCOLOURv-15:VDUrEORm:i+=m=7AND9 -6*r:IF0ELSEFORn=0TO11:d=n/3OR2EORd:GOSUBFALSE:IF1<<(n+i)MOD12AND975AND& C2590EC/8^vVDU2080*ABSr;:t+=a:IF0ELSENEXT,:VDU20:UNTILt*LOGm:UNTILVPOS=3

Re:One line?

[ShanghaiBill]

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.

Re:One line?

[lgw]

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."

Re:One line?

[ShanghaiBill]

The line length limit is 256 bytes, of course.

The program is 430 bytes.

Re:One line?

[BlackHawk-666]

In ASCII, but many BASICs will reduce keywords down to a single byte.

Re:One line?

[LordKronos]

If anybody wrote code like that for me, they'd be made to sit on the naughty step and think very, very hard about what they'd done.

Unless, of course, you were developing for embedded hardware, where you are trying to do way too many things with way too few resources***. Then you'd give that programmer a promotion.

***Although those days are gradually coming to an end, as even the tiniest systems are getting more and more resources, and eventually they'll all join the rest of us, where readability, verifiability, and maintainability take top priority. But for now, they're not all quite there yet.

Re:One line?

[sexconker]

You're no fun. If I worked for you, I'd quit as soon as possible.

Really, who couldn't love code like this:

        0d=d:IFdVDUd:a=POINT(32*POS,31-VPOS<<5):RETURNELSEMODE9:GCOL-9:CLG:O
FF:d=9:REPEATVDU30:REPEATGOSUBFALSE:IFPOS=28VDUPOS,15,VPOS,24;11,26:IF0E
LSEIFa=0PRINT:UNTIL0ELSEUNTILVPOS=25:v=ABSRNDMOD7:i=0:VDU4895;3:REPEATm=
9-INKEY6MOD3:FORr=TRUETO1:t=rANDSGNt:IFt=rCOLOURv-15:VDUrEORm:i+=m=7AND9
-6*r:IF0ELSEFORn=0TO11:d=n/3OR2EORd:GOSUBFALSE:IF1<<(n+i)MOD12AND975AND&
C2590EC/8^vVDU2080*ABSr;:t+=a:IF0ELSENEXT,:VDU20:UNTILt*LOGm:UNTILVPOS=3

Anyone who had to read it, update it, or debug it?
Anyone who had to play the fucking game (it's full of game-breaking bugs - http://survex.com/~olly/rheoli... )?

Re:One line?

[phantomfive]

Whiner. Stop complaining or you'll have to write it all in binary! And don't you dare ask for more!

Re:One line?

[Stanza]

You've never written code in perl, have you?

Re:One line?

[Saysys]

80 characters: all done in COBOL

Re:One line?

[Dogtanian]

Note that this limit is on the tokenised form stored in memory, not the ASCII representation. This is why the code e.g. uses "GOSUB FALSE" rather than "GOSUB 0": the FALSE token is shorter than the encoding of a line number.

Programs for the unexpanded (1K) ZX81 frequently used that type of memory-saving. All numbers were stored as floating point and took up 5 bytes of memory, and saying (e.g.)

LET A = CODE("$")

(where CODE is the equivalent of the ASC function for the ZX81's non-ASCII character set and $ is character 13) instead of

LET A = 13

actually saved you memory.

Re:One line?

[Anonymous Coward]

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.

Re:One line?

[K. S. Kyosuke]

It would be probably shorter in Forth. ;-)

Re:One line?

[LordKronos]

Actually, it is written for resource efficiency...specifically program size, which uses memory. The goal was to write a 1 line program, and in BBC Basic, that meant they were limited to 256 characters. Yes, maybe they could have wrote things with more verbose naming and had it compile to the same size, but the particular goal there was to write something big with little code. I think they accomplished it fairly well, and probably 95% (at least) of programmers would be hard pressed to replicate their results. I suspect the people capable of accomplishing that would be capable of similar accomplishments on an embedded platform, given the necessary experience with the particular hardware.

Re:One line?

[Ed Avis]

It's analogous to testing itself. Testing cannot prove the absence of bugs, though it can find them. Similarly a coverage check cannot show that your test suite is adequate, but it can show it to be inadequate (or perhaps reveal dead code to prune). Nobody is claiming that coverage is the be all and end all of testing. That does not mean it is useless to measure it.

Re:One line?

[Richy_T]

BBC basic was interpreted, not compiled (though there may have been compilers written for it since).

Re:One line?

[Sebastopol]

I'd hire the person in the blink of an eye. That kind of discipline is sorely missing among younger programmers these days.

Re:One line?

[LordKronos]

BBC basic was interpreted, not compiled (though there may have been compilers written for it since).

It was my original instinct to say the same (since nearly all basic languages are), but I looked it up on wikipedia before posting and found that there was indeed a compiler for it:

http://en.wikipedia.org/wiki/B...

A Compiler for BBC BASIC V was produced by Paul Fellows, team leader of the Arthur OS development, and published initially by DABS Press.[citation needed] This was able to implement almost all of the language, with the obvious exception of the EVAL function – which inevitably required run-time programmatic interpretation. As evidence of its completeness, it was able to support in-line assembler syntax. The compiler itself was written in BBC BASIC. The compiler (running under the interpreter in the early development stages) was able to compile itself, and versions that were distributed were self-compiled object code.[original research?] Many applications initially written to run under the interpreter benefitted from the performance boost that this gave, putting BBC BASIC on a par with other languages for serious application development.

There's not a whole lot of info about it on wikipedia, and it doesn't even say when it was written (and there are no citations), so I have no idea if it was something recent or very old.

Blockheads

[penguinoid]

I'm sure there is a joke in there somewhere.

Re:Blockheads

[milkmage]

9-INKEY6MOD3:FORr=TRUETO1 --- lol

Re:Blockheads

[dj_nme]

The joke is the "Tetris in one line of BBC Basic" is a lie, because it causes an error message "line too long, truncated" and then on the pop-up where the program should be running has the error "no such variable". Perhaps false claims shouldn't be made for something which can be tested very easily?

Re: Blockheads

[iapetus]

RTFM.

in Soviet Russia

[Trepidity]

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.

Tetris doesn't need coverage tool to test you. Everything about you.

Code-coverage tool is crutch for weak capitalist engineer. Tetris is Soviet technology, forged by people's will.

Re:in Soviet Russia

[flargleblarg]

Tetris doesn't need coverage tool to test you. Everything about you.

So what you're saying is...

In Soviet Russia, Tetris game tests you!

Nice advertisement

[Anonymous Coward]

From a company promoting automated WCET analysis. Hah!

Re:Nice advertisement

[phantomfive]

Normal users don't test all cases of a game.

Maybe not, but as soon as you tell yourself, "I don't need to test this code, a normal user will never get to it;" you can be certain that after saying that, a user will find a way to break it. The Gods of Eternity will laugh at you.

Re:Nice advertisement

[Mr. Freeman]

The article didn't even describe the special cases that Tetris is allegedly "filled" with. They just mentioned a single, obvious, non-special case that is encountered in almost every game.

This is just more marketing spam that's found its way onto Slashdot.

Re:Nice advertisement

[JackDW]

Submitter here. It's "marketing spam" in the sense that it's based on something I did at work. I don't see why this is a problem. Many articles linked from this site involve something that someone did at work.

I thought it was interesting that, though this is a really simple game, you can't test it effectively just by playing it. You have to deliberately seek out all of special cases. That's a fact about virtually all software, but it's not an intuitive one, and that's what the article is about.

Perl-standard line length

[Sigma 7]

Though it's simple enough to be implemented in one line of BBC BASIC

Any language that doesn't require carriage return + linefeed can do anything in one line.

And Basic comes with a ton of library fuctions that makes things easier to do. No need to initialize memory, dispaly, setup graphic or keyboard interrupts, etc.

Re:Perl-standard line length

[phantomfive]

In this case, a line is no longer than 255 characters. If you never used one of the early toy computers, you won't remember it, but each programming line was typically limited to a certain length.

And let's not even get started talking about line numbers.

Re:Perl-standard line length

[JackDW]

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.

Re:Perl-standard line length

[brantondaveperson]

Well - it does use quite a nifty trick to implement a subroutine, given that you can only GOSUB a line number, and there's only one line number.

Re:Perl-standard line length

[jopsen]

Any language that doesn't require carriage return + linefeed can do anything in one line.

Exactly... In fact there is a lot of very complicated one-line javascript libraries just download one of those .min.js files :)
br Seriously, a readable 30 line implementation would have been more impressive...

Re:Perl-standard line length

[darkain]

Maybe you'd prefer a binary version at 256 bytes?

http://256bytes.untergrund.net...

Re: Perl-standard line length

[ArcadeMan]

This is no time to read or to drink, sir.

Re:Perl-standard line length

[Dogtanian]

I've seen C64 basic. One line of code can be two lines on the screen. Maybe more than two lines when you realize you can compress names like POKE into the two-character acronym (second being shifted) and using it in list would happily decompress to something that can't be typed within the 2 screen-line limit.

BASIC on the Atari 800 and its descendants exhibited the same behaviour with respect to abbreviations and its three-screen-line limit on a single BASIC line.

Atari User magazine had a feature called "five liners" for very short programs. Many of the more elaborate ones pushed this as far as it would go by *requiring* them to be entered using abbreviations in order to fit this three-screen-line limit. IIRC most of these would be expanded upon processing, often taking them over the limit.

replacing line feeds with terminators is not a 1-l

[raymorris]

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.

One Line

[Tablizer]

Though it's simple enough to be implemented in one line of BBC BASIC

Perlers are so jealous right now; they need 2 lines.

Re:One Line

[dgatwood]

It's simple enough to implement in a shell script. At least three or four of us have done it over the years.

Re:One Line

[Tablizer]

I guess this aint the kind of joke that works on Slashdot

Re:One Line

[MadTinfoilHatter]

It's simple enough to implement in a shell script. At least three or four of us have done it over the years.

True. Here is one example: http://miria.homelinuxserver.o...

Re:replacing line feeds with terminators is not a

[Nyder]

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.

If it's a one-line program, why is it more than one line?

A line of code is not the same as a line on a screen. The program won't fit on one line on most screens, but it will fit on one line of BBC BASIC, which fortunately has a well defined, but short maximum length of 256 characters. The whole program is 257 bytes as there is an extra byte to mark the end of the program.

from: http://survex.com/~olly/rheoli...

perhaps. I wonder if it NP-hard

[raymorris]

The fact that probability is involved doesn't mean there's not an optimal strategy, of course, where optimal is defined as "highest expected score" (score X probability). So figuring out an optimal strategy is a hard problem - how hard is it?

If the probability of a certain series of shapes coming next were 100%, we'd have an NP-hard problem, agreed? Does another probability make it easier or harder? Harder, if anything. That's provable because the probability version can be solved by solving each of the potential series as if each were known. What's harder than NP-hard? It may well still be NP-hard. It can't be of any more solvable complexity class.

Re:perhaps. I wonder if it NP-hard

[phantomfive]

What's harder than NP-hard?

Intractable.

Re:perhaps. I wonder if it NP-hard

[allo]

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.

Infomercial for a code coverage tool?

[140Mandak262Jamuna]

Code coverage tool seems like a good idea from some theoretical stand point. But in practice number of code paths multiply rapidly and getting all the paths executed would involve unreasonably long time. Further rarely called procedures or rarely executed is just one class of problems. There are functions that will execute million times correctly and misbehave once in a million or once in a billion calls. For example I came across a bug in something so simple like calculating the centroid of a triangle. Absurdly simply code that adds the x, y, z coordinates of the vertices and divides by 3. That is all. In dealing with output of some CAD software, when the smallest angle of the triangle fell below 1.0e-08 radians, it returned a wrong value of the centroid. Typical sanity checks based on mathematical facts, like centroid of a triangle can never be outside the triangle will not work. The code that checks inside-or-outside of triangle is far more complex than the centroid code. The floating point truncation errors make this kind of sanity check useless. You can't even plot it on the screen and look at the centroid. OpenGL is implemented in single precision.

So at some point you reach a point of diminishing returns. It might not be worth making sure every line got tested when there are procedures that have a bug that happens in one in a billion calls. My philosophy is, "Perfection is the goal. Doing better than the last release is the shipping criterion".

Re:Infomercial for a code coverage tool?

[onepoint]

While everything you just said makes sense, nothing beats good testing, and like any tool, this is another one. All that code coverage does is let you focus on what has not been touched, then you'll be able to test it somehow. Also, I could create a similar problem, just like the one you wrote about above and would happen more often. I'm thinking of traffic management in the air. Or maybe even traffic management on land.

Re:Infomercial for a code coverage tool?

[NormalVisual]

Just writing a function that properly calculates whether the current year is a leap year would fall into that category as well, since there are exceptions for years divisible by 100 and 400. Thorough testing would be the only way to catch problems within the programmer's lifetime. However, this scenario also validates the parent poster's point - there are times when "good enough" is perfectly acceptable even though there may be logical flaws within the code. Simply doing a mod 4 on the year will likely be fine for the entire span of the program's useful life.

Re:Infomercial for a code coverage tool?

[Anonymous Brave Guy]

All that code coverage does is let you focus on what has not been touched, then you'll be able to test it somehow.

The trouble is that what you really need to test isn't how much coverage of the code you've got, but how much coverage of the possible input space. More specifically, you ideally want to know that each distinct combination of inputs that will cause a different type of behaviour in the code has been considered.

Of course, this is typically an implausibly difficult problem to solve in real world projects. To see why, consider that this article proudly claimed that finding the special case of clearing 4 lines together twice in a row was easy with their tool, and it also said that there were similar combo special cases for 3, 2 or 1 lines, but it conveniently overlooked the possibility of code that ran in all four cases and took the number of lines as a parameter. Testing for any one of those four cases would count as coverage with most tools, but wouldn't guard against implicit conditionals like overflow/underflow that might be relevant to some cases but not others, nor for behaviours that arose only with certain combinations of multiple explicit conditions.

Coverage tools are useful up to a point, but not nearly the silver bullets that these kinds of article suggest.

Re:Infomercial for a code coverage tool?

[itzly]

Also, it isn't sufficient to know that the execution has gone through the "4 lines cleared twice in a row" code, but somebody should then also watch the score to see if it was actually updated by the correct amount.

Re:Infomercial for a code coverage tool?

[JackDW]

You're right, this sort of testing should really be about covering the range of possible inputs. But that is typically impossible. There are too many possible scenarios. You need a practical substitute.

I agree that statement coverage is quite crude, it tells you very little about the data being processed. There is more detailed information being produced here - "MC/DC coverage" - which does tell you whether conditional statements have been thoroughly exercised, because each possible reason for the "true" or "false" branch of the conditional has been seen during the test. But even with that, it is no silver bullet, and you can certainly write programs that get 100% coverage on all the metrics, and are still full of bugs.

It is, however, better to have this information than not have it at all. And coverage tools are very practical in real-world situations, particularly those involving testing safety-critical code. They provide evidence that the tests have tested everything that they claim to have tested.

Re: Infomercial for a code coverage tool?

[fatgraham]

Find better programmers, pay them better, manage the project better to allow time to fix bugs after they've run through QA.

Re:Infomercial for a code coverage tool?

[Anonymous Brave Guy]

FWIW, I agree with almost everything you wrote. I have nothing against coverage tools, and I use them occasionally myself. I just think it's important to have a realistic view of the benefits you do and don't receive.

The only thing I disagree with is your final paragraph, where you talk about safety-critical code. If you really were working on systems where a failure would have catastrophic consequences, I would hope you had a QA process a lot more sophisticated than running a test suite and this kind of coverage tool to check for problems! This is precisely because coverage tools don't really provide solid evidence about what has been tested. Like an automated unit test suite, they only provide a rough guide, which can certainly be useful but is far from a robust guarantee of anything.

I would therefore argue that these tools are much more applicable, in the real world, to projects that are not safety critical. Most projects can't accept the overheads that are reasonable for those more demanding environments, but the developers might still want to do the best they can under the more usual time pressures and resource constraints for commercial or FOSS projects.

Re:Infomercial for a code coverage tool?

[onepoint]

You know, I like what you wrote since it brought up a safety issue once I read about. It was about a plane making a crash landing, and the pilots heard a "GONG" sound, they were never trained for that sound, but they were able to find it in the manual. It seemed that that gong sound was the sound of everything is failing including redundancy. Now that gong sound is in all the simulations.

So I look at it as a tool, a tool to test all the code and see if it works in general for most situations, then test again to see if it works correctly with other applications by trial and error.

Re: Infomercial for a code coverage tool?

[NormalVisual]

Sure, if you're talking about code your not-yet-born grandchild will be delivering.

Re:Infomercial for a code coverage tool?

[JackDW]

If you really were working on systems where a failure would have catastrophic consequences, I would hope you had a QA process a lot more sophisticated than running a test suite and this kind of coverage tool to check for problems!

Oh, certainly! The good news here is that the avionics industry knows this, and in any case, the FAA won't let them cut corners. I don't know exactly how the industry uses our tools, but it's typically in conjunction with lots of manual testing, with the coverage tool capturing data as human testers run through test scripts.

And you're right, non-safety critical projects can benefit from it. For any large project, it really isn't an expensive part of the development process, and it can be very revealing. The techniques we use have a low overhead in terms of memory and CPU time, so they're good for both embedded systems and high-performance desktop/server software. An "instrumented" build for coverage is not that different to a regular debug build: a bit slower, a bit larger, but with lots of helpful stuff included. But perhaps I am wandering into "infomercial" territory again... :)

Nonsense -- make your own test suite

[rs1n]

Why would you only test your code via normal use? Why wouldn't you just create a test suite that actually tests all the scenarios? In the case of tetris, you can simply force a sequence of pieces that will enable you to reach the scenarios described in the article. Or you can even start the game with a pre-made board.

Has slashdot really become a means for tech companies to inject free advertisement by a simple blog post made to look like real journalism?

Re:Nonsense -- make your own test suite

[NormalVisual]

Why wouldn't you just create a test suite that actually tests all the scenarios?

Defining all of the possible scenarios is often a lot harder than it looks. There aren't too many UI coders out there that haven't said "yeah, we need to fix it, but what made the user decide to do that?" at one time or another.

Re:Nonsense -- make your own test suite

[chrysrobyn]

Has slashdot really become a means for tech companies to inject free advertisement by a simple blog post made to look like real journalism?

Why, did you not get enough :CueCats and i-Openers? This is hardly the first Slashvertisement, and it's the only one from this company that I've seen.

Re:Nonsense -- make your own test suite

[JackDW]

Thing is, you need both your own test suite and a coverage test tool. The two work together. The coverage tool tells you if your tests are incomplete, helping you to fix them.

If I were actually testing Tetris I would definitely do it the way you suggest: a pre-arranged sequence of blocks and a pre-programmed series of moves. I'd run the game with that sequence, then look at the coverage data to see if I needed to add anything. Some of the process can be automated, but the test cases themselves have to be made by hand.

Re:Nonsense -- make your own test suite

[s0nicfreak]

Because it's much cheaper to give the game to some voluntary beta testers (or nowadays... early buyers) to do some normal use testing than to pay a programmer to force a sequence of pieces or premake a board?

Beware coverage tools

[Anonymous Coward]

The article makes it sound like coverage tools help! If you're not familiar with them, they tell you which bits of code have been run, not how many of the N cases of that code have been executed.

So the code might fail with a particular combination of inputs, but the coverage tool is more interested in which bits of the code have been execute.

It's one of these tools and metrics that non-technical managers use to substitute for an ability to read code.

Re:Beware coverage tools

[NormalVisual]

So the code might fail with a particular combination of inputs, but the coverage tool is more interested in which bits of the code have been execute.

This is quite true, but at least it's something that can help. Programmers already make enough mistakes, so any help is welcome. Whether that help is worth the price tag in dollars and time has to be determined on an individual case by case basis.

Re:Beware coverage tools

[Anonymous Coward]

All of my best testers have been people who use the product to do the job it was intended for, and that means they're testing the same common pieces of code through every use case. The coverage tool is simply the wrong metric, it assumes one use-case = one piece of code, and treats code as 'covered' if its been run because it doesn't know about the use cases.

Worse, the testers end up trying to run obscure code simply to get the right test metric. So all the belt-and-braces checks I put in to prevent future developers sending bad parameters, all of that code comes back as a fail/ unneeded code, simply because its never needed.... yet.

So I repeat my warning to clueless managers, beware coverage tools, they mislead.

Re:Beware coverage tools

[hraponssi]

A code coverage tool is useful to find the parts of the code not tested at all. As long as you remember that, it is a great tool (assuming it is free and easy to deploy). If you think achieving enough code coverage alone is all you need then you lose. But even in that case if you did not have the code coverage tool, you would probably just test even less.

Once sufficient code coverage is achieved, I would look at the interesting cases and if necessary just build a simple test generator to generate tests and track the achieved coverage in terms of combinations of these. Even here the code coverage is useful to have to show you someone implemented something "interesting" that you are never testing since it is undocumented..

So. Not the perfect tool but can be useful.

Re:Beware coverage tools

[Sebastopol]

Validation is way more important than writing code. Coding is grunt work that literally anyone can do. There is a huge demand for programmers, and very few are "good" programmers, 90% are just grunts who will never get any better, and that's life due to demand. So you need validation. I wrote and managed RTL development for 15 years at Intel and code coverage is simply mission critical. No other way around it.

If you think being able to "read code" is enough to see all the corner cases, you're either very young, or one of the aforementioned grunts.

Re:Beware coverage tools

[ianb1469]

Of course you cannot test all paths through the code, so one of the ways to have safety-critical code is to make sure that it is well tested. And that's where coverage comes in.

The way that it works for DO-178B (guidelines for airborne software) is that you do requirements-based implementation and testing. That is, you write your code AND tests from a requirements specification. Therefore, there should be NO untested code, otherwise you have either written something that's not in the requirements, or your tests are not adequately testing your requirements.

In other words, coverage is about making sure your tests are complete (not about if your software works).

This is how it's worked for a long time in aerospace, and there aren't many planes falling out the sky because of software bugs (although requirements specification issues, perhaps!)

The tetris thing does show MC/DC test coverage, which is required for DO-178B level A (the most critical software) and now in automotive software because of ISO 26262. MC/DC is basically making sure that as well as testing every statement, you also make sure that each part of a decision independently affects the branch outcome. That's been shown to catch quite a few holes in test suites.

Re:replacing line feeds with terminators is not a

[NormalVisual]

46 lines (statements), actually. There's a linked page where he blows it out into a readable form and explains how it works in depth.

Re:replacing line feeds with terminators is not a

[phantomfive]

In BBC Basic, a single line is 255 characters. RTFA.

piece of cake

[amoeba1911]

It's a piece of cake... http://bitbar.org/blocks/cake.html?fields=9

How I know it's an ad

[rebelwarlock]

Just one line in the summary gives it away:

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.

This doesn't seem like news to me! I'm shocked and appalled!

C64 BASIC version within a screen of code

[Neo-Rio-101]

It's a 15 liner.
Note that the {CBM-x} represents the graphic on that particular key (press the c= key and the letter to produce it)

1 a$="efijefijefijefijbfjnhijkbfjnhijkijfgaefjijfgaefjefjkiefbefjkiefbbfjidefj"
2 a$=a$+"abeieijkaeijijkgabfjiefgehijebfj@abe@dhe":o=207:dime(o):forx=0to111
3 print," {CBM-M}"," {CBM-G}":p=asc(mid$(a$,x+1)):e(x)=(pand3)+(pand12)*10:next:m=2024
4 print," {CBM-T}{CBM-T}{CBM-T}{CBM-T}{CBM-T}{CBM-T}{CBM-T}{CBM-T}{CBM-T}{CBM-T}":gosub6:goto7
5 pokei+e(r),c:pokei+e(r+1),c:pokei+e(r+2),c:pokei+e(r+3),c:c=160:r$="d":return
6 i=1152:r=h:c=32:gosub5:j=int(rnd(0)*7)*16:r=j:gosub5:r=h:h=j:i=i+9:return
7 gosub6:w=i:t=i:g=r:k=240:l=1278
8 gosub15:c=32:gosub5:r=-r*b-g*notb:g=r
9 i=w:w=i+40:gosub5:gosub15:ifbthen12
10 getk$:g=randkor((r-4*(k$="s"))and15)
11 t=w:w=w+(k$=l$)-(k$=r$):l=l+40:goto8
12 c=o:gosub5:m=m-(l0:w=-t*b-w*notb:l$="a":return

erratum: missing lines

[Neo-Rio-101]

13 fors=ltol+(m-160-l)*qstep-1:pokes+11,peek(s-29):next:y=y-q:m=m+q*40:z=z+q
14 l=l+40*not-q:next:print"{home}";z:goto7
15 b=0:forx=0to3:b=bor1andpeek(w+e(g+x)):next:b=b>0:w=-t*b-w*notb:l$="a":return

{home} is the home character blob (appears as reverse S character) within quotes

Use A,S,D keys to rotate and drop the blocks
Have fun!

DMCA incoming

[tepples]

How long before The Tetris Company sends a notice of claimed infringement to Slashdot's designated agent, claiming that this post and others like it infringes the copyright in Tetris ?

also, Smiling Bob

[raymorris]

What's harder than NP-hard?

Intractable.

True. Smiling Bob is also harder.

cats are mammals, not all mammals are cats

[raymorris]

A line can be no more than 256 characters. That doesn't mean that the following is one line:

foreach mammal in pets
        print mammal ' "is a mammal"
        if (is_cat(mammal) {
                print " and also a cat"
        }
}

Just because all cats are mammals doesn't mean that all mammals are cats.
Just because all one-liners are less than 257 characters doesn't mean that all programs less than 257 characters are one-liners.

Re:cats are mammals, not all mammals are cats

[BronsCon]

Yes, because line breaks in BASIC are significant. That means, of course, that they actually *do* something; and doing some things in BASIC means you *need* line breaks, so really, any BASIC program without them... is one line.

Re:cats are mammals, not all mammals are cats

[raymorris]

> Yes, because line breaks in BASIC are significant. That means, of course, that they actually *do* something;

Specifically, they *do* approximately the same thing as colons, they are generally synonymous with colons, of which this program has plenty.

Re: cats are mammals, not all mammals are cats

[BronsCon]

Not so. For example, newlines and semi-colons have special meanings in file operations and printing output. Also, BBC BASIC doesnt use GOSUB labels, so you can only GOSUB to the beginning of a newline-delineated line, similar to GOTO.

Yes, I see how the two are similare enough so as to be interchangeable. Maybe, if you don't want your program to run.

Re:cats are mammals, not all mammals are cats

[nedlohs]

Except they don't.

Lines are an important concept of the language - they are referenced by gotos and gosubs. That program is one line. It is more than one statement, but the claim wasn't a "one statement program".

Re:cats are mammals, not all mammals are cats

[JasonGoatcher]

Pedantry is only cool in small doses, and sometimes not even then is it cool. Unless someone in the conversation has Obsessive Compulsive Personality Disorder, please stfu.

Re:cats are mammals, not all mammals are cats

[phantomfive]

Pedantry may sometimes be cool (I doubt it), but morons like you are never cool. RTFA before thinking you understand what is going on, and especially before criticizing what is going on.

Speaking of UI's

[Firethorn]

Defining all of the possible scenarios is often a lot harder than it looks. There aren't too many UI coders out there that haven't said "yeah, we need to fix it, but what made the user decide to do that?" at one time or another.

This reminded me of a UI bug I discovered in Steam - if you have 2 monitors, one rotated 90 degrees, but not the primary, and try to maximize steam on that window, bad things happen.

Seeing as how I've seen only like 3 people doing that, most not in a home setting, I don't think it comes up much.

Re:Speaking of UI's

[Mal-2]

Add me to the list of those using this configuration in a home setting, unless you need to exclude me for actually having three monitors -- one is a TV that is usually off or being used for other purposes. (Having both AGP and integrated graphics active at the same time is... interesting. I get lots of odd behavior out of it.)

Sort of spammy, also not convincing

[seebs]

So, on the one hand, it's sort of a spammy/advertisey thing to begin with.

On the other hand, I'm also not entirely convinced that the code coverage tool really solves the problem, because a given line of code can have different effects under different circumstances.

If you read in an address from a text stream, and then write to the memory location denoted, that's just one line of code executing that dereferences the pointer, but good luck determining what it does on all future invocations based on watching it execute once. Similarly, consider a straightforward loop like "for (i = 1; i len; ++i) a[i] = 0;" where every line will be hit if len is at least 1, but the effect of executing the code is, to put it mildly, somewhat variable.

Re:Sort of spammy, also not convincing

[wrook]

Code coverage tools will not tell you if your tests are sufficient. They simply tell you what lines of code were hit. They don't tell you whether or not the line of code was hit while doing a meaningful test. In fact, it is trivially easy to write "tests" that exercise 100% of the code but have no expectations at all.

What code coverage tools tell you is what code you definitely haven't tested. If you haven't run that line of code in your tests, you definitely haven't tested it. This is useful information, but not essential if you have a good team. My current team is quite comfortable writing tests. We do most things TDD and without trying hard our average code coverage is 96%. I occasionally wander through the other 4% to see if it is worth testing and most of the time it isn't. Occasionally I will find the odd piece of logic that was jammed in hurriedly without tests, but on our team it is quite rare. On the other hand, I have worked on teams that were not comfortable writing tests and mostly wrote them after writing production code. On those teams we would get about 75% test coverage with holes you could drive a bus through. A code coverage tool was very useful for educating people on the need to improve the way they wrote tests.

I feel very confident I could TDD my way through a tetris implementation and get 100% code coverage without undue effort. I don't think I would find all of the corner cases without help, though. A code coverage tool wouldn't help me in that instance.

Re:replacing line feeds with terminators is not a

[Splab]

While I totally agree with the one-line bullshit, I'd just like to point out, that in fact, you can't collapse the linux kernel into a one-line statement this way; Parts of the code is using macros and they will fail if you put them on the same line.

Re:replacing line feeds with terminators is not a

[psmears]

46 lines (statements), actually

No, statements are not the same as lines. Lines have real semantic significance in BBC Basic, in a few different ways: for one, GOSUB-type subroutines can only start at the start of a line (because that's where the line number is), and you also can't terminate an "if" without starting a new line. That (plus the 256-byte limit) makes writing one-liners in the language more of a challenge than in other languages where line breaks genuinely aren't significant.

Re:replacing line feeds with terminators is not a

[allo]

what do you expect from a oneliner? Tetris()? A Perl Oneliner does have semicolons as well.

Re:replacing line feeds with terminators is not a

[WillerZ]

So you run cc -E first then

Re:replacing line feeds with terminators is not a

[itzly]

The nice part about putting the entire Linux kernel on a single line is that you always know the exact line number of the bug.

Re:up, up, down, down, left, right, left, right, B

[Cederic]

External interactions (DBs, UI, etc) and highly performant code (embedded systems, kernels, etc) are where I wouldn't instinctively look to use TDD.

The benefits around testing are massive in themselves - you can set up automated unit tests that assure you not just the code coverage, but also the broad range of inputs that might cause different behaviours within that code.

The design benefits however are significant too, and worthwhile in their own right. I find that TDD leads to code that's easier to read, understand and thus maintain.

Re:replacing line feeds with terminators is not a

[Hognoxious]

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

Ignoratio elenchi

Re:replacing line feeds with terminators is not a

[ignavus]

While I totally agree with the one-line bullshit, I'd just like to point out, that in fact, you can't collapse the linux kernel into a one-line statement this way; Parts of the code is using macros and they will fail if you put them on the same line.

#include "kernel.c"

That's a one liner!

Don't see much BBC BASIC these days!

[PhilHibbs]

My dad and I wrote a BBC BASIC interpreter for PC-DOS. I'll have to dig it out and see if I can get this working in it.

defined as expected value

[raymorris]

As I mentioned, the test of fitness is expected value - the average score of 100,000,000,000 games played with that starstrategy, not the result from one specific, randomly chosen game.

In Hold'em folding preflop with pocket aces may turn out for the best occasionally, but it's still a bad policy because it will lose more than it will win. The best strategy is the one that does well long term.

Re:defined as expected value

[allo]

Jep, and your strategy gets worse, while another strategy may stay average.

Assume you flip a coin. heads or tails.

You NP-complete algorithm knows the sequence.
The probalistic one just guesses "heads".

Now the Expectation value of both are Zero in the stochastic case. In the deterministic one its infinite win for the np-complete one and zero for the probalistic one.
So this is an example, where a perfect algorithm for deterministic data is just as good as another for stochastic data.
This does not mean, you cannot get better than the deterministic-optimal algorithm. As the data is random, the deterministic-optimal algorithm becomes "just another algorithm" and you will need to proof again its better than the other candidates. It may be, maybe even provable the still the optimal one, but the fact that its det-optimal does not imply that its prob-optimal.

A real world example: Las Vegas Quicksort.
Quicksort is O(n log n), choosing log n times a median element, then sorting in n the elements on both sides to the correct side.

calculating the median element is O(n), with some constant C.
Choosing the median element randomly is O(1).
Now you can show, that the propability of a "not too bad" element is so, that the log n * C factor is slower in most cases than the slowdown of the algorithm by choosing a non-optimal "median".

It's possible to beat good testing...

[Sits]

...but not without a price. If you can mathematically construct your program then you can prove that it is free from defects providing enough assumptions hold (the specification is correct, the tools used to build it are correct, the proof of correctness is correct, you had enough money/time/skill to do the process etc). For the time being, it's not possible to formally most programs that have already been written in mainstream languages so other techniques like testing will remain useful tools.

The code isn't so easy at it seems

[tractari auto iasi]

Hi. Im not a code professionist but when i look at these lines i get a big head pain. Honestly i don't understand a thing , and i studied php in school. If somebody could give me some detalied steps,for my beginner language,maybe i could do this too.

if I understand your point

[raymorris]

Let me see if I correctly understand your point. Are you saying:

The best algorithm for a deterministic sequence may be / is NP-hard.
Best best algorithm for the stochastic sequence may be different.
Therefore, the best algorithm for the stochastic sequence may be easier than NP-hard.

That seems to make sense. Until you realize the deterministic sequence IS one case of the stochastic - where the probabilityof a certain sequence happens to be 1.00. If you had a polynomial algorithm for probability X, you could run it for X=1 to solve the deterministic version. Thus, if the deterministic version is NP-hard, so must be the stochastic version in general.

Of course, one specific, special case probability matrix may be solvable more readily. As someone else pointed out, if you decide that your specific version of Tetris generates square pieces always, the algorithm is trivial. However, if we seek an algorithm for any version of Tetris, any probability of any given piece, that will include probability 1 of a given sequence. Thus, the generalized stochastic includes the deterministic as one case and therefore must be at least as complex as that case.

Re:if I understand your point

[allo]

no, you got it only the half way.

deterministic:
best = np-hard, perfekt
other: polynomial, good average

stochastic:
best: np-hard, not perfect, quality unknown
other: polynomial, good average

the point is not the runtime complexity, but the result. while the best algorithm cannot be beaten on the det. sequence, it may fail completely (in terms of quality) on a sequence without full information. If you got a good polynomial one with an average result, it may be better for many sequences.

one example may be an perfect algorithm with a lookup table for all sequences and a greedy algorithm.
With the random sequence, the "perfect" algorithm needs to choose the sequence which is most likely for its next move, discarding a lot of other strategies. Now it may have chosen the worst strategy for the next random and unlikely event. The other algorithm optimizes locally anyway and will continue in both cases as if it does not know the next event.

If it's hard to test

[PJ6]

you didn't write it correctly. TDD.

Re:Intriguing

[JasonGoatcher]

Does David Hassellhoff have any insightful blog posts on this subject? It sounds like his insight on burning man line queues could be beneficial here.

Dear God, the memes are reproducing like rabbits, soon we'll be overrun.

so just don't solve it

[raymorris]

So in other words, you're pointing out that you could just not solve it, not come up with the optimum move each time based on expected value. Instead, you could settle for a "good enough" move and sometimes you'd get lucky. This is true.

you stated:

stochastic:
best: np-hard, not perfect, quality unknown
other: polynomial, good average

You called the first algorithm "best", acknowledging that the best (best long- term average) is NP-hard. The other can't be better than the best (by definition) , so the problem of finding the best moves remains NP-hard. Sure you could have a simpler algorithm that comes up with reasonable moves, but it'll always be beaten by the NP-hard in the long term.

Re:so just don't solve it

[allo]

Best is only with respect to the deterministic case.

disregard runtime complexity.

deterministic:
there is a best strategy (A).
all other strategies (B) are worse or equal.
A stochastic strategy (C) may have a good average quality.

stochastic:
the deterministic best strategy (A) cannot be perfect anymore, just as no other strategy can.
(A) has now unknown quality for a random sequence.
(C) still has the same average quality.

So there is now a possibility, that (C) may beat (A) in an average over a lot of games. (as a single game does not have any relevance when using random games)