Tetris Is Hard To Test

One line? by GrahamCox · 2014-10-25 12:19 · Score: 4, Funny

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? by phantomfive · 2014-10-25 12:35 · Score: 1

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

--
"First they came for the slanderers and i said nothing."
Re:One line? by ShanghaiBill · 2014-10-25 13:26 · Score: 2, Informative

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? by lgw · 2014-10-25 13:32 · Score: 4, Informative

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.
Re:One line? by Anonymous Coward · 2014-10-25 13:42 · Score: 0

Really, who couldn't love code like this
my mom
Re:One line? by ShanghaiBill · 2014-10-25 13:46 · Score: 1

The line length limit is 256 bytes, of course.
The program is 430 bytes.
Re:One line? by BlackHawk-666 · 2014-10-25 14:02 · Score: 4, Informative

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.
Re:One line? by Anonymous Coward · 2014-10-25 14:05 · Score: 0

RTFA a little better - a BBC Basic line is defined as 256 bytes ....not lines on a screen. So yes there is a limit on line length and they meet it with this code.
Re:One line? by Anonymous Coward · 2014-10-25 14:07 · Score: 0

You could argue that the blocks are being fed based on a pseudo rng so they are in fact known (or at least predictable) given the same seed.
Re:One line? by Anonymous Coward · 2014-10-25 14:10 · Score: 0

You're no fun. If I worked for you, I'd quit as soon as possible.
And you would do him a favor. The line in question has known bugs and it's not really written in a debugger friendly way. Writing an application like this might give you l33t self esteem, but it would be dangerous in a job situation where you could become financially responsible for crashes and data corruption at the client.
As fun as such one-liners might be, no sane boss should allow them in production code. I once had code, which were a bit more readable than this, but the author left a few years earlier and nobody could figure out how it worked. This meant to solve a minor bug, the entire function ended up being redesigned and rewritten from scratch. That's what you get for allowing coder and quality control to be the same person (which was no longer allowed after that incident). It also tells something about the need for code documentation and comments (none were found in that incident).
Re:One line? by LordKronos · 2014-10-25 14:14 · Score: 1

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? by Anonymous Coward · 2014-10-25 14:32 · Score: 0

Correct
BBC BASIC tokenised BASIC keywords before the line was stored in memory, e.g. PRINT was represented by a single byte. Some tokens needed more than one byte, especially in later versions.
Re:One line? by sexconker · 2014-10-25 14:39 · Score: 1, Flamebait

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? by Anonymous Coward · 2014-10-25 14:44 · Score: 0

So how does one mod this? There's no "-1, obviously DRTFA". Offtopic? Overrated? Redundant? Those don't really fit.
Re:One line? by phantomfive · 2014-10-25 14:46 · Score: 1

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

--
"First they came for the slanderers and i said nothing."
Re:One line? by Anonymous Coward · 2014-10-25 15:18 · Score: 0

> Any program can be a "one-liner" if there is no limit on the line length.
1. You can't just take a BBC BASIC program and replace all of the newlines with colons. A newline is syntactically significant and distinct from a colon. Some statements have to start at the beginning of a line, some statements terminate at the end of the line (e.g. there is no ENDIF statement), you can't GOTO or GOSUB into the middle of a line, etc.
2. There is a limit on the length of a line: 256 bytes. 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.
Re:One line? by Anonymous Coward · 2014-10-25 15:19 · Score: 0

"Anyone who had to read it, update it, or debug it?"
It took talent to write it, it takes talent to update, read and debug it. That doesn't mean that everything should be written down to the level of the talentless.
It's beautiful.
Re:One line? by sexconker · 2014-10-25 18:26 · Score: 0

How should I know who's going to infect who next? That's precisely the point. Infected people get in, run around willy-nilly, the people treating them don't have the training or equipment to properly handle the situation let alone the public at large the come into contact with, and more people are exposed and infected. We've already had 3 confirmed transmissions of Ebola in the US since I made my statement. I've already been proven right. Hundreds of people are being monitored, thousands have been exposed, businesses are closed down, etc. Keep your head in the sand though.
Re:One line? by Stanza · 2014-10-25 19:37 · Score: 1

You've never written code in perl, have you?
Re:One line? by Anonymous Coward · 2014-10-25 20:26 · Score: 0

"Anyone who had to read it, update it, or debug it?"
It took talent to write it, it takes talent to update, read and debug it. That doesn't mean that everything should be written down to the level of the talentless.
It's beautiful.
As a work of art, I would agree with you. But the parent was responding to a general question, and he has a valid point. Part of the net worth of production code is how easy it is to maintain, debug, update, etc.
Same goes for car engines. Sure, you could have some Savant hand-design and build a fantastic car engine which could only be worked on by one or two other brilliant and talented people. Which makes a nice piece of art, just like you're talking about, and which is entirely useless to everyone else aside from saying "Wow, that's cool."
Re:One line? by Anonymous Coward · 2014-10-25 20:32 · Score: 0

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.
Keep in mind that one character of source code could easily result in hundreds or thousands of actual instructions. This is not code written for resource efficiency, it's written for source code compactness.
Re:One line? by Saysys · 2014-10-25 21:41 · Score: 1

80 characters: all done in COBOL
Re:One line? by Dogtanian · 2014-10-25 22:09 · Score: 1

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.

--
"Slashdot - News and Chat Sites Deviant". (Click "homepage" link above for details).
Re: One line? by Anonymous Coward · 2014-10-25 22:54 · Score: 0

Moreover this brilliant engine could be of just mediocre design thus all the effort put in maintenance is better spent on redesign.
Re:One line? by Anonymous Coward · 2014-10-26 00:53 · Score: 0

sexconker - October 2014:

I'd love to see you make that same post 10 days from now when the number of confirmed cases in the US skyrockets.
To confirm, you believe that the number of confirmed cases of Ebola in the US had skyrocketed as of October 18?
You were wholly wrong. You 'expect and require' an apology from someone although you were the fucking idiot who was, and continues to be, demonstrably wrong. Notably, you've yet to apologize for your own fucking idiocy. You keep your head in the sand too, sexconker.
Re:One line? by Anonymous Coward · 2014-10-26 01:08 · Score: 2, Informative

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? by K.+S.+Kyosuke · 2014-10-26 02:29 · Score: 2

It would be probably shorter in Forth. ;-)

--
Ezekiel 23:20
Re:One line? by Anonymous Coward · 2014-10-26 03:15 · Score: 0

There must be a perl module that does that somewhere is CPAN. There is one for everything ...
Re:One line? by LordKronos · 2014-10-26 03:50 · Score: 2

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? by Anonymous Coward · 2014-10-26 04:21 · Score: 0

If you're writing in Python, a lambda expression can do anything on one line.
Re:One line? by Ed+Avis · 2014-10-26 05:04 · Score: 3, Insightful

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.

--
-- Ed Avis ed@membled.com
Re:One line? by Richy_T · 2014-10-26 06:30 · Score: 1

BBC basic was interpreted, not compiled (though there may have been compilers written for it since).
Re:One line? by Sebastopol · 2014-10-26 07:56 · Score: 1

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

--
https://www.accountkiller.com/removal-requested
Re:One line? by LordKronos · 2014-10-26 12:07 · Score: 1

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.
Re:One line? by Anonymous Coward · 2014-10-26 21:55 · Score: 0

That's one basic line. It's different from, say, C lines that have no line length limit as far as I know.
Re:One line? by Anonymous Coward · 2014-10-27 04:36 · Score: 0

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.
FWIW, "The researchers found that Tetris was an NP-Hard problem, i.e. there was no easy way to maximise a score at the game, even when the sequence of blocks was known in advance."

Blockheads by penguinoid · 2014-10-25 12:20 · Score: 1

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

--
Don't waste your vote! Vote for whoever you want, unless you live in a swing state it won't matter anyways

Re:Blockheads by milkmage · 2014-10-25 12:43 · Score: 1

9-INKEY6MOD3:FORr=TRUETO1 --- lol
Re:Blockheads by dj_nme · 2014-10-25 13:04 · Score: 1

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 by iapetus · 2014-10-25 19:44 · Score: 1

RTFM.

--
++ Say to Elrond "Hello.".
Elrond says "No.". Elrond gives you some lunch.

in Soviet Russia by Trepidity · 2014-10-25 12:22 · Score: 4, Funny

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.

--
10 PRINT CHR$(205.5+RND(1)); : GOTO 10

Re:in Soviet Russia by flargleblarg · 2014-10-25 15:13 · Score: 2

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 by Anonymous Coward · 2014-10-25 12:24 · Score: 5, Insightful

From a company promoting automated WCET analysis. Hah!

Re:Nice advertisement by Anonymous Coward · 2014-10-25 13:54 · Score: 0

Indeed, plus if you read the article it's all wrong and has nothing to do with testing. Normal users don't test all cases of a game. A programmer who implements those weird cases does test them. Sure you can make an argument for a programmer implementing a rare special case, then changing something else which produces a bug in that rare special case. But still, you are meant to test that too, just like you test against buffer overflows and other crap.
These kind of coverage tools seem good only when you have started a project with poor practices or inherit an equally sucky codebase. But really, testing tetris doesn't make any sense (other than capturing the interest of people interested in AI expecting something else).
Re:Nice advertisement by phantomfive · 2014-10-25 14:55 · Score: 4, Insightful

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.

--
"First they came for the slanderers and i said nothing."
Re:Nice advertisement by Mr.+Freeman · 2014-10-25 16:53 · Score: 1

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.

--
-1 disagree is not a modifier for a reason. -1 troll, flaimbait, redundant, overrated are NOT acceptable substitutes.
Re:Nice advertisement by JackDW · 2014-10-25 20:50 · Score: 2

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.

--
You're an immobile computer, remember?

Perl-standard line length by Sigma+7 · 2014-10-25 12:26 · Score: 1

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 by Anonymous Coward · 2014-10-25 12:42 · Score: 0

Need a massively wide monitor.
Oh and a chair with wheels and wireless mouse and keyboard.
Re:Perl-standard line length by phantomfive · 2014-10-25 12:43 · Score: 1

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.

--
"First they came for the slanderers and i said nothing."
Re:Perl-standard line length by JackDW · 2014-10-25 12:43 · Score: 3, Informative

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?
Re:Perl-standard line length by brantondaveperson · 2014-10-25 12:45 · Score: 1

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 by jopsen · 2014-10-25 12:53 · Score: 1

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 by darkain · 2014-10-25 13:13 · Score: 1

Maybe you'd prefer a binary version at 256 bytes?
http://256bytes.untergrund.net...
Re: Perl-standard line length by Anonymous Coward · 2014-10-25 14:43 · Score: 0

Or a scroll bar
Re: Perl-standard line length by ArcadeMan · 2014-10-25 15:57 · Score: 1

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

--
Get free satoshi (Bitcoin) and Dogecoins
Re:Perl-standard line length by Anonymous Coward · 2014-10-25 17:14 · Score: 0

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.
They may still technically be one program line, in that you can sandwich it between two line numbers. But it still occupies more then one screen line.
Re:Perl-standard line length by Dogtanian · 2014-10-25 23:23 · Score: 1

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.

--
"Slashdot - News and Chat Sites Deviant". (Click "homepage" link above for details).

replacing line feeds with terminators is not a 1-l by raymorris · 2014-10-25 12:28 · Score: 4, Informative

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 by Tablizer · 2014-10-25 12:42 · Score: 1

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

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

--
Table-ized A.I.

Re:One Line by dgatwood · 2014-10-25 13:02 · Score: 3, Informative

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.
Re:One Line by Tablizer · 2014-10-25 15:45 · Score: 1

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

--
Table-ized A.I.
Re:One Line by MadTinfoilHatter · 2014-10-25 19:33 · Score: 1

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 by Nyder · 2014-10-25 12:44 · Score: 2

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

--
Be seeing you...

Re:replacing line feeds with terminators is not a by Anonymous Coward · 2014-10-25 12:45 · Score: 0

Yeah. The linked "one line" of code is at really least 50 lines by any sane metric.

What to do when you have got too much time on your by Anonymous Coward · 2014-10-25 12:55 · Score: 0

hands?

This.

perhaps. I wonder if it NP-hard by raymorris · 2014-10-25 14:06 · Score: 4, Interesting

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 by phantomfive · 2014-10-25 14:51 · Score: 4, Funny

What's harder than NP-hard?

Intractable.

--
"First they came for the slanderers and i said nothing."
Re:perhaps. I wonder if it NP-hard by Anonymous Coward · 2014-10-25 15:54 · Score: 0

f the probability of a certain series of shapes coming next were 100%, we'd have an NP-hard problem, agreed?
Disagreed. If the probability of getting the square piece is 100%, then Tetris is not NP-hard.
Re:perhaps. I wonder if it NP-hard by allo · 2014-10-25 20:34 · Score: 3, Informative

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? by 140Mandak262Jamuna · 2014-10-25 14:10 · Score: 4, Interesting

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

--
sed -e 's/Chuck Norris/Rajnikant/g' joke > fact

Re:Infomercial for a code coverage tool? by onepoint · 2014-10-25 14:33 · Score: 1

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.

--
if you see me, smile and say hello.
Re:Infomercial for a code coverage tool? by NormalVisual · 2014-10-25 14:55 · Score: 1

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.

--
Please stand clear of the doors, por favor mantenganse alejado de las puertas
Re:Infomercial for a code coverage tool? by Anonymous+Brave+Guy · 2014-10-25 15:36 · Score: 2

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.

--
If you disagree, post your argument. (-1, Overrated) isn't your personal censorship tool for views you don't like.
Re:Infomercial for a code coverage tool? by Anonymous Coward · 2014-10-25 15:46 · Score: 0

I've never known a programmer with perfection as a goal. They all just kind of fix a few bugs but ignore most, no matter how obvious or reproducible they are. It's pathetic.
Re:Infomercial for a code coverage tool? by itzly · 2014-10-25 17:15 · Score: 1

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? by JackDW · 2014-10-25 21:19 · Score: 1

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.

--
You're an immobile computer, remember?
Re: Infomercial for a code coverage tool? by fatgraham · 2014-10-25 21:22 · Score: 1

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? by Anonymous Coward · 2014-10-25 23:28 · Score: 0

Unless you deliver at the end of 'wrong' century.
Re: Infomercial for a code coverage tool? by Anonymous Coward · 2014-10-25 23:32 · Score: 0

Manage project better? You mean like having project managment instead the hippi commune but without drugs, sex and r&r? Oh man I am going - where do they hire?
Re:Infomercial for a code coverage tool? by Anonymous+Brave+Guy · 2014-10-26 02:46 · Score: 1

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.

--
If you disagree, post your argument. (-1, Overrated) isn't your personal censorship tool for views you don't like.
Re:Infomercial for a code coverage tool? by Anonymous Coward · 2014-10-26 03:00 · Score: 0

There exist other code coverage metrics, some of them taking into account various paths that can lead to a particular statement. But when developing avionics safety critical software the coverage metrics considered are the one shown in this demo. This is true for DO178B (used for decades for avionic software) and the next version (DO178C) still relies on this sort of code coverage. And it's coming to the automotive indistry too (ISO26262). Next time I board a plane, I'll sure hope the software team has spent more time and care testing their software than "testing" Tetris.
Re:Infomercial for a code coverage tool? by onepoint · 2014-10-26 06:03 · Score: 1

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.

--
if you see me, smile and say hello.
Re: Infomercial for a code coverage tool? by NormalVisual · 2014-10-26 06:36 · Score: 1

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

--
Please stand clear of the doors, por favor mantenganse alejado de las puertas
Re:Infomercial for a code coverage tool? by JackDW · 2014-10-26 08:46 · Score: 1

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... :)

--
You're an immobile computer, remember?

Nonsense -- make your own test suite by rs1n · 2014-10-25 14:21 · Score: 4, Insightful

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 by NormalVisual · 2014-10-25 14:58 · Score: 2

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.

--
Please stand clear of the doors, por favor mantenganse alejado de las puertas
Re:Nonsense -- make your own test suite by Anonymous Coward · 2014-10-25 15:49 · Score: 0

That's cool how you know in hindsight what "all" of the scenarios are, after reading the article.
Re:Nonsense -- make your own test suite by Anonymous Coward · 2014-10-25 16:08 · Score: 0

DICE has to make money somehow
Re:Nonsense -- make your own test suite by Anonymous Coward · 2014-10-25 18:12 · Score: 0

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?
Seems like double work. How do you test the test suite? Why not use something off the shelf?
Anywho, has anybody found with some versions of Tetris (EA Android, methinks), it is a better strategy by far to get continuous two-line "T-spins" than four liners? Is that what the guy meant by 'wall kicks' or what not???
Sorry for not googling my tetris quesions...
Re:Nonsense -- make your own test suite by Anonymous Coward · 2014-10-25 18:38 · Score: 0

If you're a programmer who has developed a simple piece of code you would how to generate inputs that will exercise all your code paths, and you don't need to read the article to know that.
Re:Nonsense -- make your own test suite by chrysrobyn · 2014-10-25 23:31 · Score: 1

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 by Anonymous Coward · 2014-10-26 00:30 · Score: 0

Has slashdot really become a means for tech companies to inject free advertisement by a simple blog post made to look like real journalism?
Yes. Yes it has.
Re:Nonsense -- make your own test suite by Anonymous Coward · 2014-10-26 03:02 · Score: 0

Plus this one time it's quite good fun.
Re:Nonsense -- make your own test suite by JackDW · 2014-10-26 03:24 · Score: 1

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.

--
You're an immobile computer, remember?
Re:Nonsense -- make your own test suite by s0nicfreak · 2014-10-26 04:48 · Score: 1

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 by Anonymous Coward · 2014-10-25 14:30 · Score: 3, Insightful

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 by NormalVisual · 2014-10-25 15:01 · Score: 1

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.

--
Please stand clear of the doors, por favor mantenganse alejado de las puertas
Re:Beware coverage tools by Anonymous Coward · 2014-10-25 15:33 · Score: 1

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 by hraponssi · 2014-10-26 01:32 · Score: 1

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 by Sebastopol · 2014-10-26 08:00 · Score: 1

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.

--
https://www.accountkiller.com/removal-requested
Re:Beware coverage tools by ianb1469 · 2014-10-26 09:53 · Score: 1

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 by NormalVisual · 2014-10-25 14:46 · Score: 2

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.

--
Please stand clear of the doors, por favor mantenganse alejado de las puertas

Re:replacing line feeds with terminators is not a by phantomfive · 2014-10-25 14:53 · Score: 2

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

--
"First they came for the slanderers and i said nothing."

piece of cake by amoeba1911 · 2014-10-25 15:01 · Score: 1

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

Re:piece of cake by Anonymous Coward · 2014-10-25 23:50 · Score: 0

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

Exactly this is not. It's completely useless to create an input that stimulates all cases. At least, without also adding checks that in all these cases the behavior is correct.

Re:replacing line feeds with terminators is not a by Anonymous Coward · 2014-10-25 15:05 · Score: 0

46 statements doesn't count the additional whitespace necessary for readability.

Sane indentation adds one for every loop or non-oneline branch.

# newline
IF (condition)
STATEMENT
ELSE
STATEMENT
# newline

How I know it's an ad by rebelwarlock · 2014-10-25 15:09 · Score: 1

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!

Re:How I know it's an ad by Anonymous Coward · 2014-10-26 04:17 · Score: 0

... and these can only be easily found with the help of a coverage tool.
What about reading the code? Code reviews are a very effective way of finding this kind of thing at an early stage.
It is often better to reject the code in order to avoid special cases if possible.

C64 BASIC version within a screen of code by Neo-Rio-101 · 2014-10-25 15:15 · Score: 3, Interesting

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

--
READY.
PRINT ""+-0

erratum: missing lines by Neo-Rio-101 · 2014-10-25 15:25 · Score: 2

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!

--
READY.
PRINT ""+-0

Re: erratum: missing lines by Anonymous Coward · 2014-10-25 15:34 · Score: 0

I'm having more fun laughing at how utterly lame you are.
Re: erratum: missing lines by Anonymous Coward · 2014-10-26 11:17 · Score: 0

I'm having more fun laughing at how utterly lame you are.
What's the point of even being on Slashdot if you can't enjoy pure geekiness now and then? The only people who'd find this lame are those who consider Slashdot lame to begin with. So clearly this isn't the place for you.

DMCA incoming by tepples · 2014-10-25 15:36 · Score: 2

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 by raymorris · 2014-10-25 15:52 · Score: 1

What's harder than NP-hard?

Intractable.

True. Smiling Bob is also harder.

cats are mammals, not all mammals are cats by raymorris · 2014-10-25 16:13 · Score: 2

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 by Anonymous Coward · 2014-10-25 19:12 · Score: 0

>Just because all one-liners are less than 257 characters doesn't mean that all programs less than 257 characters are one-liners.
You're perfectly correct - not all programs less than 257 characters are one-liners. Only the ones physically stored on one line are one-liners.
Like this one.
It doesn't magically become stored on multiple lines simply because it could be. If you enter it into a single line, it's in a single line.
Lines of code are an actual THING in BASIC. And this code is on ONE LINE.
Re:cats are mammals, not all mammals are cats by Anonymous Coward · 2014-10-25 20:57 · Score: 0

So if there existed one actual basic with a 4GB line limit, you'd be happy to accept anything under 4GB as a single line?
A yes or no answer will do.
Re:cats are mammals, not all mammals are cats by BronsCon · 2014-10-25 22:20 · Score: 1

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.

--
APK quotes people (including myself) without context and should not be trusted. Just thought you should know.
Re:cats are mammals, not all mammals are cats by raymorris · 2014-10-26 03:08 · Score: 1

> 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 by BronsCon · 2014-10-26 04:50 · Score: 1

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.

--
APK quotes people (including myself) without context and should not be trusted. Just thought you should know.
Re:cats are mammals, not all mammals are cats by Anonymous Coward · 2014-10-26 06:19 · Score: 0

No, because now we are defining a "line" as an arbitrary choice of 256 bytes by the developers of BBC Basic.
It is nonsensical to use this as the definition of a "line" since it is at variance with the generally accepted definition of a line of code - you know by developers who in general don't use, like, or defer to BBC Basic.
Re:cats are mammals, not all mammals are cats by nedlohs · 2014-10-26 10:27 · Score: 1

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 by JasonGoatcher · 2014-10-26 15:36 · Score: 1

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 by Anonymous Coward · 2014-10-26 22:10 · Score: 0

On that basic, yes. Considering that line actually had any meaning. In BBC Basic lines do have a meaning.
If some language had a limit for file lenght you'd be sure that "one file program" was a thing. Even more so if you could only make some jumps to the beginning of a file. Or if some statements such as IFs would always need a second file for the ELSE case.
Re:cats are mammals, not all mammals are cats by phantomfive · 2014-10-27 05:08 · Score: 1

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.

--
"First they came for the slanderers and i said nothing."

Re:No you can't by Anonymous Coward · 2014-10-25 17:16 · Score: 0

"For stories about boys in leather, please press 1..."

Speaking of UI's by Firethorn · 2014-10-25 17:17 · Score: 1

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.

--
I don't read AC A human right

Re:Speaking of UI's by Mal-2 · 2014-10-25 20:51 · Score: 1

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

--
How is the Riemann zeta function like Trump rallies? Both have an endless number of trivial zeros.
Re:Speaking of UI's by Anonymous Coward · 2014-10-25 23:08 · Score: 0

(Having both AGP and integrated graphics active at the same time is... interesting. I get lots of odd behavior out of it.)
From which museum did you get a computer with AGP?

Sort of spammy, also not convincing by seebs · 2014-10-25 17:33 · Score: 1

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.

--
My blog: http://www.seebs.net/log/ --- My iPhone/iPad app: http://www.seebs.net/seebsfrac/

Re:Sort of spammy, also not convincing by Anonymous Coward · 2014-10-25 18:12 · Score: 0

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.
It's no silver bullet, but combined with static code analysis and hand-written unit tests, you can reach relatively high confidence that the code works right.
Re:Sort of spammy, also not convincing by wrook · 2014-10-25 20:55 · Score: 3, Insightful

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:Sort of spammy, also not convincing by Anonymous Coward · 2014-10-26 03:09 · Score: 0

This is the wrong way to use a code coverage tool. You shouldn't be looking at the code to get the coverage up, testing should be done from requirements. And once you've done all your requirement based testing and you still don't have 100% coverage them it's likely you've got code that shouldn't be there at all ... assuming you haven't got a problem in your testing or requirements (usually more likely).
Still, next time I need to explain MC/DC to a tester I'll use that !

up, up, down, down, left, right, left, right, B, A by Anonymous Coward · 2014-10-25 18:07 · Score: 0

I'm kinda glad that code coverage is difficult to do! ( http://en.wikipedia.org/wiki/Konami_Code )

Cheat codes and "Easter Eggs" give the lowly programmer a chance to do something awesome/notorious, against the long odds of getting stuff approved by marketing, the legal/IP department.

Unit testing is meant to do full code coverage from within an app. However, it can sometimes be quite difficult to set up the complete software state to test some kinds of scenarios, but this can be made easier if the program is designed with testing in mind. I don't know what kinds of projects would benefit from "test-driven design", though. Maybe life-critical software (aerospace, medical, Facebook).

Really? by Anonymous Coward · 2014-10-25 19:03 · Score: 0

Looks more like a programming problem than pnp.

> This procedure, updateScore4, is called when a block of 4 lines are cleared at once.

What kinda mid evil crap is that?

This shit dont work man by Anonymous Coward · 2014-10-25 20:04 · Score: 0

Testing !!!!! Is !!!!! Software Development !!! HAHAHAHAHA.

Coverage tools and lack of understanding... by Anonymous Coward · 2014-10-25 20:05 · Score: 0

As others said, nice advertisement. In practice, however, such tools tend to guide people along an "easy" path, where two very basic principles are ignored.

a) The primary goal of every testing is check fulfillment of requirements. Even if coverage is reached, the same might not be true for completeness with regards to requirements. The tool may report "100%", but there is still cases described in the requirements that do not work.

b) Simply executing instructions is not worth anything towards proving code coverage. In addition it has to be shown that they positively contribute to the result. It is easily possible that some code executes incorrectly but without negative impact in a given test-case. The tool will report 100%. With a different test-case, it may still execute incorrectly and having an overall effect. If that test-case is missing the result is OK with full coverage and the product is still broken.

The one reason, and only reason, to check coverage is detection of dead code that will do something wrong when executed in situations not considered during testing. Mindless deployment of such tools distract from this. They tend to make "100% coverage" the goal, even though this is far from sufficient.

Re:replacing line feeds with terminators is not a by Splab · 2014-10-25 20:29 · Score: 1

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 by psmears · 2014-10-25 20:30 · Score: 2

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.

--
Need to type accents and special characters in Windows? Use FrKeys

Re:replacing line feeds with terminators is not a by allo · 2014-10-25 20:41 · Score: 1

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 by WillerZ · 2014-10-25 21:28 · Score: 1

So you run cc -E first then

--
I guess today is a passable day to die.

Re:replacing line feeds with terminators is not a by itzly · 2014-10-25 22:20 · Score: 2

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:replacing line feeds with terminators is not a by Anonymous Coward · 2014-10-25 22:38 · Score: 0

How is this informative?

In old micro BASIC, lines have a meaningful and clear definition. They are ordered strings of tokens prefixed by a number and containing one or more sentences, usually limited to about 256 bytes in size. You can only edit the program a line at a time, and you must edit the entire line. The numbers are also used as labels for loops and subroutines. The concept of 'a line' is not only meaningful, but fundamental for the structure of the program. The linked code is a one-liner and absolutely nobody who had programmed BBC BASIC would say otherwise.

Your confusion comes from thinking about programs as text files or streams to be parsed or compiled. That is not how old BASIC works. The program was usually stored and edited in binary form, most of the time already tokenised more or less aggressively depending on the implementation.

Even if you want 'a line' to mean a line on screen, old micros usually had several switchable screen modes with different numbers of characters per row, so that makes less sense than the correct definition.

Re:up, up, down, down, left, right, left, right, B by Cederic · 2014-10-25 22:45 · Score: 1

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 by Anonymous Coward · 2014-10-25 23:01 · Score: 0

It is a one-liner. Stop being a pedantic tit.
It is one continuous line, and I assume, no word wrap. (if there is, THAT would nullify it from being a one-liner)

A one-liner is basically a rap of the programming world. A syntactical mess waiting to happen if you do not watch what you are doing. (hint: most rappers don't and won't watch what they are doing either)

What it ISN'T, though, is a one-commander. That you would be correct with.
Commas also do not constitute a one-commander, it classifies as both an operator and a command seperator / terminator.
Well, eh, I guess it could count. It is a really grey area symbol.

Re:replacing line feeds with terminators is not a by Hognoxious · 2014-10-25 23:12 · Score: 1

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

--
Confucius say, "Find worm in apple - bad. Find half a worm - worse."

Re:replacing line feeds with terminators is not a by ignavus · 2014-10-25 23:28 · Score: 1

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!

--
I am anarch of all I survey.

test software? by Anonymous Coward · 2014-10-25 23:55 · Score: 0

I knew I was missing something lately.

Don't see much BBC BASIC these days! by PhilHibbs · 2014-10-26 02:29 · Score: 1

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 by raymorris · 2014-10-26 02:59 · Score: 1

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 by allo · 2014-10-26 06:14 · Score: 2

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... by Sits · 2014-10-26 03:18 · Score: 1

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

Score: 100% in 17 minutes by Anonymous Coward · 2014-10-26 04:31 · Score: 0

But only on my second attempt once I learned about MC/DC :(

100 % in 17 minutes by Anonymous Coward · 2014-10-26 05:11 · Score: 0

but only on the 2nd attempt once I read about MC/DC :(

Don’t Judge Software by Its (Code) Coverage by Anonymous Coward · 2014-10-26 05:32 · Score: 0

Worrying: "Coverage metrics are frequently used as stopping criteria for the testing activity"

https://hal.archives-ouvertes.fr/file/index/docid/848458/filename/8_-_ars2013_Paper11_Johansson.pdf

The code isn't so easy at it seems by tractari+auto+iasi · 2014-10-26 06:21 · Score: 1

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.

--
Tractari Auto Iasi

if I understand your point by raymorris · 2014-10-26 07:30 · Score: 2

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 by allo · 2014-10-27 05:50 · Score: 2

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 by PJ6 · 2014-10-26 11:47 · Score: 1

you didn't write it correctly. TDD.

Re:Intriguing by JasonGoatcher · 2014-10-26 15:37 · Score: 1

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.

3 different stories by Anonymous Coward · 2014-10-26 22:55 · Score: 0

1) TETRIS may be NP hard to play optimal, but its not NP hard to implement
2) The one liner does not implement the same TETRIS, the code coverage tool vendor is writing about. He tries to cover special places in game scoring (in points) while the BASIC program does do any scoring at all.

Nonsense -- make your own test suite by Anonymous Coward · 2014-10-27 00:57 · Score: 0

From a company promoting automated WCET analysis. Hah! http://www.urlbuff.net/

so just don't solve it by raymorris · 2014-10-27 14:30 · Score: 1

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 by allo · 2014-10-28 05:36 · Score: 1

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)

169 comments