Mari kita tentukan matriks yang tidak kosong, tidak disortir, dan terbatas dengan angka unik sebagai berikut:
Mari kita tentukan pergerakan 4 matriks sebagai:
- ↑ * (atas): Memindahkan kolom ke atas
- ↓ * (bawah): Memindahkan kolom ke bawah
- → * (kanan): Memindahkan satu baris ke kanan
- ← * (kiri): Memindahkan satu baris ke kiri
Tanda bintang (*) mewakili kolom / baris yang dipengaruhi oleh gerakan (Dapat diindeks 0 atau diindeks 1. Terserah Anda. Sebutkan yang mana dalam jawaban Anda).
Tantangannya adalah, menggunakan gerakan di atas, urutkan matriks dalam urutan naik (menjadi sudut kiri atas yang terendah dan sudut kanan bawah yang tertinggi).
Contoh
Input:
↑0
atau ↓0
. (Perhatikan semua gerakan itu dapat mengurutkan matriks sehingga kedua jawabannya benar)
Input:
→0
Input (Contoh test case):
↑0↑1←1↑2
Input:
↑0↑2→0→2↑0→2↑1↑2←1
↑2↑1←3→0←3↓0←0←2→3↑3↑4
Catatan
- Mungkin ada keluaran yang benar berbeda (tidak perlu harus sama dengan kasus uji atau yang terpendek)
- Anda dapat menganggap itu akan selalu menjadi cara untuk memesan matriks
- Tepi menghubungkan (seperti pacman: v)
- Tidak akan ada matriks dengan lebih dari 9 kolom atau / dan baris
- Asumsikan matriks hanya berisi bilangan bulat unik bukan nol yang positif
- Anda dapat menggunakan 4 nilai berbeda selain angka untuk mewakili gerakan (dalam hal itu, harap sebutkan dalam jawaban Anda)
- Kolom / baris dapat diindeks 0 atau 1
- Kode kriteria menang golf
Kasus uji ekstra selalu diterima
←0←0
solusi yang valid untuk contoh kedua di mana Anda telah memberikan solusi sebagai→0
. Jika ya, saya pikir setengah dari opsi pemindahan kemungkinan tidak akan digunakan.Jawaban:
JavaScript (ES6),
226219 bytePencarian kasar, menggunakan gerakan kanan (
"R"
) dan turun ("D"
).Mengembalikan string yang menggambarkan gerakan, atau array kosong jika matriks input sudah diurutkan. Kolom dan baris dalam output diindeks 0.
Cobalah online!
Berkomentar
sumber
Python 2 , 296 277 245Python 3 ,200194 byteCobalah online!
-19: panah unicode tidak diperlukan ...
-32: sedikit ulang, tapi kinerja lebih lambat rata-rata.
-45: mengambil inspirasi dari jawaban @ Arnauld. Beralih ke Python 3 untuk
f''
(-4 byte)-6:
range( )
→r_[: ]
,diff(ravel( ))
→ediff1d( )
Secara teliti mencari kombinasi dari semua kemungkinan
↓
gerakan dan→0
. Hentikan uji kasus ketiga.Karena
→n
setara dengandi mana
r
danc
jumlah baris dan kolom, gerakan ini cukup untuk menemukan setiap solusi.>v
masing-masing sesuai dengan→↓
. (lainnya tidak terdefinisi)sumber
Jelly , 35 byte
Cobalah online!
Program lengkap. Output bergerak ke STDOUT menggunakan L untuk kiri dan R untuk kanan. Terus mencoba gerakan acak sampai matriks diurutkan, jadi tidak terlalu efisien dalam hal kecepatan atau kompleksitas algoritmik.
sumber