Differences

This shows you the differences between two versions of the page.

--- lehrkraefte:blc:informatik:ffprg2-2020:dobble [2020/11/24 07:26] – created Ivo Blöchliger
+++ lehrkraefte:blc:informatik:ffprg2-2020:dobble [2020/12/11 14:43] (current) – Ivo Blöchliger
@@ Line 1: / Line 1: @@
+====== Generierung eines Dobble-Kartensets ======
+Dobble ist ein Kartenspiel, wo auf jeder Karte genau $n=8$ unterschiedliche Symbole abgebildet sind. Die Symbole auf der Karte sind so gewählt, dass bei jedem beliebigen Paar von Karten es immer genau ein Symbol gibt, in dem die Karten übereinstimmen. Im Spiel geht es darum, das gemeinsame Symbol vor den Mitspielern zu finden.
+Schreiben Sie ein Programm, das ein Dobble-Kartenset erzeugt. Anstatt $m$ verschiedene Symbole werden einfach Zahlen $0, \ldots, m-1$ verwendet, eine Karte wird als Array mit 8 Einträgen betrachtet. Z.B. ''[0,1,2,3,4,5,6,7]''.
+Das Programm sollte das grösst-mögliche Kartenset erzeugen und wenn möglich auch für andere $n$ (Anzahl Symbole auf einer Karte) funktionieren.
+Dokumentieren Sie bitte Ihre Überlegungen und Codes.
+Es ist möglich, direkt mit Mengen zu arbeiten in Python:
+<code python>
+a = {1,2,3}
+b = {2,3,4}
+c = a.union(b) # Vereinigung
+d = a.intersection(b)  # Schnittmenge
+s = len(d)  # Anzahl Elemente
+a.add(42)  # Anfügen eines Elements, modifiziert die Menge a
+b = b.copy()  # Kopie der Menge b
+</code>
+Siehe auch https://www.w3schools.com/python/python_sets_methods.asp
+<hidden Hilfestellungen>
+  * Erzeugen Sie Kartensets mit $n=2$ und $n=3$ Symbolen von Hand.
+Überlegen Sie sich folgendes:
+  * Gegeben ist ein (evtl. unvollständiges) Kartenset, das die Bedingung erfüllt, dass jedes Paar von Karte genau ein gemeinsames Symbol.
+  * Weiter ist eine (i.d.R. unvollständige) Karte gegeben, die mit jeder Karte aus dem Kartenset 0 oder 1 gemeinsames Symbol hat.
+  * Überlegen Sie sich, wie die Karte um ein ergänzt werden könnte.
+Programmieren Sie eine rekursive Funktion, die im Setting von oben eine Karte vervollständigt, oder meldet, dass die Karte nicht vervollständigt werden kann.
+Diese Methode liefert zwar valide Kartensets, die zwar nicht vergrössert werden können, die aber auch nicht optimal sind, im Sinne dass es grössere Sets gibt.
+**Ask the Interweb**
+Man findet auf dem Internet auch einiges zu diesem Problem. Es gibt dazu auch noch offene mathematische Fragen (ab $n=12$ Symbolen). Eine wirklich schöne Seite ist diese hier: https://puzzlewocky.com/games/the-math-of-spot-it/
+Hier ist sehr anschaulich eine Methode beschrieben (mit dem 7x7-Quadrat von Symbolen), mit der sich komplette Sets erzeugen lassen, wenn $n-1$ prim ist.
+</hidden>
+====== Kartenset kompletieren ======
+<code python>
+from functools import reduce
+# Voraussetzungen:
+# karten ist ein Array mit mindestens einer Karte
+# Bei mehreren Karten bildet das Array ein valides Kartendeck, d.h.
+# jedes Kartenpaar hat genau 1 gemeinsames Element.
+#
+# Die Symbole sind ganze Zahlen, startend bei 0
+#
+# karte ist eine evtl. unvollständige Karte, die mit jedem Element aus
+# karten höchstens 1 gemeinsames Element hat.
+#
+# Die Funktion liefert entweder None, wenn die Karte unmöglich
+# vervollständigt werden kann, oder die lexikografisch erste
+# vervollständigte Karte.
+def complete(karten, karte):
+    n = len(karten[0]) # Anzahl Symbole
+    if len(karte)==n:  # Test ob vollständige Karte auch gültig
+        if all(len(k & karte)==1 for k in karten):
+            return karte
+        else:
+            return None
+    # Symbole, die nicht zusätzlich auf die Karte dürfen
+    forbidden = karte.copy()
+    for k in karten:
+        if (len(k & karte)==1):
+            forbidden|=k
+    # Symbole, von denen mindestens eins auf die Karte muss
+    possibles = set()
+    hasZero = False
+    for k in karten:
+        if (len(k & karte)==0):
+            hasZero = True
+            # Karte ohne gemeinsame Symbole, aber alle verboten, also unmöglich
+            if len(k.difference(forbidden))==0:
+                return None
+            possibles |= k.difference(forbidden)
+    possibles = list(possibles)
+    if hasZero:
+        possibles.sort()
+        for p in possibles:
+            r = complete(karten, karte | {p})
+            if r!=None:
+                return r
+        # Es gibt karten ohne gemeinsames Element und es unmöglich eines davon hinzuzufügen
+        return None
+    # Alle Karten haben jetzt genau ein gemeinsames Element, also entsprechend neue Symbole hinzufügen
+    symbol = max(reduce(lambda a,b: a|b, karten, set()))+1
+    print("Nächstes Symbol ist %d" % symbol)
+    return karte|set([s for s in range(symbol, symbol+n-len(karte))])
+n = 8
+total = n*n-n+1
+karte = set([i for i in range(n)])
+print(karte)
+karten = [karte]
+for i in range(n-1):
+    karten.append(complete(karten,{0}))
+print(karten)
+for j in range(1,n):
+    while True:
+        print("Try %d" % j)
+        r = complete(karten,{j})
+        if r!=None:
+            karten.append(r)
+            print(r)
+        else:
+            break
+print(karten)
+print(len(karten))
+"""
+for i in range(2):
+    for s in range(total):
+        print("Starting with Symbol %d" % s)
+        r = complete(karten,{s})
+        if r!=None:
+            karten.append(r)
+            print(r)
+            print(len(karten))
+"""
+</code>