|
1 package takuzu |
|
2 |
|
3 import ( |
|
4 "fmt" |
|
5 |
|
6 "github.com/pkg/errors" |
|
7 ) |
|
8 |
|
9 // checkRange returns true if the range is completely defined, and an error |
|
10 // if it doesn't follow the rules for a takuzu line or column |
|
11 // Note that the boolean might be invalid if the error is not nil. |
|
12 func checkRange(cells []Cell) (bool, error) { |
|
13 full := true |
|
14 size := len(cells) |
|
15 counters := []int{0, 0} |
|
16 |
|
17 var prevCell Cell |
|
18 var prevCellCount int |
|
19 |
|
20 for _, c := range cells { |
|
21 if !c.Defined { |
|
22 full = false |
|
23 prevCell.Defined = false |
|
24 prevCellCount = 0 |
|
25 continue |
|
26 } |
|
27 counters[c.Value]++ |
|
28 if prevCellCount == 0 { |
|
29 prevCellCount = 1 |
|
30 } else { |
|
31 if c.Value == prevCell.Value { |
|
32 prevCellCount++ |
|
33 if prevCellCount > 2 { |
|
34 return full, errors.Errorf("3+ same values %d", c.Value) |
|
35 } |
|
36 } else { |
|
37 prevCellCount = 1 |
|
38 } |
|
39 |
|
40 } |
|
41 prevCell = c |
|
42 } |
|
43 if counters[0] > size/2 { |
|
44 return full, errors.Errorf("too many zeroes") |
|
45 } |
|
46 if counters[1] > size/2 { |
|
47 return full, errors.Errorf("too many ones") |
|
48 } |
|
49 return full, nil |
|
50 } |
|
51 |
|
52 // CheckRangeCounts returns true if all cells of the provided range are defined, |
|
53 // as well as the number of 0s and the number of 1s in the range. |
|
54 func CheckRangeCounts(cells []Cell) (full bool, n0, n1 int) { |
|
55 counters := []int{0, 0} |
|
56 full = true |
|
57 |
|
58 for _, c := range cells { |
|
59 if c.Defined { |
|
60 counters[c.Value]++ |
|
61 } else { |
|
62 full = false |
|
63 } |
|
64 } |
|
65 return full, counters[0], counters[1] |
|
66 } |
|
67 |
|
68 // CheckLine returns an error if the line i fails validation |
|
69 func (b Takuzu) CheckLine(i int) error { |
|
70 _, err := checkRange(b.GetLine(i)) |
|
71 return err |
|
72 } |
|
73 |
|
74 // CheckColumn returns an error if the column i fails validation |
|
75 func (b Takuzu) CheckColumn(i int) error { |
|
76 _, err := checkRange(b.GetColumn(i)) |
|
77 return err |
|
78 } |
|
79 |
|
80 // Validate checks a whole board for errors (not completeness) |
|
81 // Returns true if all cells are defined. |
|
82 func (b Takuzu) Validate() (bool, error) { |
|
83 finished := true |
|
84 |
|
85 computeVal := func(cells []Cell) (val int) { |
|
86 for i := 0; i < len(cells); i++ { |
|
87 val += cells[i].Value * 1 << uint(i) |
|
88 } |
|
89 return |
|
90 } |
|
91 |
|
92 lineVals := make(map[int]bool) |
|
93 colVals := make(map[int]bool) |
|
94 |
|
95 for i := 0; i < b.Size; i++ { |
|
96 var d []Cell |
|
97 var full bool |
|
98 var err error |
|
99 |
|
100 // Let's check line i |
|
101 d = b.GetLine(i) |
|
102 full, err = checkRange(d) |
|
103 if err != nil { |
|
104 return false, errors.Wrapf(err, "line %d", i) |
|
105 } |
|
106 if full { |
|
107 hv := computeVal(d) |
|
108 if lineVals[hv] { |
|
109 return false, fmt.Errorf("duplicate lines (%d)", i) |
|
110 } |
|
111 lineVals[hv] = true |
|
112 } else { |
|
113 finished = false |
|
114 } |
|
115 |
|
116 // Let's check column i |
|
117 d = b.GetColumn(i) |
|
118 full, err = checkRange(d) |
|
119 if err != nil { |
|
120 return false, errors.Wrapf(err, "column %d", i) |
|
121 } |
|
122 if full { |
|
123 hv := computeVal(d) |
|
124 if colVals[hv] { |
|
125 return false, fmt.Errorf("duplicate columns (%d)", i) |
|
126 } |
|
127 colVals[hv] = true |
|
128 } else { |
|
129 finished = false |
|
130 } |
|
131 } |
|
132 return finished, nil |
|
133 } |