38
\$\begingroup\$

Description

We consider a slightly simplified version of Tetris where each move consists of:

  • rotating the piece clockwise, 0 to 3 times
  • positioning the piece at a given column
  • fast drop

The goal is to determine the number of completed lines, given a list of such Tetris moves.

Completed rows are removed as pieces are dropped, following standard Tetris rules.

Playfield

The playfield is 10-column wide. There's no Game Over and it is assumed that there's always enough space and time to perform the above actions, no matter the configuration of the playfield. The height of the playfield doesn't really matter here, but you can use the standard 22 rows as an upper limit.

Shapes of Tetrominoes

shapes

Input / Output

Input

A comma separated list of Tetris moves encoded with 3 characters. The first two character describe the Tetromino shape to use and the last one describes the position where it's dropped.

  1. Tetromino: I, O, T, L, J, Z or S, in the same order as above.
  2. Number of clockwise rotations: 0 to 3
  3. Column: 0 to 9. This is the column in which the top-left corner of the piece (marked with an x on the above picture) is located after the rotation 1

It is assumed that all moves in the provided list are valid. There's no need to check for invalid entries such as I07 (horizontal I shape put too far on the right).

1 You are free to either implement a real rotation algorithm or to hardcode all the different shapes, as long as the x is located in the column given by the third character of the move.

Output

Number of completed lines.

Example

example

O00,T24 will generate the first position and O00,T24,S02,T01,L00,Z03,O07,L06,I05 will generate the second position.

Therefore, the following sequence will generate a Tetris and should return 4:

O00,T24,S02,T01,L00,Z03,O07,L06,I05,I19

Test cases

1) "O00,T24,S02,T01,L00,Z03,O07,L06,I05,I19" -> 4
2) "S00,J03,L27,Z16,Z18,I10,T22,I01,I05,O01,L27,O05,S13" -> 5
3) "I01,T30,J18,L15,J37,I01,S15,L07,O03,O03,L00,Z00,T38,T01,S06,L18,L14" -> 4
4) "S14,T00,I13,I06,I05,I19,L20,J26,O07,Z14,Z10,Z12,O01,L27,L04,I03,S07,I01,T25,J23,J27,O01,
    I10,I10" -> 8
5) "O00,T24,L32,T16,L04,Z11,O06,L03,I18,J30,L23,Z07,I19,T05,T18,L30,I01,I01,I05,T02" -> 8

Test page

You can use this JSFiddle to test a move list.

\$\endgroup\$
17
  • 1
    \$\begingroup\$ What axis are the pieces rotated about? \$\endgroup\$
    – user56309
    Aug 18, 2016 at 18:14
  • 1
    \$\begingroup\$ @Arnauld I suggest you take a look at the super rotation system, and edit the image a teency bit. tetris.wikia.com/wiki/SRS \$\endgroup\$
    – user56309
    Aug 18, 2016 at 18:57
  • 1
    \$\begingroup\$ So, we can treat these as 25 (15 if you don't count duplicates) different shapes, then? \$\endgroup\$
    – user56309
    Aug 18, 2016 at 19:42
  • 1
    \$\begingroup\$ Can solutions take input as an array rather than a comma-separated string? \$\endgroup\$
    – Jordan
    Aug 24, 2016 at 13:46
  • 1
    \$\begingroup\$ This is the best PCG question I've seen for a long time. What a great idea! Best in the subjective sense of interesting and practical and not too big yet not too small. \$\endgroup\$ Jan 20, 2017 at 23:47

4 Answers 4

16
\$\begingroup\$

C, 401 392 383 378 374 351 335 324 320 318 316 305 bytes

d[99]={'3Z3Z',983177049,513351321,1016270793,970073931,~0},*L=d+5,V,s;char c;main(x){B:for(c=0;c[++L]|V;V>>=4)c-=(L[c]=*L|(V&15)<<x)>1022;s-=c;if(scanf("%c%1d%d,",&c,&V,&x)>2)for(V=c^79?d[c/4%5]>>24-V*8:27,V=c^73?V/64%4<<8|V/8%8<<4|V%8:V&32?15:4369;;--L)for(c=4;c--;)if(L[c]>>x&V>>c*4&15)goto B;return s;}

Takes comma-separated input on stdin, returns the score in the exit status.

Requires char to be signed (which is the default for GCC) and requires '3Z3Z' to be interpreted as 861549402 (which is the case for GCC on little endian machines, at least).


Usage example:

echo "O00,T24,S02,T01,L00,Z03,O07,L06,I05,I19" | ./tetris; echo "$?";

High-level explanation:

All shapes except the line can fit in a 3x3 grid with one corner missing:

6 7 -
3 4 5
0 1 2

That means it's easy to store them in a byte each. For example:

- - -         0 0 -
- # -   -->   0 1 0   -->   0b00010111
# # #         1 1 1

(we align each piece to the bottom-left of the box to make dropping it easier)

Since we get at least 4 bytes to an int, this means we can store all 4 rotations of each piece in a single integer, with a special case for the line. We can also fit each row of the game grid into an int (only needs 10 bits), and the currently falling piece into a long (4 lines = 40 bits).


Breakdown:

d[99]={             // General memory
  '3Z3Z',           //  Shape of "S" piece (multi-char literal, value = 861549402)
  983177049,        //  Shape of "T" piece
  513351321,        //  Shape of "Z" piece
  1016270793,       //  Shape of "J" piece
  970073931,        //  Shape of "L" piece
  ~0                //  Bottom of game grid (solid row)
},                  //  Rest of array stores lines in the game
*L=d+5,             // Working line pointer (start >= base of grid)
V,                  // Current piece after expansion (also stores rotation)
s;                  // Current score (global to initialise as 0)
char c;             // Input shape identifier (also counts deleted lines)
main(x){            // "x" used to store x location
  B:                                // Loop label; jumps here when piece hits floor
  for(c=0;c[++L]|V;V>>=4)           // Paint latest piece & delete completed lines
    c-=(L[c]=*L|(V&15)<<x)>1022;
  s-=c;                             // Increment score
  if(scanf("%c%1d%d,",&c,&V,&x)>2)  // Load next command
    for(V=c^79?                     // Identify piece & rotation
          d[c/4%5]>>24-V*8          //  Not "O": load from data
        :27,                        //  Else "O": always 27
        V=c^73?                     // If not "I" (line):
          V/64%4<<8|V/8%8<<4|V%8    //  expand shape to 16-bits
        :                           // Else we are a line:
          V&32?                     //  "I" coincides with "J"; use this to check
               15:4369;             //  horizontal/vertical
        ;--L)                       // Loop from top-to-bottom of grid
      for(c=4;c--;)                 //  Loop through rows of piece
        if(L[c]>>x&V>>c*4&15)       //   If collides with existing piece:
          goto B;                   //    Exit loops
  return s;                         // Return score in exit status
}

-4, -1 thanks to @Titus, and -23, -11 with inspiration from their answer

\$\endgroup\$
17
  • \$\begingroup\$ Nice one! Could you just do s+=(d[A-x]=d[A]) without using x? \$\endgroup\$
    – Arnauld
    Aug 20, 2016 at 16:22
  • \$\begingroup\$ Unfortunately x is needed to keep track of how many rows to collapse in the current step (each row A is set to the value of row A-x as the loop progresses) \$\endgroup\$
    – Dave
    Aug 20, 2016 at 16:49
  • \$\begingroup\$ D'oh! My bad. Sorry for such a silly suggestion. :) \$\endgroup\$
    – Arnauld
    Aug 20, 2016 at 17:12
  • 1
    \$\begingroup\$ @Titus it's an abuse of C's array indexing. Put simply, 1[a] and a[1] do the same thing (or more precisely, a[b] translates to *(a+b)). It's abused like this as a way of avoiding brackets. In this case, 1[*v] == (*v)[1], i.e. the second letter of the command, i.e. the rotation. \$\endgroup\$
    – Dave
    Aug 24, 2016 at 18:14
  • 1
    \$\begingroup\$ Can you get rid of the I placeholder? If so, try /2%9 as hash instead of %12. %12%8 if not. \$\endgroup\$
    – Titus
    Aug 24, 2016 at 22:26
5
\$\begingroup\$

PHP, 405 399 378 372 368 360 354 347 331 330 328 319 309 300 bytes

(with Dave´s block mapping)

<?$f=[~0];L:for($y=0;$f[++$d+$y]|$s;$s>>=4)$y-=1022<$f[$d+$y]=$f[$d]|$s%16<<$x;$c-=$y;if(list($p,$r,$x)=$argv[++$z])for($s=I==$p?$r&1?4369:15:hexdec(decoct(O==$p?27:ord(base64_decode('M1ozWjqaF1kemR6ZPJMPyTnSJ0s')[ord($p)/4%5*4+$r])));;$d--)for($y=4;$y--;)if ($f[$d+$y]>>$x&$s>>$y*4&15)goto L;echo$c;

program, takes moves as separate arguments, prints result

breakdown to function:

takes moves as array, returns result

function t($a)
{
    $f=[~$z=0];             // init field $f (no need to init $z in golfed version)
    L:                      // jump label
                            // A: paint previous piece at line $d+1:
#   if($s)paint($f,$s,$d+1,$x);
    for($y=0;               // $y = working line offset and temporary score
        $f[++$d-$y]|$s;$s>>=4)// next field line; while field or piece have pixels ...
        $s>>=4)                 // next piece line
        $y+=1022<               // 3: decrease temp counter if updated line is full
            $f[$d-$y]=$f[$d]    // 2: use $y to copy over dropped lines
                |$s%16<<$x;     // 1: set pixels in working line
    $c+=$y;                         // add temp score to global score
#   paint($f);var_dump($c);
    if(list($p,$r,$x)=$a[$z++])// B: next piece: $p=name; $r=rotation, $x=column
#   {echo"<b>$z:$p$r-$x</b><br>";
        for(                // C: create base 16 value:
            $s=I==$p
                ? $r&1?4369:15  // I shape (rotated:0x1111, not rotated:0xf)
                : hexdec(decoct(    // 5: convert from base 8 to base 16
                    O==$p ? 27  // O shape (rotation irrelevant: 033)
                    : ord(          // 4: cast char to byte
                                    // 0: 4 bytes for each remaining tetromino
                        base64_decode('M1ozWjqaF1kemR6ZPJMPyTnSJ0s')[
                            ord($p)/4%5 // 1: map STZJL to 01234
                            *4      // 2: tetromino offset
                            +$r]    // 3: rotation offset
            )));;$d--
        )
            for($y=4;$y--;) // D: loop $y through piece lines
                if ($f[$d+$y]>>$x & $s>>$y*4 & 15) // if collision ...
                    goto L;         // goto Label: paint piece, tetris, next piece
#   }
    return$c;               // return score
}

for reference: the old mapping

            hexdec(decoct(          // 3. map from base 8 to base 16
                                    // 0. dword values - from high to low: rotation 3,2,1,0
                [0x991e991e,0xc90f933c,0x4b27d239,0x1b1b1b1b,0,0x5a335a33,0x59179a3a]
                [ord($m[0])/2%9]    // 1. map ZJLO.ST to 0123.56 -> fetch wanted tetromino
                >>8*$m[1]&255       // 2. the $m[1]th byte -> rotated piece
            ))

testing

see my other PHP answer

want to watch?

remove the # from the function source and add this:

function paint($f,$s=0,$d=0,$x=0){echo'<pre>';for($y=count($f)+5;$y--;$g=0)if(($t=(($z=$y-$d)==$z&3)*($s>>4*$z&15)<<$x)|$r=$f[$y]|0){$z=$t?" $r|$t=<b".(1022<($z=$t|$r)?' style=color:green':'').">$z":" <b>$r";for($b=1;$b<513;$b*=2)$z=($t&$b?'<b>'.($r&$b?2:1).'</b>':($r&$b?1:'.')).$z;printf("%02d $z</b>\n",$y);}echo'</pre>';}

some golfing steps

Rev. 5: A big leap (399-21=378) came by simply moving the column shift
from a separate loop to the two existing loops.

Rev. 8: Switching from array to base 16 for the piece ($s) did not give much,
but made way for some more golfing.

Rev. 17: crunched the values with base64_encode(pack('V*',<values>))
and used byte indexing instead of unpack to save 16 bytes

Rev. 25 to 29: inspired by Dave´s code: new hashing (-2), new loop design (-9), goto (-10)
no pre-shift though; that would cost 17 bytes.

more potential

With /2%9, I could save 15 bytes (only 14 bytes with /4%5)
by putting binary data into a file b and then indexing file(b)[0].
Do I want that?

UTF-8 characters would cost a lot for the transformation.

on the hashing

I used ZJLO.ST /2%9 -> 0123.56; but T.ZJLOS /3%7 -> 0.23456 is as good.
one byte longer: O.STJLZ %13/2 -> 0.23456
and three more: OSTZJ.L %17%12%9 -> 01234.6

I could not find a short hash (max. 5 bytes) that leaves no gap;
but Dave found STZJL /4%5 -> 01234, dropping the O from the list. wtg!

btw: TIJSL.ZO (%12%8) -> 01234.67 leaves room for the I shape
(and a fictional A, M or Y shape). %28%8 and %84%8, do the same (but with E instead of A).

\$\endgroup\$
6
  • \$\begingroup\$ Nice; I like the combined painting+line detection, and the break 2 is much cleaner than what I had to do in C! You might be able to save some bytes by using array_diff (set completed lines to a fixed value instead of using unset then replace array_values with array_diff), but I can't tell from the docs if that would flatten repeated values (e.g. array_diff([1,2,2,3],[1]) -> [2,2,3] or just [2,3]) \$\endgroup\$
    – Dave
    Aug 24, 2016 at 18:29
  • \$\begingroup\$ @Dave: array_diff does not remove duplicate values; and I already have the fixed value (1023); but it does not reindex the array. Great idea, but it would cost a byte. \$\endgroup\$
    – Titus
    Aug 24, 2016 at 18:56
  • \$\begingroup\$ wow that was a loud whoosh as you flew past me! Looks like I've got some catching up to do! \$\endgroup\$
    – Dave
    Aug 26, 2016 at 17:17
  • \$\begingroup\$ Congrats on reaching 300! I'll implement your latest suggested change (hadn't thought to simplify the rotation check now that I don't need /10 all over the place), but otherwise I think I'm done. I'm surprised at how directly competitive PHP and C turned out to be. This was fun — hope the OP accepts your answer! \$\endgroup\$
    – Dave
    Aug 30, 2016 at 18:27
  • \$\begingroup\$ @Dave & Titus - I wish I could accept both answers. You guys did a great job. Congrats anyway to Titus for reaching 300. And I think that's actually 299 since you have a useless space after a if. \$\endgroup\$
    – Arnauld
    Sep 1, 2016 at 21:58
2
\$\begingroup\$

Ruby, 474 443 428 379 + 48 = 427 bytes

-1 thanks to @Titus

This can definitely be golfed more.

Reads a binary dictionary of pieces (see below) from STDIN or a filename and takes a move list as an argument, e.g. $ cat pieces | ruby script.rb O00,T24,S02,....

q=$*.pop
z=$<.read.unpack('S*')
b=c=g=i=0
x=10
u=1023
r=->n{n&2**x-1>0?n:r[n>>x]}
y=->n{n>0?[n&u]+y[n>>x]:[]}
l=->c,n{z.find{|m|m>>x==c<<2|n.to_i}||l[c,n-2]}
q.scan(/(\w)(\d)(\d)/){n=l["IOTLJSZ".index($1),$2.to_i]
v=(n&1|(n&6)<<9|(n&56)<<17|(n&960)<<24)<<$3.to_i
(y[b].size+1).times{t=b<<40
t&v>0&&break
g=t|v
v<<=x}
b=0
a=y[r[g]]
a.grep_v(u){|o|b|=o<<x*i
i+=1}
c+=a.count u}
p c

Binary piece data (xxd format)

0000000: c003 4b04 d810 d814 b820 9c24 d029 5a2c  ..K...... .$.)Z,
0000010: 7830 9634 e039 ca3c 3841 d444 c849 4e4c  x0.4.9.<8A.D.INL
0000020: 9861 9869 5c64 5c6c f050 f058 9a54 9a5c  .a.i\d\l.P.X.T.\

See it on repl.it (with hard-coded arguments, dictionary): https://repl.it/Cqft/2

Ungolfed & explanation

# Move list from ARGV
q = $*.pop

# Read piece dictionary; pieces are 16-bit integers: 3 for letter,
# 2 for rotation, 10 for shape (and 1 wasted)
z = $<.read.unpack('S*')

# Empty board and various counters
b = c = g = i = 0
x = 10 # Magic numbers
u = 1023

# A function to remove empty lines
r = ->n{ n & 2**x - 1 > 0 ? n : r[n >> x] }

# A function to split the board into lines
y = ->n{ n > 0 ? [n & u] + y[n >> x] : [] }

# A function to lookup a piece by letter and rotation index
l = ->c,n{ z.find {|m| m >> x == c << 2 | n.to_i } || l[c, n-2] }

# Read the move list
q.scan(/(\w)(\d)(\d)/) {
  # Look up the piece
  n = l["IOTLJSZ".index($1), $2.to_i]

  # Convert the 10-bit piece to a 40-bit piece (4 rows of 10 columns)
  v = (n & 1 |
        (n & 6) << 9 |
        (n & 56) << 17 |
        (n & 960) << 24
      ) << $3.to_i # Shift by the appropriate number of columns

  # Drop the piece onto the board
  (y[b].size + 1).times {
    t = b << 40
    t & v > 0 && break
    g = t | v
    v <<= x
  }

  # Clear completed rows
  b = 0
  a = y[r[g]]
  a.grep_v(u) {|o|
    b |= o << x * i
    i += 1
  }

  c += a.count u # Count cleared rows
}
p c
\$\endgroup\$
3
  • \$\begingroup\$ 1 byte: m >> 10 could be m >> x \$\endgroup\$
    – Titus
    Aug 24, 2016 at 17:54
  • \$\begingroup\$ @Titus Good eye. Thanks! \$\endgroup\$
    – Jordan
    Aug 24, 2016 at 17:57
  • \$\begingroup\$ No need to explicitly require \ds in the regular expression: /(\w)(\d)(\d)//(\w)(.)(.)/ \$\endgroup\$
    – manatwork
    Aug 25, 2016 at 9:34
2
\$\begingroup\$

PHP, 454 435 427 420 414 bytes

bit fields for pieces and map; but no special case for the I shape as Dave´s golfing.

<?$t=[I=>[15,4369],O=>[51],T=>[114,562,39,305],L=>[113,802,71,275],J=>[116,547,23,785],Z=>[54,561],S=>[99,306]];foreach($argv as$z=>$m)if($z){$s=$t[$m[0]][$m[1]%count($t[$m[0]])];for($d=$i=0;$i<4;$i++)for($k=0;$k<4;$k++)if($s>>4*$k&1<<$i){for($y=0;$y++<count($f);)if($f[$y-1]&1<<$m[2]+$i)$d=max($d,$y-$k);$k=3;}for($k=$d;$s;$k++,$s>>=4)if(1022<$f[$k]|=$s%16<<$m[2]){$c++;unset($f[$k]);}$f=array_values($f);}echo$c;

takes arguments from command line, prints result

ungolfed as function

takes arguments as array, returns result

function t($a)
{
    // bitwise description of the stones and rotations
    $t=[I=>[15,4369],O=>[51],T=>[114,562,39,305],L=>[113,802,71,275],J=>[116,547,23,785],Z=>[54,561],S=>[99,306]];
    foreach($a as$m)
    {
        $s=$t[$m[0]][$m[1]%count($t[$m[0]])];   // $s=stone
        // find dropping space
        for($d=$i=0;$i<4;$i++)
            // a) lowest pixel of stone in column i
            for($k=0;$k<4;$k++)
                if($s>>4*$k&1<<$i)
                {
                    // b) top pixel of field in column x+i 
                    for($y=0;$y++<count($f);)
                        if($f[$y-1]&1<<$m[2]+$i)$d=max($d,$y-$k);
                    $k=3; // one byte shorter than `break;`
                }
        // do drop
        for($k=$d;$s;$k++,$s>>=4)
            if(1022<$f[$k]|=$s%16<<$m[2])   // add block pixels to line pixels ... if full,
            {$c++;unset($f[$k]);}           // tetris
        $f=array_values($f);
    }
    return$c;
}

tests (on function)

$data=[
    "O00,T24,S02,T01,L00,Z03,O07,L06,I05,I19"=>4,
    "S00,J03,L27,Z16,Z18,I10,T22,I01,I05,O01,L27,O05,S13" => 5,
    "I01,T30,J18,L15,J37,I01,S15,L07,O03,O03,L00,Z00,T38,T01,S06,L18,L14" => 4,
    "S14,T00,I13,I06,I05,I19,L20,J26,O07,Z14,Z10,Z12,O01,L27,L04,I03,S07,I01,T25,J23,J27,O01,I10,I10" => 8,
    // additional example for the two last tetrominoes:
    'O00,T24,L32,T16,L04,Z11,O06,L03,I18,J30,L23,Z07,I19,T05,T18,L30,I01,I01,I05,T02' => 8,
];
function out($a){if(is_object($a)){foreach($a as$v)$r[]=$v;return'{'.implode(',',$r).'}';}if(!is_array($a))return$a;$r=[];foreach($a as$v)$r[]=out($v);return'['.join(',',$r).']';}
function cmp($a,$b){if(is_numeric($a)&&is_numeric($b))return 1e-2<abs($a-$b);if(is_array($a)&&is_array($b)&&count($a)==count($b)){foreach($a as $v){$w = array_shift($b);if(cmp($v,$w))return true;}return false;}return strcmp($a,$b);}
function test($x,$e,$y){static $h='<table border=1><tr><th>input</th><th>output</th><th>expected</th><th>ok?</th></tr>';echo"$h<tr><td>",out($x),'</td><td>',out($y),'</td><td>',out($e),'</td><td>',cmp($e,$y)?'N':'Y',"</td></tr>";$h='';}
foreach($data as $v=>$e)
{
    $x=explode(',',$v);
    test($x,$e,t($x));
}
\$\endgroup\$
2
  • \$\begingroup\$ 427? You're on! \$\endgroup\$
    – Jordan
    Aug 24, 2016 at 13:47
  • \$\begingroup\$ @Jordan: and those 427 include the <? overhead :) \$\endgroup\$
    – Titus
    Aug 24, 2016 at 17:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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