Chờ đã, đó là tetromino nào?
Lý lịch
Tetris là một trò chơi một người chơi trên một lưới hình chữ nhật với các mảnh tetromino.
Khi bạn tô một hoặc nhiều dòng bằng tetrominoes, các dòng đã tô sẽ bị xóa và tất cả các khối phía trên chúng sẽ di chuyển xuống tương ứng. Trong các sơ đồ sau, .là một không gian trống, #là một khối hiện có và tetromino được đánh dấu bằng As là khối vừa được đặt:
One line cleared example
#...AA.. -> ........
####AA## #...##..
---
Two lines cleared example
(note that the 3rd line moved down once, while the top line moved twice)
...A.... ........
###A#### ........
##.A.##. -> ...#....
###A#### ##.#.##.
####.### ####.###
Thử thách
Hai trạng thái bảng sẽ được đưa ra làm đầu vào. Một là ngay trước khi một tetromino cụ thể xuất hiện (trạng thái bên trái của các sơ đồ trên, không có As), và một là ngay sau khi tetromino được đặt và việc xóa dòng hoàn tất (trạng thái bên phải). Với thông tin này, hãy khôi phục loại tetromino được đặt giữa hai trạng thái, là một trong bảy loại sau:
O J L S T Z I
## # # ## # ## ####
## ### ### ## ### ##
Bạn có thể giả định như sau:
- Đầu vào hợp lệ; hai bảng có cùng kích thước và trạng thái trò chơi có thể được thay đổi từ bảng đầu tiên sang bảng thứ hai bằng cách đặt một tetromino duy nhất. Ngoài ra, tetromino được đặt nằm hoàn toàn bên trong lưới trước khi việc xóa dòng xảy ra (tức là nó sẽ không được đặt trên trần của lưới đã cho, thậm chí một phần).
- Câu trả lời là duy nhất.
- Chiều rộng của bảng ít nhất là 5.
Đối với thử thách này, hãy bỏ qua các quy tắc xoay của trò chơi Tetris thực tế và giả định rằng mọi vị trí đặt tetromino đều hợp lệ, miễn là tetromino không chồng lên các khối hiện có hoặc lơ lửng trong không khí. Điều này cho phép đặt một tetromino bên trong một phòng kín (điều này thực sự xảy ra trong một số trò chơi kỳ lạ).
Bạn có thể lấy đầu vào dưới dạng ma trận (hoặc tương đương) bao gồm hai giá trị khác nhau cho khoảng trắng và khối. Bạn có thể xuất loại tetromino dưới dạng một trong bảy giá trị riêng biệt mà bạn chọn. Các định dạng đầu ra được phép bao gồm số, chuỗi và có thể là các mảng số và / hoặc chuỗi lồng nhau hoặc nhiều chiều.
Luật chơi gôn tiêu chuẩn được áp dụng. Mã ngắn nhất tính bằng byte sẽ thắng.
Các trường hợp thử nghiệm
Kí hiệu giống như ví dụ trên. Beforevà Afterlà hai lưới đầu vào, Answerlà đầu ra dự kiến (được đưa ra dưới dạng mã bảng chữ cái) và Explanationhiển thị vị trí đặt tetromino.
Before:
......
......
After:
..##..
..##..
Answer: O
Explanation:
..AA..
..AA..
----------------
Before:
..####
...###
#.####
After:
......
......
..####
Answer: T
Explanation:
..####
AAA###
#A####
----------------
Before:
...###
...###
#.....
After:
......
..####
#.....
Answer: L (J doesn't work since the piece will be floating)
Explanation:
..A###
AAA###
#.....
----------------
Before:
##..##
##..##
##..##
After:
......
###.##
##.###
Answer: S
Explanation:
##A.##
##AA##
##.A##
----------------
Before:
##.##
##..#
##.##
After:
.....
.....
.....
Answer: T
Explanation: self-explanatory
----------------
Before:
.###.
#...#
.....
#...#
.###.
After:
.....
.###.
#...#
..#..
.###.
Answer: T
Explanation:
.###.
#...#
..A..
#AAA#
.###.
Trả lời
JavaScript (ES10), 286 282 byte
Kỳ vọng (a)(b), ở đâu \$a\$và \$b\$là 2 danh sách các chuỗi nhị phân. Trả về một số nguyên giữa \$0\$và \$6\$cho JLTIOZS, hoặc \$-1\$ nếu không có giải pháp (nhưng chúng tôi không nên hỗ trợ điều đó).
a=>b=>"0NF71ZMA13FM000F1F1F1IFL2R8I38LT357N368H".match(/../g).findIndex(p=>b.some((r,y)=>[...r].some((_,x)=>!b.some((s,i)=>[...a.map(B=r=>'0b'+r),~0].flatMap(t=(r,Y,a)=>~(q=((parseInt(p,36)||4369)>>(Y-y)*4&15)<<x,t|=q&a[Y+1],q|=q&r?~0:r)+2**s.length?q:(i--,[]))[i]^B(s)|!t))))%14>>1
Hãy thử nó trực tuyến!
Làm sao?
Mã hóa hình dạng
Mỗi hình dạng được mã hóa bằng 2 chữ số trong cơ số 36, cho phép lưu trữ:
$$\lfloor 2\times\log_2 36\rfloor=10\text{ bits}$$
Các bit được sắp xếp trong một \$4\times 4\$ma trận, với mảnh được nêm ở góc trên bên phải. Bit ít quan trọng nhất được ánh xạ tới ô trên cùng bên phải và có 6 số 0 ngầm ở đầu.
Ví dụ:
1 st entry là
0Nở cơ sở 36, đó là \$23\$ở dạng thập phân và \$0000010111\$trong hệ nhị phân. Đây là mộtJ.Mục nhập thứ 6
FMở cơ số 36, là \$562\$ở dạng thập phân và \$1000110010\$trong hệ nhị phân. Đây là mộtT.
Tất cả các hình dạng có thể được mã hóa theo cách đó, ngoại trừ chiều dọc I. Cái này được mã hóa thành 00và giá trị thực của nó ( \$4369\$ trong số thập phân) được mã hóa cứng riêng biệt.
Thuật toán chính
Thuật toán chính bao gồm 5 vòng lặp lồng nhau, nơi chúng tôi cố gắng đặt từng hình dạng \$p\$ở mỗi vị trí có thể có \$(x,y)\$trong lưới \$a\$và tìm ra cái nào dẫn đến lưới \$b\$.
Bất cứ khi nào một hàng được hoàn thành, chúng tôi mang lại một mảng trống để .flatMap()xóa hàng này và chúng tôi giảm chỉ số \$i\$ của mục nhập cần được đọc trong mảng kết quả để giải thích cho sự dịch chuyển hàng.
Chúng tôi có thể kết thúc bằng một tiêu cực \$i\$. Nhưng vì chúng tôi sử dụng XOR để so sánh, các hàng không xác định sẽ hoạt động như thể chúng được đặt thành \$0\$, đó là những gì chúng tôi muốn.
"...".match(/../g) // list of shapes
.findIndex(p => // for each shape p:
b.some((r, y) => // for each y:
[...r].some((_, x) => // for each x:
!b.some((s, i)=> // for each row s at position i in b:
[ ...a.map( // using the helper function B, decode a[] by
B = r => '0b' + r // converting each binary string to an integer
), ~0 // and append a full line at the bottom
].flatMap(t = // initialize t to a non-numeric value
(r, Y, a) => // for each row r at position Y in this array:
~( //
q = ( // q is the 4-bit mask of the shape
( parseInt(p, 36) // decoded from the base-36 value p,
|| 4369 ) //
>> (Y - y) * 4 // keeping only the bits for this row
& 15 //
) << x, // and left-shifting by x
t |= q & a[Y + 1], // update the 'touching' mask
q |= q & r ? ~0 // invalidate the row if q overlaps r
: r // otherwise, merge q and r
) + 2 ** s.length ? // if the resulting line is not full:
q // yield q
: // else:
(i--, []) // decrement i and yield an empty array,
// which results in the deletion of this
// line by flatMap()
)[i] // end of flatMap(); extract the i-th row
^ B(s) // the test fails if this row is not equal to s
| !t // or the shape is floating in the air
) // end of some()
) // end of some()
) // end of some()
) // end of findIndex()
Kết quả cuối cùng
Các hình dạng được lưu trữ theo thứ tự sau:
0N F7 1Z MA 13 FM 00 0F 1F 1F 1I FL 2R 8I 38 LT 35 7N 36 8H
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
J J L L T T I I O O Z Z S S J J L L T Tđó là lý do tại sao kết quả cuối cùng là giá trị được trả về bởi .findIndex()modulo \$14\$, chia cho \$2\$và làm tròn về phía \$0\$.
(NB: Hình dạng Ođược lưu trữ hai lần để nó không bị vỡ mẫu.)
Brachylog , 156 124 byte
Lấy hai ma trận, 1cho biết một ô trống, 2cho biết một ô có một mảnh. Bản đồ O => 15, I => 1, J => 57, L => 60, S => 30, T => 23, Z => 51.
hI{∧Ḋ}ᵐ²O;I{zzᵐ+ᵐ²};21ẹᵗ↔c{≡ᵛ²h|∧1}ᵍbᵐ{-₁ᵐ²}ʰc~t?&h{{∧2}ᵐ}ʰ↺₁;O↰₂c∋3∧O{{¬=₀&}ˢ\}↰₇{\↔ᵐ|}{↔↔ᵐ|}{l₂ccẹ~ḃ{15|23|30|51|57|60}}|1
Hãy thử nó trực tuyến! hoặc thử tất cả các trường hợp thử nghiệm (với I / O đẹp hơn)! (Số byte dài hơn một chút vì tiêu đề tăng số vị từ.)
Làm thế nào nó hoạt động
Chúng tôi tìm kiếm một ma trận Ođể đầu vào cộng Osau các quy tắc loại bỏ sẽ bằng đầu ra. Sau đó, chúng tôi cắt Ođể chứa một submatrix, được bao quanh bởi tetromino. Thử tất cả các định hướng, nó phù hợp với ma trận 2 x x - sau đó chúng ta có thể chuyển đổi nó từ cơ số 2. Nếu không thì nó là Imảnh.
h{∧Ḋ}ᵐ²O
Trước thử thách này, tôi sẽ tạo một ma trận có cùng thứ nguyên bằng cách lấy độ dài đầu vào, ánh xạ độ dài các hàng lên nó và nói rằng mọi phần tử phải là một số… nhưng điều này gọn gàng hơn nhiều: Olà đầu vào, nhưng mọi phần tử trong nó chỉ là một con số bất kỳ. Cái này gọn gàng hơn nhiều!
;I{zzᵐ+ᵐ²}
O + Đầu vào
;21ẹᵗ↔c{≡ᵛ²h|∧1}ᵍbᵐ
Đây là một cách rất phức tạp để chia các hàng thành ((chỉ chứa 2s), (không chỉ chứa 2s)). Có những phiên bản ngắn hơn về mặt kỹ thuật, nhưng tất cả những nỗ lực của tôi đều buộc phải gắn nhãn các con số, làm chậm chương trình xuống mức thô bạo. (Điều này thực sự khó chịu khi tìm thấy một phiên bản hoạt động được.)
{-₁ᵐ²}ʰc~t?
Trừ 1 khỏi các hàng đã loại bỏ và nối ((chỉ chứa 2 giây, bây giờ chỉ 1 giây), (còn lại)) lại với nhau. Điều này phải bằng với ma trận đầu vào thứ hai.
&h{{∧2}ᵐ}ʰ↺₁;O↰₃c∋3
Nếu chúng ta lấy ma trận đầu vào, đặt hàng trên cùng chỉ 2 giây, xoay nó lên và sau khi thêm vào Osẽ có 3: thì tetromino không nổi.
∧O{{¬=₀&}ˢ\}↰₅
Cắt Ođể nó chỉ chứa tetromino. Sẽ rất tốt nếu điều này có thể kết thúc ở đây. Tuy nhiên, Obây giờ không được đảm bảo là một tetromino và có thể là một số 1 bị ngắt kết nối. Vì thế …
{\↔ᵐ|}{↔↔ᵐ|}{l₂ccẹ~ḃ{15|23|30|51|57|60}}|1
Kiểm tra tất cả các phép quay và nếu đó là ma trận 2 x x, hãy chuyển đổi sang cơ số 2 và kiểm tra xem một trong các số có khớp không. Nếu không có gì phù hợp, đó là I mảnh.