Code Golf: Playing Tetris

Question

Locked. This question and its answers are locked because the question is off-topic but has historical significance. It is not currently accepting new answers or interactions.

The basics:

Consider the following tetrominoes and empty playing field:

                                            0123456789
    I   O    Z    T    L    S    J         [          ]
                                           [          ]
    #   ##   ##   ###  #     ##   #        [          ]
    #   ##    ##   #   #    ##    #        [          ]
    #                  ##        ##        [          ]
    #                                      [          ]
                                           [==========]

The dimensions of the playing field are fixed. The numbers at the top are just here to indicate the column number (also see input).

Input:

1. You are given a specific playing field (based on the above) which can already be filled partly with tetrominoes (this can be in a separate file or provided via stdin).

Sample input:

[          ]
[          ]
[          ]
[          ]
[ #    #  #]
[ ## ######]
[==========]

2. You are given a string which describes (separated by spaces) which tetromino to insert (and drop down) at which column. Tetrominoes don't need to be rotated. Input can be read from stdin.

Sample input:

T2 Z6 I0 T7

You can assume input is 'well-formed' (or produce undefined behaviour when it's not).

Output

Render the resulting field ('full' lines must disappear) and print the score count (every dropped line accounts for 10 points).

Sample output based on the sample input above:

[          ]
[          ]
[          ]
[#      ###]
[#     ### ]
[##### ####]
[==========]
10

Winner:

Shortest solution (by code character count). Usage examples are nice. Have fun golfing!

Edit: added a bounty of +500 reputation to draw some more attention to the nice efforts the answerers already made (and possibly some new solutions to this question)...

Answer 1

Perl, 586 523 483 472 427 407 404 386 387 356 353 chars

(Needs Perl 5.10 for the defined-or // operator).

Takes all input from stdin. Still needs some serious golfing.
Note that ^Q represents ASCII 17 (DC1/XON), ^C represents ASCII 3 and ^@ represents ASCII 0 (NUL).

while(<>){push@A,[split//]if/]/;while(/\w/g){for$i(0..6){for($f=0,$j=4;$j--;){$c=0;map{if($_){$i--,$f=$j=3,redo if$A[$k=$i+$j][$C=$c+$'+1]ne$";$A[$k][$C]="#"if$f}$c++}split//,unpack"b*",chr vec"3^@'^@c^@^Q^C6^@\"^C^Q^Q",index(OTZLSJI,$&)*4+$j,4;$s+=10,@A[0..$k]=@A[$k,0..$k-1],map{s/#/ /}@{$A[0]},$i++if 9<grep/#/,@{$A[$k]}}last if$f}}}print+(map@$_,@A),$s//0,$/

Commented version:

while(<>){
    # store the playfield as an AoA of chars
    push@A,[split//]if/]/;
    # while we're getting pieces
    while(/\w/g){
            # for each line of playfield
            for$i(0..6){
                    # for each line of current piece
                    for($f=0,$j=4;$j--;){
                            # for each column of current piece
                            $c=0;
                            map{
                                    if($_){
                                            # if there's a collision, restart loop over piece lines
                                            # with a mark set and playfield line decremented
                                            $i--,$f=$j=3,redo if$A[$k=$i+$j][$C=$c+$'+1]ne$";
                                            # if we already found a collision, draw piece
                                            $A[$k][$C]="#"if$f
                                    }
                                    $c++
                            # pieces are stored as a bit vector, 16 bits (4x4) per piece,
                            # expand into array of 1's and 0's
                            }split//,unpack"b*",chr vec"3^@'^@c^@^Q^C6^@\"^C^Q^Q",index(OTZLSJI,$&)*4+$j,4;
                            # if this playfield line is full, remove it. Done by array slicing
                            # and substituting all "#"'s in line 0 with " "'s
                            $s+=10,@A[0..$k]=@A[$k,0..$k-1],map{s/#/ /}@{$A[0]},$i++if 9<grep/#/,@{$A[$k]}
                    }
                    # if we found a collision, stop iterating over the playfield and get next piece from input
                    last if$f
            }
    }
}
# print everything
print+(map@$_,@A),$s//0,$/

Edit 1: some serious golfing, fix output bug.
Edit 2: some inlining, merged two loops into one for a net saving of (drum roll...) 3 chars, misc golfing.
Edit 3: some common subexpression elimination, a little constant merging and tweaked a regex.
Edit 4: changed representation of tetrominoes into a packed bit vector, misc golfing.
Edit 5: more direct translation from tetromino letter to array index, use non-printable characters, misc golfing.
Edit 6: fixed bug cleaning top line, introduced in r3 (edit 2), spotted by Nakilon. Use more non-printable chars.
Edit 7: use vec for getting at tetromino data. Take advantage of the fact that the playfield has fixed dimensions. if statement => if modifier, the merging of loops of edit 2 starts paying off. Use // for the 0-score case.
Edit 8: fixed another bug, introduced in r6 (edit 5), spotted by Nakilon.
Edit 9: don't create new references when clearing lines, just move references around via array slicing. Merge two map's into one. Smarter regex. "Smarter" for. Misc golfings.
Edit 10: inlined tetromino array, added commented version.

Answer 2

C, 727 [...] 596 581 556 517 496 471 461 457 chars

This is my first code golf, I think character count can get much lower, would be nice if experienced golfers can give me some hints.

The current version can handle playfields with different dimensions, too. The input can have linebreaks in both DOS/Windows and Unix format.

The code was pretty straightforward before optimization, the tetrominoes are stored in 4 integers that are interpreted as an (7*3)x4 bit array, the playfield is stored as-is, tiles are dropped and complete lines are removed at start and after each tile drop.

I wasn't sure how to count characters, so I used the filesize of the code with all unneccessary linebreaks removed.

EDIT 596=>581: Thanks to KitsuneYMG, everything except the %ls suggestion worked perfectly, additionally, I noticed putch instead of putchar can be used (getch somehow doesn't work) and removed all the parentheses in #define G.

EDIT 581=>556: Wasn't satisfied with the remaining for and the nested F loops, so there was some merging, changing and removing of loops, quite confusing but definitely worth it.

EDIT 556=>517: Finally found a way to make a an int array. Some N; merged with c, no break anymore.

EDIT 496=>471: Playfield width and height fixed now.

EDIT 471=>461: Minor modifications, putchar used again as putch is no standard function.

EDIT: Bugfix, complete lines were removed before tile drop instead of after, so complete lines could be left at the end. Fix doesn't change the character count.

#define N (c=getchar())
#define G T[j%4]&1<<t*3+j/4
#define X j%4*w+x+j/4
#define F(x,m) for(x=0;x<m;x++)
#define W while
T[]={916561,992849,217,1},C[99],c,i,j,s,t,x,A,a[99],w=13;
main(){F(j,7)C["IJLSTZO"[j]]=j;
F(j,91)a[j]=N;
W(N>w){t=C[c];x=N-86;
W(c){F(j,12)if(G&&X>1?a[X]-32:0)c=0;
F(j,12)if(G&&X>w&&!c)a[X-w]=35;x+=w;}N;
F(i,6){A=0;t=i*w;F(x,w)A|=(a[t+x]==32);
if(!A){s++;F(j,t)a[t+w-j]=a[t-j];
x=1;W(a[x]-93)a[x++]=32;}}}
F(i,91)putchar(a[i]);printf("%i0",s);}

Answer 3

Python 2.6+ - 334 322 316 characters

^{397 368 366 characters uncompressed}

#coding:l1
exec'xÚEPMO!½ï¯ i,P*Ýlš%ì­‰=‰Ö–*†­þz©‰:‡—Lò¾fÜ”bžAù,MVi™.ÐlǃwÁ„eQL&•uÏÔ‹¿1O6ǘ.€LSLÓ’¼›î”3òšL¸tŠv[ѵl»h;ÁºŽñÝ0Àë»Ç‡ÛûH.ª€¼âBNjr}¹„V5¾3Dë@¼¡•gO. ¾ô6 çÊsÃЮürÃ1&›ßVˆ­ùZ`Ü€ÿžcx±ˆ‹sCàŽ êüRô{U¯ZÕDüE+³ŽFA÷{CjùYö„÷¦¯Î[0þøõ…(Îd®_›â»E#–Y%’›”ëýÒ·X‹d¼.ß9‡kD'.decode('zip')

The single newline is required, and I've counted it as one character.

Browser code-page mumbo jumbo might prevent a successful copy-and-paste of this code, so you can optionally generate the file from this code:

s = """
23 63 6F 64 69 6E 67 3A 6C 31 0A 65 78 65 63 27 78 DA 45 50 4D 4F 03 21
10 BD EF AF 20 69 2C 50 2A 02 DD 6C 9A 25 EC AD 07 8D 89 07 3D 89 1C D6
96 2A 86 05 02 1B AD FE 7A A9 89 3A 87 97 4C F2 BE 66 DC 94 62 9E 41 F9
2C 4D 56 15 69 99 0F 2E D0 6C C7 83 77 C1 16 84 65 51 4C 26 95 75 CF 8D
1C 15 D4 8B BF 31 4F 01 36 C7 98 81 07 2E 80 4C 53 4C 08 D3 92 BC 9B 11
EE 1B 10 94 0B 33 F2 9A 1B 4C B8 74 8A 9D 76 5B D1 B5 6C BB 13 9D 68 3B
C1 BA 8E F1 DD 30 C0 EB BB C7 87 DB FB 1B 48 8F 2E 1C AA 80 19 BC E2 42
4E 6A 72 01 7D B9 84 56 35 BE 33 44 8F 06 EB 40 BC A1 95 67 4F 08 2E 20
BE F4 36 A0 E7 CA 73 C3 D0 AE FC 72 C3 31 26 9B DF 56 88 AD F9 5A 60 DC
80 FF 9E 63 78 B1 88 8B 73 43 E0 8E A0 EA FC 52 F4 7B 55 8D AF 5A 19 D5
44 FC 45 2B B3 8E 46 9D 41 F7 7B 43 6A 12 F9 59 F6 84 F7 A6 01 1F AF CE
5B 30 FE F8 F5 85 28 CE 64 AE 5F 9B E2 BB 45 23 96 59 25 92 9B 94 EB FD
10 D2 B7 58 8B 64 BC 2E DF 39 87 6B 44 27 2E 64 65 63 6F 64 65 28 27 7A
69 70 27 29
"""

with open('golftris.py', 'wb') as f:
    f.write(''.join(chr(int(i, 16)) for i in s.split()))

---

Testing

intetris

[          ]
[          ]
[          ]
[          ]
[ #    #  #]
[ ## ######]
[==========]
T2 Z6 I0 T7

Newlines must be Unix-style (linefeed only). A trailing newline on the last line is optional.

To test:

> python golftris.py < intetris
[          ]
[          ]
[          ]
[#      ###]
[#     ### ]
[##### ####]
[==========]
10

---

This code unzips the original code, and executes it with exec. This decompressed code weighs in at 366 characters and looks like this:

import sys
r=sys.stdin.readlines();s=0;p=r[:1];a='[##########]\n'
for l in r.pop().split():
 n=int(l[1])+1;i=0xE826408E26246206601E>>'IOZTLSJ'.find(l[0])*12;m=min(zip(*r[:6]+[a])[n+l].index('#')-len(bin(i>>4*l&31))+3for l in(0,1,2))
 for l in range(12):
  if i>>l&2:c=n+l/4;o=m+l%4;r[o]=r[o][:c]+'#'+r[o][c+1:]
 while a in r:s+=10;r.remove(a);r=p+r
print''.join(r),s

Newlines are required, and are one character each.

Don't try to read this code. The variable names are literally chosen at random in search of the highest compression (with different variable names, I saw as much as 342 characters after compression). A more understandable version follows:

import sys

board = sys.stdin.readlines()
score = 0
blank = board[:1] # notice that I rely on the first line being blank
full  = '[##########]\n'

for piece in board.pop().split():
    column = int(piece[1]) + 1 # "+ 1" to skip the '[' at the start of the line

    # explanation of these three lines after the code
    bits = 0xE826408E26246206601E >> 'IOZTLSJ'.find(piece[0]) * 12
    drop = min(zip(*board[:6]+[full])[column + x].index('#') -
               len(bin(bits >> 4 * x & 31)) + 3 for x in (0, 1, 2))

    for i in range(12):
        if bits >> i & 2: # if the current cell should be a '#'
            x = column + i / 4
            y = drop + i % 4
            board[y] = board[y][:x] + '#' + board[y][x + 1:]

    while full in board:      # if there is a full line,
        score += 10           # score it,
        board.remove(full)    # remove it,
        board = blank + board # and replace it with a blank line at top

print ''.join(board), score

The crux is in the three cryptic lines I said I'd explain.

The shape of the tetrominoes is encoded in the hexadecimal number there. Each tetronimo is considered to occupy a 3x4 grid of cells, where each cell is either blank (a space) or full (a number sign). Each piece is then encoded with 3 hexadecimal digits, each digit describing one 4-cell column. The least significant digits describe the left-most columns, and the least significant bit in each digit describes the top-most cell in each column. If a bit is 0, then that cell is blank, otherwise it's a '#'. For example, the I tetronimo is encoded as 00F, with the four bits of the least-significant digit set on to encode the four number signs in the left-most column, and the T is 131, with the top bit set on the left and the right, and the top two bits set in the middle.

The entire hexadecimal number is then shift one bit to the left (multiplied by two). This will allow us to ignore the bottom-most bit. I'll explain why in a minute.

So given the current piece from the input, we find the index into this hexadecimal number where the 12 bits describing it's shape begin, then shift that down so that bits 1–12 (skipping bit 0) of the bits variable describe the current piece.

The assignment to drop determines how many rows from the top of the grid the piece will fall before landing on other piece fragments. The first line finds how many empty cells there are at the top of each column of the playing field, while the second finds the lowest occupied cell in each column of the piece. The zip function returns a list of tuples, where each tuple consists of the n^th cell from each item in the input list. So, using the sample input board, zip(board[:6] + [full]) will return:

[
 ('[', '[', '[', '[', '[', '[', '['),
 (' ', ' ', ' ', ' ', ' ', ' ', '#'),
 (' ', ' ', ' ', ' ', '#', '#', '#'),
 (' ', ' ', ' ', ' ', ' ', '#', '#'),
 (' ', ' ', ' ', ' ', ' ', ' ', '#'),
 (' ', ' ', ' ', ' ', ' ', '#', '#'),
 (' ', ' ', ' ', ' ', ' ', '#', '#'),
 (' ', ' ', ' ', ' ', '#', '#', '#'),
 (' ', ' ', ' ', ' ', ' ', '#', '#'),
 (' ', ' ', ' ', ' ', ' ', '#', '#'),
 (' ', ' ', ' ', ' ', '#', '#', '#'),
 (']', ']', ']', ']', ']', ']', ']')
]

We select the tuple from this list corresponding to the appropriate column, and find the index of the first '#' in the column. This is why we appended a "full" row before calling zip, so that index will have a sensible return (instead of throwing an exception) when the column is otherwise blank.

Then to find the lowest '#' in each column of the piece, we shift and mask the four bits that describe that column, then use the bin function to turn that into a string of ones and zeros. The bin function only returns significant bits, so we need only calculate the length of this string to find the lowest occupied cell (most significant set bit). The bin function also prepends '0b', so we have to subtract that. We also ignore the least significant bit. This is why the hexadecimal number is shift one bit to the left. This is to account for empty columns, whose string representations would have the same length as a column with only the top cell full (such as the T piece).

For example, the columns of the I tetromino, as mentioned earlier, are F, 0, and 0. bin(0xF) is '0b1111'. After ignoring the '0b', we have a length of 4, which is correct. But bin(0x0) is 0b0. After ignoring the '0b', we still have a length of' 1, which is incorrect. To account for this, we've added an additional bit to the end, so that we can ignore this insignificant bit. Hence, the +3 in the code is there to account for the extra length taken up by the '0b' at the beginning, and the insignificant bit at the end.

All of this occurs within a generator expression for three columns ((0,1,2)), and we take the min result to find the maximum number of rows the piece can drop before it touches in any of the three columns.

The rest should be pretty easy to understand by reading the code, but the for loop following these assignments adds the piece to the board. After this, the while loop removes full rows, replacing them with blank rows at the top, and tallies the score. At the end, the board and score are printed to the output.

Answer 4

Golfscript 260 chars

I'm sure this could be improved, I'm kind of new to Golfscript.

[39 26.2/0:$14{.(}:?~1?15?1?14 2??27?13.!14?2?27?14 1]4/:t;n/)\n*:|;' '/-1%.,:c;~{)18+:&;'XIOZTLSJX'\%~;,1-t\={{.&+.90>{;.}*|\=32=!{&13-:&;}*}%}6*{&+}/|{\.@<'#'+\)|>+}4*{'['\10*']'++}:
;n/0\~n+:|;0\{.'#'
={;)}{n+|+:|;}if\.}do;' '
n+\.@*|+\$+:$;.,1-<:|;}c*|n?$*

End of lines are relevant (there shouldn't be one at the end). Anyway, here are some of the test cases I used:

> cat init.txt 
[          ]
[          ]
[          ]
[          ]
[ #    #  #]
[ ## ######]
[==========]
T2 Z6 I0 T7> cat init.txt | ruby golfscript.rb tetris.gsc
[          ]
[          ]
[          ]
[#      ###]
[#     ### ]
[##### ####]
[==========]
10

> cat init.txt
[          ]
[          ]
[          ]
[          ]
[ #    #  #]
[ ## ##### ]
[==========]
I0 O7 Z1 S4> cat init.txt | ruby golfscript.rb tetris.gsc
[          ]
[          ]
[          ]
[#         ]
[###  #### ]
[### ##### ]
[==========]
10

> cat init.txt
[          ]
[          ]
[          ]
[ ## ###   ]
[ #    #   ]
[ ## ######]
[==========]
T7 I0 I3> cat init.txt | ruby golfscript.rb tetris.gsc
[          ]
[          ]
[          ]
[          ]
[#  #      ]
[## #  # # ]
[==========]
20

Note that there is no end of line in the input file, an end of line would break the script as is.

Answer 5

Ruby — 427 408 398 369 359

t=[*$<]
o=0
u=->f{f.transpose}
a=u[t.reverse.join.scan /#{'( |#)'*10}/]
t.pop.split.map{|w|m=(g='I4O22Z0121T01201L31S1201J13'[/#{w[0]}\d+/].scan(/0?\d/).zip a.drop w[1].to_i).map{|r,b|(b.rindex ?#or-1)-r.size+1}.max
g.map{|r,b|b.fill ?#,m+r.size,r.to_i}
v=u[a]
v.reject!{|i|i-[?#]==[]&&(o+=10;v)<<[' ']*10}
a=u[v]}
puts u[a].reverse.map{|i|?[+i*''+?]},t[-1],o

Answer 6

Ruby 505 479 474 442 439 426 chars

A first attempt. Have done it with IronRuby. I'm sure it can be improved, but I really should get some work done today!

p,q,r,s=(0..9),(0..2),(0..6),0
t=[*$<]
f=p.map{|a|g=0;r.map{|b|g+=2**b if t[6-b][a+1]==?#};g}
t.pop.split.map{|x|w,y=[15,51,306,562,23,561,113]["IOZTLSJ"=~/#{x[0]}/],x[1].to_i
l=q.map{|d|r.inject{|b,c|f[d+y]&(w>>(d*4)&15-c+1)>0?c:b}}.max
q.map{|b|f[b+y]|=w>>(b*4)&15-l}
r.map{i=f.inject{|a,b|a&b};f.map!{|a|b=i^(i-1);a=((a&~b)>>1)+(a&(b>>1))};s+=i>0?10:0}}
p.map{|a|r.map{|b|t[6-b][a+1]=f[a]&2**b>0??#:' '}}
puts t,s

Testing

cat test.txt | ruby tetris.rb
[          ]
[          ]
[          ]
[          ]
[#      ###]
[#     ### ]
[##### ####]
[==========]
10

Edit Now using normal ruby. Got the walls output..