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 (
	"bufio"
	"errors"
	"fmt"
	"log"
	"math"
	"os"
	"flag"
	"strconv"
)

var maximForDim = []int{1, 2, 4, 9, 20, 45, 112, 236}

type Card string

type Deck struct {
	// dim is the number of dimensions for the set.
	dim int
	// cards is the full deck of cards, sorted.
	cards []Card
	// card2index maps from a card back to its position in cards slice.
	card2index map[Card]int
}

func NewDeck(dimensions int) *Deck {
	size := int(math.Pow(3, float64(dimensions)))
	d := &Deck{
		dim:        dimensions,
		cards:      make([]Card, size),
		card2index: make(map[Card]int, size),
	}
	for i := range d.cards {
		card := d.computeInt2Card(size - i - 1)
		d.cards[i] = card
		d.card2index[card] = i
	}
	return d
}

func (d *Deck) computeInt2Card(num int) Card {
	if num < 0 {
		panic("Number must be positive")
	}
	strlist := make([]byte, d.dim)
	for i := 0; i < d.dim; i++ {
		// Always have three options for each dimension
		strlist[d.dim-i-1] = '0' + byte(num%3)
		num /= 3
	}
	return Card(strlist)
}

func (d *Deck) card2int(card Card) int {
	i, ok := d.card2index[card]
	if !ok {
		return -1
	}
	return i
}

type Capset struct {
	d       *Deck
	tableau []Card
	maxim   int
	hasSet  bool
}

// NewCapset makes an initialized Capset for the provided deck. If maxim is -1,
// then the maximum known capset size for the deck's dimension will be used, or
// 0 if it is unknown.
func NewCapset(d *Deck, maxim int) *Capset {
	if maxim == -1 {
		maxim = maximForDim[d.dim]
	}
	return &Capset{
		d:       d,
		tableau: make([]Card, 0, len(d.cards)),
		maxim:   maxim,
	}
}

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 := Card(token)
			index := cs.d.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 = cs.d.cards[index]
			cs.tableau = append(cs.tableau, card)
		}
	}
	cs.hasSet = hasSet(cs.tableau)
	// 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()
		cs.hasSet = hasSet(cs.tableau)
	}
	return nil
}

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

func (cs *Capset) incrementTableau() bool {
	pop := cs.hasSet
	var index int
	if len(cs.tableau) > 0 {
		index = cs.d.card2int(cs.tableau[len(cs.tableau)-1]) + 1
	} else {
		index = 0
	}
	if index != len(cs.d.cards) {
		if pop {
			cs.popTableau()
		}
		cs.tableau = append(cs.tableau, cs.d.cards[index])
		return true
	}
	cs.popTableau()
	if len(cs.tableau) == 0 {
		// No combinations left
		return false
	}
	index = cs.d.card2int(cs.popTableau()) + 1
	if len(cs.tableau) == 1 {
		fmt.Println("incrementing second card to index", index)
		if index+cs.maxim-2 > len(cs.d.cards) {
			return false
		}
	}
	cs.tableau = append(cs.tableau, cs.d.cards[index])
	return true
}

// hasSet returns whether the provide tableau contains at least one set.
func hasSet(tableau []Card) bool {
	if len(tableau) <= 2 {
		return false
	}
	dim := len(tableau[0])
	same := make([]bool, dim)
	for i := 0; i < len(tableau); i++ {
		for j := i + 1; j < len(tableau); j++ {
			for x := 0; x < dim; x++ {
				same[x] = tableau[i][x] == tableau[j][x]
			}
		kloop:
			for k := j + 1; k < len(tableau); k++ {
				for x := 0; x < dim; x++ {
					if same[x] {
						if tableau[i][x] != tableau[k][x] {
							continue kloop
						}
					} else {
						if tableau[i][x] == tableau[k][x] ||
							tableau[j][x] == tableau[k][x] {
							continue kloop
						}
					}
				}
				return true
			}
		}
	}
	return false
}

// hasSetWithLast returns whether the provided tableau contains at least one set
// with the last element of tableau as a member.
func hasSetWithLast(tableau []Card) bool {
	if len(tableau) <= 2 {
		return false
	}
	// We try sets such that only the rightmost item could possibly be in a set.
	i := len(tableau) - 1
	dim := len(tableau[0])
	// Using make instead of "var same [4]bool" causes a ~6% slowdown
	same := make([]bool, dim)
	for j := 0; j < i; j++ {
		for x := 0; x < dim; x++ {
			same[x] = tableau[i][x] == tableau[j][x]
		}
	kloop:
		for k := j + 1; k < i; k++ {
			for x := 0; x < dim; x++ {
				if same[x] {
					if tableau[i][x] != tableau[k][x] {
						continue kloop
					}
				} else {
					if tableau[i][x] == tableau[k][x] ||
						tableau[j][x] == tableau[k][x] {
						continue kloop
					}
				}
			}
			return true
		}
	}
	return false
}

// FindNextCapset iterates over combinations of the tableau until it finds a
// capset that is at least the maxim in size. It returns false if it was unable
// to find such a capset.
func (cs *Capset) FindNextCapset() bool {
	for cs.incrementTableau() {
		cs.hasSet = hasSetWithLast(cs.tableau)
		if cs.hasSet {
			continue
		}
		if len(cs.tableau) < cs.maxim {
			continue
		}
		cs.maxim = len(cs.tableau)
		return true
	}
	return false
}

// GetTableau returns the current tableau. Callers must not modify the slice.
func (cs *Capset) GetTableau() []Card {
	return cs.tableau
}

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

func main() {
	flag.Parse()
	args := flag.Args()
	if len(args) != 1 {
		fmt.Println("Usage: capset dim\n\tdim int := number of dimensions/attributes")
		log.Fatal("Improper Usage")
	}
	dim, err := strconv.Atoi(args[0])
	if err != nil {
		log.Fatal(err)
	}
	d := NewDeck(dim)
	cs := loadFromSave(d)
	if cs == nil {
		cs = NewCapset(d, -1)
	}
	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.GetTableau())
		_, err = fmt.Fprintln(outfile, cs.GetTableau())
		if err != nil {
			log.Println(err)
		}
		err = outfile.Sync()
		if err != nil {
			log.Println(err)
		}
	}
}