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:

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.

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 !

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

Perl 6 , 88 77 bajtów

{+(combinations($^a,$^n),{my \d=.[0];say d.join;grep *∩d==1,.[1..*]}...!*)}

Wypróbuj online!