サブロウ丸

Sabrou-mal サブロウ丸

主にプログラミングと数学

Master mind in Rust; part 1

Rust mastermind

これからRustでmaster mindというボードゲームの実装をしていきます。以前C++で実装したもののRust版ですね。なるべく標準でシンプルな実装を目指します。C++版はこちら↓↓

master mind ( マスターマインド ) とは

master mind というゲームを解くプログラムを作成します。

隠されたピンの配列secretを当てるゲームです。 本来はプレイヤーはピンの配列を試し、それがどれほどsecretに近いかを表すヒントをもらう、ということを繰り返します。ヒントとしては

  • hit ヒット = 色と配置が合っているピンの数
  • blow ブロー = 色は合っているけど配置が違うピンの数

の2つが与えられます。 次はゲーム進行の図です。

このプロジェクトではユーザーがsecretを決めた上で、それをプログラム側が当てるようにします。

実装

用語

記事やプログラムで用いる用語の整理

  • code コード ... ピンの配列
  • secret 秘密コード ... 隠されたピンの配列
  • guess 推測コード ... 試すピンの配列
  • hint ヒント ... 2つのコードに対する(hit, blow)の情報
  • trial 試行 ... ピン配列guessを試して、hintをもらうこと

全体の流れ

まずは最もシンプルな全体フローを考えてみます。

  1. 秘密コードの候補となるコード集合の取得
  2. policy: 推論コードguessを選択
  3. trial: ユーザからhintをもらう
  4. 秘密コード候補を更新
  5. もし秘密コード候補の要素数が1であれば、その要素が秘密コードsecretであるため、それを出力して終了。 そうでなければ2に戻る

全体のコード

3色、2ピン、コードに色の重複なし、の設定で動くコードです。

policy

最もシンプルなものとして先頭のコードを推論コードに選択します。VecはCopyトレイトを持っていないため、明示的にcloneした要素を返します。

// select guess
fn policy(guess_set: Vec<Vec<usize>>) -> Vec<usize> {
    guess_set[0].clone()
}

trial

ユーザーが秘密コードsecretを持っており、プログラムがそのsecretを推測する状況を考えましょう。trialでは推論コードguessを元にユーザーがヒントを入力します。

// get a hint according to the guess from user input
fn trial(guess: Vec<usize>) -> (usize, usize) {
    println!("Guess is {:?}", guess);
    print!("input hit and blow (format: hit blow)> ");
    std::io::stdout().flush().unwrap();
    let mut input_string = String::new();
    std::io::stdin().read_line(&mut input_string).ok();
    let parts: Vec<&str> = input_string.split_whitespace().collect();
    let hit = parts[0].parse().expect("Hit should be an integer number.");
    let blow = parts[1].parse().expect("Blow should be an integer number.");
    (hit, blow)
}
  • .split_whitespace(): 文字列を空白で分割し、そのイテレータを返します。
  • .parse(): 文字列スライスをある型に変換し、Result型で結果を返します。ここでhitやblowはusizeであるため、usize型に変換されます。

calc_hint関数

二つのコードを元にhintであるhitとblowを計算する関数を実装します。hitとblowはそれぞれ、

  • hit: 位置と色が一致している数
  • blow: 位置は違うが色が一致している数

です。calc_hint関数がそれにあたります。

update candidates

Vec型の場合、retainメソッドを用いることで条件を満たす要素のみを残すことができます。条件を満たさない要素についてはメモリを解放します。

candidates.retain(|x| calc_hint(x, &guess) == hint); // update candidates

Rust Playground

Rustコードをブラウザで実行できる有能ツール。コンパイルをはじめ、TOOLSからformat (fmt) コード整形や、Clippy というlinter(静的解析ツール)を用いることができます。 Miriを用いてもコードの動作に問題が無いか確認できます。

ひとまず、 ここまで。

参考

関連