/
game.go
218 lines (196 loc) · 4.88 KB
/
game.go
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
package main
import "fmt"
const (
length = 5
letters = 26
)
type clue uint8
const (
unknown clue = iota
gray
yellow
green
)
func resultString(result [length]clue) string {
b := make([]byte, length)
for i, c := range result {
switch c {
case unknown:
b[i] = ' '
case gray:
b[i] = '_'
case yellow:
b[i] = 'Y'
case green:
b[i] = 'G'
}
}
return string(b)
}
// low 5 bits: bitmask of where the letter is
// high 3 bits: int3 of how many there are
type (
charIndex uint8
index [letters]charIndex
)
func newIndex(word string) index {
var ret index
for i, c := range []byte(word) {
ret[c-'a'] |= 1 << i
ret[c-'a'] += 1 << length
}
return ret
}
func (ci charIndex) count() uint8 {
return uint8(ci >> length)
}
func (ci charIndex) at(i int) bool {
return ci&(1<<i) != 0
}
type state struct {
target string
targetIndex index
// high 5 bits: (letter that was green)+1, or 0 if none
// low 26 bits: bitmask of letters that were yellow/gray
clues [length]uint32
// low 7 bits: max times yellow/green
// high bit: 1 if exact (i.e. also had gray on that guess)
counts [letters]uint8
}
func newState(target string) *state {
if len(target) != length {
panic(fmt.Sprintf("invalid target: len(%v) = %v", target, len(target)))
}
s := state{
target: target,
targetIndex: newIndex(target),
}
return &s
}
func (s *state) guess(word string) (result [length]clue, won bool) {
if len(word) != length {
panic(fmt.Sprintf("invalid guess: len(%v) = %v", word, len(word)))
}
wordIndex := newIndex(word)
for i, charIndex := range wordIndex {
targetIndex := s.targetIndex[i]
switch {
case charIndex == 0:
// didn't guess this character
// (note this is actually a special case of the third case,
// included for speed and clarity)
continue
case targetIndex == 0:
// character not in target: this letter is gray
// (note this is actually a special case of the last case, included
// for speed and clarity)
for j := 0; j < length; j++ {
if charIndex.at(j) {
result[j] = gray
s.clues[j] |= 1 << i
}
}
s.counts[i] = 0x80
case charIndex.count() <= targetIndex.count():
// guessed at most the right number of this letter: they'll all be
// green/yellow.
for j := 0; j < length; j++ {
if charIndex.at(j) {
if targetIndex.at(j) {
result[j] = green
s.clues[j] |= uint32(i+1) << (32 - length)
} else {
result[j] = yellow
s.clues[j] |= 1 << i
}
}
}
s.counts[i] = charIndex.count()
default:
// guessed too many of this letter: correct positions are
// green/yellow, then the first n are yellow to get the right
// number, rest are gray.
need := targetIndex.count()
// first find green.
for j := 0; j < length; j++ {
if charIndex.at(j) && targetIndex.at(j) {
result[j] = green
s.clues[j] |= uint32(i+1) << (32 - length)
need--
}
}
// next find yellow/gray.
for j := 0; j < length; j++ {
if charIndex.at(j) && !targetIndex.at(j) {
if need > 0 {
result[j] = yellow
s.clues[j] |= 1 << i
need--
} else {
result[j] = gray
s.clues[j] |= 1 << i
}
}
}
s.counts[i] = 0x80 | targetIndex.count()
}
}
return result, result == [length]clue{green, green, green, green, green}
}
func (s *state) hardModeInfo(word string) (bool, string, byte, int) {
if len(word) != length {
panic(fmt.Sprintf("invalid guess: len(%v) = %v", word, len(word)))
}
wordIndex := newIndex(word)
for i, n := range s.counts {
max := n & 0x7f
c := byte(i + 'a')
if n&0x80 == 0x80 {
// if prev guess has m copies of a letter, and k < m are
// yellow/green, must use that letter exactly k times
if wordIndex[i].count() != max {
if max == 0 {
return false, "can't use %c", c, -1
} else {
return false, "need to use %c exactly %d times", c, int(max)
}
}
} else {
// if prev guess has m copies of a letter, and all are
// yellow/green, must use that letter at least m times
if wordIndex[i].count() < max {
return false, "need to use %c at least %d times", c, int(max)
}
}
}
for j, c := range []byte(word) {
i := c - 'a'
clue := s.clues[j]
// if prev guess has green in a spot, must use that letter in that spot
green := clue >> (32 - length)
if green != 0 && i != byte(green-1) {
return false, "need %c as letter %d", 'a' + byte(green-1), j + 1
}
// if prev guess has yellow or gray in a spot, must NOT use that letter
// in that spot
if clue&(1<<i) != 0 {
return false, "can't use %c as letter %d", c, j + 1
}
}
return true, "", 0, 0
}
func (s *state) hardModeProblem(word string) error {
ok, str, b, n := s.hardModeInfo(word)
switch {
case ok:
return nil
case n == -1:
return fmt.Errorf(str, b)
default:
return fmt.Errorf(str, b, n)
}
}
func (s *state) hardModeOK(word string) bool {
ok, _, _, _ := s.hardModeInfo(word)
return ok
}