Apakah ini permainan yang valid dari Five Up (Dominoes)?

8

Seperangkat domino terdiri dari ubin dengan dua angka di atasnya sehingga setiap kombinasi bilangan bulat dari 0 hingga N terwakili. Contoh di bawah ini mengacu pada N = 6 karena kenyamanan, tetapi N = 9 dan N = 12 juga umum. Orientasi ubin tidak masalah (biasanya dicetak dengan titik daripada angka), jadi [1-6]dan [6-1]lihat ubin yang sama, yang hanya ada satu dalam satu set.

Sebagian besar permainan yang dimainkan dengan kartu domino melibatkan pemain secara bergiliran menambahkan kartu domino ke garis yang sudah dimainkan di atas meja, sehingga salah satu angka pada kartu domino ditempatkan berdekatan dengan nomor yang sama di salah satu ujung garis kartu di atas meja. Dengan demikian, Anda dapat menambahkan a [2-5]ke salah satu ujung garis yang ada [2-3][3-3][3-5], memproduksi [5-2][2-3][3-3][3-5]atau [2-3][3-3][3-5][5-2].

Banyak permainan semacam itu membutuhkan "dobel", domino dengan dua nomor yang sama, harus ditempatkan tegak lurus terhadap domino lain yang terhubung dengannya. Selain dari penilaian yang tidak kami perhatikan di sini, ini tidak berpengaruh kecuali ketika ...

Banyak dari game-game itu kemudian memungkinkan "garis" untuk bercabang di beberapa atau semua ganda. Five Up adalah gim di mana garis dapat bercabang menjadi 3 baris baru di masing-masing double, sehingga keempat sisi double mungkin memiliki domino yang cocok.

Berikut adalah contoh tata letak domino dari set "double 6" dalam game Five Up (di mana A | B atau AB adalah domino tunggal):

     4
     -
     0

3|0 0|0 0|2

     0
     -
     1

4|1 1|1 1|6
                3
     1          -
     -          6
     5
                6
6|5 5|5 5|0 0|6 - 6|2 2|1
                6
     5
     -          6
     4          -
                4

Tugas Anda adalah untuk mengambil daftar domino dalam urutan di mana mereka ditambahkan ke meja, dan menentukan apakah pesanan ini merupakan permainan legal Five Up.

Anda dapat menulis seluruh program yang mengambil input dari stdin, atau fungsi yang mengambil input sebagai satu atau lebih parameter.

Input kanonik akan berupa daftar atau larik dua-tupel bilangan bulat. Daftar daftar, larik array, vektor tupel, dll adalah semua formulir yang valid untuk mengambil input, seperti string yang mewakili salah satu dari string di atas, atau banyak. Input hanya akan berisi pasangan bilangan bulat non-negatif, domino yang valid.

Output harus berupa nilai truey atau falsey, untuk masing-masing game yang valid dan tidak valid.

Kode Anda harus menerima nomor domino besar yang sewenang-wenang, dalam kemampuan nilai integer maksimum bahasa Anda.

Contoh:

  • 0-6 valid, seperti domino tunggal lainnya
  • 0-6 6-0tidak valid, hanya ada satu 0-6domino dalam satu set
  • 6-6 6-5 5-3 3-0 valid, pengaturan linier sederhana
  • 6-6 6-5 3-0 5-3tidak valid, tidak ada 3atau 0dalam permainan untuk domino ketiga untuk terhubung sebelum 5-3diputar
  • 1-1 1-2 1-3 1-4 1-5 1-6tidak valid, keempat 1ujung terbuka digunakan tanpa meninggalkan tempat untuk menghubungkan1-6
  • 1-1 1-2 1-3 1-4 1-5 3-6 1-6 valid, 3-6 terhubung ke 1-3, lalu 1-6 dapat terhubung ke 3-6
  • 5-5 5-4 5-0 0-6 6-6 6-4 6-2 2-1 6-3 5-1 1-1 1-6 4-1 1-0 0-0 2-0 3-0 0-4 valid, contoh ilustrasi di atas
  • 12-12 12-1 3-12 3-1 1-2 3-3 valid, menggunakan domino yang lebih besar, dan memiliki penempatan yang ambigu

CATATAN: Fungsi yang diperlukan di sini bukan pemeriksaan sempurna untuk game Five Up yang valid. Di sini kami mengabaikan aturan tentang domino mana yang akan dimainkan terlebih dahulu, yang akan membutuhkan lebih banyak informasi tentang varian permainan dan jumlah pemain, dan akan mendiskualifikasi sejumlah kecil input yang signifikan.

Sparr
sumber
Apakah kita perlu memperhitungkan kendala geometrik pada penempatan, yaitu rantai domino menabrak dirinya sendiri?
xnor
@xnor Anda tidak. Saya lupa menyebutkan konvensi umum bahwa "garis" dapat ditekuk secara sewenang-wenang untuk kenyamanan dalam permainan domino. juga baik untuk menghindari tepi meja :)
Sparr
Saya pikir itu mungkin untuk menghasilkan urutan permainan patologis dengan 12 set domino ganda yang tidak dapat menghindari persimpangan diri. Itu pasti mungkin dengan set yang lebih besar. Mari kita abaikan saja kasus-kasus itu. Kasus terburuk, mereka dapat diselesaikan dengan menekuk garis dalam 3D :)
Sparr
Apakah kita benar-benar harus mampu menangani domino yang memiliki nilai> 6? Jika demikian, dapatkah Anda membuatnya lebih jelas dalam spec dan mungkin menambahkan test case. Sebaliknya, tantangan yang bagus - +1 dari saya.
Shaggy
@Shaggy menambahkan test case untuk domino yang lebih besar
Sparr

Jawaban:

1

Haskell , 188 174 168 bytes

f(p:r)=[p]!r$p?p
(s!(p:r))o|b<-[p,reverse p]=or[(q:s)!r$q%o|q<-b,elem(q!!0)o,all(`notElem`s)b]
(s!_)o=1<3
p@[x,y]?r=[c|x==y,c<-p]++r
p@[x,y]%(a:r)|a/=x=a:p%r|z<-y:r=p?z

Cobalah online! Contoh penggunaan: f [[6,6],[6,5],[5,3],[3,0]]hasil True.

Tidak Disatukan:

f :: [[Int]] -> Bool
f (p:r) = check [p] (double p p) r

check :: [[Int]] -> [Int] -> [[Int]] -> Bool
check seen open [] = True
check seen open ([x,y]:r) = 
	  notElem [x,y] seen
   && notElem [y,x] seen
   && (elem x open && check ([x,y]:seen) (update [x,y] open) r 
   ||  elem y open && check ([y,x]:seen) (update [y,x] open) r)

double :: [Int] -> [Int] -> [Int]
double [x,y] rest = 
    if x==y 
    then [x,y] ++ rest 
    else rest

update :: [Int] -> [Int] -> [Int]
update [x,y] (a:rest) = 
    if x==a 
    then double [x,y] (y:rest) 
    else a : update [x,y] rest

Cobalah online!

Laikoni
sumber
0

R , 224 byte

function(L,x=c(),y=c()){o=T
z=length
if(z(L)){p=sort(L[1:2])
w=rep(p,2-(p[2]>p[1]))
x=rbind(p,x)
if(z(y)){m=match(p,y,0)
v=which.max(m)
if(m[v]>0){y=y[-m[v]]
w=w[-v]}}
y=c(y,w)
L=L[-1:-2]
o=o&f(L,x,y)&!sum(duplicated(x))}
o}

Cobalah online!

Kode menerima potongan sebagai daftar yang dipesan dan mengembalikan TRUE atau FALSE sesuai dengan spesifikasi. Fungsi memindai setiap bagian secara rekursif, menambahkan bagian ke indeks untuk memverifikasi tidak adanya duplikat, dan melacak titik penyisipan yang tersedia untuk memeriksa bahwa bagian tersebut dapat secara efektif ditambahkan ke tumpukan. Penanganan sambungan potongan (mis. Melampirkan 1-2 oleh 1 atau 2) dilakukan dengan cara serakah, sehingga tidak sepenuhnya mustahil bahwa beberapa konfigurasi aneh mungkin meledak.

NofP
sumber
sayangnya keserakahan tidak cukup baik. pertimbangkan 6-6 6-3 6-2 2-3Anda harus dapat menangani ini dengan 2-_atau 3-_berikutnya karena 2-3bisa ditempatkan di kedua ujungnya.
Sparr
Saya akan lihat.
NofP