author | Mikael Berthe <mikael@lilotux.net> |
Sun, 16 Oct 2016 09:48:36 +0200 | |
changeset 7 | e284e3ad2800 |
parent 6 | 110d38ae22cd |
child 8 | 955d3add9426 |
permissions | -rw-r--r-- |
0 | 1 |
package takuzu |
2 |
||
3 |
import ( |
|
4 |
"bytes" |
|
5 |
"fmt" |
|
6 |
"math" |
|
7 |
||
8 |
"github.com/pkg/errors" |
|
9 |
) |
|
10 |
||
11 |
// Cell is a single cell of a Takuzu game board |
|
12 |
type Cell struct { |
|
13 |
Defined bool |
|
14 |
Value int |
|
15 |
} |
|
16 |
||
17 |
// Takuzu is a Takuzu game board (Size x Size) |
|
18 |
type Takuzu struct { |
|
19 |
Size int |
|
20 |
Board [][]Cell |
|
21 |
} |
|
22 |
||
23 |
// New creates a new Takuzu board |
|
24 |
func New(size int) Takuzu { |
|
25 |
t := Takuzu{Size: size} |
|
26 |
t.Board = make([][]Cell, size) |
|
27 |
for l := range t.Board { |
|
28 |
t.Board[l] = make([]Cell, size) |
|
29 |
} |
|
30 |
return t |
|
31 |
} |
|
32 |
||
33 |
// NewFromString creates a new Takuzu board from a string definition |
|
34 |
func NewFromString(s string) (*Takuzu, error) { |
|
35 |
l := len(s) |
|
2 | 36 |
if l < 4 { |
37 |
return nil, errors.New("bad string length") |
|
38 |
} |
|
39 |
||
0 | 40 |
size := int(math.Sqrt(float64(l))) |
41 |
if size*size != l { |
|
42 |
return nil, errors.New("bad string length") |
|
43 |
} |
|
44 |
||
45 |
i := 0 |
|
46 |
t := New(size) |
|
47 |
||
48 |
for line := 0; line < size; line++ { |
|
49 |
for col := 0; col < size; col++ { |
|
50 |
switch s[i] { |
|
51 |
case '0', 'O': |
|
52 |
t.Board[line][col].Defined = true |
|
53 |
t.Board[line][col].Value = 0 |
|
54 |
case '1', 'I': |
|
55 |
t.Board[line][col].Defined = true |
|
56 |
t.Board[line][col].Value = 1 |
|
57 |
case '.': |
|
58 |
default: |
|
59 |
return nil, errors.New("invalid char in string") |
|
60 |
} |
|
61 |
i++ |
|
62 |
} |
|
63 |
} |
|
64 |
return &t, nil |
|
65 |
} |
|
66 |
||
67 |
// ToString converts a takuzu board to its string representation |
|
68 |
func (b Takuzu) ToString() string { |
|
69 |
var sbuf bytes.Buffer |
|
70 |
for line := 0; line < b.Size; line++ { |
|
71 |
for col := 0; col < b.Size; col++ { |
|
72 |
if b.Board[line][col].Defined { |
|
73 |
sbuf.WriteString(fmt.Sprintf("%d", b.Board[line][col].Value)) |
|
74 |
continue |
|
75 |
} |
|
76 |
sbuf.WriteByte('.') |
|
77 |
} |
|
78 |
} |
|
79 |
return sbuf.String() |
|
80 |
} |
|
81 |
||
6
110d38ae22cd
Refactor code; split takuzu.go and create solve.go
Mikael Berthe <mikael@lilotux.net>
parents:
4
diff
changeset
|
82 |
// DumpString writes the content of the board as a string |
0 | 83 |
func (b Takuzu) DumpString() { |
84 |
fmt.Println(b.ToString()) |
|
85 |
} |
|
86 |
||
87 |
// Clone returns a copy of the Takuzu board |
|
88 |
func (b Takuzu) Clone() Takuzu { |
|
89 |
c := New(b.Size) |
|
90 |
for line := range b.Board { |
|
91 |
for col := range b.Board[line] { |
|
92 |
c.Board[line][col] = b.Board[line][col] |
|
93 |
} |
|
94 |
} |
|
95 |
return c |
|
96 |
} |
|
97 |
||
98 |
// Copy copies a Takuzu board to another existing board |
|
99 |
func Copy(src, dst *Takuzu) error { |
|
100 |
if src.Size != dst.Size { |
|
101 |
return errors.New("sizes do not match") |
|
102 |
} |
|
103 |
for line := range src.Board { |
|
104 |
for col := range src.Board[line] { |
|
105 |
dst.Board[line][col] = src.Board[line][col] |
|
106 |
} |
|
107 |
} |
|
108 |
return nil |
|
109 |
} |
|
110 |
||
111 |
// BoardsMatch compares a Takuzu board to another, optionally ignoring |
|
112 |
// empty cells. Returns true if the two boards match. |
|
113 |
func BoardsMatch(t1, t2 *Takuzu, ignoreUndefined bool) (match bool, line, col int) { |
|
114 |
match = true |
|
115 |
||
2 | 116 |
if t1 == nil || t2 == nil { |
117 |
line, col = -1, -1 |
|
118 |
match = false |
|
119 |
return |
|
120 |
} |
|
121 |
||
0 | 122 |
if t1.Size != t2.Size { |
123 |
line, col = -1, -1 |
|
124 |
match = false |
|
125 |
return |
|
126 |
} |
|
2 | 127 |
|
0 | 128 |
for line = range t1.Board { |
129 |
for col = range t1.Board[line] { |
|
130 |
if !t1.Board[line][col].Defined || !t2.Board[line][col].Defined { |
|
131 |
// At least one of the cells is empty |
|
132 |
if ignoreUndefined || |
|
133 |
!(t1.Board[line][col].Defined || t2.Board[line][col].Defined) { |
|
134 |
// Both cells are empty or we ignore empty cells |
|
135 |
continue |
|
136 |
} |
|
137 |
match = false |
|
138 |
return |
|
139 |
} |
|
140 |
// Both cells are defined |
|
141 |
if t1.Board[line][col].Value != t2.Board[line][col].Value { |
|
142 |
match = false |
|
143 |
return |
|
144 |
} |
|
145 |
} |
|
146 |
} |
|
147 |
||
148 |
line, col = -1, -1 |
|
149 |
return |
|
150 |
} |
|
151 |
||
152 |
// Set sets the value of the cell; a value -1 will set the cell as undefined |
|
153 |
func (c *Cell) Set(value int) { |
|
154 |
if value != 0 && value != 1 { |
|
155 |
c.Defined = false |
|
156 |
return |
|
157 |
} |
|
158 |
c.Defined = true |
|
159 |
c.Value = value |
|
160 |
} |
|
161 |
||
162 |
// Set sets the value of a specific cell |
|
163 |
// A value -1 will undefine the cell |
|
164 |
func (b Takuzu) Set(l, c, value int) { |
|
165 |
if value != 0 && value != 1 { |
|
166 |
b.Board[l][c].Defined = false |
|
167 |
return |
|
168 |
} |
|
169 |
b.Board[l][c].Defined = true |
|
170 |
b.Board[l][c].Value = value |
|
171 |
} |
|
172 |
||
173 |
// GetLine returns a slice of cells containing the ith line of the board |
|
174 |
func (b Takuzu) GetLine(i int) []Cell { |
|
175 |
return b.Board[i] |
|
176 |
} |
|
177 |
||
178 |
// GetColumn returns a slice of cells containing the ith column of the board |
|
179 |
func (b Takuzu) GetColumn(i int) []Cell { |
|
180 |
c := make([]Cell, b.Size) |
|
181 |
for l := range b.Board { |
|
182 |
c[l] = b.Board[l][i] |
|
183 |
} |
|
184 |
return c |
|
185 |
} |
|
186 |
||
187 |
// GetLinePointers returns a slice of pointers to the cells of the ith line of the board |
|
188 |
func (b Takuzu) GetLinePointers(i int) []*Cell { |
|
189 |
r := make([]*Cell, b.Size) |
|
190 |
for l := range b.Board[i] { |
|
191 |
r[l] = &b.Board[i][l] |
|
192 |
} |
|
193 |
return r |
|
194 |
} |
|
195 |
||
196 |
// GetColumnPointers returns a slice of pointers to the cells of the ith column of the board |
|
197 |
func (b Takuzu) GetColumnPointers(i int) []*Cell { |
|
198 |
r := make([]*Cell, b.Size) |
|
199 |
for l := range b.Board { |
|
200 |
r[l] = &b.Board[l][i] |
|
201 |
} |
|
202 |
return r |
|
203 |
} |
|
204 |
||
205 |
// FillLineColumn add missing 0s or 1s if all 1s or 0s are there. |
|
206 |
// Note: This method can update b. |
|
207 |
func (b Takuzu) FillLineColumn(l, c int) { |
|
208 |
fillRange := func(r []*Cell) { |
|
209 |
size := len(r) |
|
210 |
var notFull bool |
|
211 |
var n [2]int |
|
212 |
for x := 0; x < size; x++ { |
|
213 |
if r[x].Defined { |
|
214 |
n[r[x].Value]++ |
|
215 |
} else { |
|
216 |
notFull = true |
|
217 |
} |
|
218 |
} |
|
219 |
if !notFull { |
|
220 |
return |
|
221 |
} |
|
222 |
if n[0] == size/2 { |
|
223 |
// Let's fill the 1s |
|
224 |
for _, x := range r { |
|
225 |
if !x.Defined { |
|
226 |
x.Defined = true |
|
227 |
x.Value = 1 |
|
228 |
} |
|
229 |
} |
|
230 |
} else if n[1] == size/2 { |
|
231 |
// Let's fill the 0s |
|
232 |
for _, x := range r { |
|
233 |
if !x.Defined { |
|
234 |
x.Defined = true |
|
235 |
x.Value = 0 |
|
236 |
} |
|
237 |
} |
|
238 |
} |
|
239 |
} |
|
240 |
||
241 |
var cells []*Cell |
|
242 |
||
243 |
// Fill line |
|
244 |
cells = b.GetLinePointers(l) |
|
245 |
fillRange(cells) |
|
246 |
// Fill column |
|
247 |
cells = b.GetColumnPointers(c) |
|
248 |
fillRange(cells) |
|
249 |
} |
|
250 |
||
251 |
// DumpBoard displays the Takuzu board |
|
252 |
func (b Takuzu) DumpBoard() { |
|
253 |
fmt.Println() |
|
254 |
for i := range b.Board { |
|
255 |
dumpRange(b.Board[i]) |
|
256 |
} |
|
257 |
} |
|
258 |
||
259 |
// CheckLine returns an error if the line i fails validation |
|
260 |
func (b Takuzu) CheckLine(i int) error { |
|
261 |
_, err := checkRange(b.GetLine(i)) |
|
262 |
return err |
|
263 |
} |
|
264 |
||
265 |
// CheckColumn returns an error if the column i fails validation |
|
266 |
func (b Takuzu) CheckColumn(i int) error { |
|
267 |
_, err := checkRange(b.GetColumn(i)) |
|
268 |
return err |
|
269 |
} |
|
270 |
||
271 |
// Validate checks a whole board for errors (not completeness) |
|
272 |
// Returns true if all cells are defined. |
|
273 |
func (b Takuzu) Validate() (bool, error) { |
|
274 |
finished := true |
|
275 |
||
276 |
computeVal := func(cells []Cell) (val int) { |
|
277 |
for i := 0; i < len(cells); i++ { |
|
278 |
val += cells[i].Value * 1 << uint(i) |
|
279 |
} |
|
280 |
return |
|
281 |
} |
|
282 |
||
283 |
lineVals := make(map[int]bool) |
|
284 |
colVals := make(map[int]bool) |
|
285 |
||
286 |
for i := 0; i < b.Size; i++ { |
|
287 |
var d []Cell |
|
288 |
var full bool |
|
289 |
var err error |
|
290 |
||
291 |
// Let's check line i |
|
292 |
d = b.GetLine(i) |
|
293 |
full, err = checkRange(d) |
|
294 |
if err != nil { |
|
295 |
return false, errors.Wrapf(err, "line %d", i) |
|
296 |
} |
|
297 |
if full { |
|
298 |
hv := computeVal(d) |
|
299 |
if lineVals[hv] { |
|
300 |
return false, fmt.Errorf("duplicate lines (%d)", i) |
|
301 |
} |
|
302 |
lineVals[hv] = true |
|
303 |
} else { |
|
304 |
finished = false |
|
305 |
} |
|
306 |
||
307 |
// Let's check column i |
|
308 |
d = b.GetColumn(i) |
|
309 |
full, err = checkRange(d) |
|
310 |
if err != nil { |
|
311 |
return false, errors.Wrapf(err, "column %d", i) |
|
312 |
} |
|
313 |
if full { |
|
314 |
hv := computeVal(d) |
|
315 |
if colVals[hv] { |
|
3 | 316 |
return false, fmt.Errorf("duplicate columns (%d)", i) |
0 | 317 |
} |
318 |
colVals[hv] = true |
|
319 |
} else { |
|
320 |
finished = false |
|
321 |
} |
|
322 |
} |
|
323 |
return finished, nil |
|
324 |
} |
|
325 |
||
326 |
func dumpRange(cells []Cell) { |
|
327 |
for _, c := range cells { |
|
328 |
if !c.Defined { |
|
329 |
fmt.Printf(". ") |
|
330 |
continue |
|
331 |
} |
|
332 |
fmt.Printf("%d ", c.Value) |
|
333 |
} |
|
334 |
fmt.Println() |
|
335 |
} |
|
336 |
||
337 |
// checkRange returns true if the range is completely defined, and an error |
|
338 |
// if it doesn't follow the rules for a takuzu line or column |
|
339 |
// Note that the boolean might be invalid if the error is not nil. |
|
340 |
func checkRange(cells []Cell) (bool, error) { |
|
341 |
full := true |
|
342 |
size := len(cells) |
|
343 |
counters := []int{0, 0} |
|
344 |
||
345 |
var prevCell Cell |
|
346 |
var prevCellCount int |
|
347 |
||
348 |
for _, c := range cells { |
|
349 |
if !c.Defined { |
|
350 |
full = false |
|
351 |
prevCell.Defined = false |
|
352 |
prevCellCount = 0 |
|
353 |
continue |
|
354 |
} |
|
355 |
counters[c.Value]++ |
|
356 |
if prevCellCount == 0 { |
|
357 |
prevCellCount = 1 |
|
358 |
} else { |
|
359 |
if c.Value == prevCell.Value { |
|
360 |
prevCellCount++ |
|
361 |
if prevCellCount > 2 { |
|
362 |
return full, errors.Errorf("3+ same values %d", c.Value) |
|
363 |
} |
|
364 |
} else { |
|
365 |
prevCellCount = 1 |
|
366 |
} |
|
367 |
||
368 |
} |
|
369 |
prevCell = c |
|
370 |
} |
|
371 |
if counters[0] > size/2 { |
|
372 |
return full, errors.Errorf("too many zeroes") |
|
373 |
} |
|
374 |
if counters[1] > size/2 { |
|
375 |
return full, errors.Errorf("too many ones") |
|
376 |
} |
|
377 |
return full, nil |
|
378 |
} |
|
379 |
||
7 | 380 |
// CheckRangeCounts returns true if all cells of the provided range are defined, |
381 |
// as well as the number of 0s and the number of 1s in the range. |
|
382 |
func CheckRangeCounts(cells []Cell) (full bool, n0, n1 int) { |
|
0 | 383 |
counters := []int{0, 0} |
384 |
full = true |
|
385 |
||
386 |
for _, c := range cells { |
|
387 |
if c.Defined { |
|
388 |
counters[c.Value]++ |
|
389 |
} else { |
|
390 |
full = false |
|
391 |
} |
|
392 |
} |
|
393 |
return full, counters[0], counters[1] |
|
394 |
} |