Initial commit of jandew's Python capset

1 files changed, 70 insertions, 0 deletions

diff --git a/capset.py b/capset.py
new file mode 100755
index 0000000..65341b9
--- /dev/null
+++ b/capset.py
@@ -0,0 +1,70 @@
+#!/bin/env python3
+# A capset is a collection of cards that contains no sets.
+# The supposed maximal cardinality of a capset in Set is 20.
+# I wish to find such a collection with this program.
+
+from random import shuffle
+from itertools import combinations
+
+def is_set(cards):
+    if len(cards) != 3:
+        raise Exception("Not the right number of cards.")
+    for i in range(4):
+        if cards[0][i] == cards[1][i] == cards[2][i]: continue
+        if cards[0][i] != cards[1][i] != cards[2][i] != cards[0][i]: continue
+        return False
+    return True
+
+def int2card(num):
+    if num != int(num):
+        raise Exception("Number must be an integer.")
+    if num < 0:
+        raise Exception("Number must be nonnegative.")
+    if num > 80:
+        raise Exception("Number must be less than 81.")
+    strlist = []
+    for i in range(4):
+        strlist.append(str(num%3))
+        num //= 3
+    return ''.join(strlist[::-1])
+
+def increment_tableau(tableau, deck, pop=False):
+    index = deck.index(tableau[-1]) + 1
+    if index != len(deck):
+        if pop: tableau.pop()
+        tableau.append(deck[index])
+        return
+    tableau.pop()
+    index = deck.index(tableau.pop()) + 1
+    if len(tableau) == 1:
+        print("incrementing second card to index", index)
+        if index + 18 > len(deck): quit()
+    tableau.append(deck[index])
+
+def check_tableau(tableau):
+    if len(tableau) == 2: return True
+    for comb in combinations(tableau, 3):
+        if is_set(comb): return False
+    return True
+
+def main():
+    outfile = open("./capset.out", mode="w")
+    tableau = ["2222"]
+    deck = reversed(range(80)) # all cards other than 2222
+    deck = list(map(int2card, deck))
+    #shuffle(deck)
+    tableau.append(deck[0])
+    maxim = 20
+    while True:
+        if check_tableau(tableau):
+            if len(tableau) >= maxim:
+                print(tableau)
+                print(tableau, file=outfile, flush=True)
+                maxim = len(tableau)
+            increment_tableau(tableau, deck)
+        else:
+            increment_tableau(tableau, deck, pop=True)
+    outfile.close()
+
+if __name__ == "__main__": main()
+