Differences

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

--- lehrkraefte:blc:informatik:ffprg2-2020:dobble [2020/11/24 08:27]
Ivo Blöchliger
+++ lehrkraefte:blc:informatik:ffprg2-2020:dobble [2020/12/11 15:43] (current)
Ivo Blöchliger
@@ Line 6: / Line 6: @@
 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.
-Lösungsvorschläge per e-mail an ivo.bloechliger@ksbg.ch.
+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>