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

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

type Card struct {
	// dim is the number of dimensions the card has. Necessary for String().
	dim uint8
	// attrs contains bit-wise representation of attributes. Each attribute
	// consumes 2 bits with values 0, 1, or 2. Attributes are aligned to the right
	// and the most significant bits correspond to the attribute that appears
	// first in the string representation.
	attrs uint16
}

func (c Card) String() string {
	attrs := c.attrs
	repr := make([]byte, c.dim)
	for pos := int(c.dim) - 1; pos >= 0; pos-- {
		repr[pos] = byte('0' + (attrs & 0x3))
		attrs >>= 2
	}
	return string(repr)
}

func (c *Card) Scan(state fmt.ScanState, verb rune) error {
	if verb != 'v' {
		return errors.New(fmt.Sprint("Card.Scan: unexpected verb: ", verb))
	}
	*c = Card{}
	for {
		r, _, err := state.ReadRune()
		if err == io.EOF {
			if c.dim > 0 {
				return nil
			} else {
				return errors.New("Card.Scan: got EOF before any attributes")
			}
		}
		if err != nil {
			return errors.New(fmt.Sprint("Card.Scan: ", err))
		}
		if r < '0' || r > '3' {
			state.UnreadRune()
			if c.dim > 0 {
				return nil
			} else {
				return errors.New(fmt.Sprint("Card.Scan: Not a card character: ", r))
			}
		}
		c.dim++
		c.attrs = (c.attrs << 2) | uint16(r-'0')
	}
}

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
	// 0x1 for each attribute
	isSetBitMask uint16
	// str2card maps from a string representation to a particular card.
	str2card map[string]Card
}

func NewDeck(dimensions int) *Deck {
	if dimensions > 8 {
		panic("Can't handle dims > 8")
	}
	size := int(math.Pow(3, float64(dimensions)))
	d := &Deck{
		dim:        dimensions,
		cards:      make([]Card, size),
		card2index: make(map[Card]int, size),
		str2card:   make(map[string]Card, size),
	}
	for i := range d.cards {
		card := d.computeInt2Card(i)
		d.cards[i] = card
		d.card2index[card] = i
		d.str2card[card.String()] = card
	}
	for i := 0; i < d.dim; i++ {
		d.isSetBitMask <<= 2
		d.isSetBitMask |= 0x1
	}
	return d
}

func (d *Deck) computeInt2Card(num int) Card {
	if num < 0 {
		panic("Number must be positive")
	}
	c := Card{dim: uint8(d.dim)}
	for i := 0; i < d.dim; i++ {
		// Always have three options for each dimension
		c.attrs |= uint16((num % 3) << (2 * uint(i)))
		num /= 3
	}
	return c
}

func (d *Deck) card2int(card Card) int {
	i, ok := d.card2index[card]
	if !ok {
		panic(fmt.Sprint("Could not find card ", card, " in ", d))
	}
	return i
}

// hasSet returns whether the provided tableau contains at least one set.
func (d *Deck) hasSet(tableau []Card) bool {
	for i := len(tableau); i > 2; i-- {
		if d.hasSetWithLast(tableau[:i]) {
			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 (d *Deck) hasSetWithLast(tableau []Card) bool {
	if len(tableau) <= 2 {
		return false
	}
	i := len(tableau) - 1
	for j := 0; j < i; j++ {
		// Both same and diff are trying to get 11 for each attribute to indicate a
		// match.
		same := ^(tableau[i].attrs ^ tableau[j].attrs)
		diff := tableau[i].attrs ^ tableau[j].attrs
		for k := j + 1; k < i; k++ {
			// same and diff become fully computed. 11 indicates match.
			sameFinal := same & ^(tableau[i].attrs ^ tableau[k].attrs)
			diffFinal := diff ^ tableau[k].attrs
			// Shift and AND so that we have a single bit to indicate success. This is
			// necessary for the OR to function appropriately.
			sameSingle := sameFinal & (sameFinal >> 1)
			diffSingle := diffFinal & (diffFinal >> 1)
			if (sameSingle|diffSingle)&d.isSetBitMask == d.isSetBitMask {
				return true
			}
		}
	}
	return false
}

func (d *Deck) FindCards(strArr []string) ([]Card, error) {
	cards := make([]Card, 0, len(strArr))
	for _, v := range strArr {
		c, ok := d.FindCard(v)
		if !ok {
			return nil, errors.New(fmt.Sprint("Could not find card: ", v))
		}
		cards = append(cards, c)
	}
	return cards, nil
}

func (d *Deck) FindCard(cardStr string) (card Card, ok bool) {
	card, ok = d.str2card[cardStr]
	return card, ok
}

type Capset struct {
	// d is the search space to find capsets.
	d *Deck
	// tableau is the current attempt to find a capset.
	tableau []Card
	// maxim is the minimum size for found capsets.
	maxim int
	// hasSet is true if the current tableau contains at least one set.
	hasSet bool
	// fixedMaxim is false when maxim should be increased as larger capsets are
	// found.
	fixedMaxim 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) String() string {
	return fmt.Sprintf("{%v %v %v}", cs.tableau, cs.maxim, cs.hasSet)
}

func (cs *Capset) Scan(state fmt.ScanState, verb rune) error {
	if verb != 'v' {
		return errors.New("Capset.Scan: unexpected verb")
	}
	r, _, err := state.ReadRune()
	if err != nil {
		return err
	}
	if r != '[' {
		return errors.New("Capset.Scan: didn't start with [")
	}
	cs.tableau = cs.tableau[:0]
	for end := false; !end; {
		state.SkipSpace()
		r, _, err = state.ReadRune()
		if r == ']' {
			break
		}
		state.UnreadRune()

		var c Card
		err = c.Scan(state, 'v')
		if err != nil {
			return errors.New(fmt.Sprint(
				"Capset.Scan: for rune ", len(cs.tableau)+1, " got error ", err))
		}
		if c.dim != uint8(cs.d.dim) {
			return errors.New(fmt.Sprint(
				"Capset.Scan: card is dim ", c.dim, " but deck is ", cs.d.dim))
		}
		cs.tableau = append(cs.tableau, c)
	}
	cs.hasSet = cs.d.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 = cs.d.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
}

// 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 = cs.d.hasSetWithLast(cs.tableau)
		if cs.hasSet {
			continue
		}
		if len(cs.tableau) < cs.maxim {
			continue
		}
		if !cs.fixedMaxim {
			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, saveFile string, initialMaxim int) (*Capset, error) {
	savefile, err := os.Open(saveFile)
	if err != nil {
		return nil, err
	}
	defer savefile.Close()
	scanner := bufio.NewScanner(savefile)
	for scanner.Scan() {
	}
	if err := scanner.Err(); err != nil {
		return nil, err
	}
	cs := NewCapset(d, initialMaxim)
	if _, err := fmt.Sscanln(scanner.Text(), cs); err != nil {
		return nil, err
	}
	fmt.Print("Loaded save file\n")
	return cs, nil
}

func main() {
	flag.Usage = func() {
		fmt.Fprintf(os.Stderr, "Usage: %s [OPTIONS] DIMENSIONS\n", os.Args[0])
		fmt.Fprintf(os.Stderr, "Calculate cards that do not contain a set.\n\n")
		flag.PrintDefaults()
	}
	initialMaxim := flag.Int("maxim", -1, "initial maxim to use; -1 for auto")
	fixedMaxim := flag.Bool("fixed-maxim", false,
		"maxim does not change when larger capset is found")
	saveFile := flag.String("save-file", "", "file to save progress to")

	flag.Parse()
	args := flag.Args()
	if len(args) != 1 {
		flag.Usage()
		os.Exit(1)
	}
	dim, err := strconv.Atoi(args[0])
	if err != nil {
		log.Fatal(err)
	}
	d := NewDeck(dim)
	var cs *Capset
	var outfile *os.File
	if *saveFile != "" {
		var err error
		cs, err = loadFromSave(d, *saveFile, *initialMaxim)
		if err != nil && !os.IsNotExist(err) {
			log.Fatal(err)
		}

		outfile, err = os.OpenFile(*saveFile,
			os.O_WRONLY|os.O_CREATE|os.O_APPEND, 0644)
		if err != nil {
			log.Fatal(err)
		}
		defer outfile.Close()
	}
	if cs == nil {
		cs = NewCapset(d, *initialMaxim)
	}
	cs.fixedMaxim = *fixedMaxim
	fmt.Println("Starting processing with", cs.tableau)

	for cs.FindNextCapset() {
		fmt.Println(cs.GetTableau())
		if outfile != nil {
			_, err = fmt.Fprintln(outfile, cs.GetTableau())
			if err != nil {
				log.Println(err)
			}
		}
	}
}