Swap to bitwise hasSet()

Using bitwise operations yields over a 2x speedup.

The iteration order of hasSet was reversed which causes it to be within
60% of the performance of hasSetWithLast, instead of 6x slower. It was
also rewritten to use hasSetWithLast for better code reuse.

2 files changed, 219 insertions, 111 deletions

diff --git a/capset.go b/capset.go
index 9824e37..89cf92d 100644
--- a/capset.go
+++ b/capset.go
@@ -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)
 	}
 }