path: root/capset.go

// 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"
import "bufio"
import "errors"

var deck [81]string
var card2IntMap map[string]int
var useMap = true

func init() {
	for i := range deck {
		deck[i] = computeInt2Card(80 - i)
	}
	card2IntMap = make(map[string]int)
	for i, v := range deck {
		card2IntMap[v] = i
	}
}

func computeInt2Card(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 card2int(item string) int {
	if useMap {
		i, ok := card2IntMap[item]
		if !ok {
			return -1
		}
		return i
	} else {
		for i, v := range deck {
			if v == item {
				return i
			}
		}
		return -1
	}
}

type capset struct {
	tableau []string
	maxim   int
	hasSet  bool
}

func (cs *capset) Scan(state fmt.ScanState, verb rune) error {
	if verb != 'v' {
		return errors.New("unexpected verb")
	}
	r, _, err := state.ReadRune()
	if err != nil {
		return err
	}
	if r != '[' {
		return errors.New("didn't start with [")
	}
	cs.tableau = cs.tableau[:0]
	for end := false; !end; {
		token, err := state.Token(true, nil)
		if err != nil {
			return err
		}
		if len(token) == 0 {
			return errors.New("Premature end")
		}
		if token[len(token)-1] == ']' {
			end = true
			token = token[:len(token)-1]
		}
		if len(token) > 0 {
			card := string(token)
			index := card2int(card)
			if index == -1 {
				return errors.New(fmt.Sprintf("Invalid card: %v", card))
			}
			// Always use same strings in hope underlying strcmp short circuits
			card = deck[index]
			cs.tableau = append(cs.tableau, card)
		}
	}
	cs.updateTableauHasSetCached()
	// Loop until it isn't a set, to make sure we didn't load a tableau with lots
	// of sets.
	for cs.hasSet {
		cs.incrementTableau(true)
	}
	return nil
}

func (cs *capset) popTableau() string {
	v := cs.tableau[len(cs.tableau)-1]
	cs.tableau = cs.tableau[:len(cs.tableau)-1]
	return v
}

func (cs *capset) incrementTableau(noAssume bool) bool {
	pop := cs.hasSet
	index := card2int(cs.tableau[len(cs.tableau)-1]) + 1
	if index != len(deck) {
		if pop {
			cs.popTableau()
		}
		cs.tableau = append(cs.tableau, deck[index])
		cs.updateTableauHasSet(noAssume)
		return true
	}
	cs.popTableau()
	index = card2int(cs.popTableau()) + 1
	if len(cs.tableau) == 1 {
		fmt.Println("incrementing second card to index", index)
		if index+18 > len(deck) {
			return false
		}
	}
	cs.tableau = append(cs.tableau, deck[index])
	cs.updateTableauHasSet(noAssume)
	return true
}

func isSet(cards [3]string) bool {
	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 (cs *capset) updateTableauHasSet(noAssume bool) {
	if noAssume {
		cs.updateTableauHasSetCached()
	} else {
		cs.updateTableauHasSetOnlyNew()
	}
}

// TODO(ejona): remove
func (cs *capset) updateTableauHasSetSimple() {
	if len(cs.tableau) <= 2 {
		cs.hasSet = false
		return
	}
	var comb [3]string
	for i := 0; i < len(cs.tableau); i++ {
		comb[0] = cs.tableau[i]
		for j := i + 1; j < len(cs.tableau); j++ {
			comb[1] = cs.tableau[j]
			for k := j + 1; k < len(cs.tableau); k++ {
				comb[2] = cs.tableau[k]
				if isSet(comb) {
					cs.hasSet = true
					return
				}
			}
		}
	}
	cs.hasSet = false
}

func (cs *capset) updateTableauHasSetCached() {
	var same [4]bool
	for i := 0; i < len(cs.tableau); i++ {
		for j := i + 1; j < len(cs.tableau); j++ {
			for x := 0; x < 4; x++ {
				same[x] = cs.tableau[i][x] == cs.tableau[j][x]
			}
		kloop:
			for k := j + 1; k < len(cs.tableau); k++ {
				for x := 0; x < 4; x++ {
					if same[x] {
						if cs.tableau[i][x] != cs.tableau[k][x] {
							continue kloop
						}
					} else {
						if cs.tableau[i][x] == cs.tableau[k][x] ||
							cs.tableau[j][x] == cs.tableau[k][x] {
							continue kloop
						}
					}
				}
				cs.hasSet = true
				return
			}
		}
	}
	cs.hasSet = false
}

func (cs *capset) updateTableauHasSetOnlyNew() {
	if len(cs.tableau) <= 2 {
		cs.hasSet = false
		return
	}
	// We try sets such that only the rightmost item could possibly be in a set.
	i := len(cs.tableau) - 1
	var same [4]bool
	for j := 0; j < i; j++ {
		for x := 0; x < 4; x++ {
			same[x] = cs.tableau[i][x] == cs.tableau[j][x]
		}
	kloop:
		for k := j + 1; k < i; k++ {
			for x := 0; x < 4; x++ {
				if same[x] {
					if cs.tableau[i][x] != cs.tableau[k][x] {
						continue kloop
					}
				} else {
					if cs.tableau[i][x] == cs.tableau[k][x] ||
						cs.tableau[j][x] == cs.tableau[k][x] {
						continue kloop
					}
				}
			}
			cs.hasSet = true
			return
		}
	}
	cs.hasSet = false
}

func (cs *capset) findNextCapset() bool {
	for cs.incrementTableau(false) {
		if cs.hasSet {
			continue
		}
		if len(cs.tableau) < cs.maxim {
			continue
		}
		cs.maxim = len(cs.tableau)
		return true
	}
	return false
}

func loadFromSave() *capset {
	savefile, err := os.Open("./capset.out")
	if err != nil {
		return nil
	}
	defer savefile.Close()
	scanner := bufio.NewScanner(savefile)
	for scanner.Scan() {
	}
	var cs capset
	_, err = fmt.Sscanln(scanner.Text(), &cs)
	if err != nil {
		return nil
	}
	return &cs
}

func main() {
	cs := loadFromSave()
	if cs == nil {
		cs = &capset{tableau: []string{"2222"}}
	}
	cs.maxim = 20
	fmt.Println("Starting processing with", cs.tableau)

	outfile, err := os.OpenFile("./capset.out",
		os.O_WRONLY|os.O_CREATE|os.O_APPEND, 0644)
	if err != nil {
		log.Fatal(err)
	}
	defer outfile.Close()

	for cs.findNextCapset() {
		fmt.Println(cs.tableau)
		_, err = fmt.Fprintln(outfile, cs.tableau)
		if err != nil {
			log.Println(err)
		}
		err = outfile.Sync()
		if err != nil {
			log.Println(err)
		}
	}
}