東方算程譚

Oriental Code Talk ── επιστημηが与太をこく、弾幕とは無縁のシロモノ。

目次

Blog 利用状況

ニュース

著作とお薦めの品々は

著作とお薦めの品々は
東方熱帯林へ。

あわせて読みたい

わんくま

  1. 東京勉強会#2
    C++/CLI カクテル・レシピ
  2. 東京勉強会#3
    template vs. generics
  3. 大阪勉強会#6
    C++むかしばなし
  4. 東京勉強会#7
    C++むかしばなし
  5. 東京勉強会#8
    STL/CLRによるGeneric Programming
  6. TechEd 2007 @YOKOHAMA
    C++・C++/CLI・C# 適材適所
  7. 東京勉強会#14
    Making of BOF
  8. 東京勉強会#15
    状態遷移
  9. 名古屋勉強会#2
    WinUnit - お気楽お手軽UnitTest

CodeZine

  1. Cで実現する「ぷちオブジェクト指向」
  2. CUnitによるテスト駆動開発
  3. SQLiteで組み込みDB体験(2007年版)
  4. C++/CLIによるCライブラリの.NET化
  5. C# 1.1からC# 3.0まで~言語仕様の進化
  6. BoostでC++0xのライブラリ「TR1」を先取りしよう (1)
  7. BoostでC++0xのライブラリ「TR1」を先取りしよう (2)
  8. BoostでC++0xのライブラリ「TR1」を先取りしよう (3)
  9. BoostでC++0xのライブラリ「TR1」を先取りしよう (4)
  10. BoostでC++0xのライブラリ「TR1」を先取りしよう (5)
  11. C/C++に対応した、もうひとつのUnitTestFramework ─ WinUnit
  12. SQLiteで"おこづかいちょう"
  13. STL/CLRツアーガイド
  14. マージ・ソート : 巨大データのソート法
  15. ヒープソートのアルゴリズム
  16. C++0xの新機能「ラムダ式」を次期Visual Studioでいち早く試す
  17. .NETでマンデルブロ集合を描く
  18. .NETでマンデルブロ集合を描く(後日談)
  19. C++/CLI : とある文字列の相互変換(コンバージョン)
  20. インテルTBBによる選択ソートの高速化
  21. インテルTBB3.0 によるパイプライン処理
  22. Visual C++ 2010に追加されたSTLアルゴリズム
  23. Visual C++ 2010に追加されたSTLコンテナ「forward_list」
  24. shared_ptrによるObserverパターンの実装
  25. .NETでマンデルブロ集合を描く(番外編) ── OpenCLで超並列コンピューティング
  26. StateパターンでCSVを読む
  27. 状態遷移表からStateパターンを自動生成する
  28. 「ソートも、サーチも、あるんだよ」~標準C++ライブラリにみるアルゴリズムの面白さ
  29. インテルTBBの同期メカニズム
  30. なぜsetを使っちゃいけないの?
  31. WPFアプリケーションで腕試し ~C++でもWPFアプリを
  32. C++11 : スレッド・ライブラリひとめぐり
  33. Google製のC++ Unit Test Framework「Google Test」を使ってみる
  34. メールでデータベースを更新するココロミ
  35. Visitorパターンで遊んでみたよ
  36. Collection 2題:「WPFにバインドできる辞書」と「重複を許す検索set」
  37. Visual C++ 2012:stateless-lambdaとSQLiteのぷち拡張
  38. 「Visual C++ Compiler November 2012 CTP」で追加された6つの新機能

@IT

  1. Vista時代のVisual C++の流儀(前編)Vista到来。既存C/C++資産の.NET化を始めよう!
  2. Vista時代のVisual C++の流儀(中編)MFCから.NETへの実践的移行計画
  3. Vista時代のVisual C++の流儀(後編) STL/CLRによるDocument/Viewアーキテクチャ
  4. C++開発者のための単体テスト入門 第1回 C++開発者の皆さん。テスト、ちゃんとしていますか?
  5. C++開発者のための単体テスト入門 第2回 C++アプリケーションの効率的なテスト手法(CppUnit編)
  6. C++開発者のための単体テスト入門 第3回 C++アプリケーションの効率的なテスト手法(NUnit編)

AWARDS


Microsoft MVP
for Visual Developer - Visual C++


Wankuma MVP
for いぢわる C++


Nyantora MVP
for こくまろ中国茶

Xbox

Links

記事カテゴリ

書庫

日記カテゴリ

Hit&Blow お化粧直し

んーと、これでちっとはC++らしくなったかな。

#include <iostream>
#include <string>
#include <array>
#include <vector>
#include <algorithm>
#include <utility>
#include <iterator>

using namespace std;

const int N = 3;

// N桁の数
typedef array<int,N> number;

ostream& operator<<(ostream& stream, const number& n) {
  for_each(begin(n),end(n),[&](int n) { stream << n;});
  return stream;
} 

// Hit/Blowの組
typedef pair<int,int> hb;

ostream& operator<<(ostream& stream, const hb& h) {
  return stream << h.first << "Hit / " << h.second << "Blow";
} 

// 出題者
class contributor {
  friend class referee;
public:
  contributor(number a) : answer(a) {}
private:
  number answer;
};

// 審判員
class referee {
public:
  // 重複のないことを確認する
  static bool isnot_duplicated(number n) {
    sort(begin(n),end(n));
    return unique(begin(n),end(n)) == end(n);
  }
  // hit/blow数を勘定する
  static 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);
  }
  static hb judge(contributor& con, const number& guess) {
    return judge(con.answer, guess);
  }
};

// 解答者
class solver {
private:
  typedef pair<number,hb> hint;
public:
  solver() {
    init_candidates();
  }
  // hintを追加する
  void add_hint(number n, hb h) {
    hints.push_back(hint(n,h));
  }
  // 候補の中から答案をひとつ返す
  number submit() {
    think();
    random_shuffle(begin(candidates),end(candidates));
    return candidates.back();
  }
  // 候補の数を返す
  int n_candidates() const {
    return candidates.size();
  }
private:
  // 1~9から重複なくN個選び、候補を列挙する。
  void init_candidates() {
    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;
      }
      do {
        candidates.push_back(tmp);
      } while ( next_permutation(begin(tmp),end(tmp)) );
    } while ( prev_permutation(begin(bits),end(bits)) );
  }
  void think() {
    // 候補の中から、これまでに得られたhintと矛盾があるものを除外する
    candidates.erase(
      remove_if(begin(candidates),end(candidates),
                [&](number n) { 
                  return any_of(begin(hints),end(hints),
                                [&](hint h) { 
                                  return referee::judge(n,h.first) != h.second;
                                });
                }), 
                end(candidates));
  }
  vector<number> candidates; // 候補
  vector<hint> hints; // もらったヒント
};

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 ( referee::isnot_duplicated(answer) ) break;
    }
  }    
  cout << "君が選んだのは " << answer << " だね。";
  contributor con(answer);
  solver      sol;
  cout << "では僕がその数を推理しよう。" << endl;

  int trial = 0;
  while ( true ) {
    // 候補の中からひとつ選ぶ
    cout << ++trial << "回目:"
         << " 正解となる数の候補は " << sol.n_candidates() << " あるが... ";
    number candidate = sol.submit();
    cout << candidate << " ではないかな?" << endl;

    // 結果を判定。 正解ならばloopを抜ける
    hb result = referee::judge(con, candidate);
    cout << result << endl;
    if ( result.first == N ) break;

    // 判定結果をhintsに追加する
    sol.add_hint(candidate,result);    
  }
}

投稿日時 : 2012年12月28日 1:55

コメントを追加

No comments posted yet.
タイトル  
名前  
URL
コメント