From 022843b76031d925fc5f93ab088512bfad5ad65b Mon Sep 17 00:00:00 2001
From: Joe Anderson <jandew+dev@gmail.com>
Date: Mon, 30 Jun 2014 23:04:01 -0700
Subject: Initial commit of jandew's Python capset

---
 capset.py | 70 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 70 insertions(+)
 create mode 100755 capset.py

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()
+
-- 
cgit v1.2.3-70-g09d2