Diberikan daftar gerakan Tetris, kembalikan jumlah garis yang diselesaikan

37

Deskripsi

Kami menganggap versi Tetris yang sedikit disederhanakan di mana setiap gerakan terdiri dari:

  • memutar potongan searah jarum jam, 0 hingga 3 kali
  • memposisikan potongan pada kolom yang diberikan
  • penurunan cepat

Tujuannya adalah untuk menentukan jumlah garis yang diselesaikan, mengingat daftar gerakan Tetris tersebut.

Baris yang sudah selesai dihapus saat potongan dijatuhkan, mengikuti aturan Tetris standar.

Playfield

Playfield memiliki lebar 10 kolom. Tidak ada Game Over dan diasumsikan bahwa selalu ada cukup ruang dan waktu untuk melakukan tindakan di atas, tidak peduli konfigurasi playfield. Ketinggian playfield tidak terlalu penting di sini, tetapi Anda dapat menggunakan 22 baris standar sebagai batas atas.

Bentuk Tetromino

bentuk

Input output

Memasukkan

Daftar tetris bergerak dengan koma yang disandikan dengan 3 karakter. Dua karakter pertama menggambarkan bentuk Tetromino yang akan digunakan dan yang terakhir menggambarkan posisi di mana ia dijatuhkan.

  1. Tetromino: I, O, T, L, J, ZatauS , dalam urutan yang sama seperti di atas.
  2. Jumlah rotasi searah jarum jam: 0ke3
  3. Kolom: 0ke 9. Ini adalah kolom di mana sudut kiri atas potongan (ditandai dengan xgambar di atas) terletak setelah rotasi 1

Diasumsikan bahwa semua gerakan dalam daftar yang disediakan valid. Tidak perlu memeriksa entri yang tidak valid seperti I07( Ibentuk horizontal diletakkan terlalu jauh di sebelah kanan).

1 Anda bebas menerapkan algoritme rotasi nyata atau meng-hardcode semua bentuk yang berbeda, asalkan xterletak di kolom yang diberikan oleh karakter ketiga gerakan.

Keluaran

Jumlah garis yang diselesaikan.

Contoh

contoh

O00,T24 akan menghasilkan posisi pertama dan O00,T24,S02,T01,L00,Z03,O07,L06,I05 akan menghasilkan posisi kedua.

Oleh karena itu, urutan berikut akan menghasilkan Tetris dan harus kembali 4:

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

Uji kasus

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

Halaman uji

Anda dapat menggunakan JSFiddle ini untuk menguji daftar pemindahan.

Arnauld
sumber
1
Apa sumbu potongan diputar?
1
@Arnauld Saya sarankan Anda melihat sistem super rotasi, dan mengedit gambar sedikit. tetris.wikia.com/wiki/SRS
1
Jadi, kita dapat memperlakukan ini sebagai 25 (15 jika Anda tidak menghitung duplikat) bentuk yang berbeda, lalu?
1
Bisakah solusi mengambil input sebagai array daripada string yang dipisahkan koma?
Jordan
1
Ini adalah pertanyaan PCG terbaik yang pernah saya lihat sejak lama. Ide yang bagus! Terbaik dalam arti subyektif menarik dan praktis dan tidak terlalu besar namun tidak terlalu kecil.
GreenAsJade

Jawaban:

5

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

(dengan pemetaan blok Dave )

<?$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, mengambil gerakan sebagai argumen terpisah, mencetak hasil

kerusakan berfungsi:

mengambil gerakan sebagai array, mengembalikan hasil

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
}

untuk referensi: pemetaan lama

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

pengujian

lihat jawaban PHP saya yang lain

mau nonton

hapus #dari sumber fungsi dan tambahkan ini:

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>';}

beberapa langkah golf

Wahyu 5: Sebuah lompatan besar (399- 21 = 378) datang hanya dengan menggerakkan pergeseran kolom
dari loop terpisah untuk dua loop yang ada.

Rev. 8: Beralih dari array ke base 16 untuk bagian ($ s) tidak memberi banyak,
tetapi memberi jalan bagi golf lagi.

Rev. 17: membuat nilai-nilai dengan base64_encode(pack('V*',<values>))
dan menggunakan pengindeksan byte alih-alih unpackmenyimpan 16 byte

Wahyu 25 hingga 29: terinspirasi oleh kode Dave: hashing baru (-2), desain loop baru (-9), goto (-10)
tidak ada pre-shift; biayanya 17 byte.

lebih potensial

Dengan /2%9, saya bisa menyimpan 15 byte (hanya dengan 14 byte /4%5)
dengan memasukkan data biner ke dalam file bdan kemudian mengindeks file(b)[0].
Apakah saya menginginkan itu?

Karakter UTF-8 akan membutuhkan banyak biaya untuk transformasi.

pada hashing

Saya menggunakan ZJLO.ST /2%9 -> 0123.56; tetapi T.ZJLOS /3%7 -> 0.23456sama baiknya.
satu byte lebih lama: O.STJLZ %13/2 -> 0.23456
dan tiga lagi:OSTZJ.L %17%12%9 -> 01234.6

Saya tidak dapat menemukan hash pendek (maks. 5 byte) yang tidak meninggalkan celah;
tetapi Dave menemukan STZJL /4%5 -> 01234, menjatuhkan O dari daftar. wtg!

btw: TIJSL.ZO (%12%8) -> 01234.67menyisakan ruang untuk Ibentuk
(dan fiksi A, Matau Ybentuk). %28%8dan %84%8, lakukan hal yang sama (tetapi dengan Ebukannya A).

Titus
sumber
Bagus; Saya suka lukisan gabungan + deteksi garis, dan break 2jauh lebih bersih daripada apa yang harus saya lakukan di C! Anda mungkin dapat menyimpan beberapa byte dengan menggunakan array_diff(atur baris yang telah selesai ke nilai tetap alih-alih menggunakan unsetlalu ganti array_valuesdengan array_diff), tetapi saya tidak dapat mengatakan dari dokumen jika itu akan meratakan nilai yang diulang (misalnya array_diff ([1,2, 2,3], [1]) -> [2,2,3] atau hanya [2,3])
Dave
@Dave: array_difftidak menghapus nilai duplikat; dan saya sudah memiliki nilai tetap (1023); tetapi itu tidak mengindeks ulang array. Ide bagus, tapi biayanya satu byte.
Titus
wow itu suara deru keras saat kamu terbang melewatiku! Sepertinya aku harus mengejar ketinggalan!
Dave
Selamat atas pencapaian 300! Saya akan menerapkan perubahan yang disarankan terbaru Anda (tidak berpikir untuk menyederhanakan pemeriksaan rotasi sekarang karena saya tidak perlu di /10semua tempat), tetapi kalau tidak saya pikir saya sudah selesai. Saya terkejut melihat betapa kompetitifnya PHP dan C secara langsung. Ini menyenangkan - semoga OP menerima jawaban Anda!
Dave
@ Dave & Titus - Saya berharap saya bisa menerima kedua jawaban. Kamu sudah melakukan pekerjaan yang hebat. Lagi pula selamat untuk Titus untuk mencapai 300. Dan saya pikir itu sebenarnya 299 karena Anda memiliki ruang yang tidak berguna setelah if.
Arnauld
16

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

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;}

Mengambil input yang dipisahkan koma pada stdin, mengembalikan skor dalam status keluar.

Harus charditandatangani (yang merupakan standar untuk GCC) dan '3Z3Z'harus ditafsirkan sebagai 861549402 (yang merupakan kasus untuk GCC pada mesin endian kecil, setidaknya).


Contoh penggunaan:

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

Penjelasan tingkat tinggi:

Semua bentuk kecuali garis dapat ditampung dalam kisi 3x3 dengan satu sudut hilang:

6 7 -
3 4 5
0 1 2

Itu berarti mudah untuk menyimpannya dalam byte masing-masing. Sebagai contoh:

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

(kami menyelaraskan setiap bagian ke kiri bawah kotak untuk memudahkan menjatuhkannya)

Karena kita mendapatkan setidaknya 4 byte ke int, ini berarti kita dapat menyimpan semua 4 rotasi setiap bagian dalam bilangan bulat tunggal, dengan kasing khusus untuk garis. Kami juga dapat memasukkan setiap baris kisi permainan ke int (hanya membutuhkan 10 bit), dan potongan yang saat ini jatuh menjadi panjang (4 baris = 40 bit).


Kerusakan:

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 terima kasih kepada @Titus, dan -23, -11 dengan inspirasi dari jawaban mereka

Dave
sumber
Yang bagus! Bisakah Anda melakukannya s+=(d[A-x]=d[A])tanpa menggunakan x?
Arnauld
Sayangnya xdiperlukan untuk melacak berapa banyak baris untuk runtuh pada langkah saat ini (setiap baris Adiatur ke nilai baris A-xsaat loop berlangsung)
Dave
Doh! Salahku. Maaf untuk saran konyol seperti itu. :)
Arnauld
1
@Itus itu penyalahgunaan indeks array C. Sederhananya, 1[a]dan a[1]lakukan hal yang sama (atau lebih tepatnya, a[b]diterjemahkan menjadi *(a+b)). Ini disalahgunakan seperti ini sebagai cara menghindari kurung. Dalam hal ini, 1[*v]== (*v)[1], yaitu huruf kedua dari perintah, yaitu rotasi.
Dave
1
Bisakah Anda menyingkirkan Iplaceholder? Jika demikian, coba /2%9sebagai hash alih-alih %12. %12%8jika tidak.
Titus
2

Ruby, 474 443 428 379 + 48 = 427 byte

-1 terima kasih kepada @Titus

Ini pasti bisa bermain golf lebih banyak.

Membaca kamus potongan-potongan biner (lihat di bawah) dari STDIN atau nama file dan mengambil daftar pemindahan sebagai argumen, misalnya $ 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

Data potongan biner (format xxd)

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

Lihat di repl.it (dengan argumen hard-kode, kamus): https://repl.it/Cqft/2

Tidak dikelompokkan & penjelasan

# 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
Jordan
sumber
1 byte: m >> 10bisam >> x
Titus
@Titus, mata yang bagus. Terima kasih!
Jordan
Tidak perlu secara eksplisit meminta \ds dalam ekspresi reguler: /(\w)(\d)(\d)//(\w)(.)(.)/
manatwork
2

PHP, 454 435 427 420 414 byte

bidang bit untuk potongan dan peta; tetapi tidak ada kasus khusus untuk Ibentuk seperti golf Dave.

<?$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;

mengambil argumen dari baris perintah, mencetak hasil

ungolfed sebagai fungsi

mengambil argumen sebagai array, mengembalikan hasil

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;
}

tes (berfungsi)

$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));
}
Titus
sumber
427? Anda berada di!
Jordan
@Jordan: dan 427 itu termasuk <?biaya overhead :)
Titus