Faithful port to Go

It is around 60 times faster

2 files changed, 131 insertions, 70 deletions

diff --git a/capset.go b/capset.go
new file mode 100644
index 0000000..9a74038
--- /dev/null
+++ b/capset.go
@@ -0,0 +1,131 @@
+// 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.
+
+package main
+
+import "log"
+import "os"
+import "fmt"
+
+func is_set(cards []string) bool {
+	if len(cards) != 3 {
+		log.Fatal("Not the right number of cards.")
+	}
+	for i := 0; i < 4; i++ {
+		if cards[0][i] == cards[1][i] && cards[0][i] == cards[2][i] {
+			continue
+		}
+		if cards[0][i] != cards[1][i] &&
+			cards[0][i] != cards[2][i] &&
+			cards[1][i] != cards[2][i] {
+			continue
+		}
+		return false
+	}
+	return true
+}
+
+func int2card(num int) string {
+	if num < 0 {
+		log.Fatal("Number must be nonnegative.")
+	}
+	if num > 81 {
+		log.Fatal("Number must be less than 81.")
+	}
+	var strlist [4]byte
+	for i := 0; i < 4; i++ {
+		strlist[3-i] = '0' + byte(num%3)
+		num /= 3
+	}
+	return string(strlist[:])
+}
+
+func find_index(deck []string, item string) int {
+	for i, v := range deck {
+		if v == item {
+			return i
+		}
+	}
+	panic("Somehow couldn't find index")
+}
+
+func list_pop(arr *[]string) string {
+	v := (*arr)[len(*arr)-1]
+	*arr = (*arr)[:len(*arr)-1]
+	return v
+}
+
+func increment_tableau(tableau []string, deck []string, pop bool) []string {
+	index := find_index(deck, tableau[len(tableau)-1]) + 1
+	if index != len(deck) {
+		if pop {
+			list_pop(&tableau)
+		}
+		tableau = append(tableau, deck[index])
+		return tableau
+	}
+	list_pop(&tableau)
+	index = find_index(deck, list_pop(&tableau)) + 1
+	if len(tableau) == 1 {
+		fmt.Println("incrementing second card to index", index)
+		if index+18 > len(deck) {
+			os.Exit(0)
+		}
+	}
+	tableau = append(tableau, deck[index])
+	return tableau
+}
+
+func check_tableau(tableau []string) bool {
+	if len(tableau) == 2 {
+		return true
+	}
+	var comb [3]string
+	for i := 0; i < len(tableau); i++ {
+		comb[0] = tableau[i]
+		for j := i + 1; j < len(tableau); j++ {
+			comb[1] = tableau[j]
+			for k := j + 1; k < len(tableau); k++ {
+				comb[2] = tableau[k]
+				if is_set(comb[:]) {
+					return false
+				}
+			}
+		}
+	}
+	return true
+}
+
+func main() {
+	outfile, err := os.OpenFile("./capset.out", os.O_WRONLY|os.O_CREATE|os.O_TRUNC, 0644)
+	if err != nil {
+		log.Fatal(err)
+	}
+	defer outfile.Close()
+	deck := [81]string{}
+	for i := range deck {
+		deck[i] = int2card(80-i)
+	}
+	tableau := []string{deck[0], deck[1]}
+	maxim := 20
+	for {
+		if check_tableau(tableau) {
+			if len(tableau) >= maxim {
+				fmt.Println(tableau)
+				_, err = fmt.Fprintln(outfile, tableau)
+				if err != nil {
+					log.Println(err)
+				}
+				err = outfile.Sync()
+				if err != nil {
+					log.Println(err)
+				}
+				maxim = len(tableau)
+			}
+			tableau = increment_tableau(tableau, deck[:], false)
+		} else {
+			tableau = increment_tableau(tableau, deck[:], true)
+		}
+	}
+}
diff --git a/capset.py b/capset.py
deleted file mode 100755
index 65341b9..0000000
--- a/capset.py
+++ /dev/null
@@ -1,70 +0,0 @@
-#!/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()
-