^{Tantangan Diambil dari kontes tantangan kode universitas saya}

^{Ini sebenarnya adalah Hari 0 tetapi tantangan kemarin terlalu mudah dan dapat ditipu pertanyaan lain di sini.}

Tetris adalah permainan video yang menjadi populer di tahun 80-an. Ini terdiri dari menempatkan serangkaian potongan dengan bentuk berbeda yang jatuh di atas papan, sehingga mereka pas dengan cara yang paling kompak.

Dalam masalah ini kita akan mengasumsikan urutan potongan yang jatuh, masing-masing dalam posisi tertentu dan dengan orientasi tertentu yang tidak dapat diubah. Potongan-potongan ditumpuk saat jatuh dan baris lengkap tidak dihilangkan (seperti dalam game asli). Tujuannya adalah untuk menentukan ketinggian akhir dari setiap kolom papan setelah semua bagian jatuh.

Ada total 7 buah yang berbeda, yang ditunjukkan pada gambar:

Tantangan

Diberikan daftar potongan, hasilkan ketinggian semua kolom dari papan setelah semua potongan jatuh

Sepotong terdiri dari tiga angka: I, R dan P. Angka pertama, I, adalah pengidentifikasi keping (angka antara 1 dan 7, dalam urutan yang sama seperti pada gambar). Angka kedua, R, adalah rotasi potongan. Ini dapat mengambil nilai 0, 90, 180 atau 270 dan mewakili sudut rotasi potongan dalam arah anti-jarum jam. Angka ketiga, P, menunjukkan posisi potongan. Merupakan kolom di sebelah kiri ditempati oleh potongan (ini bisa 1 atau 0 Indeks. Silakan tentukan).

Contoh dan Uji kasus (1 Indeks)

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

• Keluaran [3, 3, 1, 3, 2]

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

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

• [[3,0,1],[3,180,3]]Output yang diberikan[1,1,4,4,4]

• [[2,180,1],[2,0,3]]Output yang diberikan[2,2,4,3,3]

Catatan

• Ini adalah kode-golf
• Baris / Kolom dapat berupa Indeks 1 atau 0. Silakan tentukan.
• Anda dapat mendefinisikan kembali nilai input (mungkin Anda ingin memanggil bagian 1 sebagai A, dll.). Dalam hal ini harap tentukan

Pertanyaan

• Bisakah kita menggunakan 4 nilai berbeda daripada sudut dalam derajat ?: Ya

• Apakah kita seharusnya menangani "lubang" jika sepotong tidak benar-benar cocok dengan yang sebelumnya ?: Ya

• Apakah tinggi atau lebar papan dibatasi? Tidak. Baik lebar maupun tinggi tidak dibatasi

Terima kasih @Arnauld untuk gambar dan test case *. *

JavaScript (Node.js) ,  286 284 270  266 bytes

$[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

Cobalah online! atau coba versi yang disempurnakan yang juga menampilkan papan akhir.

Pengkodean bentuk

Semua bagian disimpan persis 4 nibble (4x4 bit) dengan baris diurutkan dalam urutan terbalik dan piksel paling kiri dipetakan ke bit paling tidak signifikan. Dengan kata lain, representasi biner dari bentuk tersebut dicerminkan secara vertikal dan horizontal.

Contoh:

Fungsi hash dan tabel pencarian

$p \in [0..6]$$r \in [0..3]$$y \in [0..3]$$n$ dari bitmask yang sesuai dari tabel pencarian:

$82$$0$ .

Entri-entri ini dikemas sebagai:

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

yang mengembang ke 82 camilan berikut:

"717433667233ff47173333276611000000000000113213001112221112123333333311133233221211"

$I$"ff"

Parameter fungsi hash dipaksakan dengan cara yang mengoptimalkan nol awal dan akhir. Fakta bahwa string dapat dikompres lagi dengan menggunakan1e12 untuk nol di tengah dan konversi dari basis-16 ke basis-4 untuk bagian kanan hanyalah efek samping yang diterima tetapi tidak terduga. :-)

Ini sebuah demonstrasi proses pembongkaran untuk semua bagian dan semua rotasi.

Berkomentar

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 (dentang) , 253 239 221 212 byte

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

Cobalah online!

ps Sebenarnya ukuran kode adalah 221 byte (tetapi 212 karakter) karena karakter UNICODE dikodekan dalam UTF-8. Tapi tio.run memperlakukannya sebagai kode 212 byte ...

Ukuran kode pada komputer saya adalah 209 karakter (218 byte). Tapi saya tidak bisa mengganti \225dengan char terlihat di tio.run 😞

Kode tidak dikunci

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

Deskripsi

Mari kita temukan garis dasar atas ( TBL ) dari setiap gambar dan menggambarkannya sebagai sejumlah sel di bawah TBL untuk setiap posisi horizontal. Juga mari kita jelaskan jumlah sel (tinggi) di atas TBL ( HAT )

Misalnya:

                       ________ ________
_ [] _____ 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

Mari kita gambarkan TBL dan HAT untuk setiap gambar dan setiap sudut rotasi:

Lebar TBL HAT
----- ------- -------
L-angka:
  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-gambar:
  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 °

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

Zigzag:
  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 °

Kubus:
  2 2 2 0 0 // sudut mana pun

Sekarang kita harus mengkodekan angka-angka ini sebagai urutan 2 bit dan dimasukkan ke dalam sebuah array (menggantikan 4 0oleh 3 190 ° sudut "line" untuk menyesuaikan diri 2 bit - hasil akan sama, dan penurunan lebar oleh 1).

Kami akan menyandikan secara berurutan: lebar (dalam 2 LSB), TBL , HAT (mundur untuk loop mundur). Misalnya 2 2 1 1 0 untuk 270 ° sudut T-angka akan dikodekan sebagai 1 0 1 2 1(terakhir 1 adalah lebar-1 ): 0b0100011001 = 281.

diperbarui 12.02:

a) Saya telah mengubah array menjadi string dan menyimpan 18 karakter (Anda dapat melihat kode 239 byte sebelumnya ) :))

b) Lebih optimasi, kode disusutkan oleh 9 karakter.
Ini adalah upaya terakhir saya (saya pikir begitu, lol!) 😀

Common Lisp, 634 bytes

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

Verbose

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

Menguji

Potongan-potongan adalah daftar bundar daftar angka. Sub-daftar ini masing-masing mewakili sisi bentuk, angka-angka yang menunjukkan seberapa jauh mereka dari sisi yang berlawanan. Mereka dibiarkan ke kanan ketika sisi itu di bagian bawah, kanan ke kiri ketika di atas, atas ke bawah ketika di kiri, dan bawah ke atas ketika di kanan. Pilihan desain ini menghilangkan kebutuhan untuk menulis kode untuk rotasi. Sayangnya, kurangnya kode rotasi tampaknya tidak menebus representasi bentuk yang panjang, atau logika yang agak rumit yang saya gunakan untuk menghitung ketinggian kolom baru.

Rotasi adalah bilangan bulat non-negatif. 0 = 0 derajat, 1 = 90 derajat, 2 = 180 derajat, 4 = 270 derajat

C # (Visual C # Interactive Compiler) , 308 byte

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

Cobalah online!

OK - Itu gila ... Saya mengirimkan jawaban yang menggunakan teknik kode-golf run-of-the-mill. Tetapi ketika saya melihat apa yang disampaikan orang lain, saya menyadari ada cara yang lebih baik.

Setiap (shape, rotation)tuple dikodekan ke dalam string C # literal dengan duplikat dihapus. Proses pengkodean menangkap masing-masing konfigurasi ini dalam 2 byte.

Tinggi toko 3 bit terendah dan 3 lebar toko berikutnya. Karena masing-masing nilai ini tidak pernah lebih dari 4, nilai tersebut dapat dibaca langsung dari 3 bit tanpa konversi apa pun. Berikut ini beberapa contohnya:

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

Selanjutnya, setiap kolom disimpan dalam 3 bit. Yang paling berguna bagi saya untuk menyimpan adalah jumlah kotak yang hilang dari bagian atas dan bawah kolom.

// 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 ------+

Tidak pernah ada lebih dari 2 kotak yang hilang dari atas atau bawah, dan tidak pernah lebih dari 1 kotak hilang dari keduanya pada saat yang sama. Dengan serangkaian kendala ini, saya menghasilkan pengkodean berikut:

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

Karena kita harus menghitung paling banyak 3 kolom dengan kotak yang hilang di atas atau di bawah, kita dapat menyandikan setiap (shape, rotation)tuple dalam 15 bit.

 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

Terakhir, bentuk duplikat telah dihapus. Contoh berikut menunjukkan bagaimana beberapa (shape,rotation)tupel dapat menghasilkan output duplikat untuk bentuk yang sama pada rotasi yang berbeda:

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

Semua output unik ditentukan dan disimpan ke a byte[]dan dikonversi ke string C # literal. Untuk mencari dengan cepat di mana bentuk didasarkan pada Idan R, 7 byte pertama dari array terdiri dari kunci pencarian yang dikodekan.

Di bawah ini adalah tautan ke program yang saya gunakan untuk mengompres bagian-bagian itu.

Cobalah online!

Lebih sedikit kode golf dan komentar:

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

Arang , 98 byte

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

Cobalah online! Tautan adalah untuk mengucapkan versi kode. Mengambil input sebagai array nilai [P, R, I], di mana saya dari 0 hingga 6, R adalah dari 0 o 3 dan P juga diindeks 0. Penjelasan:

Ｆθ«

Ulangi potongan input.

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

Ekstrak deskripsi potongan dan rotasi saat ini. (Lihat di bawah.)

≔⊟ιζ

Ekstrak posisi.

Ｗ‹Ｌυ⁺ζＬη⊞υ⁰

Pastikan ada ruang horizontal yang cukup untuk meletakkan potongan.

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

Pastikan ada ruang vertikal yang cukup untuk menempatkan potongan.

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

Hitung ketinggian baru dari kolom yang terpengaruh.

»Ｉυ

Ketika semua bagian telah diproses, buat daftar akhir ketinggian kolom pada baris yang berbeda.

String yang dikompresi mewakili string asli 00001923001061443168200318613441602332034173203014614341642430137. Di sini 2s adalah Ipemisah dan 1s adalah Rpemisah. Potongan-potongan itu diterjemahkan sebagai berikut:

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

RNilai yang hilang secara otomatis diisi secara siklis oleh Charcoal. Setiap digit kemudian memetakan ke dua nilai, overhang dan tinggi total, sesuai dengan tabel berikut:

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

Overhang dan tinggi total berhubungan dengan ketinggian kolom sebagai berikut: Mengingat sepotong yang ingin kita tempatkan pada posisi tertentu e, dimungkinkan untuk menempatkan potongan meskipun salah satu kolom lebih tinggi dari e. Jumlah ruang cadangan diberikan oleh emperan. Ketinggian baru kolom setelah menempatkan potongan hanyalah posisi ditempatkan ditambah tinggi total.

Contoh: Misalkan kita mulai dengan menempatkan 5bagian dalam kolom 1. Karena tidak ada yang lain maka bagian itu ditempatkan di posisi 0 dan kolom 1 dan 3 sekarang memiliki tinggi 1 sedangkan kolom 2 memiliki tinggi 2. Kami kemudian ingin menempatkan 6sepotong dengan 1rotasi pada kolom 0. Di sini kita dapat menempatkan potongan ini pada posisi 0; meskipun kolom 1 memiliki tinggi 1, keping tersebut memiliki overhang 1, sehingga ada cukup ruang untuk meletakkannya. Kolom 0 berakhir dengan ketinggian 2 dan kolom 1 berakhir dengan ketinggian 3.