Deskripsi tantangan
Domino adalah permainan yang dimainkan dengan ubin dengan dua nilai di atasnya - satu di sebelah kiri, satu di sebelah kanan, misalnya [2|4]
atau [4|5]
. Dua ubin bisa digabung bersama jika mengandung nilai yang sama. Dua ubin di atas dapat digabungkan seperti ini:
[2|4][4|5]
Kami akan menyebut urutan n
ubin yang bergabung dengan rantai panjang n. Tentu saja, ubin bisa diputar, jadi ubin [1|2]
, [1|3]
dan [5|3]
bisa disusun ulang menjadi rantai [2|1][1|3][3|5]
dengan panjang 3.
Diberikan daftar pasang bilangan bulat, tentukan panjang rantai terpanjang yang dapat dibentuk menggunakan ubin ini. Jika daftar kosong, jawaban yang benar adalah 0
(perhatikan bahwa Anda selalu dapat membentuk rantai panjang 1
dari daftar ubin yang tidak kosong).
Contoh input / output
[(0, -1), (1, -1), (0, 3), (3, 0), (3, 1), (-2, -1), (0, -1), (2, -2), (-1, 2), (3, -3)] -> 10
([-1|0][0|-1][-1|2][2|-2][-2|-1][-1|1][1|3][3|0][0|3][3|-3])
[(17, -7), (4, -9), (12, -3), (-17, -17), (14, -10), (-6, 17), (-16, 5), (-3, -16), (-16, 19), (12, -8)] -> 4
([5|-16][-16|-3][-3|12][12|-8])
[(1, 1), (1, 1), (1, 1), (1, 1), (1, 1), (1, 1), (1, 1)] -> 7
([1|1][1|1][1|1][1|1][1|1][1|1][1|1])
[(0, 1), (2, 3), (4, 5), (6, 7), (8, 9), (10, 11)] -> 1
(any chain of length 1)
[] -> 0
(no chain can be formed)
code-golf
combinatorics
path-finding
dominoes
shooqie
sumber
sumber
O(n!)
sesuai keinginan AndaI guess it's P
Jawaban:
Brachylog , 23 byte
Cobalah online!
Penjelasan
Jadi dengan kata lain, untuk input seperti
[[1:2]:[1:3]:[5:3]]
, kami mencoba mengaturnya kembali menjadi rantai yang valid[[2:1]:[1:3]:[3:5]]
, kemudian ratakan / pangkas / hapuskan untuk menghasilkan[1:1:3:3:5:_]
(di mana_
merupakan yang tidak diketahui). Kombinasi dari~c
dan:{…l2}a
secara efektif membagi ini menjadi kelompok-kelompok 2 elemen, dan kami memastikan bahwa semua kelompok adalah sama. Saat kami meratakan (menggandakan panjang), menghapus satu elemen dari awal dan menambahkan satu di akhir (tidak ada perubahan), dan dikelompokkan menjadi berpasangan (membagi dua panjangnya), ini akan memiliki panjang yang sama dengan rantai domino asli.Instruksi "pemenggalan" akan gagal jika tidak ada domino di input (sebenarnya, IIRC
:pa
juga akan gagal;a
tidak suka daftar kosong), jadi kita perlu kasus khusus untuk 0. (Satu alasan besar kita memiliki asimetri antarab
dan~k
begitu bahwa kita tidak perlu kasus khusus untuk 1.)sumber
Brachylog , 29 byte
Cobalah online!
Cukup yakin ini sangat panjang, tapi terserahlah. Ini juga sangat lambat.
Penjelasan
Alasan ini akan menemukan yang terbesar adalah karena
s - subset
menghasilkan poin pilihan dari subset terbesar ke terkecil.sumber
Mathematica, 191 byte
Bisa bermain golf sedikit, saya yakin. Tetapi pada dasarnya algoritma yang sama seperti pada jawaban Brachylog dari Fatalize , dengan tes yang sedikit berbeda pada akhirnya.
sumber
Differences/@Rest@Flatten@#~Partition~2
alih-alihDifferences/@Partition[Rest@Flatten@#,2]
(Infix
memiliki prioritas lebih tinggi dariMap
)JavaScript (Firefox 30-57), 92 byte
l
adalah nilai terakhir, atauundefined
untuk doa awal.l-n
Oleh karena itu nilai yang salah jika domino dapat dimainkan.d
adalah domino yang dipertimbangkan.n
adalah akhir domino yang sedang dipertimbangkan untuk dirantai ke domino sebelumnya. Ujung lainnya dapat dengan mudah dihitung sebagaid[0]+d[1]-n
.0,
hanya menangani kasus dasar tidak ada kartu domino yang dapat dimainkan.sumber
Haskell ,
180 134131117 byteCobalah online! Pendekatan baru ternyata lebih pendek dan lebih efisien. Alih-alih semua permutasi yang mungkin hanya semua rantai yang valid dibangun.
Sunting: Versi 117 byte jauh lebih lambat lagi, tetapi masih lebih cepat dari brute-force.
Metode gaya lama:
Ini adalah implementasi brute-force yang mencoba semua permutasi yang mungkin (Jumlah permutasi yang mungkin tampaknya diberikan oleh A000165 , " faktorial ganda bilangan genap "). Cobalah secara online hanya mengelola input hingga panjang 7 (yang agak mengesankan karena 7 sesuai dengan 645120 permutasi).
Pemakaian:
sumber
Python 2, 279 byte
Golf:
Cobalah online!
Hal yang sama dengan beberapa komentar:
Saya memposting karena saya tidak melihat jawaban python ... seseorang akan melihat jawaban saya dan, dengan jijik, dipaksa untuk memposting sesuatu yang jauh lebih pendek dan efisien.
sumber
Clojure,
198183 bytePembaruan: Penanganan yang lebih baik dari "urutan maksimum yang mungkin kosong"
Versi sebelumnya:
Konvensi panggilan dan uji kasus:
F
mengembalikan elemen daftarC
tanpa elemena
,M
mengembalikan maksimal ingerer input atau 1.L
adalah fungsi utama, ketika dipanggil dengan argumen tunggal ia menghasilkan semua potongan awal yang mungkin dan menemukan panjang maks untuk masing-masing. Ketika dipanggil dengan dua argumen, itul
adalah elemen pertama dari urutan yang cocok dengan bagian berikutnya danR
sisanya dari potongan.Menghasilkan permutasi dan "memilih satu elemen dan membelah untuk beristirahat" cukup sulit untuk diterapkan secara ringkas.
sumber