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 game

I don't think this game needs explanation. Wikipedia provides more information.

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 mut rng = thread_rng();
        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()
        .filter(|sol| Answer::from_guess(proposal, sol) == *hint)
        .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.

[1]Mastermind with Steve Mould, singing banana

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

Read More

Differential equation in python

Sat 04 April 2020
Second order differential equation (Photo credit: Wikipedia)

In python, differential equations can be numerically solved thanks to scipy [1]. Is usage is not as intuitive as I expected.

Simple equation

Let's start small. The first equation will be really simple:

\begin{equation*} \frac{\partial{f}}{\partial{t}} = a \times f …

Category: maths Tagged: python maths equation

Read More

Zombie propagation

Sat 21 March 2020
Zombie favorite food warning (Photo credit: wikipedia)

I recently read a paper [1] trying to model a disease propagation. I wanted to play with this model.

The model

The model is know as "SIR" as it divide the population into 3 groups:

  • S: suceptible to become a zombie
  • I: infected …

Category: maths Tagged: python maths zombie

Read More

big cloud data

Sun 02 February 2014

[caption id="" align="alignright" width="350"]Français : Big pink cloud Oia Big cloud not computing (Photo credit: Wikipedia)[/caption]

This post should be untitled From cloud computing to big data to fast data.

The previously next big stuff: cloud

computing

[caption id="" align="alignright" width="75"]English: Cloud Computing Image Cloud computing (Photo credit: Wikipedia)[/caption]

Once upon a …

Category: maths Tagged: Apache Hadoop BigData Cloud computing Data mining Forecasting MongoDB NoSQL Platform as a service Software as a service SQL reflections

Read More

Music reflection: timeline and publications

Sat 18 January 2014

[caption id="" align="alignright" width="350"]English: artificial omni-directional sound sou... sound research material (Photo credit: Wikipedia)[/caption]

I just discover google music timeline. That leads me to several publications from google about music.

I wonder why does google work on music. Google is a commercial company whose business model is based on ads and …

Category: maths Tagged: Business model Google Play Publication search engine Timeline maths music reflections

Read More

music physics: notes

Mon 23 December 2013

Explications here are based on what I've learn thanks to this youtube channel and the related researches (including the famous french documentary series c'est pas sorcier)

sound physics

For this post, we will use the following definitions:

  • a sound: fluid vibration (air, water, ...) that reach our ears
  • a noise: a …

Category: maths

Read More
Page 1 of 2

Next »