Mastermind solver in rust

Sun 17 March 2024
(Not mastermind) code breaking machine (Photo credit: wikipedia)

I recently watch a video [1] explaining how to solve mastermind. I wanted to try it myself, so I coded it in rust. Here are the code and the playground.

The code

Let's divide our code in several steps and produce a quick and (not so) dirty code.

The board

We need:
• colored pins (Color struct)
• a structure to represent a pattern (the Code)
• Pegs for the master to give hints to the guesser.

I implemented the Display trait for the Code to have a more compact representation than the Debug.

```#[derive(Clone, Debug, Eq, PartialEq, Hash)]
enum Peg {
Correct,
Misplaced,
}

#[derive(Clone, Debug, Eq, PartialEq, Hash)]
enum Color {
Red,
Green,
Yellow,
Blue,
Purple,
White,
}

impl fmt::Display for Color {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
let c = match self {
Color::Red => "R",
Color::Green => "G",
Color::Yellow => "Y",
Color::Blue => "B",
Color::Purple => "P",
Color::White => "W",
};
write!(f, "{c}")
}
}

#[derive(Clone, Debug, Eq, PartialEq, Hash)]
struct Code(Vec<Color>);

impl fmt::Display for Code {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{}", self.0.iter().map(|c| format!("{}", c)).join(" "))
}
}
```

I added a possible random initialization for a Code

```impl Code {
fn random() -> Self {
let colors = vec![
Color::Red,
Color::Green,
Color::Yellow,
Color::Blue,
Color::Purple,
Color::White,
];
Self(
(0..4)
.map(|_| {
colors
.choose(&mut rng)
.expect("at least one color exist")
.clone()
})
.collect::<Vec<_>>(),
)
}
}
```

Hints

The Answer (set of Correct and Misplaced pegs) can be initiated from guess (given a guess and a solution, what is the hint the master must give?). To compute it, I used a 2 passes approach: on the first pass, I identify the correct colors and remove them (pins used) and on the second one, I identify the misplaced colors. I used this approach to be able to remove pins already used to compute the hint.

Minimax

The heart of the algorithm reside here. Given all the remaining possible answer (left, l.136) the algorithm must look for what can happen in the next step. In this next step, the guesser (code breaker) will obtain a hint. For all possible hint he can obtain, there will be some solutions left. The worse hint he can get is the one leaving the more remaining codes. The guesser must propose a code from those remaining codes in order to maximize the quantity of information received.

```fn get_worse_solution<'a>(proposal: &'a Code, hint: &'a Answer, left: &HashSet<Code>) -> Code {
let left: HashSet<Code> = left
.iter()
.cloned()
.collect();

let mut ans = HashMap::new();
let possible_hints = get_all_hints();
for possible_hint in possible_hints {
ans.insert(
possible_hint.clone(),
get_possible_codes(proposal, &possible_hint, &left),
);
}
let worse_next_score = ans
.values()
.map(|v| v.len())
.max()
.expect("at least one value");
let worse_next_hint = ans
.iter()
.filter_map(|(k, v)| {
if v.len() == worse_next_score {
Some(k)
} else {
None
}
})
.next()
.expect("there should be at least one solution left");
ans[worse_next_hint]
.iter()
.next()
.expect("worse solution is greater than zero")
.clone()
}
```

Players

To play, I decided to implement 2 threads, one for the guesser, the other for the master. They communicate sending Code and Answer on dedicated channels. They also output some state. Their implementation is straight forward.

Category: maths Tagged: rust maths game game theory

GNSS as an optimization problem

Thu 20 July 2023
Satellite optimized (Photo credit: Wikipedia)

GNSS's basic functionality works as follow: Satellites sends their position and their local time frequently. The time is synchronized between satellites thanks to the most accurate time keeping devices ever made (atomic clock). Each GNSS constellation implements its own time (e.g. GPS time). The …

Category: maths Tagged: python maths optimization

Differential thrust

Wed 27 July 2022
Differential thrust (Photo credit: GE)

Principle overview

The basic principle is to create a torque offsetting the total thrust. This offset is done by throttling thrust of multiple engines whose thrust is not align with gravity center.

On the drawing, the thrust is aligned with CG for the left engine …

Category: aviation Tagged: aviation Fight dynamics rocket science

Voting method reflections

Fri 28 January 2022
Transparent voting box (Photo credit: Wikipedia)

This article presents personal thoughts on voting methods. More specifically, it presents guarantees offer by the traditional non-electronic voting method and won’t elaborate on electronic voting.

Specifications

First, let’s define few specifications I’d like to develop.

• any voter can understand how …

Category: reflections Tagged: geopolitics reflection vote

Tkinter and Asyncio

Thu 18 February 2021
Asynchronous process results waiting (Photo credit: Wikipedia)

Graphical interfaces are typically the kind of object that can take advantage of asynchrounous programming as a GUI spend lot of time waiting for user input.

Tkinter <https://docs.python.org/3/library/tkinter.html#module-tkinter>_ is a kind of standard for …

Category: how to Tagged: python asyncio