diff options
| -rw-r--r-- | capset.go | 131 | ||||
| -rwxr-xr-x | capset.py | 70 |
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() - |