Generator kart Dobble / SpotIt

15

Wprowadzenie

Dobble / Spot Jest to gra karciana, w której ludzie muszą w krótkim czasie wykryć ten sam symbol na karcie, wskazać ją i przejść do następnej pary. Każda karta ma wiele symboli (8 w normalnej wersji), ale dokładnie jeden jest wspólny dla każdej pary kart.

Przykład z fizycznej kopii gry: Karty z przykładami par

Wyzwanie

Napisz program, który podając zestaw symboli (pojedyncze znaki ascii) i liczbę symboli na pojedynczej karcie wytworzy wyjściowe karty z symbolami dla każdej karty. Istnieje oczywiście wiele równoważnych kombinacji, twój program musi tylko napisać dowolną kombinację, która daje największą liczbę kart dla danego wejścia.

To jest golf golfowy, więc lepiej skróć kod, lepiej.

Byłoby również świetnie, gdyby obliczenia zakończyły się przed śmiercią wszechświata przed upałem w najbardziej skomplikowanym przypadku.

Wejście

Dwa argumenty funkcji / stdin (twój wybór)

  • Pierwszym z nich jest zbiór symboli, coś w rodzaju „ABCDE” lub [„A”, „B”, „C”, „D”, „E”] - wybór formatu, ciąg znaków, zestaw, lista, strumień lub cokolwiek jest idiomatyczne dla wybranego języka. Znaki będą podane z zestawu [A-Za-z0-9], bez duplikatów (więc maksymalny rozmiar zestawu symboli wejściowych wynosi 62). Nie będą koniecznie uporządkowane w ( więc możesz dostać „yX4i9A” również dla przypadku z 6 symbolami).

  • Drugim argumentem jest liczba całkowita, wskazująca liczbę symboli na pojedynczej karcie. Będzie to <= rozmiar zestawu symboli.

Wynik

Wydrukuj wiele wierszy oddzielonych znakami nowej linii, z których każdy zawiera symbole pojedynczej karty.

Przykłady

ABC
2
>>>>
AB
BC
AC

Lub

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

Lub

ABCDE
4
>>>>
ABCD

Poradnik

  • Liczba wyprodukowanych kart nie może być większa niż liczba odrębnych symboli, aw wielu kombinacjach będzie znacznie mniejsza
  • Możesz przeczytać trochę matematyki, jeśli potrzebujesz pomocy z matematyczną stroną problemu

To jest moje pierwsze wyzwanie golfowe, więc proszę wybacz możliwe problemy z formatowaniem / stylem - postaram się poprawić błędy, jeśli podasz je w komentarzach.

Artur Biesiadowski
źródło
Powiązane
Peter Taylor
Sugerowany przypadek testowy ('abcdefghijklmnopqrstu', 5)-> ['abcde', 'afghi', 'ajklm', 'anopq', 'arstu', 'bfjnr', 'bgkpt', 'bhlou', 'bimqs', 'cfkqu', 'cgjos', 'chmpr', 'cilnt', 'dfmot', 'dglqr', 'dhkns', 'dijpu', 'eflps', 'egmnu', 'ehjqt', 'eikor']lub inne rozwiązanie robocze na 21 kart. (Zauważ, że jest to rzutowa skończona płaszczyzna rzędu 4).
Jonathan Allan

Odpowiedzi:

5

Python 2 , 192 162 bajty

Mam argument, że daje to maksymalny zestaw kart dla każdego scenariusza i obsługuje 3 przypadki testowe.

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))

Wypróbuj online!

Algorytm

Biorąc pod uwagę alfabet ai rozmiar karty s, weź wszystkie kombinacje selementów ai wywołaj go C, a następnie:

  • Weź pierwszy element C, nazwij toC0
  • Zapisać C0
  • Usuń wszystkie elementy, Cktóre mają połączenie o wartości C0nie równej1
  • Powtórz z drugim elementem C
  • Kontynuuj, aż Cbędzie pusty

Następnie wydrukuj zapisane elementy.

Argument

Niektóre niepusty podzbiór Cjest nasza maksymalna rozwiązanie K. Ponieważ zawiera co najmniej jeden element i jakieś dwa elementy są nie do odróżnienia, wybrać dowolny element C0, od Cbyć w K. Dla każdego elementu ew THE K, cardinality ejedności xoznacza 1 x != eW K; więc wyeliminuj wszystkie elementy, w Cktórych zjednoczeniu C0nie ma kardynalności 1. Z tego samego powodu wybierz nowy dowolny element w C, dodaj go Ki zmniejsz C. Ostatecznie Cjest to pusty zestaw i Kbędzie to maksymalne rozwiązanie, ponieważ w żadnym momencie nie wybraliśmy elementu, który można odróżnić od jakiegokolwiek innego elementu.


Przypadki testowe

Te przypadki testowe zostały napisane, zanim zdałem sobie sprawę, że drukowanie jest wymagane.

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

Aktualizacja

  • +9 [16-12-07] Dopasuj wymagania dotyczące drukowania
  • -11 [16-12-07] Grałem w golfa moją Rzmienną
  • -30 [16-12-09] Grał moją Kzmienną w golfa , dzięki @Leo !
Nieliniowe Owoce
źródło
1
Czy naprawdę musisz odejmować zestaw K od C na każdym kroku? Myślę, że filtrowanie, które robisz ( A for A in C if len(set(A)&set(C[0]))==1) już usuwa wybrane elementy, chyba że s == 1 (w tym przypadku len (set (C [0]) i set (C [0])) wynosiłby 1). Możesz zagrać w golfa od drugiej do ostatniej linii do:C=[A for A in C if len(set(A)&set(C[0]))==1<s]
Leo
Pisałam wyzwanie Dobble w piaskownicy i Dom Hastings wskazał mi na to pytanie jako ewentualnego dupe (która równie dobrze może być), jednak jedna rzecz, jaką zauważyłem jest to, że o wiele trudniej jest dokonać pełnej Dobble talię N * N + N + 1 kart (i symboli) z N + 1 symbolami na kartę, przy czym N jest nie-główną siłą pierwotną. Dla N = 4 = 2 ^ 2 byłaby to talia wykorzystująca 4 * 4 + 4 + 1 = 21 symboli i taką samą liczbę kart; jednak z tego rozwiązania powstaje talia składająca się tylko z 13 kart - jednak 21 jest możliwe .
Jonathan Allan
@JonathanAllan Właśnie dodał link TIO. Uruchomiłem tę funkcję z alfabetem 21 znaków i 5 znakami na kartę. Wytwarza 21 kart. Myślę, że jest to poprawne, chyba że źle zrozumiałem.
NonlinearFruit,
Hmm, przepraszam, chyba popełniłem błąd, uruchamiając go lokalnie! ( To jest pełny Dobble Deck 4. rzędu ) :)
Jonathan Allan
2

Haskell, 175 156 bajtów

Moja pierwsza gra w golfa, daj mi znać, jeśli coś pomieszałem.

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)

Wypróbuj online!

Dziękujemy @Paul Mutser za ulepszenia i -19 bajtów


Orginalna wersja

błędy
źródło
1
Witamy w PPCG! Pamiętaj, że import liczy się do twojego wyniku. Możliwa poprawa: 156 bajtów, w tym import
Paul Mutser
Dzięki za heads-upy, nie byłem pewien, czy tak!
błędy