Biorąc pod uwagę listę ruchów Tetris, zwróć liczbę zakończonych linii

37

Opis

Rozważamy nieco uproszczoną wersję Tetris, w której każdy ruch składa się z:

  • obracając element zgodnie z ruchem wskazówek zegara, od 0 do 3 razy
  • pozycjonowanie elementu w danej kolumnie
  • szybki spadek

Celem jest określenie liczby ukończonych linii, biorąc pod uwagę listę takich ruchów Tetris.

Ukończone rzędy są usuwane w miarę upuszczania elementów, zgodnie ze standardowymi zasadami Tetris.

Boisko

Pole gry ma szerokość 10 kolumn. Nie ma końca gry i zakłada się, że zawsze jest wystarczająco dużo miejsca i czasu na wykonanie powyższych czynności, bez względu na konfigurację pola gry. Wysokość pola gry tak naprawdę nie ma znaczenia, ale możesz użyć standardowych 22 rzędów jako górnej granicy.

Kształty Tetrominoes

kształty

Wejście wyjście

Wkład

Rozdzielona przecinkami lista ruchów Tetris zakodowanych 3 znakami. Pierwsze dwie znaki opisują kształt Tetromino, a ostatni opisuje pozycję, w której został upuszczony.

  1. Tetromino: I, O, T, L, J, Zi S, w tej samej kolejności, jak opisano powyżej.
  2. Liczba obrotów w prawo: 0do3
  3. Kolumna: 0do 9. Jest to kolumna, w której xpo obrocie znajduje się lewy górny róg elementu (oznaczony na powyższym obrazku) 1

Zakłada się, że wszystkie ruchy na podanej liście są prawidłowe. Nie trzeba sprawdzać, czy nie ma niepoprawnych wpisów, takich jak I07( Ikształt poziomy umieszczony zbyt daleko po prawej stronie).

1 Możesz zaimplementować prawdziwy algorytm obrotu lub na stałe zakodować wszystkie różne kształty, o ile xjest on umieszczony w kolumnie podanej przez trzeci znak ruchu.

Wydajność

Liczba ukończonych linii.

Przykład

przykład

O00,T24wygeneruje pierwszą pozycję i O00,T24,S02,T01,L00,Z03,O07,L06,I05wygeneruje drugą pozycję.

Dlatego następująca sekwencja wygeneruje Tetris i powinna zwrócić 4:

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

Przypadki testowe

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

Strona testowa

Możesz użyć tego JSFiddle do testowania listy ruchów.

Arnauld
źródło
1
Na jakiej osi obracają się elementy?
1
@Arnauld Proponuję przyjrzeć się systemowi superobrotów i nieco edytować obraz. tetris.wikia.com/wiki/SRS
1
Możemy więc traktować je jako 25 (15, jeśli nie liczymy duplikatów) różne kształty?
1
Czy rozwiązania mogą przyjmować dane wejściowe jako tablicę zamiast ciągu oddzielonego przecinkami?
Jordan
1
To najlepsze pytanie PCG, jakie widziałem od dłuższego czasu. Co za świetny pomysł! Najlepszy w subiektywnym sensie interesujący i praktyczny i niezbyt duży, ale nie za mały.
GreenAsJade

Odpowiedzi:

5

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

(z mapowaniem bloków Dave'a )

<?$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, przyjmuje ruchy jako osobne argumenty, wyświetla wynik

podział na funkcje:

przyjmuje ruchy jako tablicę, zwraca wynik

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
}

w celach informacyjnych: stare mapowanie

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

testowanie

zobacz moją inną odpowiedź na PHP

Chcę obejrzeć?

usuń #ze źródła funkcji i dodaj to:

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

kilka kroków w golfa

Obj 5: Big Leap (399- 21 = 378) był po prostu przesuwając przesunięcie kolumny
z osobnej pętli do dwóch istniejących pętli.

Rev. 8: Przejście z tablicy na bazę 16 za sztukę ($ s) nie dało wiele,
ale ustąpiło miejsca trochę golfa.

Wersja 17: łączyć wartości z base64_encode(pack('V*',<values>))
indeksowaniem bajtów i stosowaniem zamiast unpackzapisywania 16 bajtów

Rev 25 do 29: zainspirowany kodem Dave'a: nowy skrót (-2), nowy projekt pętli (-9), goto (-10)
bez wcześniejszej zmiany; to kosztowałoby 17 bajtów.

większy potencjał

Za pomocą /2%9mogę zapisać 15 bajtów (tylko 14 bajtów /4%5)
, umieszczając dane binarne w pliku, ba następnie indeksując file(b)[0].
Czy tego chcę?

Postacie UTF-8 kosztowałyby dużo transformacji.

na haszowanie

Użyłem ZJLO.ST /2%9 -> 0123.56; ale T.ZJLOS /3%7 -> 0.23456jest równie dobry.
jeden bajt dłużej: O.STJLZ %13/2 -> 0.23456
i jeszcze trzy:OSTZJ.L %17%12%9 -> 01234.6

Nie mogłem znaleźć krótkiego skrótu (maks. 5 bajtów), który nie pozostawia luki;
ale Dave znalazł STZJL /4%5 -> 01234, usuwając O z listy. wtg!

btw: TIJSL.ZO (%12%8) -> 01234.67pozostawia miejsce dla Ikształtu
(i fikcyjna A, Mlub Ykształt). %28%8i %84%8zrób to samo (ale z Ezamiast A).

Tytus
źródło
Miły; Podoba mi się łączone malowanie + wykrywanie linii, a break 2jest znacznie czystsze niż to, co musiałem zrobić w C! Państwo może być w stanie zaoszczędzić kilka bajtów za pomocą array_diff(zestaw zakończone linie do ustalonej wartości, zamiast używać unsetnastępnie zastąpić array_valuesz array_diff), ale nie mogę powiedzieć z docs, jeżeli byłoby spłaszczyć powtarzające się wartości (np array_diff ([1,2, 2,3], [1]) -> [2,2,3] lub po prostu [2,3])
Dave
@Dave: array_diffnie usuwa zduplikowanych wartości; i mam już stałą wartość (1023); ale nie reindeksuje tablicy. Świetny pomysł, ale kosztowałby bajt.
Tytus
wow, to było głośne bzyczenie, kiedy mijałeś mnie! Wygląda na to, że muszę nadrobić zaległości!
Dave
Gratulujemy osiągnięcia 300! Wdrożę twoją ostatnią sugerowaną zmianę (nie myślałem, żeby uprościć sprawdzanie rotacji teraz, gdy nie potrzebuję /10wszędzie), ale poza tym myślę, że skończone. Jestem zaskoczony, jak bezpośrednio konkurencyjne były PHP i C. To była świetna zabawa - mam nadzieję, że OP zaakceptuje twoją odpowiedź!
Dave
@Dave & Titus - Chciałbym zaakceptować obie odpowiedzi. Świetnie się spisaliście. Gratulacje dla Tytusa za osiągnięcie 300. I myślę, że to w rzeczywistości 299, ponieważ masz po sobie bezużyteczne miejsce po if.
Arnauld
16

C 401 392 383 378 374 351 335 324 320 318 316 305 bajtów

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

Pobiera wejście rozdzielone przecinkami na standardowe wejście, zwraca wynik w statusie wyjścia.

Wymaga charpodpisania (co jest domyślnym ustawieniem GCC) i wymaga '3Z3Z'interpretacji jako 861549402 (co ma miejsce w przypadku GCC na małych komputerach z systemem Endian).


Przykład użycia:

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

Wyjaśnienie na wysokim poziomie:

Wszystkie kształty oprócz linii można zmieścić na siatce 3x3 z brakującym jednym rogiem:

6 7 -
3 4 5
0 1 2

Oznacza to, że łatwo jest przechowywać je w bajtach. Na przykład:

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

(wyrównujemy każdy element do dolnej lewej części pudełka, aby ułatwić upuszczenie)

Ponieważ otrzymujemy co najmniej 4 bajty do liczby całkowitej, oznacza to, że możemy przechowywać wszystkie 4 obroty każdego elementu w jednej liczbie całkowitej, ze specjalnym przypadkiem dla linii. Możemy również dopasować każdy rząd siatki gry do int (potrzebuje tylko 10 bitów), a aktualnie spadający kawałek do długiej (4 linie = 40 bitów).


Awaria:

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 dzięki @Titus i -23, -11 z inspiracją z ich odpowiedzi

Dave
źródło
Niezłe! Czy możesz zrobić to s+=(d[A-x]=d[A])bez użycia x?
Arnauld,
Niestety xjest potrzebne, aby śledzić, ile wierszy do zapaści w obecnym etapie (każdy wiersz Ajest ustawiony na wartości rzędu A-xco postępami pętla)
Dave
Nie! Mój błąd. Przepraszam za taką głupią sugestię. :)
Arnauld,
1
@Titus jest to nadużycie indeksowania tablicy C. Mówiąc prościej 1[a]i a[1]rób to samo (a dokładniej a[b]tłumacząc *(a+b)). Jest to nadużywane w ten sposób, aby uniknąć nawiasów klamrowych. W tym przypadku 1[*v]== (*v)[1], tj. Druga litera polecenia, tj. Obrót.
Dave
1
Czy możesz pozbyć się Isymbolu zastępczego? Jeśli tak, spróbuj /2%9jako hash zamiast %12. %12%8Jeśli nie.
Tytus
2

Rubinowy, 474 443 428 379 + 48 = 427 bajtów

-1 dzięki @Titus

Można zdecydowanie bardziej grać w golfa.

Czyta binarny słownik elementów (patrz poniżej) ze STDIN lub nazwy pliku i przyjmuje listę ruchów jako argument, np $ 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

Dane binarne (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.\

Zobacz na repl.it (z zakodowanymi argumentami, słownikiem): https://repl.it/Cqft/2

Nie golf i wyjaśnienia

# 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
Jordania
źródło
1 bajt: m >> 10może byćm >> x
Tytus
@Titus Dobre oko. Dzięki!
Jordan
Nie trzeba jawnie wymagać \ds w wyrażeniu regularnym: /(\w)(\d)(\d)//(\w)(.)(.)/
manatwork
2

PHP, 454 435 427 420 414 bajtów

pola bitowe na kawałki i mapę; ale nie ma specjalnego przypadku dla Ikształtu jak golf Dave'a.

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

pobiera argumenty z wiersza poleceń, wyświetla wynik

niepoddane golfowi jako funkcja

przyjmuje argumenty jako tablicę, zwraca wynik

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

testy (w funkcji)

$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));
}
Tytus
źródło
427? Jesteś na!
Jordan
@Jordan: a te 427 zawierają <?koszty ogólne :)
Tytus