Go to Qiita Advent Calendar 2024 Top
LoginSignup
38
41

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@hiki_neet_p

「オブジェクト指向が5000%理解できる記事(実践編)」の解答編

Last updated at Posted at 2018-09-30

2018/10/10追記
記事を大きく修正しました。
変更箇所は、お手数ですが「編集履歴」を参照してください。

謝辞

本記事の答えに辿り着くまでに、色々な方にご指摘をいただき、大変助かりました（コメント欄をご覧ください）。

特に @sumim 氏には、問題と解答を提供していただきましたが、これがなければ本記事を仕上げることは叶いませんでした。深く感謝いたします。

試行錯誤する中で、私にとって勉強になることは多く、良い経験になりました。ありがとうございました。

はじめに

本記事は、@sumim 氏が改変して紹介したインディアン・ポーカーに関するプログラミング問題の解法を説明しながら、オブジェクト指向プログラミングに触れてみるものです。

私がこの問題を目にしたのは、@gorillab 氏による以下の記事を読んだときでした。

オブジェクト指向が5000%理解できる記事
オブジェクト指向が5000%理解できる記事(実践編)

両記事は大きな反響を生んだため、ご存知の方も多いと思います。この「実践編」にて、インディアン・ポーカー問題が取り上げられていました。

この問題は非情に難しく、また奥が深い問題です。しかし、上記事では大変雑に取り上げられていました。オブジェクト指向の初心者向け解説記事を謳いながら、実質的に何の解決にもならない曖昧な説明で終わっています。

対照的に、コメント欄は盛り上がりました。問題の紹介者である @sumim 氏が登場し、解法を示してくださいました。しかし、そこで示された解法が不完全であることに気がついたので、私なりにこの問題を解き、本記事を書こうと思いました。

インディアン・ポーカー問題

解決対象となる問題

リクルートコミュニケーションズのコーディング試験で過去に出題された問題を、@sumim 氏が改変したものです。

問題はこちら → https://twitter.com/sumim/status/1043665621433470977

問題の要点

  • この問題におけるインディアン・ポーカー
    • 2人以上のプレイヤーで行なう。
    • 数字の書かれたカードを用意する（カード数はプレイヤー数以上）。
    • プレイヤーにカードを配るが、各プレイヤーは自分のカードの数字を見てはいけない。
    • 各プレイヤーはカードを額にかざす。カード数字は自分を除く他プレイヤーに見える状態となる。
    • この状態で、各プレイヤーは順番に、自分のカードの数字を予想し、宣言してゆく。
    • 宣言の内容は4種類。
      • 自分が1番小さい「MIN」
      • 自分が1番大きい「MAX」
      • 自分は最大と最小以外である「MID」
      • 分からない「?」
    • 1人でも答えが分かったらゲーム終了。
    • プレイヤーは嘘をつかず、最善を尽くす。
    • 無限ループになる可能性がある。 無限ループは発生せず、答えは必ず求まることが分かりました。

例

カード { 1, 2, 3, 4, 5 }
プレイヤー { A, B, C }

  • A=1, B=4, C=5 の場合

    • A=>MIN

  • A=1, B=2, C=4 の場合

    • A=>?, B=>MID

問題の解答

こちらです↓

インディアン・ポーカー・ソルバー

.NET Core 2.1、C#7.3 です。

動かし方

git clone git@github.com:tana-gh/indian_poker.git
cd indian_poker
dotnet run -p IndianPoker.App.Multiple/IndianPoker.App.Multiple.csproj -- 5 3

上記 5 3 の部分には、それぞれカード枚数、プレイヤー人数を指定してください。
（大きな数を指定すると計算時間がかかる場合があります）

dotnet run -p IndianPoker.App.Multiple/IndianPoker.App.Multiple.csproj -- <カード枚数> <プレイヤー人数>

配るカードを指定する場合はこちらです。

dotnet run -p IndianPoker.App.Single/IndianPoker.App.Single.csproj -- <カード枚数> <プレイヤー人数> <カード1> <カード2> ...

コードの概要

私の書いたコードは 5 つのプロジェクトに分割されています。

IndianPoker.App.Multiple // 実行プログラム（複数ケースを出力）
IndianPoker.App.Single   // 実行プログラム（単一ケースを出力）
IndianPoker.Lib          // 今回のソルバーを含む
IndianPoker.Lib.Utils    // ユーティリティ
IndianPoker.Test         // テスト

このうち、IndianPoker.Lib だけが重要なので、以下ではこのプロジェクトについて説明します。クラスをどのように分けるかというのは、一種のパズルです。各クラスがどのような意図を持つのか、想像しながら見ていただけると嬉しいです。

※ 私のコードの書き方で、アクセス修飾子が internal または private のシンボルに _ アンダースコアのプレフィックスをつけています。

クラス構成

IndianPoker.Lib

public class Solver          // ゲームを進行し、結果を生成
public struct PlayerAnswer   // プレイヤーの答え
public enum AnswerValue      // 答えの内容
internal class _Card         // カード
internal class _Deck         // カードのデッキ
internal class _Player       // プレイヤー
internal struct _VisibleCard // 見えているカード
internal class _Inference    // 推論に関する情報
internal class _PlayerOrder  // 手番の順序

クラス図

classes.png

Solver 

// ゲームを進行し、結果を生成
public class Solver
{
    // 参加プレイヤーと所持カード
    public IEnumerable<(string playerName, int cardNumber)> NameAndNumbers { get; }

    // allNumbers : 全カードの数字列
    // deckNumbers: プレイヤーのドローするカードの数字列（与えられた順）
    // playerNames: プレイヤーの名前列（与えられた順）
    public Solver(IEnumerable<int> allNumbers, IEnumerable<int> deckNumbers, IEnumerable<string> playerNames) { }

    // ゲームを進行し、結果を生成する
    // return: 答え列
    public IEnumerable<PlayerAnswer> Solve() { }
}

ゲームの進行を担います。

最初にコンストラクタで、全てのカードに書かれた数字、プレイヤーに配られるカードの数字、全てのプレイヤーの名前、を受け取ります。その情報をもとに、まず _Deck を生成します。_Deck は _Card を生成し、その _Card を _Player コンストラクタに渡します。このとき渡す _Card は、他の _Player が掲げているカードです（このゲームでは、自分のカードを見てはいけない）。

Solve メソッドでゲームをシミュレートし、ゲーム中にプレイヤー達が宣言した答えを返します。

PlayerAnswer 

// プレイヤーの答え
public struct PlayerAnswer
{
    // 答えを宣言したプレイヤーの名前（nullable）
    public string PlayerName { get; }

    // 答えの内容
    public AnswerValue Value { get; }

    // playerName: 答えを宣言したプレイヤーの名前（nullable）
    // value: 答えの内容
    public PlayerAnswer(string playerName, AnswerValue value) { }
    
    public override string ToString() { }
}

プレイヤーの名前と、プレイヤーが宣言した答えです。

AnswerValue 

// 答えの内容
public enum AnswerValue
{
    Unknown, // ?   に相当
    Min,     // MIN に相当
    Mid,     // MID に相当
    Max      // MAX に相当
}

答えの内容です。

_Card 

internal class _Card
{
    // カードに書かれた数字
    public int Number { get; }

    // number: カードに書かれた数字
    public _Card(int number) { }
}

カードです。カードに書かれた数字を取得できます。

_Deck 

// カードのデッキ
internal class _Deck
{
    // プレイヤーがドローするカード列
    public IEnumerable<_Card> DeckCards { get; }

    // ソート済みの全カード
    public IEnumerable<_Card> SortedCards { get; }

    // allNumber  : 全カードの数字列
    // deckNumbers: プレイヤーがドローするカードの数字列
    public _Deck(IEnumerable<int> allNumbers, IEnumerable<int> deckNumbers) { }
}

デッキです。DeckCards は、プレイヤーに配られるカードがプレイヤー順に格納されています。対して SortedCards は、全てのカードが昇順に格納されています。

DeckCards と SortedCards で共通の数字を持つカードは、同一のインスタンスです。

_Player 

internal class _Player
{
    // プレイヤーの名前
    public string Name { get; }
    
    // 推論に関する情報
    private _Inference _Inference { get; }

    // name: プレイヤーの名前
    // visibleCards: 他プレイヤーのカード
    // allCards    : 全カード
    // order       : 手番の順序
    public _Player(string name, IEnumerable<_VisibleCard> visibleCards, IEnumerable<_Card> allCards, _PlayerOrder order) { }

    // 答えを宣言する
    // orderIndex: _PlayerOrder上における現在の順番
    public PlayerAnswer SayAnswer(int orderIndex) { }
}

プレイヤーです。推論に関する情報である _Inference を内部に持っています。
SayAnswer で、自分の答えを宣言します。

_VisibleCard 

// 見えているカード
internal struct _VisibleCard
{
    // カードを所持するプレイヤーの名前
    public string PlayerName { get; }

    // 見えているカード
    public _Card Card { get; }

    // playerName: カードを所持するプレイヤーの名前
    // card: 見えているカード
    public _VisibleCard(string playerName, _Card card) { }
}

プレイヤーが額にかざしているカードです。プレイヤーの名前とカードがセットになっています。

_Inference 

// 推論に関する情報
internal class _Inference
{
    // 推論対象のプレイヤーの名前
    private string _PlayerName { get; }

    // プレイヤーに見えているカード列
    private IEnumerable<_VisibleCard> _VisibleCards { get; }

    // 全カード列
    private IEnumerable<_Card> _AllCards { get; }

    // 手番の順序
    private _PlayerOrder _Order { get; }

    // _Inferメソッドのメモ
    private Dictionary<_MemoKey, PlayerAnswer> _Memo { get; }

    // playerName  : 推論対象のプレイヤーの名前
    // visibleCards: プレイヤーに見えているカード列
    // allCards    : 全カード列
    // order       : 手番の順序
    public _Inference(string playerName, IEnumerable<_VisibleCard> visibleCards, IEnumerable<_Card> allCards, _PlayerOrder order) { }

    // 現在の順番に基づき、答えを導出する
    // orderIndex: _PlayerOrder上における現在の順番
    // return    : 答え
    public PlayerAnswer Infer(int orderIndex) { }
}

今回のソルバーの推論に関わる、アルゴリズムをまとめたものです。

各プレイヤーがこの _Inference を 1 つずつ持ちます。自プレイヤーが持つ推論情報は、当然自分のカードを知らない状態にあります。与えられた他プレイヤーのカード情報をもとに、最善手で答えを導きます。

答えを導出する Infer メソッドは、orderIndex を受け取りますが、これは、プレイヤーの手番の順序列を生成する _PlayerOrder のインデックスです。

次章では、このクラスがどのようにインディアン・ポーカー問題を解決するのかを見ていきます。

_PlayerOrder 

// 手番の順序
internal class _PlayerOrder
{
    // 全プレイヤーの名前列
    private IEnumerable<string> _PlayerNames { get; }

    // playerNames: 全プレイヤーの名前列
    public _PlayerOrder(IEnumerable<string> playerNames) { }

    // 手番の順序を生成する
    // return: 順序付けられたプレイヤーの名前列
    public IEnumerable<string> GetPlayerNames() { }
}

プレイヤーの手番の順序どおりに、プレイヤー名をイテレートする列挙子を生成します。

アルゴリズム

答えの確定条件

ルールをもう一度確認します。プレイヤーには、自分以外のカードが見えており、自分の手番が回ってきたとき、自分のカードを予想します。このとき、嘘を言ってはいけません。

宣言内容は以下のとおりです。

  • 自分が1番小さい「MIN」
  • 自分が1番大きい「MAX」
  • 自分は最大と最小以外である「MID」
  • 分からない「?」

話を簡単にするため、カードを { 1, 2, 3, 4, 5 } 、プレイヤーを { A, B, C } とします。

プレイヤー B の答えが確定するのはどのようなときでしょうか。

  • 「MIN」は、他プレイヤー（A、C）が大きい数字に隙間なく固まっている（5、4）とき。
  • 「MAX」は、他プレイヤー（A、C）が小さい数字に隙間なく固まっている（1、2）とき。
  • 「MID」は、他プレイヤー（A、C）が小さい数字と大きい数字に固まっている（1、5）とき。

では、A=2, C=5 のときはどうでしょうか。これは、「MIN」の可能性と「MID」の可能性がありますので、分からない「?」と答えます。

本当にそうでしょうか。

B の手番が回ってくる直前、A は「?」と答えました。もし B=1 だったら、A から見て B=1, C=5 なので、A は「MID」と答えたはずです。そうならなかったということは、B=1 はありえません。

ありえないカードを X で表すと、現在の状態は X=1, A=2, C=5 です。これで B の答えは「MID」に確定しました。

このとき答えを確定できたのは、ありえないカードである X の存在があったからです。可能性のあるカードから、ありえないカードを除外してゆくことが、アルゴリズムの要となります。

話を戻しまして、答えが確定する条件を以下のように決めます。

  • 「MIN」は、可能性のあるカードが、他プレイヤーのどのカードよりも小さいとき。
  • 「MAX」は、可能性のあるカードが、他プレイヤーのどのカードよりも大きいとき。
  • 「MID」は、可能性のあるカードの最小値が他プレイヤーのカードの最小値よりも大きく、可能性のあるカードの最大値が他プレイヤーのカードの最大値よりも小さいとき。
  • 「?」は、上記以外のとき。

推論テーブルの表記

以下、カードとプレイヤーの対応を、次のように表記します。

  • 他プレイヤーのかかげている（Visible）カード「A、B、C、...」（プレイヤー名）
  • 自分のカードである可能性のある（Possible）カード「O」
  • 自分のカードである可能性のない（Impossible）カード「X」

以上の記号をこのように表記します。

B
[ 1:X, 2:A, 3:O, 4:O, 5:C ]

ここで、B は推論対象プレイヤーです。

この表記を「推論テーブル」と呼ぶことにします。

推論の多重化

この節では、カードを { 1, 2, 3, 4, 5, 6, 7 } 、プレイヤーを { A, B, C } とします。A=3, B=4, C=5 のとき、C がどのように推論するのか考えてみましょう。

前述の推論テーブルの表記を用いると、プレイヤー C の推論の初期状態は以下のようになります。

C
[ 1:O, 2:O, 3:A, 4:B, 5:O, 6:O, 7:O ]

推論対象プレイヤー C

ここでは、1 つ前の手番である B に着目することにします。B のカードは 4 です。覚えておきましょう。

Possible であるカードを推論の対象とします。Possible であるカードは 1、2、5、6、7 ですが、ここでは 1 と 2 だけに注目してみましょう。推論対象プレイヤー C のカードは 1 である、もしくは 2 である、と考えるのです。

ここでは、1 を選択してみましょう。C のカードは 1 である、と仮定します。すると、推論テーブルはいかのようになります。

C
[ 1:C, 2:O, 3:A, 4:B, 5:O, 6:O, 7:O ]

この推論テーブルは、まだ答えの確定条件を満たしていません。次の推論に進みます。B の推論について想像してみましょう。

推論対象プレイヤー B（C の想像）

プレイヤー C が想像する、プレイヤー B の推論テーブルはどうなっているでしょうか。

今、C のカードは 1 であると仮定しています。そして、B からは B 自身のカードは見えません。推論テーブルは以下のようになります。

C -> B
[ 1:C, 2:O, 3:A, 4:O, 5:O, 6:O, 7:O ]

ここで、C -> B とは C の想像する B の推論テーブルである、という意味です。

先程 C で行なったプロセスを再度やってみましょう。前の手番のプレイヤーは A=3 です。Possible なのは 2、4、5、6、7 ですが、ここでは 2 に着目します。B のカードは 2 であると仮定してみましょう。推論テーブルはこうです。

C -> B
[ 1:C, 2:B, 3:A, 4:O, 5:O, 6:O, 7:O ]

今度は、答えの確定条件を満たしています。それは「誰の」確定条件かというと、A ですね。この推論テーブルは B のものなので、前の手番のプレイヤーである A の推論に移ります。

推論対象プレイヤー A（C の 想像の B の想像）

そろそろ、ややこしくなってきたと思いませんか。私は思います。こんな難しい問題（しかし解ける）、よく考えつくなーと感心しきりです。

今回考えるのは、「「C の想像する B」の想像する A」の推論テーブルです。

C -> B -> A
[ 1:C, 2:B, 3:O, 4:O, 5:O, 6:O, 7:O ]

この条件であれば、答えの確定条件を満たしています。A=>MAX ですね。

しかし、思い出してみてください。そもそも、この節で議論を始めたときの前提は A=3, B=4, C=5 でした。A は「MAX」ではありませんし、A 自身、それを分かっています。ですから、A は最初の手番で「?」と答えます。

推論テーブルの推論が崩れました。仮定が間違っていたのです。前の推論に戻る必要があります。1 つ前の推論はこうです。

C -> B
[ 1:C, 2:B, 3:A, 4:O, 5:O, 6:O, 7:O ]

ここでの仮定 2:B が間違っていたのですね。ですから、正しい推論テーブルはこのようになります。

C -> B
[ 1:C, 2:X, 3:A, 4:O, 5:O, 6:O, 7:O ]

すると、この推論テーブルは確定条件を満たしています。B=>MAX です。

しかし、ここでも推論は正しくありません。前提は A=3, B=4, C=5 でした。B は手番で答えられず、「?」と宣言します。

仮定が崩れました。前に戻りましょう。

C
[ 1:C, 2:O, 3:A, 4:B, 5:O, 6:O, 7:O ]

この 1:C が間違っていたことになります。正しい推論テーブルはこうです。

C
[ 1:X, 2:O, 3:A, 4:B, 5:O, 6:O, 7:O ]

これで最初に戻ってきました。

やってみると分かるのですが、これも B が「?」と答えた時点で、2:X となります。ですから、C の手番が回ってきた時点での推論テーブルは以下のようになっています。

C
[ 1:X, 2:X, 3:A, 4:B, 5:O, 6:O, 7:O ]

これは、確定条件を満たしています。今度こそ、C は「MAX」と答えることが可能になります。

ということで、答えは「A=>?, B=>?, C=>MAX」でした。

再帰呼び出しによる実装

前節の考え方をすると、最初の状態から次の推論へと移ってゆく際に分岐が発生するため、データ構造としては木構造を形成します。本記事の投稿当初の方法では、推論テーブルを持つノードを木構造の形で保持する、という愚直な実装でした。しかし、@sumim 氏が示した再帰呼び出しによる方法が、よりスマートでした（木構造を構築する方法では、結局正答に至らず）。

アルゴリズムのコア部分となるメソッドを掲載します。

// 現在の順番に基づき、答えを導出する
// orderIndex: _PlayerOrder上における現在の順番
// return    : 答え
public PlayerAnswer Infer(int orderIndex)
{
    return _Infer(_PlayerName, _VisibleCards, orderIndex);
}

// 答えを導出する
// targetPlayerName: 推論対象のプレイヤーの名前
// visibleCards    : プレイヤーに見えているカード列
// orderIndex      : _PlayerOrder上における現在の順番
// return          : 答え
public PlayerAnswer _Infer(string targetPlayerName, IEnumerable<_VisibleCard> visibleCards, int limit)
{
    var memoKey = new _MemoKey(targetPlayerName, visibleCards, limit);

    // メモより取得
    if (_Memo.ContainsKey(memoKey))
    {
        return _Memo[memoKey];
    }

    // 自分のカードである可能性のあるカード列（あとで削除するためリストにする）
    var possibleCardList = _AllCards.Except(visibleCards.Select(x => x.Card))
                                    .ToList();

    var playerNames = _Order.GetPlayerNames().Select((playerName, index) => (playerName, index));

    foreach (var (playerName, index) in playerNames.Take(limit + 1))
    {
        // 前の手番が存在するなら
        if (index >= 1)
        {
            var prevIndex = index - 1;
            var prevPlayerName = _Order.GetPlayerNames().ElementAt(prevIndex);

            // possibleCardListのクローンでループ
            foreach (var p in possibleCardList.ToArray())
            {
                // 前の手番を仮定する
                var candidates = visibleCards.Concat(new[] { new _VisibleCard(targetPlayerName, p) })
                                             .Where(x => x.PlayerName != prevPlayerName)
                                             .OrderBy(x => x.PlayerName)
                                             .ToArray();
                
                // 仮定を元に答えを導出する
                var inferred = _Infer(prevPlayerName, candidates, prevIndex);

                // 答えの食い違い
                if (inferred.Value != AnswerValue.Unknown)
                {
                    possibleCardList.Remove(p);
                }
            }
        }
    }

    var answer = _GetAnswer(targetPlayerName, possibleCardList, visibleCards);
    _Memo.Add(memoKey, answer);

    return answer;
}

処理の流れはコメントの通りです。

計算量が多いため、メモ化により高速化を図っています。

出力例

最後に、カード 5 枚、プレイヤー 3 人の場合の出力例をお見せします。

順列の生成は IndianPoker.Lib.Utils に含まれています。また、各行の最後に付加された OK ですが、これはデバッグのため、宣言された答えが配られたカードと比較して正しいかどうかを出力したものです。

<A=1, B=2, C=3> A=>?, B=>?, C=>MAX : OK
<A=1, B=2, C=4> A=>?, B=>MID : OK
<A=1, B=2, C=5> A=>?, B=>MID : OK
<A=1, B=3, C=2> A=>?, B=>MAX : OK
<A=1, B=3, C=4> A=>?, B=>MID : OK
<A=1, B=3, C=5> A=>?, B=>MID : OK
<A=1, B=4, C=2> A=>?, B=>MAX : OK
<A=1, B=4, C=3> A=>?, B=>?, C=>MID : OK
<A=1, B=4, C=5> A=>MIN : OK
<A=1, B=5, C=2> A=>?, B=>MAX : OK
<A=1, B=5, C=3> A=>?, B=>?, C=>MID : OK
<A=1, B=5, C=4> A=>MIN : OK
<A=2, B=1, C=3> A=>?, B=>?, C=>MAX : OK
<A=2, B=1, C=4> A=>?, B=>?, C=>MAX : OK
<A=2, B=1, C=5> A=>MID : OK
<A=2, B=3, C=1> A=>?, B=>MAX : OK
<A=2, B=3, C=4> A=>?, B=>?, C=>MAX : OK
<A=2, B=3, C=5> A=>?, B=>MID : OK
<A=2, B=4, C=1> A=>?, B=>MAX : OK
<A=2, B=4, C=3> A=>?, B=>?, C=>MID : OK
<A=2, B=4, C=5> A=>MIN : OK
<A=2, B=5, C=1> A=>MID : OK
<A=2, B=5, C=3> A=>?, B=>?, C=>MID : OK
<A=2, B=5, C=4> A=>MIN : OK
<A=3, B=1, C=2> A=>MAX : OK
<A=3, B=1, C=4> A=>?, B=>MIN : OK
<A=3, B=1, C=5> A=>MID : OK
<A=3, B=2, C=1> A=>MAX : OK
<A=3, B=2, C=4> A=>?, B=>MIN : OK
<A=3, B=2, C=5> A=>?, B=>MIN : OK
<A=3, B=4, C=1> A=>?, B=>MAX : OK
<A=3, B=4, C=2> A=>?, B=>MAX : OK
<A=3, B=4, C=5> A=>MIN : OK
<A=3, B=5, C=1> A=>MID : OK
<A=3, B=5, C=2> A=>?, B=>MAX : OK
<A=3, B=5, C=4> A=>MIN : OK
<A=4, B=1, C=2> A=>MAX : OK
<A=4, B=1, C=3> A=>?, B=>?, C=>MID : OK
<A=4, B=1, C=5> A=>MID : OK
<A=4, B=2, C=1> A=>MAX : OK
<A=4, B=2, C=3> A=>?, B=>?, C=>MID : OK
<A=4, B=2, C=5> A=>?, B=>MIN : OK
<A=4, B=3, C=1> A=>?, B=>MID : OK
<A=4, B=3, C=2> A=>?, B=>?, C=>MIN : OK
<A=4, B=3, C=5> A=>?, B=>MIN : OK
<A=4, B=5, C=1> A=>MID : OK
<A=4, B=5, C=2> A=>?, B=>?, C=>MIN : OK
<A=4, B=5, C=3> A=>?, B=>?, C=>MIN : OK
<A=5, B=1, C=2> A=>MAX : OK
<A=5, B=1, C=3> A=>?, B=>?, C=>MID : OK
<A=5, B=1, C=4> A=>?, B=>MIN : OK
<A=5, B=2, C=1> A=>MAX : OK
<A=5, B=2, C=3> A=>?, B=>?, C=>MID : OK
<A=5, B=2, C=4> A=>?, B=>MIN : OK
<A=5, B=3, C=1> A=>?, B=>MID : OK
<A=5, B=3, C=2> A=>?, B=>MID : OK
<A=5, B=3, C=4> A=>?, B=>MIN : OK
<A=5, B=4, C=1> A=>?, B=>MID : OK
<A=5, B=4, C=2> A=>?, B=>MID : OK
<A=5, B=4, C=3> A=>?, B=>?, C=>MIN : OK

考察

コメント欄で議論となりましたが、答えが出るまでのターン数は結局求まりませんでした。Impossible の条件が複雑で追いきれませんでした。

実装したプログラムでは、前述の通りのやり方で必ず収束するため、ターン数は不要となりました。

課題

計算量が膨大なため、実行時間がかかります。

本物のインディアン・ポーカーはカード数 53 枚ですが、プレイヤー数 2 のときは答えを導けるものの、それ以上の人数では 53 枚に対応することはできませんでした。

LINQ を多用しているため、元々速度は最適化されていませんが、計算量のオーダー自体に問題があると思います。

おわりに

オブジェクト指向は大変難しいです。特に、このような難解な問題を解こうとする場合、答えが分かっていないと、確固たる設計をするのは不可能です。

しかし、オブジェクト指向はまた、このようなケースに対してアルゴリズム部分をブラックボックス化する力も持っています。ですから、最初に設計を決めることは可能で、しかし作り込んでゆくうちに設計が変化してゆく場合がほとんどだと思います。

よく、コードを書かない SE の存在を耳にしますが、コードを書かずに設計なんてできないというのが私の考えです。

コードを書いてオブジェクト指向力を磨きましょう。私も精進します。

38
41
19

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
38
41

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?