11
\$\begingroup\$

Write code to figure out whether a run of Tetris pieces could be generated by the official Tetris algorithm. Fewest bytes wins.


Official Tetris games generate the sequence of falling pieces in a special way. The seven pieces IJLOSTZ are dropped in a random order, then another random permutation is dropped, and so on.

JTLOISZ STJOLIZ LISJOTZ ...

This example contains the contiguous run of pieces

SZSTJOLIZLIS

Note that it cuts across the boundaries of a group of 7. But, the run of pieces

SZOTLZSOJSIT

cannot be a substring of any Tetris sequence, so it can never be seen in an official Tetris game.


Input: A non-empty string of letters IJLOSTZ.

Output: A Truthy or Falsey value for whether the input is a substring of a sequence that can be generated by the official Tetris Random Generator, i.e. of a concatenation of permutations of the seven letters.

Test cases:

True:

T
JJ                        (unique breakdown: J J)
JTJ                     (possible breakdown: JT J)
LTOZIJS
SZSTJOLIZLIS            (possible breakdown: SZ STJOLIZ LIS)
JTLOISZSTJOLIZLISJOTZ   (possible breakdown: JTLOISZ STJOLIZ LISJOTZ)  
LIJZTSLIJZTS              (unique breakdown: LIJZTS LIJZTS)

False:

SZOTLZSOJSIT
ZZZ
ZIZJLJ
ZJLJLZITSOTLISOJT
JTLOISZSTJOLIZLISJOTZLJTSZLI
IOJZSITOJZST
LIJZTSLIJZTSL

Leaderboard

Courtesy of Martin Büttner.

function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/55689/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function getAnswers(){$.ajax({url:answersUrl(page++),method:"get",dataType:"jsonp",crossDomain:true,success:function(e){answers.push.apply(answers,e.items);if(e.has_more)getAnswers();else process()}})}function shouldHaveHeading(e){var t=false;var n=e.body_markdown.split("\n");try{t|=/^#/.test(e.body_markdown);t|=["-","="].indexOf(n[1][0])>-1;t&=LANGUAGE_REG.test(e.body_markdown)}catch(r){}return t}function shouldHaveScore(e){var t=false;try{t|=SIZE_REG.test(e.body_markdown.split("\n")[0])}catch(n){}return t}function getAuthorName(e){return e.owner.display_name}function process(){answers=answers.filter(shouldHaveScore).filter(shouldHaveHeading);answers.sort(function(e,t){var n=+(e.body_markdown.split("\n")[0].match(SIZE_REG)||[Infinity])[0],r=+(t.body_markdown.split("\n")[0].match(SIZE_REG)||[Infinity])[0];return n-r});var e={};var t=1;answers.forEach(function(n){var r=n.body_markdown.split("\n")[0];var i=$("#answer-template").html();var s=r.match(NUMBER_REG)[0];var o=(r.match(SIZE_REG)||[0])[0];var u=r.match(LANGUAGE_REG)[1];var a=getAuthorName(n);i=i.replace("{{PLACE}}",t++ +".").replace("{{NAME}}",a).replace("{{LANGUAGE}}",u).replace("{{SIZE}}",o).replace("{{LINK}}",n.share_link);i=$(i);$("#answers").append(i);e[u]=e[u]||{lang:u,user:a,size:o,link:n.share_link}});var n=[];for(var r in e)if(e.hasOwnProperty(r))n.push(e[r]);n.sort(function(e,t){if(e.lang>t.lang)return 1;if(e.lang<t.lang)return-1;return 0});for(var i=0;i<n.length;++i){var s=$("#language-template").html();var r=n[i];s=s.replace("{{LANGUAGE}}",r.lang).replace("{{NAME}}",r.user).replace("{{SIZE}}",r.size).replace("{{LINK}}",r.link);s=$(s);$("#languages").append(s)}}var QUESTION_ID=45497;var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";var answers=[],page=1;getAnswers();var SIZE_REG=/\d+(?=[^\d&]*(?:&lt;(?:s&gt;[^&]*&lt;\/s&gt;|[^&]+&gt;)[^\d&]*)*$)/;var NUMBER_REG=/\d+/;var LANGUAGE_REG=/^#*\s*((?:[^,\s]|\s+[^-,\s])*)/
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src=https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js></script><link rel=stylesheet type=text/css href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"><div id=answer-list><h2>Leaderboard</h2><table class=answer-list><thead><tr><td></td><td>Author<td>Language<td>Size<tbody id=answers></table></div><div id=language-list><h2>Winners by Language</h2><table class=language-list><thead><tr><td>Language<td>User<td>Score<tbody id=languages></table></div><table style=display:none><tbody id=answer-template><tr><td>{{PLACE}}</td><td>{{NAME}}<td>{{LANGUAGE}}<td>{{SIZE}}<td><a href={{LINK}}>Link</a></table><table style=display:none><tbody id=language-template><tr><td>{{LANGUAGE}}<td>{{NAME}}<td>{{SIZE}}<td><a href={{LINK}}>Link</a></table>

\$\endgroup\$
6
\$\begingroup\$

Pyth, 16 15 bytes

sm*F.{Mc+>Gdz7T

Prints 0 for false, a positive integer for true.

\$\endgroup\$
6
\$\begingroup\$

CJam, 23 20 16 bytes

q7{\+_7/_Lf|=},&

Credits to Sp3000 for shaving off 4 bytes!

It prints a bunch of digits as a truthy value or nothing as a falsy value (before printing these are actually a non-empty or empty list, which are indeed truthy and falsy in CJam).

Test it here.

Explanation

This just checks all 7 possible partitions of the input into chunks.

q      e# Read the input
7{     e# Select the numbers from 0 to 6 for which the following block is true.
  \+   e#   Prepend the number to the input. This shifts the string by one cell
       e#   without adding non-unique elements.
  _7/  e#   Make a copy and split into chunks of 7.
  _Lf| e#   Remove duplicates from each chunk.
  =    e#   Check if the last operation was a no-op, i.e. that there were no duplicates.
},
&      e# The stack now contains the input with [6 5 ... 1 0] prepended as well as a list
       e# of all possible splittings. We want to get rid of the former. To do this in one
       e# byte we take the set intersection of the two: since we've prepended all the
       e# integers to the list, this will always yield the list of splittings.
\$\endgroup\$
4
\$\begingroup\$

Retina, 61 55 bytes

^((.)(?<!\2.+))*((){7}((?<-4>)(.)(?!(?<-4>.)*\4\6))*)*$

Since this is just a single regex, Retina will run in Match mode and report the number of matches it found, which will be 1 for valid sequences and 0 otherwise. This isn't competitive compared with the golfing languages, but I'm quite happy with it, seeing I started out with a monster of 260 bytes.

Explanation

^((.)(?<!\2.+))*

This bit consumes a prefix of unique letters of variable length, i.e. it matches the potentially incomplete leading chunk. The lookbehind ensures that any character matched in this bit has not appeared in the string before.

Now for the rest of the input, we want to match chunks of 7 without repeating characters. We could match such a chunk like this:

(.)(?!.{0,5}\1)(.)(?!.{0,4}\2)(.)(?!.{0,3}\3)...(.)(?!.?\5).

I.e. we match a character that doesn't appear for another 6 characters, then one which doesn't appear for another 5 characters and so on. But this requires fairly horrible code repetition, and we'd have to match a trailing (potentially incomplete) chunk separately.

Balancing groups to the rescue! A different way to match

(.)(?!.{0,5}\1)

is to push 5 empty matches onto a capture stack and try emptying it:

(){5}(.)(?!(?<-1>.)*\2)

The * allows a minimum of zero repetitions, just like {0,5}, and because we've pushed five captures, it won't be able to pop more than 5 times either. This is longer for a single instance of this pattern, but this is much more reusable. Since we're doing the popping in a negative lookahead, this doesn't affect the actual stack once the lookahead has completed. So after the lookahead, we've still got 5 elements on the stack, no matter what happened inside. Furthermore, we can simply pop one element from the stack before each lookahead, and run the code in a loop, to automatically decrement the lookahead width from 5 down to 0. So that really long bit up there can actually be shortened to

(){7}((?<-1>)(.)(?!(?<-1>.)*\1\3))*

(You may notice two differences: we're pushing 7 instead of 5. One additional capture is because we pop before each iteration, not after it. The other is actually necessary so that we can pop from the stack 7 times (since we want the loop to run 7 times), we can fix that off-by-one error inside the lookahead by ensuring with the \1 that there is still at least one element left on the stack.)

The beauty of this is that it can also match the trailing incomplete chunk, because we never required it to repeat 7 times (that's just the necessary maximum, because we can't pop from the stack more often than that). So all we need to do is wrap this in another loop and ensure we've reached the end of the string to get

^((.)(?<!\2.+))*((){7}((?<-4>)(.)(?!(?<-4>.)*\4\6))*)*$
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.