Dobble / SpotIt-Kartengenerator

15

Einführung

Dobble / SpotIt ist ein Kartenspiel, bei dem Menschen in kürzester Zeit dasselbe Symbol auf einem Kartenpaar erkennen, darauf hinweisen und zum nächsten Paar wechseln müssen. Jede Karte hat mehrere Symbole (8 in der normalen Version), aber genau eines ist für jedes Kartenpaar gleich.

Beispiel aus physischer Kopie des Spiels: Karten mit Paarbeispielen

Herausforderung

Schreiben Sie ein Programm, das aus einer Reihe von Symbolen (einzelne ASCII-Zeichen) und einer Anzahl von Symbolen auf einer einzelnen Karte eine Liste von Ausgabekarten mit Symbolen für jede Karte erstellt. Es gibt offensichtlich viele äquivalente Kombinationen. Ihr Programm muss nur eine der Kombinationen schreiben, die die größte Menge an Karten für eine bestimmte Eingabe ergeben.

Es ist ein Code-Golf, also kürzer, besser.

Es wäre auch großartig, wenn die Berechnung für den kompliziertesten Fall vor dem Hitzetod des Universums abgeschlossen wäre.

Eingang

Zwei Argumente für function / stdin (Ihre Wahl)

  • Als erstes handelt es sich dabei um eine Sammlung von Symbolen, wie z. B. "ABCDE" oder ["A", "B", "C", "D", "E"] - das Format Ihrer Wahl, sei es eine Zeichenfolge, eine Menge, eine Liste oder ein Stream , oder was auch immer für die Sprache der Wahl idiomatisch ist. Die Zeichen werden aus dem Satz von [A-Za-z0-9] ohne Duplikate vergeben (daher beträgt die maximale Größe des Eingabesymbolsatzes 62). Sie werden nicht notwendigerweise in ( so können Sie "yX4i9A" auch für 6-Symbol-Fall erhalten).

  • Das zweite Argument ist eine Ganzzahl, die die Anzahl der Symbole auf einer einzelnen Karte angibt. Es wird <= als die Größe des Symbolsatzes sein.

Ausgabe

Drucken Sie mehrere durch Zeilenumbrüche getrennte Zeilen, von denen jede Symbole für eine einzelne Karte enthält.

Beispiele

ABC
2
>>>>
AB
BC
AC

Oder

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

Oder

ABCDE
4
>>>>
ABCD

Hinweise

  • Die Anzahl der produzierten Karten kann nicht größer als die Anzahl der unterschiedlichen Symbole sein und wird in vielen Kombinationen erheblich kleiner sein
  • Möglicherweise möchten Sie einige mathematische Hintergrundinformationen lesen, wenn Sie Hilfe bei der mathematischen Seite des Problems benötigen

Dies ist meine erste Code-Golf-Herausforderung. Bitte verzeihen Sie eventuelle Probleme mit der Formatierung / dem Stil. Ich werde versuchen, Fehler zu korrigieren, wenn Sie sie in Kommentaren angeben.

Artur Biesiadowski
quelle
Related
Peter Taylor
Vorgeschlagener Testfall ('abcdefghijklmnopqrstu', 5)-> ['abcde', 'afghi', 'ajklm', 'anopq', 'arstu', 'bfjnr', 'bgkpt', 'bhlou', 'bimqs', 'cfkqu', 'cgjos', 'chmpr', 'cilnt', 'dfmot', 'dglqr', 'dhkns', 'dijpu', 'eflps', 'egmnu', 'ehjqt', 'eikor']oder eine andere 21-Karten-Arbeitslösung. (Beachten Sie, dass dies die projektive endliche Ebene der Ordnung 4 ist).
Jonathan Allan

Antworten:

5

Python 2 , 192 162 Bytes

Ich habe ein Argument, dass dies den maximalen Kartensatz für jedes Szenario erzeugt und die 3 Testfälle behandelt.

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

Probieren Sie es online!

Algorithmus

Nehmen Sie für ein gegebenes Alphabet aund eine gegebene Kartengröße salle Elementkombinationen sauf aund nennen Sie es Cdann:

  • Nehmen Sie das erste Element von C, nennen Sie esC0
  • speichern C0
  • Entfernen Sie alle Elemente C, deren Vereinigung C0ungleich ist1
  • Wiederholen Sie mit dem zweiten Element von C
  • Fahren Sie fort, bis Cleer ist

Dann drucken Sie die gespeicherten Elemente.

Streit

Eine nicht leere Teilmenge von Cist unsere maximale Lösung K. Da es zumindest ein Element enthält , und zwei beliebige Elemente sind nicht zu unterscheiden, wählen , ein beliebiges Element, C0, der Cin sein K. Für jedes Element ein der Kist die Kardinalität der eVereinigung x1 für x != ein K; eliminieren so alle Elemente in Cderen Vereinigung mit C0nicht über cardinallity 1. Aus den gleichen Gründen, wählen Sie ein neues beliebiges Element in C, fügen Sie ihn K, und zu reduzieren C. Letztendlich Cist die leere Menge Kdie maximale Lösung, da wir zu keinem Zeitpunkt ein Element ausgewählt haben, das von anderen Elementen unterscheidbar war.


Testfälle

Diese Testfälle wurden geschrieben, bevor mir klar wurde, dass das Drucken eine Anforderung war.

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

Aktualisieren

  • +9 [16-12-07] Passen Sie die Druckanforderungen an
  • -11 [16-12-07] Hab meine RVariable ausgespielt
  • -30 [16-12-09] Ich habe meine KVariable ausgespielt , danke an @Leo !
NichtlinearFruit
quelle
1
Müssen Sie die Menge K wirklich bei jedem Schritt von C subtrahieren? Ich denke, die von Ihnen vorgenommene Filterung ( A for A in C if len(set(A)&set(C[0]))==1) entfernt bereits die ausgewählten Elemente, es sei denn, s == 1 (in diesem Fall len (set (C [0]) & set (C [0])) wäre 1). Sie könnten Ihre vorletzte Zeile auf Golf spielen, um:C=[A for A in C if len(set(A)&set(C[0]))==1<s]
Leo
Ich schrieb gerade eine Dobble-Herausforderung im Sandkasten und Dom Hastings wies mich auf diese Frage als möglichen Betrüger hin (was durchaus der Fall sein könnte). Mir ist jedoch aufgefallen, dass es viel schwieriger ist, ein vollständiges Dobble-Deck mit N * N zu erstellen + N + 1 Karten (und Symbole) mit N + 1 Symbolen pro Karte, wobei N keine Primzahl ist. Für N = 4 = 2 ^ 2 wäre dies ein Deck mit 4 * 4 + 4 + 1 = 21 Symbolen und der gleichen Anzahl von Karten; Diese Lösung erzeugt jedoch ein Deck von nur 13 Karten - 21 sind jedoch möglich .
Jonathan Allan
@JonathanAllan Gerade einen TIO-Link hinzugefügt. Ich habe die Funktion mit einem Alphabet von 21 Zeichen und mit 5 Zeichen pro Karte ausgeführt. Es werden 21 Karten ausgegeben. Ich denke, das ist richtig, wenn ich nicht falsch verstanden habe.
NonlinearFruit
Hmm, sorry, dann muss ich einen Fehler gemacht haben! ( Das ist ein Full Dobble Deck of Order 4. :) )
Jonathan Allan
2

Haskell, 175 bis 156 Bytes

Mein erster Versuch, Golf zu spielen, lass es mich wissen, wenn ich etwas durcheinander gebracht habe.

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)

Probieren Sie es online!

Vielen Dank an @Paul Mutser für die Verbesserung und -19 Bytes


Originalfassung

Bugs
quelle
1
Willkommen bei PPCG! Beachten Sie, dass die Importe für Ihre Punktzahl zählen. Mögliche Verbesserung: 156 Bytes, einschließlich des Imports
Paul Mutser
Vielen Dank für das Heads-up, ich war mir nicht sicher, ob sie es taten!
Bugs