ヌメロンとかいうテレビ番組があるらしい。
つまりは古典的数当てゲーム「Hit&Blow」なんだね。
- 出題者は1～9から重複なしに3つ選び、3桁の数(正解)を作る
- 解答者はその数を推理し3桁の数(答案)を宣言する
- 出題者は正解と答案とを比較し、
数も桁も一致している数(Hit) と
数は合っているが桁の異なる数(Blow) を返す
これを繰り返し、少ない回数で正解を導く、と。
計算機ゲームとしては計算機が出題者となるんだろうけども、
ここでは計算機に回答者を演じてもらおう...
#include <iostream>
#include <string>
#include <array>
#include <vector>
#include <numeric>
#include <algorithm>
#include <utility>
#include <iterator>
#include <cassert>
using namespace std;
const int N = 3;
typedef array<int,N> number;
typedef pair<int,int> hb;
typedef pair<number,hb> hint;
// 各桁に0を含まず、重複のないことを確認する
bool is_good(number n) {
if ( find(begin(n),end(n),0) != end(n) ) return false;
sort(begin(n),end(n));
return unique(begin(n),end(n)) == end(n);
}
// 1～9を重複なくN個選ぶ
void init_candidates(vector<number>& candidates) {
array<int,9> digits;
iota(begin(digits), end(digits), 1);
array<bool,9> bits;
fill(begin(bits),end(bits),false);
fill_n(begin(bits), N, true);
do {
int c = 0;
number tmp;
for ( int i = 0; i < 9; ++i ) {
if ( bits[i] ) tmp[c++] = i+1;
}
assert(is_good(tmp));
do {
candidates.push_back(tmp);
} while ( next_permutation(begin(tmp),end(tmp)) );
} while ( prev_permutation(begin(bits),end(bits)) );
}
// hit/blow数を勘定する
hb judge(const number& actual, const number& guess) {
int hit = 0;
int blow = 0;
for ( int i = 0; i < N ; ++i ) {
for ( int j = 0; j < N; ++j ) {
if ( actual[i] == guess[j] ) {
if ( i == j ) ++hit; else ++blow;
}
}
}
return hb(hit,blow);
}
ostream& operator<<(ostream& stream, const number& n) {
for_each(begin(n),end(n),[&](int n) { stream << n;});
return stream;
}
ostream& operator<<(ostream& stream, const hb& h) {
return stream << h.first << "Hit / " << h.second << "Blow";
}
int main() {
number answer;
while ( true ) {
cout << "各桁が1～9である" << N << "桁の数を入力してほしい。各桁で数が重複するのは避けてくれ" << endl;
string str; cin >> str;
const string digits = "123456789";
if ( str.size() == N && all_of(begin(str),end(str),[&](char c) { return digits.find(c) != string::npos;}) ) {
transform(begin(str), end(str), begin(answer), [](char c) { return c - '0';});
if ( is_good(answer) ) break;
}
}
cout << "君が選んだのは " << answer << " だね。では僕がその数を推理しよう。" << endl;
int trial = 0;
vector<number> candidates;
init_candidates(candidates);
random_shuffle(begin(candidates),end(candidates));
vector<hint> hints;
while ( true ) {
cout << ++trial << "回目："
<< " 正解となる数の候補は " << candidates.size() << " あるが... ";
number candidate = candidates.front();
cout << candidates.front() << " ではないかな?" << endl;
hb result = judge(answer, candidate);
cout << result << endl;
if ( result.first == N ) break; // 正解ならばloopを抜ける
hints.push_back(hint(candidate,result)); // 判定結果をhintsに追加する
// これまでに得られたhintsから候補を絞り込む
vector<number> new_candidates;
// 候補となる数 n について:
for ( number n : candidates ) {
// nがこれまでに得られたhintと矛盾がないならば、それは正解かもしれないので候補に残す
if ( all_of(begin(hints),end(hints),[&](hint h) { return judge(n,h.first) == h.second;}) ) {
new_candidates.push_back(n);
}
}
candidates = new_candidates;
}
}
/* --- 実行結果 ---
各桁が1～9である3桁の数を入力してほしい。各桁で数が重複するのは避けてくれ
918
君が選んだのは 918 だね。では僕がその数を推理しよう。
1回目： 正解となる数の候補は 504 あるが... 978 ではないかな?
2Hit / 0Blow
2回目： 正解となる数の候補は 18 あるが... 976 ではないかな?
1Hit / 0Blow
3回目： 正解となる数の候補は 10 あるが... 378 ではないかな?
1Hit / 0Blow
4回目： 正解となる数の候補は 4 あるが... 928 ではないかな?
2Hit / 0Blow
5回目： 正解となる数の候補は 3 あるが... 918 ではないかな?
3Hit / 0Blow
*/