Faithful port to Go

It is around 60 times faster

1 files changed, 131 insertions, 0 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)
+		}
+	}
+}