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

Suicide burn

Sat 27 August 2022
Rocket burn (Photo credit: Wikipedia)

Principle overview

The goal of the suicide burn (also called hoverslam) [1] is to land a rocket while minimal thrust is not low enough to hover [2]. Thus, the engine must be turned off at the point where the rocket land.

The challenge is then …

Category: aviation Tagged: aviation Fight dynamics rocket science

Read More

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

Read More

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

Read More

Mobile OS alternatives and european sovereignty

Tue 04 May 2021
Sailfish (not OS) (photo credit: wikipedia)

OS for mobile devices has evolved over the pasts years. Once, European actors (e.g. Nokia) were in lead position. Now it's hard to find non-android mobile OS. Each OS mobile comes with its software and hardware environements, and its geopolitical considerations.

Here is …

Category: tools Tagged: smartphone geopolitics

Read More

Cache implementation using weakref

Fri 30 April 2021
Bird's cache (Photo credit: Wikipedia)

This article presents a quick example of how to use weakref to implement a home-made cache mechanism.

Let's use the following use case:

  • Let's consider items:
    • items can be stored on a storage
    • items can be retrieved from storage
    • items are identify by an ID …

Category: how to Tagged: python cache weakref

Read More

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

Read More
Page 1 of 12

Next »