Code Golf: Playing Tetris
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)...
Solution 1:
GolfScript - 181 characters
Newlines are not necessary. Output is in standard output, although some errors are present in stderr.\10 should be replaced by the corresponding ASCII character for the program to be 181 characters.
{):X!-{2B{" #"=}%X" ":f*+-1%}%:P;:>.{\!:F;>P{\(@{3&\(@.2$&F|:F;|}%\+}%\+F![f]P+:P
;}do;{"= "&},.,7^.R+:R;[>0="#"/f*]*\+}0"R@1(XBc_""~\10"{base}:B/3/~4*"nIOZTLSJR "
";:"*~;n%)n*~ 10R*+n*
Sample I/O:
$ cat inp
[ ]
[ ]
[ ]
[ ]
[ # # #]
[ ## ######]
[==========]
T2 Z6 I0 T7
$ cat inp|golfscript tetris.gs 2>/dev/null
[ ]
[ ]
[ ]
[# ###]
[# ### ]
[##### ####]
[==========]
10
Tetromino compression:
Pieces are stored as three base 8 digits. This is a simple binary representation, e.g.T=[7,2,0], S=[6,3,0], J=[2,2,3]. [1] is used for the I piece in compression, but this is explicitly set to [1,1,1,1] later (i.e. the 4* in the code). All of these arrays are concatenated into a single array, which is converted into an integer, and then a string (base 126 to minimize non-printable characters, length, and not encounter utf8). This string is very short: "R@1(XBc_".
Decompression is then straightforward. We first do a base 126 conversion followed by a base 8 conversion ("~\10"{base}/, i.e. iterate through "~\10" and do a base conversion for each element). The resulting array is split into groups of 3, the array for I is fixed (3/~4*). We then convert each element to base 2 and (after removing zeros) replace each binary digit with the character of that index in the string " #" (2base{" #"=}%...-1% - note that we need to reverse the array otherwise 2 would become "# " instead of " #").
Board/piece format, dropping pieces
The board is simply an array of strings, one for each line. No work is initially done on this, so we can generate it with n/( on the input. Pieces are also arrays of strings, padded with spaces to the left for their X position, but without trailing spaces. Pieces are dropped by prepending to the array, and continuously testing whether there is a collision.
Collision testing is done by iterating through all characters in the piece, and comparing against the character of the same position on the board. We want to regard #+= and #+# as collisions, so we test whether ((piecechar&3)&boardchar) is nonzero. While doing this iteration, we also update (a copy of) the board with ((piecechar&3)|boardchar), which correctly sets the value for pairs #+, +#, +[. We use this updated board if there is a collision after moving the piece down another row.
Removing filled rows is quite simple. We remove all rows for which "= "& return false. A filled row will have neither = or , so the conjunction will be a blank string, which equates to false. Then we count the number of rows that have been removed, add the count to the score and prepend that many "[ ... ]"s. We generate this compactly by taking the first row of the grid and replacing # with .
Bonus
Since we compute what the board would look like in each position of the piece as it falls, we can keep these on the stack instead of deleting them! For a total of three characters more, we can output all these positions (or two characters if we have the board states single spaced).
{):X!-{2B{" #"=}%X" ":f*+-1%}%:P;:>.{>[f]P+:P(!:F;{\(@{3&\(@.2$&F|:F;|}%\+}%\+F!}
do;{"= "&},.,7^.R+:R;[>0="#"/f*]*\+}0"R@1(XBc_""~\10"{base}:B/3/~4*"nIOZTLSJR "
";:"*~;n%)n*~ ]{n*n.}/10R*
Solution 2:
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.
Solution 3:
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
Solution 4:
Bash shell script (301 304 characters)
UPDATE: Fixed a bug involving pieces that extend into the top row. Also, the output is now sent to standard out, and as a bonus, it is possible to run the script again to continue playing a game (in which case you must add up the total score yourself).
This includes nonprintable characters, so I have provided a hex dump. Save it as tetris.txt:
0000000: 7461 696c 202d 3120 245f 7c7a 6361 743e tail -1 $_|zcat>
0000010: 753b 2e20 750a 1f8b 0800 35b0 b34c 0203 u;. u.....5..L..
0000020: 5590 516b 8330 10c7 dff3 296e 4c88 ae64 U.Qk.0....)nL..d
0000030: a863 0c4a f57d 63b0 07f7 b452 88d1 b4da .c.J.}c....R....
0000040: 1a5d 5369 91a6 df7d 899a d05d 5e72 bfbb .]Si...}...]^r..
0000050: fbff 2fe1 45d5 0196 7cff 6cce f272 7c10 ../.E...|.l..r|.
0000060: 387d 477c c4b1 e695 855f 77d0 b29f 99bd 8}G|....._w.....
0000070: 98c6 c8d2 ef99 8eaa b1a5 9f33 6d8c 40ec ...........3m.@.
0000080: 6433 8bc7 eeca b57f a06d 27a1 4765 07e6 d3.......m'.Ge..
0000090: 3240 dd02 3df1 2344 f04a 0d1d c748 0bde 2@..=.#D.J...H..
00000a0: 75b8 ed0f 9eef 7bd7 7e19 dd16 5110 34aa u.....{.~...Q.4.
00000b0: c87b 2060 48a8 993a d7c0 d210 ed24 ff85 .{ `H..:.....$..
00000c0: c405 8834 548a 499e 1fd0 1a68 2f81 1425 ...4T.I....h/..%
00000d0: e047 bc62 ea52 e884 42f2 0f0b 8b37 764c .G.b.R..B....7vL
00000e0: 17f9 544a 5bbd 54cb 9171 6e53 3679 91b3 ..TJ[.T..qnS6y..
00000f0: 2eba c07a 0981 f4a6 d922 89c2 279f 1ab5 ...z....."..'...
0000100: 0656 c028 7177 4183 2040 033f 015e 838b .V.(qwA. @.?.^..
0000110: 0d56 15cf 4b20 6ff3 d384 eaf3 bad1 b9b6 .V..K o.........
0000120: 72be 6cfa 4b2f fb03 45fc cd51 d601 0000 r.l.K/..E..Q....
Then, at the bash command prompt, preferably with elvis rather than vim installed as vi:
$ xxd -r tetris.txt tetris.sh
$ chmod +x tetris.sh
$ cat << EOF > b
> [ ]
> [ ]
> [ ]
> [ ]
> [ # # #]
> [ ## ######]
> [==========]
> EOF
$ ./tetris.sh T2 Z6 I0 T7 2>/dev/null
-- removed stuff that is not in standard out --
[ ]
[ ]
[ ]
[# ###]
[# ### ]
[##### ####]
[==========]
10
How it works
The code self-extracts itself similarly to how executable programs compressed using the gzexe script do. Tetromino pieces are represented as sequences of vi editor commands. Character counting is used to detect collisions, and line counting is used to calculate the score.
The unzipped code:
echo 'rej.j.j.:wq!m'>I
echo '2rejh.:wq!m'>O
echo '2rej.:wq!m'>Z
echo '3rejh1.:wq!m'>T
echo 'rej.j2.:wq!m'>L
echo 'l2rej2h.:wq!m'>S
echo 'lrej.jh2.:wq!m'>J
for t
do for y in `seq 1 5`
do echo -n ${y}jk$((${t:1}+1))l|cat - ${t:0:1}|vi b>0
grep ========== m>0||break
[ `tr -cd '#'<b|wc -c` = `tr -cd '#'<m|wc -c` ]||break
tr e '#'<m>n
done
cat n>b
grep -v '##########' b>m
$((S+=10*(`wc -l < b`-`wc -l < m`)))
yes '[ ]'|head -7|cat - m|tail -7>b
done
cat b
echo $S
The original code before golfing:
#!/bin/bash
mkpieces() {
pieces=('[email protected].' '2r@jh.' '2r@j.' '3r@jh1.' '[email protected].' 'l2r@j2h.' '[email protected].')
letters=(I O Z T L S J)
for j in `seq 0 9`; do
for i in `seq 0 6`; do
echo "jk$(($j+1))l${pieces[$i]}:wq! temp" > ${letters[$i]}$j
done
done
}
counthashes() {
tr -cd '#' < $1 | wc -c
}
droppiece() {
for y in `seq 1 5`; do
echo -n $y | cat - $1 | vi board > /dev/null
egrep '={10}' temp > /dev/null || break
[ `counthashes board` -eq `counthashes temp` ] || break
tr @ "#" < temp > newboard
done
cp newboard board
}
removelines() {
egrep -v '#{10}' board > temp
SCORE=$(($SCORE + 10 * (`wc -l < board` - `wc -l < temp`)))
yes '[ ]' | head -7 | cat - temp | tail -7 > board
}
SCORE=0
mkpieces
for piece; do
droppiece $piece
removelines
done
cat board
echo $SCORE
Solution 5:
Python: 504 519 chars
(Python 3 solution) Currently requires to set the input in the format as shown at the top (input code is not counted). I'll expand to read from file or stdin later. Now works with a prompt, just paste the input in (8 lines total).
R=range
f,p=[input()[1:11]for i in R(7)],p
for(a,b)in input().split():
t=[' '*int(b)+r+' '*9for r in{'I':'#,#,#,#','O':'##,##','Z':'##, ##','T':'###, # ','L':'#,#,##','S':' ##,##','J':' #, #,##'}[a].split(',')]
for r in R(6-len(t),0,-1):
for i in R(len(t)):
if any(a==b=='#'for(a,b)in zip(t[i],f[r+i])):break
else:
for i in R(0,len(t)):
f[r+i]=''.join(a if b!='#'else b for(a,b)in zip(t[i],f[r+i]))
if f[r+i]=='#'*10:del f[r+i];f[0:0]=[' '*10];p+=10
break
print('\n'.join('['+r+']'for r in f[:7]),p,sep='\n')
Not sure if I can save much more there. Quite a lot characters are lost from the transformation to bitfields, but that saves a lot more characters than working with the strings. Also I'm not sure if I can remove more whitespace there, but I'll try it later.
Won't be able to reduce it much more; after having the bitfield-based solution, I transitioned back to strings, as I found a way to compress it more (saved 8 characters over the bitfield!). But given that I forgot to include the L and had an error with the points inside, my character count only goes up sigh... Maybe I find something later to compress it a bit more, but I think I'm near the end. For the original and commented code see below:
Original version:
field = [ input()[1:11] for i in range(7) ] + [ 0, input() ]
# harcoded tetrominoes
tetrominoes = {'I':('#','#','#','#'),'O':('##','##'),'Z':('##',' ##'),'T':('###',' # '),'L':('#','#','##'),'S':(' ##','##'),'J':(' #',' #','##')}
for ( f, c ) in field[8].split():
# shift tetromino to the correct column
tetromino = [ ' ' * int(c) + r + ' ' * 9 for r in tetrominoes[f] ]
# find the correct row to insert
for r in range( 6 - len( tetromino ), 0, -1 ):
for i in range( len( tetromino ) ):
if any( a == b == '#' for (a,b) in zip( tetromino[i], field[r+i] ) ):
# skip the row if some pieces overlap
break
else:
# didn't break, insert the tetromino
for i in range( 0, len( tetromino ) ):
# merge the tetromino with the field
field[r+i] = ''.join( a if b != '#' else b for (a,b) in zip( tetromino[i], field[r+i] ) )
# check for completely filled rows
if field[r+i] == '#' * 10:
# remove current row
del field[r+i]
# add new row
field[0:0] = [' '*10]
field[7] += 10
# we found the row, so abort here
break
# print it in the requested format
print( '\n'.join( '[' + r + ']' for r in field[:7] ) )
# and add the points = 10 * the number of redundant lines at the end
print( str( field[7] ) )