diff options
Diffstat (limited to 'capset.go')
| -rw-r--r-- | capset.go | 247 |
1 files changed, 151 insertions, 96 deletions
@@ -9,6 +9,7 @@ import ( "errors" "flag" "fmt" + "io" "log" "math" "os" @@ -17,7 +18,55 @@ import ( var maximForDim = []int{1, 2, 4, 9, 20, 45, 112, 236} -type Card string +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. @@ -26,19 +75,32 @@ type Deck struct { 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 } @@ -47,23 +109,83 @@ func (d *Deck) computeInt2Card(num int) Card { if num < 0 { panic("Number must be positive") } - strlist := make([]byte, d.dim) + c := Card{dim: uint8(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) + c.attrs |= uint16((num % 3) << (2 * uint(i))) num /= 3 } - return Card(strlist) + return c } func (d *Deck) card2int(card Card) int { i, ok := d.card2index[card] if !ok { - return -1 + 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++ { + same := ^(tableau[i].attrs ^ tableau[j].attrs) + diff := tableau[i].attrs ^ tableau[j].attrs + for k := j + 1; k < i; k++ { + sameFinal := same & ^(tableau[i].attrs ^ tableau[k].attrs) + diffFinal := diff ^ tableau[k].attrs + 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 +} + +// TODO: test to make sure leading and trailing spaces cause error +func (d *Deck) FindCard(cardStr string) (card Card, ok bool) { + card, ok = d.str2card[cardStr] + return card, ok + /*var c Card + _, err := fmt.Sscan(cardStr, &c) + if err != nil { + return Card{}, false + } + if d.dim != int(c.dim) { + return Card{}, false + } + return c, true*/ +} + type Capset struct { d *Deck tableau []Card @@ -85,47 +207,48 @@ func NewCapset(d *Deck, maxim int) *Capset { } } +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("unexpected verb") + return errors.New("Capset.Scan: unexpected verb") } r, _, err := state.ReadRune() if err != nil { return err } if r != '[' { - return errors.New("didn't start with [") + return errors.New("Capset.Scan: 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") + state.SkipSpace() + r, _, err = state.ReadRune() + if r == ']' { + break } - if token[len(token)-1] == ']' { - end = true - token = token[:len(token)-1] + 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 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) + 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 = hasSet(cs.tableau) + 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 = hasSet(cs.tableau) + cs.hasSet = cs.d.hasSet(cs.tableau) } return nil } @@ -167,80 +290,12 @@ func (cs *Capset) incrementTableau() bool { 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) + cs.hasSet = cs.d.hasSetWithLast(cs.tableau) if cs.hasSet { continue } |