Permainan BattleBlock Theater kadang-kadang berisi teka-teki yang merupakan versi umum dari Lights Out . Anda memiliki tiga blok yang berdekatan, masing-masing menunjukkan tingkat antara 1 dan 4 termasuk dengan bar, misalnya:
|
||||
||
Jika Anda menyentuh sebuah blok, maka blok itu serta blok yang berdekatan akan menambah levelnya (membungkus kembali dari 4 ke 1). Teka-teki diselesaikan ketika ketiga blok menunjukkan level yang sama (tidak masalah level mana). Karena, urutan Anda menyentuh blok tidak menjadi masalah, kami menunjukkan solusi dengan seberapa sering setiap blok disentuh. Solusi optimal untuk input di atas adalah 201
:
| --> || --> ||| |||
|||| | || |||
|| || || --> |||
Gim ini sangat mudah menggeneralisasikan sejumlah blok, meskipun untuk beberapa angka, tidak semua konfigurasi dapat dipecahkan.
Tantangan
Diberikan urutan level blok, kembalikan seberapa sering setiap blok perlu disentuh untuk memecahkan teka-teki. Misalnya contoh di atas akan diberikan sebagai 142
dan dapat menghasilkan 201
sebagai hasilnya. Jika tidak ada solusi, kembalikan beberapa output yang konsisten dari pilihan Anda, yang dapat dibedakan dari semua solusi potensial, misalnya -1
atau string kosong.
Anda dapat menulis suatu fungsi atau program, mengambil input melalui STDIN, argumen baris perintah atau argumen fungsi, dalam setiap format daftar atau string yang mudah, dan dengan cara yang sama menghasilkan melalui nilai balik atau dengan mencetak ke STDOUT.
Kode Anda harus mengembalikan hasil yang benar untuk semua kasus uji dalam satu menit pada mesin yang masuk akal. (Ini bukan batas yang sepenuhnya ketat, jadi jika solusi Anda membutuhkan satu menit dan sepuluh detik, itu baik-baik saja, tetapi jika dibutuhkan 3 menit, tidak. Algoritma yang baik akan dengan mudah menyelesaikannya dalam hitungan detik.)
Ini kode golf, jadi jawaban tersingkat (dalam byte) menang.
Contohnya
Solusi tidak unik, sehingga Anda dapat memperoleh hasil yang berbeda.
Input Output
1 0
11 00
12 No solution
142 201
434 101
222 000
4113 0230
32444 No solution
23432 10301
421232 212301
3442223221221422412334 0330130000130202221111
22231244334432131322442 No solution
111111111111111111111222 000000000000000000000030
111111111111111111111234 100100100100100100100133
412224131444114441432434 113013201011001101012133
Sejauh yang saya tahu, ada tepat 4 solusi untuk setiap input di mana jumlah blok adalah 0 mod 3, atau 1 mod 3, dan ada 0 atau 16 solusi di mana itu adalah 2 mod 3.
sumber
Jawaban:
Python 2, 115 byte
Ini adalah versi golf dari program yang saya tulis ketika membahas masalah dengan Martin.
Input adalah daftar melalui STDIN. Output adalah daftar yang mewakili solusi terakhir yang ditemukan jika ada solusi, atau nol jika tidak ada. Sebagai contoh:
Pyth,
3229 bytePelabuhan wajib. Berkat @ Jakube untuk penghematan 3 byte.
Metode input sama seperti di atas, coba online .
Penjelasan (panjang dan penuh logika!)
Pertama, dua pengamatan dasar:
Pengamatan 1: Tidak masalah urutan mana yang Anda sentuh blok
Pengamatan 2: Jika Anda menyentuh blok 4 kali, itu setara dengan menyentuhnya satu kali
Dengan kata lain, jika ada solusi maka ada solusi di mana jumlah sentuhan adalah antara 0 dan 3 inklusif.
Karena modulo 4 sangat bagus, mari kita lakukan dengan balok juga. Untuk sisa penjelasan ini, level blok 0 setara dengan level blok 4.
Sekarang mari kita menyatakan
a[k]
sebagai level blok saat inik
danx[k]
menjadi berapa kali kita menyentuh blokk
dalam suatu solusi. Juga biarlahn
jumlah total blok. Seperti yang telah dicatat @Jakube, solusi harus memuaskan:di mana
C
level akhir semua blok berakhir, antara 0 dan 3 inklusif (ingat kita memperlakukan level 4 sebagai level 0) dan semua persamaan di atas benar-benar sesuai dengan modulo 4.Sekarang inilah bagian yang menyenangkan:
0 <= C <= 3
.Ada tiga kasus berdasarkan jumlah blok modulo 3. Penjelasan untuk masing-masing blok adalah sama - untuk sejumlah blok, ada subset blok yang, jika Anda menyentuh masing-masing satu kali, menambah semua level blok dengan tepat 1.
Ini menjelaskan mengapa ada 4 solusi untuk
0 mod 3
dan1 mod 3
, dan biasanya 16 solusi untuk2 mod 3
. Jika Anda sudah memiliki solusi, menyentuh blok seperti di atas memberikan solusi lain yang berakhir pada level blok yang lebih tinggi (melilit).Jadi apa artinya ini? Kami dapat memilih level blok akhir mana pun
C
kami inginkan! Mari kita pilihC = 0
, karena ini menghemat byte.Sekarang persamaan kami menjadi:
Dan mengatur ulang:
Jadi yang bisa kita lihat adalah, jika ada
x[0]
, maka kita bisa menggunakan semua persamaan kecuali yang terakhir untuk mencari tahu satu sama lainx[k]
. Persamaan terakhir adalah kondisi tambahan yang harus kita periksa.Ini memberi kami sebuah algoritma:
x[0]
x[k]
Itu memberikan solusi di atas.
Jadi mengapa kita terkadang tidak mendapat solusi
2 mod 3
? Mari kita lihat dua pola ini lagi:Sekarang perhatikan persamaan pada posisi-posisi itu, yaitu untuk yang pertama:
Tambahkan mereka:
Untuk yang kedua:
Tambahkan lagi:
Jadi jika
(a[1] + a[4] + a[7] + a[10])
dan(a[0] + a[3] + a[6] + a[9])
tidak sama, maka kita tidak punya solusi. Tetapi jika mereka sama, maka kita mendapatkan 16 solusi. Ini untukn = 11
kasus ini, tetapi tentu saja hal ini bersifat umum ke nomor apa pun2 mod 3
- ambil jumlah setiap elemen ketiga mulai dari yang kedua, dan bandingkan dengan jumlah setiap elemen ketiga mulai dari yang pertama.Sekarang akhirnya, apakah mungkin untuk mencari tahu apa yang
x[0]
harus terjadi daripada mencoba semua kemungkinan? Setelah semua, karena kita dibatasi tingkat target kamiC
untuk menjadi 0, hanya ada satux[0]
yang memberikan solusi dalam0 mod 3
atau1 mod 3
kasus (sebagai4 solutions / 4 final levels = 1 solution for a specific final level
).Jawabannya iya! Kita dapat melakukan ini untuk
0 mod 3
:Yang diterjemahkan menjadi:
Mengurangkan memberi:
Demikian pula untuk
1 mod 3
kita dapat melakukan pola ini:Pemberian yang mana:
Ini tentu saja menggeneralisasi dengan memperluas indeks dengan kenaikan 3.
Karena
2 mod 3
, karena kami memiliki dua himpunan bagian yang mencakup setiap blok, kami dapat memilihnyax[0]
. Bahkan, ini berlaku untukx[0], x[1], x[3], x[4], x[6], x[7], ...
(pada dasarnya setiap indeks tidak kongruen2 mod 3
, karena mereka tidak tercakup oleh salah satu bagian).Jadi kami memiliki cara memilih
x[0]
alih - alih mencoba semua kemungkinan ...... tetapi berita buruknya adalah ini tidak menghemat byte (124 byte):
sumber
J
alih-alihH
dan 2 karakter, jika Anda menghapus elemen terakhirPJ
alih-alih mengiris.<J_1
.V4J]NVQaJ%_+s>J_2@QN4)I!eJPJB
Pyth,
727673663938 karaktersunting 4: Direalisasikan, bahwa perhitungan
Q[N]-Q[N+1]+solution[-3]
danQ[-2]-Q[-1]+solution[-3]
diidentifikasi. Karena itu saya menghitung terlalu tinggi solusinya dengan 1, dan menyaring solusi, di mana entri terakhir adalah 0. Lalu saya memunculkan entri terakhir. Untungnya kasus-kasus khusus tidak memerlukan perawatan tambahan dengan pendekatan ini. -27 karaktersunting 3: Menerapkan beberapa trik golf dari FryAmTheEggman: -7 karakter
sunting 2: Menggunakan filter, kurangi dan petakan: -3 karakter
sunting 1: Dalam versi pertama saya, saya tidak mencetak apa pun, jika tidak ada solusi. Saya tidak berpikir itu diperbolehkan, oleh karena itu karakter +4.
Mengharapkan daftar bilangan bulat sebagai input
[1,4,2]
dan mengeluarkan solusi yang valid[2,0,1]
jika ada, jika tidak, daftar kosong[]
.Penjelasan:
Membiarkan
Q
menjadi daftar 5 level danY
daftar solusi. Persamaan berikut harus dipegang:Karena itu jika kita menggunakan
Y0
danY1
, kita dapat menghitungY2
,Y3
danY4
dengan cara berikut.Dari semua level kecuali yang terakhir sama (karena kami tidak menggunakan persamaan
= Q4 + Y3 + Y4
. Untuk mengecek, jika yang terakhir ini juga sama dengan level yang lain, kita cukup memeriksa apakah(Q3 - Q4 + Y2) mod 4 == 0
. Perhatikan, bahwa bagian kiri akan menjadi nilaiY5
Jika saya menghitung bagian keenam dari solusi, saya dapat dengan mudah memeriksa, apakah itu nol.Dalam pendekatan saya, saya hanya mengulangi semua mulai mungkin (
[0,0]
, untuk[3,3]
), dan menghitung panjang (input) -1 entri lebih banyak dan menyaring semua solusi yang berakhir dengan nol.pada dasarnya adalah sebagai berikut:
lalu saya filter solusi yang mungkin untuk yang valid:
untuk daftar solusi ini saya tambahkan daftar kosong, sehingga memiliki setidaknya satu item di dalamnya
dan ambil solusi pertama
h
, pop elemen terakhirp
dan cetakPerhatikan, bahwa ini juga berfungsi, jika hanya ada satu blok. Dalam pendekatan saya, saya mendapatkan posisi awal [0,0] dan tidak memperpanjangnya. Karena entri terakhir adalah 0, ia mencetak solusinya [0].
Kasus spesial kedua (2 blok) sama sekali tidak spesial. Tidak yakin, mengapa saya terlalu rumit sebelumnya.
sumber
?**lQ]0qhQeQ<lQ3h+f!%-+ePQ@T_3eQ4mu+G]%+&H@G_3-@QH@QhH4UttQd^UT2]Y
adalah 66 byte. Performanya sedikit terpukul, tetapi masih menjalankan test case terbesar dalam <1s untuk saya. Ping saya jika Anda ingin penjelasan tentang beberapa golf; tidak ada ruang yang cukup dalam komentar ini;) Harap Anda menikmati menggunakan Pyth: D+<list><int>
memiliki efek yang sama dengan+<list>]<int>
, jadi Anda dapat menghapus yang pertama]
. Juga, solusi yang sangat bagus.~
? Sepertinya tidak ketika saya mencoba~
dengana
-~<list>]<int>
sama dengana<list><int>
.~
adalah+=
, sementaraa
ini.append()
Ruby,
320313 karakterPasti bisa main golf lagi. Tidak menghasilkan apa-apa untuk puzzle yang tidak dapat diselesaikan.
Versi tidak disatukan:
Oke, ini menyenangkan. Inilah algoritma dasar, dengan
{n}
mewakili n "sentuhan" pada angka di atasn
, seperti yang ditunjukkan pada salah satu contoh:Saya sedikit bingung di sini. Bagaimana saya bisa mengubahnya
111...1110
menjadi serangkaian angka yang sama? Jadi saya membandingkan solusi saya dan solusi yang benar (catatan: jumlah "sentuhan" semuanya satu lebih besar dari yang seharusnya karena input 1-diindeks, sedangkan outputnya adalah 0-diindeks):Saya perhatikan bahwa setiap angka adalah satu dari yang benar
mod 4
, jadi saya menandainya dengan+
s,-
s, dan=
s:Itu bekerja sebentar, sampai saya perhatikan bahwa kadang-kadang hasil akhirnya
111...11112
atau11...1113
juga! Untungnya, berulang kali menerapkan formula ajaib yang tidak masuk akal tetapi bekerja juga memilah ini.Jadi, begitulah. Sebuah program yang mulai masuk akal, tetapi menurun menjadi lebih banyak dan lebih buruk lagi. Cukup khas untuk solusi kode golf, saya pikir. :)
sumber
exit if (r+=1)>5
ke(r+=1)>5&&exit
. Juga,(code)while cond
sintaks lebih pendek dariwhile cond \n code \n end
.Python 2,
294.289.285.281273 byteDEMO
Saya yakin ini bisa bermain golf lebih lanjut ..
Berikut adalah hasil dari kasus uji:
Algoritme pertama-tama memastikan bahwa nilai semua blok kecuali blok terakhir adalah sama (dengan mengulangi dan menambahkan "jumlah sentuhan" semua blok kecuali 2 yang pertama). Kemudian, jika jumlah blok memungkinkan (
(num_of_blocks - 1) % 3 != 1
), kembali dan pastikan nilai sisa blok sesuai dengan blok terakhir. Mencetakx
jika tidak ada solusi.sumber