Generator kartu Dobble / SpotIt

15

pengantar

Dobble / SpotIt adalah permainan kartu, di mana orang harus melihat simbol yang sama pada pasangan kartu dalam waktu singkat, menunjukkannya dan pindah ke pasangan berikutnya. Setiap kartu memiliki banyak simbol (8 dalam versi normal), tetapi persis satu yang umum di antara setiap pasangan kartu.

Contoh dari salinan fisik game: Kartu dengan contoh pasangan

Tantangan

Menulis sebuah program, yang diberi set simbol (karakter ascii tunggal) dan jumlah simbol pada kartu tunggal akan menghasilkan kartu daftar keluaran dengan simbol untuk setiap kartu. Jelas ada banyak kombinasi yang setara, program Anda hanya perlu menulis kombinasi yang menghasilkan jumlah kartu terbesar untuk input yang diberikan.

Ini adalah kode-golf, jadi kodenya lebih pendek, lebih baik.

Akan lebih bagus jika perhitungan akan selesai sebelum panasnya kematian alam semesta untuk kasus yang paling rumit.

Memasukkan

Dua argumen berfungsi / stdin (pilihan Anda)

  • Pertama-tama mereka adalah kumpulan simbol, seperti 'ABCDE "atau [' A ',' B ',' C ',' D ',' E '] - pilihan format Anda, baik itu string, set, list, stream , atau apa pun yang idiomatis untuk bahasa pilihan. Karakter akan diberikan dari set [A-Za-z0-9], tidak ada duplikat (jadi ukuran maksimum set simbol input adalah 62). Mereka tidak akan perlu dipesan dalam ( sehingga Anda bisa mendapatkan "yX4i9A" juga untuk kasus 6-simbol).

  • Argumen kedua adalah bilangan bulat, menunjukkan jumlah simbol pada kartu tunggal. Itu akan menjadi <= dari ukuran set simbol.

Keluaran

Cetak beberapa baris yang dipisahkan oleh baris baru, masing-masing mengandung simbol untuk kartu tunggal.

Contohnya

ABC
2
>>>>
AB
BC
AC

Atau

ABCDEFG
3
>>>>
ABC
BDE
CEF
BFG
AEG
CDG
ADF

Atau

ABCDE
4
>>>>
ABCD

Petunjuk

  • Jumlah kartu yang dihasilkan tidak boleh lebih besar dari jumlah simbol yang berbeda dan dalam banyak kombinasi akan jauh lebih kecil
  • Anda mungkin ingin membaca beberapa latar belakang matematika jika Anda memerlukan bantuan dengan sisi matematika masalah

Ini adalah tantangan golf kode pertama saya, jadi tolong maafkan masalah yang mungkin terjadi dengan pemformatan / gaya - Saya akan mencoba memperbaiki kesalahan jika Anda mengarahkannya dalam komentar.

Artur Biesiadowski
sumber
Terkait
Peter Taylor
Kasing uji yang disarankan ('abcdefghijklmnopqrstu', 5)-> ['abcde', 'afghi', 'ajklm', 'anopq', 'arstu', 'bfjnr', 'bgkpt', 'bhlou', 'bimqs', 'cfkqu', 'cgjos', 'chmpr', 'cilnt', 'dfmot', 'dglqr', 'dhkns', 'dijpu', 'eflps', 'egmnu', 'ehjqt', 'eikor']atau solusi kerja 21 kartu lainnya. (Perhatikan bahwa ini adalah bidang hingga proyektif pesanan 4).
Jonathan Allan

Jawaban:

5

Python 2 , 192 162 byte

Saya punya argumen bahwa ini menghasilkan set kartu maksimum untuk setiap skenario dan itu menangani 3 kasus uji.

from itertools import*
def m(a,s):
    C=["".join(x)for x in combinations(a,s)]
    while len(C):
        print C[0]
        C=list(set(A for A in C if len(set(A)&set(C[0]))==1<s))

Cobalah online!

Algoritma

Diberi alfabet a dan ukuran kartu s, masukkan semua kombinasi selemen adan sebut C, lalu:

  • Ambil elemen pertama C, sebut sajaC0
  • Menyimpan C0
  • Hapus semua elemen dari Cyang memiliki persatuan dengan C0tidak sama dengan1
  • Ulangi dengan elemen kedua C
  • Lanjutkan sampai C kosong

Kemudian cetak elemen yang disimpan.

Argumen

Beberapa subset kosong Cadalah solusi maksimal kami K,. Karena mengandung setidaknya satu elemen dan dua elemen apa pun tidak dapat dibedakan, pilih elemen yang arbitrer C0, Cuntuk dimasukkan K. Untuk setiap elemen edalam K, kardinalitas epersatuan xadalah 1 untuk x != edalam K; jadi hilangkan semua elemen Cyang persatuannya C0tidak memiliki kardinalitas 1. Dengan alasan yang sama, pilih elemen arbitrer baru C, tambahkan K, dan kurangi C. Akhirnya Cadalah himpunan kosong dan Kakan menjadi solusi maksimal karena pada titik mana pun kami memilih elemen yang dapat dibedakan dari elemen lainnya.


Uji Kasus

Kasing uji ini ditulis sebelum saya menyadari bahwa percetakan adalah persyaratan.

a=["a","b","c"]
b=2
c=3
d=m(a,b)
print d,len(d)==c
>> ['bc', 'ab', 'ac'] True

a=["a","b","c","d","e","f","g"]
b=3
c=7
d=m(a,b)
print d,len(d)==c
>> ['aef', 'abc', 'bde', 'ceg', 'adg', 'cdf', 'bfg'] True

a=["a","b","c","d","e"]
b=4
c=1
d=m(a,b)
print d,len(d)==c
>> ['abcd'] True

Memperbarui

  • +9 [16-12-07] Sesuai dengan persyaratan cetak
  • -11 [16-12-07] Keluar dari Rvariabel saya
  • -30 [16-12-09] Keluar dari Kvariabel saya , Terima kasih kepada @Leo !
Buah Nonlinier
sumber
1
Apakah Anda benar-benar perlu mengurangi set K dari C di setiap langkah? Saya pikir penyaringan yang Anda lakukan ( A for A in C if len(set(A)&set(C[0]))==1) sudah menghilangkan elemen yang dipilih, kecuali s == 1 (dalam hal ini len (set (C [0]) & set (C [0])) akan menjadi 1). Anda bisa bermain golf baris kedua ke terakhir ke:C=[A for A in C if len(set(A)&set(C[0]))==1<s]
Leo
Saya sedang menulis tantangan Dobble di kotak pasir dan Dom Hastings menunjuk saya ke pertanyaan ini sebagai kemungkinan penipuan (yang mungkin terjadi), namun satu hal yang saya perhatikan adalah bahwa jauh lebih sulit untuk membuat tumpukan Dobble penuh N * N + N + 1 kartu (dan simbol) dengan simbol N + 1 per kartu dengan N menjadi kekuatan utama non-prime. Untuk N = 4 = 2 ^ 2 ini akan menjadi dek menggunakan 4 * 4 + 4 + 1 = 21 simbol dan jumlah kartu yang sama; namun solusi ini menghasilkan setumpuk hanya 13 kartu - namun 21 adalah mungkin .
Jonathan Allan
@JonathanAllan Baru saja menambahkan tautan TIO. Saya menjalankan fungsi dengan alfabet 21 karakter dan dengan 5 karakter per kartu. Ini menghasilkan 21 kartu. Saya pikir ini benar kecuali saya salah paham.
NonlinearFruit
Hmm, maaf, saya pasti membuat kesalahan menjalankannya secara lokal kalau begitu! ( Itu Dek Penuh Dobble of Order 4. :) )
Jonathan Allan
2

Haskell, 175 156 bytes

Pertama saya bermain golf, beri tahu saya jika saya mengacaukan sesuatu.

import Data.List
f 0_=[[]]
f n a=g$c n a
c n a=[a!!i:x|i<-[0..(length a)-1],x<-f(n-1)(drop(i+1)a)]
g[]=[]
g(x:t)=x:g(filter(\z->length(z`intersect`x)<= 1)t)

Cobalah online!

Terima kasih kepada @Paul Mutser untuk peningkatan dan -19 byte


Versi asli

bug
sumber
1
Selamat datang di PPCG! Perhatikan bahwa impor dihitung berdasarkan skor Anda. Kemungkinan peningkatan: 156 byte, termasuk impor
Paul Mutser
Terima kasih atas perhatiannya, saya tidak yakin mereka melakukannya!
bug