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
use std::cmp::min;
use rand::seq::SliceRandom as _;
use rayon::iter::{IntoParallelRefIterator, ParallelIterator as _};
use crate::{
code::{all_possible_codes, Code, NUMBER_OF_PEGS_IN_CODE},
hint::Hint,
peg::NUM_DIFFERENT_PEGS,
};
/// A solver for codebreaker
pub struct Solver {
/// Codes which have not been guessed so far yet, but are also possible solutions. We may still
/// want to guess them though, because guessing them might reveal more information, than
/// guessing a potential solution.
remaining_unguessed_codes: Vec<Code>,
/// Solutions which are still possible.
potential_solutions: Vec<Code>,
}
impl Solver {
/// Creates a solver which deterministically solves the codebreaker game.
pub fn new() -> Self {
let mut potential_solutions =
Vec::with_capacity((NUM_DIFFERENT_PEGS as usize).pow(NUMBER_OF_PEGS_IN_CODE as u32));
potential_solutions.extend(all_possible_codes());
Solver {
remaining_unguessed_codes: Vec::new(),
potential_solutions,
}
}
/// Creates a solver which picks randomly one of the best guesses
pub fn with_sampled_guesses(rng: &mut impl rand::Rng) -> Self {
let mut solver = Solver::new();
solver.remaining_unguessed_codes.shuffle(rng);
solver
}
pub fn guess(&mut self) -> Code {
// Maximize guaranteed elimination of possiblities. We find a guess which maximizes the
// potential solutions elimintated. We would do so, even if the guess is not a potential
// solution itself, however, if two guesses eliminate the same number of possibilities, we
// prefer to guess a potential solution, so we might get lucky and finish the game right
// there.
let best_candidate = self
.potential_solutions
.par_iter()
.chain(self.remaining_unguessed_codes.par_iter())
.map(|&code| Candidate::new(code))
.reduce_with(|a, b| {
Candidate::better(a, b, |code, lower_bound| {
self.min_possibilties_eliminated(code, lower_bound)
})
})
.expect("Solution must be possible");
best_candidate.code
}
pub fn update(&mut self, guess: Code, hint: Hint) {
self.potential_solutions.retain(|&code| {
let canidate_hint = Hint::new(guess, code);
if hint != canidate_hint && code != guess {
self.remaining_unguessed_codes.push(code);
}
hint == canidate_hint
});
self.remaining_unguessed_codes.retain(|&code| code != guess);
}
/// Minimum number of possiblities a guess would eliminate. If the minimum is larger than the
/// lower_bound result is exact, otherwise it is lower_bound. Setting a lower bound allows the
/// function to exit early if the result would be smaller than the a better maximum we already
/// know about.
fn min_possibilties_eliminated(&self, candidate_guess: Code, lower_bound: u32) -> u32 {
let mut current_min = u32::MAX;
for &possible_solution in &self.potential_solutions {
let hint = Hint::new(candidate_guess, possible_solution);
let eliminated = self.num_eliminated_possiblities(hint, candidate_guess, current_min);
current_min = min(current_min, eliminated);
if current_min <= lower_bound {
return lower_bound;
}
}
current_min
}
/// How many possible codes would be remaining by a guess with a certain hint. The result will
/// be exact if it is smaller or equal to upper bound. Otherwise it is larger than upper bound.
fn num_eliminated_possiblities(&self, hint: Hint, guess: Code, upper_bound: u32) -> u32 {
self.potential_solutions
.iter()
.filter(|&&code| hint != Hint::new(guess, code) || guess == code)
.take(upper_bound as usize)
.count() as u32
}
}
impl Default for Solver {
fn default() -> Self {
Self::new()
}
}
/// Candidate for a guess
struct Candidate {
/// Code the guess represents
code: Code,
/// Laziyly computed number of guaranteed possibilities eliminated by this guess
eliminated: Option<u32>,
}
impl Candidate {
fn new(code: Code) -> Self {
Candidate {
code,
eliminated: None,
}
}
/// Out of two candidates, picks the better one, or the first one if they are equal.
fn better(
mut a: Candidate,
mut b: Candidate,
min_eliminated_with_lower_bound: impl Fn(Code, u32) -> u32,
) -> Candidate {
// Calculate the guaranteed number of eliminated possibilities, if missing, but using an
// existing number as lower bound, if available.
match (a.eliminated, b.eliminated) {
// Both values availabe, nothing to do
(Some(_), Some(_)) => a.replace_if_better(b),
(Some(a_eliminated), None) => {
b.eliminated = Some(min_eliminated_with_lower_bound(b.code, a_eliminated));
// Be careful, the order matters here. Due to short circuiting, above b might be
// worse, but seem just as good.
a.replace_if_better(b)
}
(None, Some(b_eliminated)) => {
a.eliminated = Some(min_eliminated_with_lower_bound(a.code, b_eliminated));
b.replace_if_better(a)
}
(None, None) => {
a.eliminated = Some(min_eliminated_with_lower_bound(a.code, 0));
b.eliminated = Some(min_eliminated_with_lower_bound(
b.code,
a.eliminated.unwrap(),
));
a.replace_if_better(b)
}
}
}
/// Replaces the candidate with another one if the other one is better. If both are equal, self
/// is returned. Requires eliminated to be computed.
fn replace_if_better(self, other: Candidate) -> Candidate {
if other.eliminated.unwrap() > self.eliminated.unwrap() {
other
} else {
self
}
}
}
#[cfg(test)]
mod tests {
use crate::{code::Code, hint::Hint};
use super::Solver;
#[test]
fn solve_5611() {
let code: Code = "5611".parse().unwrap();
let mut solver = Solver::new();
let guesses = play_out(code, &mut solver);
assert_eq!(&["2211", "4321", "5131", "5511", "5611"], &guesses[..]);
}
#[test]
fn solve_2231() {
let code: Code = "2231".parse().unwrap();
let mut solver = Solver::new();
let guesses = play_out(code, &mut solver);
assert_eq!(&["2211", "3221", "2231"], &guesses[..]);
}
fn play_out(code: Code, solver: &mut Solver) -> Vec<String> {
let mut guesses = Vec::new();
let mut count = 0;
loop {
assert!(count < 5, "Too many guesses");
let guess = solver.guess();
guesses.push(guess.to_string());
let hint = Hint::new(guess, code);
solver.update(guess, hint);
if hint.is_solution() {
break;
}
count += 1;
}
guesses
}
}