master mind by rust; part 7 HashMapとそれを用いたmin max policyの追加

今回やること

• policyの追加
• HashMapの説明

minmax policy

いままでは推論コードguessの選択にfirst_pickというものを使っていました。これはguessの候補集合から最初のものを選ぶという単純なものです。 ここをもう少し工夫します。

作成するのはminmax policyです。これはguessを提示してhintが返ってきたときに、そのhintに対して最悪の場合の最小の候補数を最大化するものです。 そのため全てのguess候補に対してそのhint当てはまる秘密コード候補の数をカウントします。

// select guess from guesses, which has minimum candidates in worst case
pub fn minmax(
    candidates: &def::CodeSet,
    guess_set: &def::CodeSet,
    context: &def::Context,
) -> def::Code {
    let mut best_guess = guess_set[0].clone();
    let mut min_max_candidate_num = i16::MAX;
    for guess in guess_set {
        let map = utils::calc_hint_based_candidate_num_map(candidates, guess, context);
        let max_candidate_num = map.values().max().unwrap();
        if *max_candidate_num < min_max_candidate_num {
            best_guess = guess.clone();
            min_max_candidate_num = *max_candidate_num;
        }
    }
    best_guess
}

mapはhintに対してそれに当てはまる秘密コード候補の数を保持するHashMapです。これを用いて最大の候補数を取得します。

• valuesでmapの値のイテレータを取得
• maxで最大値を取得
• unwrapでOptionを取り出す

utils::calc_hint_based_candidate_num_mapは次のようになっています。

// create map whose key is hint vaule is number of code set
pub fn calc_hint_based_candidate_num_map(
    candidates: &def::CodeSet,
    guess: &def::Code,
    context: &def::Context,
) -> HashMap<def::Hint, i16> {
    let mut map = HashMap::new();
    for code in candidates {
        let hint = calc_hint(code, guess, context);
        let candidate_num = map.entry(hint).or_insert(0);
        *candidate_num += 1;
    }
    map
}

HashMap

上記のコードのmap変数はHashMap<K, V>はK型のキーとV型の値を持つハッシュマップです。

• map.entry(hint)はキーhintに対応する値を取得します。.or_insert(0)はキーがない場合に0を挿入します。返り値は&mut Vです。
• *candidate_num += 1はキーhintに対応する値をインクリメントします。

argument parserの更新

コマンドライン引数でpolicyの種類を指定できるようにします。次のようにPolicyの列挙型を作成し、clap::ValueEnumをderiveします。

#[derive(Debug, Clone, clap::ValueEnum)]
pub enum Policy {
    Firstpick,
    Minmax,
}

main.rsのArgs構造体にpolicyを追加します。

#[derive(Parser)]
#[command(about)]
struct Args {
    // (省略)
    #[arg(short, long, value_enum, default_value_t = def::Policy::Minmax, help = "policy for choosing guess")]
    policy: def::Policy,
}

// parse command line arguments
let cli = Args::parse();
let context = def::Context {
    // (省略)
    policy: cli.policy,
};

そして推論コードguessを選択する際にPolicyに応じてfirst_pickかminmaxを選択します。

let guess = match context.policy {
    def::Policy::Firstpick => policy::first_pick(&candidates),
    def::Policy::Minmax => policy::minmax(&candidates, &all_codes, &context),
};

コード

• 差分

参考

• https://qiita.com/masakuni-ito/items/10603050c7a06f329da2#commandauthor