summaryrefslogtreecommitdiff
path: root/capset.go
blob: 2b182cb9bf50bda05be1913c25e8d5e1fbc30e7c (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
// 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)
			}
		}
	}
}