^{Wyzwanie zaczerpnięte z mojego konkursu na kod uniwersytecki}

^{To właściwie Dzień 0, ale wczorajsze wyzwanie było zbyt łatwe i może być duplikatem innego pytania tutaj.}

Tetris to gra wideo, która stała się popularna w latach 80. Polega ona na umieszczeniu szeregu elementów o różnych kształtach, które spadają na deskę, aby pasowały w możliwie najbardziej kompaktowy sposób.

W tym problemie założymy sekwencję spadających kawałków, każda w określonej pozycji i o określonej orientacji, której nie można zmienić. Kawałki są ułożone w stos, gdy spadają, a pełne rzędy nie są eliminowane (jak w oryginalnej grze). Celem jest ustalenie ostatecznej wysokości każdej kolumny planszy po upadku wszystkich elementów.

Istnieje 7 różnych elementów pokazanych na rysunku:

Wyzwanie

Biorąc pod uwagę listę elementów, wypuść wysokość wszystkich kolumn z planszy po opadnięciu wszystkich elementów

Kawałek składa się z trzech liczb: I, R i P. Pierwsza liczba, I, jest identyfikatorem kawałka (liczba od 1 do 7, w tej samej kolejności, jak na rysunku). Druga liczba, R, oznacza obrót kawałka. Może przyjmować wartości 0, 90, 180 lub 270 i reprezentuje kąt obrotu elementu w kierunku przeciwnym do ruchu wskazówek zegara. Trzecia liczba, P, wskazuje pozycję utworu. Reprezentuje kolumnę po lewej stronie zajmowaną przez element (może to być indeks 1 lub 0. Proszę określić).

Przykład i przypadek testowy (1 indeks)

• Dany [[1, 0, 1], [4, 0, 1], [5, 90, 4]]

• Wynik [3, 3, 1, 3, 2]

• Dany [[6, 270, 4], [1, 180, 5], [1, 90, 6], [7, 0, 4]]

• Wynik [0, 0, 0, 9, 9, 8, 3, 3]

• Podana [[3,0,1],[3,180,3]]wydajność[1,1,4,4,4]

• Podana [[2,180,1],[2,0,3]]wydajność[2,2,4,3,3]

Notatki

• To jest golf golfowy
• Wiersz / kolumna może mieć indeks 1 lub 0. Proszę sprecyzuj.
• Możesz ponownie zdefiniować wartości wejściowe (być może chcesz nazwać element 1 jako A itp.). W takim przypadku proszę określić

pytania

• Czy możemy użyć dowolnych 4 różnych wartości zamiast kąta w stopniach ?: Tak

• Czy mamy radzić sobie z „dziurami”, jeśli element nie pasuje dokładnie do poprzednich ?: Tak

• Czy wysokość lub szerokość deski jest ograniczona? Nie. Szerokość ani wysokość nie są ograniczone

Dzięki @Arnauld za obrazy i przypadki testowe *. *

JavaScript (Node.js) ,  286 284 270  266 bajtów

$[0..3]$

a=>a.map(([p,r,x])=>(g=y=>y>3?g(+!Y--):b[Y+y]&(m[y]=('0x'+`717433667233ff4717333327661${1e12+0x5e7056a566ffff57efa65n.toString(4)}`[(p*2+r*56+y*99+13)%113])<<x)?m.map(v=>(g=x=>v&&g(x+1,H[x]=v&1?Y:~~H[x],v>>=1))(0,b[++Y]|=v)):g(y+1))(Y=a.length*4),m=[b=[-1]],H=[])&&H

Wypróbuj online! lub wypróbuj ulepszoną wersję, która wyświetla także ostateczną tablicę.

Kodowanie kształtu

Wszystkie elementy są przechowywane jako dokładnie 4 skrawki (4x4 bity) z rzędami posortowanymi w odwrotnej kolejności, a piksel skrajnie lewy odwzorowany na najmniej znaczący bit. Innymi słowy, binarna reprezentacja kształtu jest odbijana zarówno pionowo, jak i poziomo.

Przykład:

Funkcja skrótu i ​​tabela odnośników

$p \in [0..6]$$r \in [0..3]$$y \in [0..3]$$n$

Tylko pierwsze wpisy są jawnie przechowywane. Cała reszta jest ustawiona na .$82$$0$

Te wpisy są pakowane jako:

`717433667233ff4717333327661${1e12+0x5e7056a566ffff57efa65n.toString(4)}`

która rozwija się do następujących 82 skubków:

"717433667233ff47173333276611000000000000113213001112221112123333333311133233221211"

Użycie formatu szesnastkowego w ostatecznym formacie jest wymagane tylko dla dwóch poziomych reprezentacji kawałka , stąd powyższy ciąg.$I$"ff"

Parametry funkcji skrótu zostały brutalnie wymuszone w sposób, który optymalizuje wiodące i końcowe zera. Fakt, że ciąg można jeszcze bardziej skompresować za pomocą 1e12zer po środku i konwersji z base-16 na base-4 dla prawej części, jest po prostu pożądanym, ale nieoczekiwanym efektem ubocznym. :-)

Oto demonstracja procesu rozpakowywania wszystkich sztuk i wszystkich obrotów.

Skomentował

a => a.map(([p, r, x]) => (     // for each piece p with rotation r and position x:
  g = y =>                      //   g = recursive function taking y
    y > 3 ?                     //   if y is greater than 3:
      g(+!Y--)                  //     reset y to 0, decrement Y and try again
    :                           //   else:
      b[Y + y] & (              //     test if we have a collision of the board with
        m[y] =                  //     the y-th row m[y] of the current piece
          ('0x' + `717...`[     //     which is extracted from a lookup table
            (p * 2 + r * 56 +   //     using the hash function described in the
             y * 99 + 13) % 113 //     previous paragraph
          ]) << x               //     and shifted to the left according to x
      ) ?                       //     if we have a collision:
        m.map(v => (            //       we iterate again on the piece rows stored in m[]
          g = x =>              //         g = recursive function taking x
            v &&                //         if v is not equal to 0:
            g(                  //           do a recursive call:
              x + 1,            //             increment x
              H[x] =            //             update the height at x:
                v & 1 ?         //               if this bit is set:
                  Y             //                 set it to Y
                :               //               else:
                  ~~H[x],       //                 leave it unchanged or force it to 0
                                //                 if it was still undefined
              v >>= 1           //             shift v to the right
            )                   //           end of recursive call
          )(0,                  //         initial call to g with x = 0
               b[++Y] |= v)     //         increment Y and copy the piece row to the board
        )                       //     end of map()
      :                         //   else (no collision):
        g(y + 1)                //     do a recursive call to test the next row
  )(Y = a.length * 4),          //   initial call to g with y = Y = 4 * the number of pieces
                                //   (assuming the worst case: piled vertical I pieces)
  m = [b = [-1]], H = []        //   initialize m[], b[] and H[]
                                //   we set a full line at the bottom of b[]
) && H                          // end of map(); return H[]

C (clang) , 253 239 221 212 bajtów

t(*a,*b,c){char*z="VP\225TBUIUVAaUZ@AWVDeTf@EVWhU😎EQV😀RTYT😉UU";for(size_t*p,f,n,y,i;c--;b++){f=1<<(8-*b)/3;p=z+*b++*8+*b++%f*2;f=n=*p;for(y=i=0;i<=f%4;y=fmax(y,a[*b+i++]+n%4))n/=4;for(;i--;a[*b+i]=y+n%4)n/=4;}}

Wypróbuj online!

ps W rzeczywistości rozmiar kodu wynosi 221 bajtów (ale 212 znaków) z powodu znaków UNICODE zakodowanych w UTF-8. Ale tio.run traktuje to jako kod 212 bajtów ...

Rozmiar kodu na moim komputerze to 209 znaków (218 bajtów). Ale nie mogłem zastąpić \225widocznym char w tio.run 😞

Nieskluczony kod

// a - output array (must be zeroed), b - array of block info, c - number of blocks

// Figure codes: 2->0, 3->1, 6->2, 1->3, 5->4, 7->5, 4->6 (0,1 are L-figures, 2 is is T-figure, 3 is a line 1x4; 4,5 are zigzags; 6 is a cube 2x2)
// Vertical and horizontal positions are zero-indexed, angles = 0..3

t(*a,*b,c)
{
  char*z="VP\225TBUIUVAaUZ@AWVDeTf@EVWhU😎EQV😀RTYT😉UU";  // UTF-8
//char*z="VP\225TBUIUVAaUZ@AWVDeTf@EVW\1hU😎\26EQV😀RTYT😉UU";  // 3 bytes longer (use it if you can't copy previous string correctly) :)
  // Blocks
  for(size_t*p,f,n,y,i;c--;b++){
    f=1<<(8-*b)/3;  // number of figure variants
    p=z+*b++*8+*b++%f*2;
    // Get top base line position (y)
    f=n=*p;  // figure width, TBLs and HATs
    for(y=i=0;i<=f%4;
      y=fmax(y,a[*b+i++]+n%4))
      n/=4;
    // Add heights (HATs)
    for(;i--;
      a[*b+i]=y+n%4)
      n/=4;
  }
}  // 215 chars (224 bytes)

Opis

Znajdźmy górną linię podstawową ( TBL ) każdej figury i opiszmy ją jako liczbę komórek poniżej TBL dla każdej pozycji poziomej. Opiszmy także liczbę komórek (wysokość) powyżej TBL ( HAT ).

Na przykład:

                       ________ ________
_ [] _____ HAT = 1,0,0 [] [] [] HAT = 0,0,0 ___ [] [] _ ​​HAT = 0,1,1 [] [] HAT = 0,0,0
 [] [] [] TBL = 1,1,1 [] TBL = 2,1,1 [] [] TBL = 1,1,0 [] TBL = 1,2,1

Opiszmy TBL i HAT dla każdej figury i każdego kąta obrotu:

Szerokość TBLs HATs
----- ------- -------
Liczby L:
  3 1 1 1 1 0 0 // 0 °
  2 1 1 0 2 // 90 °
  3 1 1 2 0 0 0 // 180 °
  2 3 1 0 0 // 270 °

  3 1 1 1 0 0 1 // 0 °
  2 1 3 0 0 // 90 °
  3 2 1 1 0 0 0 // 180 °
  2 1 1 2 0 // 270 °

T-rysunek:
  3 1 1 1 0 1 0 // 0 °
  2 1 2 0 1 // 90 °
  3 1 2 1 0 0 0 // 180 °
  2 2 1 1 0 // 270 °

Linia:
  4 1 1 1 1 0 0 0 0 // 0 °, 180 °
  1 4 0 // 90 °, 270 °

Zygzaki:
  3 1 1 0 0 1 1 // 0 °, 180 °
  2 1 2 1 0 // 90 °, 270 °

  3 0 1 1 1 1 0 // 0 °, 180 °
  2 2 1 0 1 // 90 °, 270 °

Sześcian:
  2 2 2 0 0 // dowolny kąt

Teraz trzeba kodują te numery jako sekwencje 2 bitów i wprowadzane do macierzy (zastępującego 4 0przy 3 190 ° kącie „linia”, aby zmieścić się w 2 bity - efekt będzie taki sam, i zmniejszania szerokości od 1).

Będziemy kodować w kolejności: szerokość (w 2 LSB), TBL , HAT (wstecz dla pętli wstecznej). Na przykład 2 2 1 1 0 do 270 ° kąta T rysunku są kodowane jako 1 0 1 2 1(ostatnia 1 ma szerokość 1 ) 0b0100011001 = 281.

aktualizacja 12.02:

a) Przekształciłem tablicę na ciąg i zapisałem 18 znaków (możesz zobaczyć poprzedni kod 239 bajtów ) :))

b) Większa optymalizacja, kod jest zmniejszony o 9 znaków.
To moja ostatnia próba (tak myślę, lol!) 😀

Common Lisp, 634 bajty

(let((w(make-hash-table))(r 0))(defun z(c)(or(gethash c w)0))(defun x(c v)(setf r(max r c))(setf(gethash c w)v))(defun m(s)(dolist(c s)(apply(lambda(n u p)(let*((i(let*((j'(2 2 2))(k'(3 3))(l'(2 3))(m'(3 2))(o(case n(1(list'(1 1 1 1)'(4)))(2(list j k'(1 1 2)'(3 1)))(3(list j'(1 3)'(2 1 1)k))(4(list'(2 2)))(5(list'(2 2 1)l))(6(list j l'(1 2 1)m))(7(list'(1 2 2)m)))))(setf(cdr(last o))o)))(o(nth(+ u 2)i))(b(nth u i))(s(length o))(d 0)(h 0))(dotimes(i s)(let*((w(nth i b))(g(z(+ i p)))(m(+ g w)))(when(> m d)(setf d m)(setf h(- g(-(apply'max b)w))))))(dotimes(i s)(x(-(+ s p)i 1)(+(nth i o)h)))))c))(dotimes(i r)(print(z (+ i 1))))))

Gadatliwy

(defun circular (list)
  (setf (cdr (last list)) list))

(defun get-piece (piece-number)
  (circular (case piece-number
              (1 (list '(1 1 1 1)
                       '(4)))
              (2 (list '(2 2 2)
                       '(3 3)
                       '(1 1 2)
                       '(3 1)))
              (3 (list '(2 2 2)
                       '(1 3)
                       '(2 1 1)
                       '(3 3)))
              (4 (list '(2 2)))
              (5 (list '(2 2 1)
                       '(2 3)))
              (6 (list '(2 2 2)
                       '(2 3)
                       '(1 2 1)
                       '(3 2)))
              (7 (list '(1 2 2)
                       '(3 2))))))

(let ((world (make-hash-table))
      (rightmost-column 0))
  (defun get-world-column (column)
    (or (gethash column world) 0))

  (defun set-world-column (column value)
    (setf rightmost-column (max rightmost-column column))
    (setf (gethash column world) value))

  (defun drop-piece (piece-number rotation position)
    (let* ((piece (get-piece piece-number))
           (top (nth (+ rotation 2) piece))
           (bottom (nth rotation piece))
           (size (length top))
           (max-combined-height 0)
           (contact-height 0))
      (dotimes (i size)
        (let* ((down-distance (nth i bottom))
               (height (get-world-column (+ i position)))
               (combined-height (+ height down-distance)))
          (when (> combined-height max-combined-height)
            (setf max-combined-height combined-height)
            (setf contact-height
                  (- height
                     (- (apply #'max bottom)
                        down-distance))))))
      (dotimes (i size)
        (set-world-column (- (+ size position) i 1)
                          (+ (nth i top) contact-height)))))

  (defun drop-pieces (pieces)
    (dolist (piece pieces)
      (apply #'drop-piece piece)))

  (defun print-world ()
    (loop for i from 1 to rightmost-column
          do (print (get-world-column i)))))

(defun play-tetris (pieces)
  (drop-pieces pieces)
  (print-world))

Sprawdź to

Kawałki są okrągłymi listami liczb. Każda z tych list podrzędnych reprezentuje bok kształtu, liczby wskazujące, jak daleko są od przeciwnej strony. Są one od lewej do prawej, gdy ta strona znajduje się na dole, od prawej do lewej, gdy jest u góry, od góry do dołu, gdy jest po lewej stronie, i od dołu do góry, gdy jest po prawej stronie. Te opcje projektowania eliminują potrzebę pisania kodu do rotacji. Niestety, brak kodu rotacji nie nadrobił długich reprezentacji kształtów lub nieco skomplikowanej logiki, której użyłem do obliczenia nowych wysokości kolumn.

Rotacja jest nieujemną liczbą całkowitą. 0 = 0 stopni, 1 = 90 stopni, 2 = 180 stopni, 4 = 270 stopni

C # (interaktywny kompilator Visual C #) , 308 bajtów

a=>{var o=new int[a.Max(x=>x.Item3+4)];foreach(var(i,r,p)in a){var b="\"4TqzŒª!\0\0HSš	Ó\0$\n\0!“A“š š@";int m=0,n=b[i],t=0,u=n/8+r%(n%8),v=b[u*=2]<<8|b[u-1];for(;t<v/8%8;m=m>n?m:n)n=o[p+t]+v%8-(n=(u=v>>6+3*t++)/2&1)-(n&u);for(;t-->0;)o[p+t]=m-(n=(u=v>>6+3*t)/4&1)-(n&u);}return o;}

Wypróbuj online!

OK - To było szaleństwo ... Przekazałem odpowiedź, w której stosowałem techniki gry w golfa. Ale kiedy zobaczyłem, co podchodzą inni, zrozumiałem, że jest lepszy sposób.

Każda (shape, rotation)krotka jest kodowana w dosłownym ciągu znaków C # z usuniętymi duplikatami. Proces kodowania rejestruje każdą z tych konfiguracji w 2 bajtach.

Najniższa wysokość 3 bitów i szerokość następnych 3 bitów. Ponieważ każda z tych wartości nigdy nie jest większa niż 4, można je odczytać bezpośrednio z 3 bitów bez jakiejkolwiek konwersji. Oto kilka przykładów:

  W   H
010 010 (2x2)
010 011 (2x3)
001 100 (1x4)
011 010 (3x2)
100 001 (4x1)

Następnie każda kolumna jest przechowywana w 3 bitach. Najbardziej użyteczną rzeczą do przechowywania była liczba brakujących kwadratów od góry i dołu kolumny.

// missing squares per column

+------ 0 top / 0 bottom
|+----- 0 top / 1 bottom
||+---- 0 top / 1 bottom
|||
HHH (L-Shape)         HH (Jagged-Shape)
H                    HH
                     |||
1 top / 0 bottom ----+||
0 top / 0 bottom -----+|
0 top / 1 bottom ------+

Nigdy nie brakuje więcej niż 2 kwadratów od góry lub od dołu i nigdy nie brakuje więcej niż 1 kwadratu z obu jednocześnie. Biorąc pod uwagę ten zestaw ograniczeń, wymyśliłem następujące kodowanie:

// column encoding of missing squares per column

000: none missing
100: 1 missing on top
101: 2 missing on top
010: 1 missing on bottom
011: 2 missing on bottom
110: 1 missing on top and bottom

Ponieważ musimy uwzględnić maksymalnie 3 kolumny z brakującymi kwadratami powyżej lub poniżej, możemy zakodować każdą (shape, rotation)krotkę w 15 bitach.

 C3  C2  C1   W   H
000 000 000 010 010 - 2x2 with no missing squares
000 000 000 100 001 - 4x1 with no missing squares
100 000 100 011 010 - 3x2 with missings square on top of columns 1 and 3
000 110 000 010 011 - 2x3 with missing squares on top and bottom of column 2

Wreszcie zduplikowane kształty zostały usunięte. Poniższy przykład pokazuje, jak wiele (shape,rotation)krotek może wytwarzać zduplikowane dane wyjściowe dla tego samego kształtu przy różnych obrotach:

// Square
HH  (0, 90, 180, 270)
HH
#-------------------------------#
// ZigZag
HH  (0, 180)    H  (90, 270)
 HH            HH
               H
#-------------------------------#
// T
 H  (0)        HHH  (180)
HHH             H

 H  (90)       H    (270)
HH             HH
 H             H

Wszystkie unikalne dane wyjściowe są określane i zapisywane w a byte[]oraz konwertowane na literał ciągu C #. W celu szybkiego LOOKUP w której kształt jest na podstawie I, a Rpierwsze 7 bajtów tablicy składa zakodowanego klucza wyszukiwania.

Poniżej znajduje się link do programu, którego użyłem do kompresji elementów.

Wypróbuj online!

Kod mniej golfowy i komentowany:

// a: input list of (i,r,p) tuples
a=>{
  // create an output array that 4 more than
  // the largest position. this may result
  // in some trailing 0's
  var o=new int[a.Max(x=>x.Item3+4)];

  // iterate over each (i,r,p) tuple
  foreach(var(i,r,p)in a){
    // escaped string
    var b="\"4Tqzª!\0\0HS   Ó\0$\n\0!A @";
    // declare several variables that will be used later
    int m=0,n=b[i],t=0,
      // u is the decoded index into b for the current (i,r) pair
      u=n/8+r%(n%8),
      // convert 2 bytes from b into an encoded (shape,rotation) pair
      v=b[u*=2]<<8|b[u-1];
    // iterate over the columns, determining the top of the current
    // piece. The formula here is:
    //   piece_top = max(column_height + shape_height - shape_space_bottom)
    for(;t<v/8%8;m=m>n?m:n)
      n=o[p+t]+v%8-(n=(u=v>>6+3*t++)/2&1)-(n&u);
    // iterate over the columns again, saving the the new height
    // in each column. The formula here is:
    //   new_column_height = piece_top - shape_space_top
    for(;t-->0;)
      o[p+t]=m-(n=(u=v>>6+3*t)/4&1)-(n&u);
  }
  return o;
}

Węgiel , 98 bajtów

Ｆθ«≔§⪪§⪪”)¶∧↷"e«↨U∧0%3；D∧⁼~h⊟⁵h/₂dΦ↗(EＦ”2⊟ι1⊟ιη≔⊟ιζＷ‹Ｌυ⁺ζＬη⊞υ⁰≔⌈Ｅη⁻§υ⁺ζλ﹪Ｉκ³εＦＬη§≔υ⁺ζκ⁺ε⊕÷Ｉ§ηκ³»Ｉυ

Wypróbuj online! Link jest do pełnej wersji kodu. Pobiera dane wejściowe jako tablicę wartości [P, R, I], gdzie I wynosi od 0 do 6, R wynosi od 0 do 3, a P jest również indeksowany na 0. Wyjaśnienie:

Ｆθ«

Zapętlić elementy wejściowe.

≔§⪪§⪪”)¶∧↷"e«↨U∧0%3；D∧⁼~h⊟⁵h/₂dΦ↗(EＦ”2⊟ι1⊟ιη

Wyodrębnij opis bieżącego kawałka i rotacji. (Patrz poniżej.)

≔⊟ιζ

Wyodrębnij pozycję.

Ｗ‹Ｌυ⁺ζＬη⊞υ⁰

Upewnij się, że jest wystarczająca pozioma przestrzeń do umieszczenia elementu.

≔⌈Ｅη⁻§υ⁺ζλ﹪Ｉκ³ε

Upewnij się, że jest wystarczająco dużo miejsca w pionie, aby umieścić element.

ＦＬη§≔υ⁺ζκ⁺ε⊕÷Ｉ§ηκ³

Oblicz nowe wysokości dotkniętych kolumn.

»Ｉυ

Po przetworzeniu wszystkich elementów wyślij ostateczną listę wysokości kolumn w osobnych wierszach.

Skompresowany ciąg reprezentuje oryginalny ciąg 00001923001061443168200318613441602332034173203014614341642430137. Tutaj 2s są Iseparatorami i 1s są Rseparatorami. Elementy dekodują zatem w następujący sposób:

P\R  0    1    2    3
0    0000 9
1    300  06   443  68
2    003  86   344  60
4    33
5    034  73
6    030  46   434  64
7    430  37

Brakujące Rwartości są automatycznie uzupełniane cyklicznie przez węgiel drzewny. Każda cyfra jest następnie odwzorowywana na dwie wartości, zwis i całkowitą wysokość, zgodnie z poniższą tabelą:

\ O H
0 0 1
3 0 2
4 1 2
6 0 3
7 1 3
8 2 3
9 0 4

Zwis i całkowita wysokość odnoszą się do wysokości kolumn w następujący sposób: Biorąc pod uwagę element, który chcemy umieścić w danej pozycji e, może być możliwe umieszczenie elementu, nawet jeśli jedna z kolumn jest wyższa niż e. Ilość wolnego miejsca wynika z nawisu. Nowa wysokość kolumny po umieszczeniu elementu jest po prostu położoną pozycją powiększoną o całkowitą wysokość.

Przykład: Załóżmy, że zaczynamy od umieszczenia 5kawałka w kolumnie 1. Ponieważ nie ma nic innego, kawałek jest zatem umieszczany w pozycji 0, a kolumny 1 i 3 mają teraz wysokość 1, a kolumna 2 ma wysokość 2. Chcemy następnie umieścić 6kawałek z 1rotacją w kolumnie 0. Tutaj możemy faktycznie umieścić ten kawałek w pozycji 0; chociaż kolumna 1 ma wysokość 1, element ma zwis 1, więc jest wystarczająco dużo miejsca, aby ją umieścić. Kolumna 0 kończy się na wysokości 2, a kolumna 1 kończy na wysokości 3.