diff options
| -rw-r--r-- | capset.go | 247 | ||||
| -rw-r--r-- | capset_test.go | 83 |
2 files changed, 219 insertions, 111 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 } diff --git a/capset_test.go b/capset_test.go index 29a77da..a807b3b 100644 --- a/capset_test.go +++ b/capset_test.go @@ -3,7 +3,6 @@ package main import ( "bufio" "fmt" - "log" "os" "reflect" "testing" @@ -11,22 +10,68 @@ import ( var deck = NewDeck(4) +var hassettests = []struct { + tableau []string + hasSet bool + hasSetLast bool +}{ + {[]string{"0000"}, false, false}, + {[]string{"0000", "0001"}, false, false}, + {[]string{"0000", "0001", "0002"}, true, true}, + {[]string{"0000", "0001", "0011"}, false, false}, + {[]string{"0000", "1111", "2222"}, true, true}, + {[]string{"0000", "1111", "2222", "0100"}, true, false}, + {[]string{"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", + "1000", "1001", "1012"}, false, false}, + {[]string{"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", + "1000", "1001", "1012", "1022", "1102", "1202", "2012", "2102", "2110", + "2111", "2122", "2212"}, false, false}, +} + +func TestHasSet(t *testing.T) { + for _, tt := range hassettests { + tableau, err := deck.FindCards(tt.tableau) + if err != nil { + t.Error(err) + continue + } + found := deck.hasSet(tableau) + if tt.hasSet != found { + t.Error("HasSet: For", tableau, "found", found, "but expected", tt.hasSet) + } + found = deck.hasSetWithLast(tableau) + if tt.hasSetLast != found { + t.Error("HasSetLast: For", tableau, "found", found, "but expected", tt.hasSet) + } + } +} + var capsettests = []struct { maxim int - start, finish []Card + start, finish []string }{ - {20, []Card{"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", + {20, []string{"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1012"}, - []Card{"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", + []string{"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1012", "1022", "1102", "1202", "2012", "2102", "2110", "2111", "2122", "2212"}}, } func TestFindNextCapset(t *testing.T) { for _, tt := range capsettests { - cs := Capset{tableau: tt.start, maxim: tt.maxim, d: deck} + start, err := deck.FindCards(tt.start) + if err != nil { + t.Error(err) + continue + } + finish, err := deck.FindCards(tt.finish) + if err != nil { + t.Error(err) + continue + } + cs := Capset{tableau: start, maxim: tt.maxim, d: deck} cs.FindNextCapset() - expected := Capset{tableau: tt.finish, maxim: len(tt.finish), d: deck} + expected := Capset{tableau: finish, maxim: len(tt.finish), d: deck} if !reflect.DeepEqual(cs, expected) { t.Fatalf("Got \n%v but expected \n%v", cs, expected) } @@ -35,17 +80,17 @@ func TestFindNextCapset(t *testing.T) { var scantests = []struct { in string - out []Card + out []string err bool }{ {"", nil, true}, - {"[]", []Card{}, false}, - {"[0000]", []Card{"0000"}, false}, - {"[0000 2222]", []Card{"0000", "2222"}, false}, + {"[]", []string{}, false}, + {"[0000]", []string{"0000"}, false}, + {"[0000 2222]", []string{"0000", "2222"}, false}, {"[2]", nil, true}, {"not it", nil, true}, {"[0000", nil, true}, - {"[ 0000 2222 ]", []Card{"0000", "2222"}, false}, + {"[ 0000 2222 ]", []string{"0000", "2222"}, false}, } func TestScan(t *testing.T) { @@ -63,7 +108,12 @@ func TestScan(t *testing.T) { if err != nil { t.Errorf("Sscanln(%v). Unexpected error %v", tt.in, err) } else { - if !reflect.DeepEqual(cs.tableau, tt.out) { + out, err := deck.FindCards(tt.out) + if err != nil { + t.Error("For input", tt.in, "got unexpected error:", err) + continue + } + if !reflect.DeepEqual(cs.tableau, out) { t.Errorf("Sscanln(%v) => %v, want %v", tt.in, cs.tableau, tt.out) } } @@ -85,7 +135,7 @@ func TestDim3(t *testing.T) { cmpfile, err := os.Open("./capset3.out") if err != nil { - log.Fatal(err) + t.Fatal(err) } defer cmpfile.Close() scanner := bufio.NewScanner(cmpfile) @@ -98,6 +148,9 @@ func TestDim3(t *testing.T) { newline, scanner.Text()) } } + if scanner.Scan() { + t.Error("Did not find items starting with", scanner.Text()) + } } func BenchmarkIncrement(b *testing.B) { @@ -111,7 +164,7 @@ func BenchmarkIncrementHasSet(b *testing.B) { cs := NewCapset(deck, -1) for i := 0; i < b.N; i++ { cs.incrementTableau() - cs.hasSet = hasSet(cs.tableau) + cs.hasSet = deck.hasSet(cs.tableau) } } @@ -119,6 +172,6 @@ func BenchmarkIncrementHasSetWithLast(b *testing.B) { cs := NewCapset(deck, -1) for i := 0; i < b.N; i++ { cs.incrementTableau() - cs.hasSet = hasSetWithLast(cs.tableau) + cs.hasSet = deck.hasSetWithLast(cs.tableau) } } |