2015年04月15日

C#でトランプの和と積のパズルを解く

   このエントリーをはてなブックマークに追加 Clip to Evernote
どう書く?orgに感謝を込めて」シリーズ その85

■問題 (出題者:光成さん)
ここにトランプが一組あります.
司会者がそこから二枚抜いて,その積をAさんに,その和をBさんに教えました.

#トランプにジョーカーはなく、1〜13までの数字が書かれたカードであると考えて構いません.
#たとえば,二枚のトランプの数字が2と5なら,Aさんには10,Bさんには7を教えます.
#二つの数は同じかもしれません.

司会者がAさん,Bさんに二つの数字が分かるかと質問しました.
Aさん「(この情報だけでは)分かりません」
Bさん「私も分かりません.ただ,Aさんが『分かりません』というのは分かっていました」
それを聞いたAさん「それなら,分かりました」
それを聞いたBさん「それなら,私も分かりました」
元の二つの数はなんだったのでしょうか.

この「2つの数」を求めるプログラムを作ってください。解が複数個ある場合はすべて求めてください。
参考URL
http://www12.ocn.ne.jp/~kumo/trump.html


この問題を解くにあたり、帰納的に良い方法がないものかと具体的な例で考えはじめたら、 僕の頭は完全にオーバーフローを起こし、思考停止に陥りました(笑)
なので、具体例は考えるのはあきらめて、あくまでもこの問題にある質問を素直にコードに落とすことにしました。
同じ質問(メソッド)が同じ値(引数)に対して何回も呼ばれることになるので、効率が悪いですが、1から13までのペアならば、 瞬時に答えが表示されます。
GetAllPairメソッドの引数の 13 を 100とかにすれば、1から100のペアで答えを見つけることができます。

実行結果は、あえて載せないでおこうと思います。
それと、参考URLには別の方法が載っているようですので興味があるかたは、そちらも参考にしてみてください。

using System;
using System.Collections.Generic;
using System.Linq;

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            var sol = new Solver();
            var q = sol.Execute();
            foreach (var a in q)
                Console.WriteLine(a);
            Console.ReadLine();
        }
    }

    class Solver {
        private IList<Pair> allpair = GetAllPair(13);

        public IEnumerable<Pair> Execute() {
          foreach (var p in allpair) {
                if (ADidYouFind(p.X * p.Y) &&
                    BDidYouFind(p.X + p.Y) &&
                    AThenDidYouFind(p.X * p.Y) &&
                    BThenDidYouFind(p.X + p.Y))
                    yield return p;
            }
        }

        // Aさん「(この情報だけでは)分かりません」 と答えるか
        private bool ADidYouFind(int n) {
            var pairs = allpair.Where(t => t.Product == n).ToList();
            return (pairs.Count() >= 2);
        }

        // Bさん「私も分かりません.ただ,Aさんが『分かりません』というのは分かっていました」と答えるか
        private bool BDidYouFind(int n) {
            var pairs = allpair.Where(t => t.Sum == n).ToList();
            if (pairs.Count() == 1)
                return false;
            return (pairs.All(t => ADidYouFind(t.Product) == true)); // Aはすべてが分からない
        }

        // それを聞いたAさん「それなら,分かりました」と答えるか
        private bool AThenDidYouFind(int n) {
            var pairs = allpair.Where(t => t.Product == n).ToList();
            return (pairs.Count(t => BDidYouFind(t.Sum) == true) == 1);
        }

        // それを聞いたBさん「それなら,私も分かりました」と答えるか
        private bool BThenDidYouFind(int n) {
            var pairs = allpair.Where(t => t.Sum == n).ToList();
            return (pairs.Count(t => AThenDidYouFind(t.Product) == true) == 1);
        }

        private static IList<Pair> GetAllPair(int n) {
            var cards = Enumerable.Range(1, n);
            // すべてのカードの組み合わせ
            var q = from c1 in cards
                    from c2 in cards
                    where c1 <= c2
                    select new Pair(c1, c2);
            return q.ToList();
        }
    }

    class Pair {
        public int X { get; set; }
        public int Y { get; set; }
        public override string ToString() {
            return string.Format("({0}, {1})", X, Y);
        }

        public Pair(int x, int y) {
            this.X = x;
            this.Y = y;
        }
        public int Product {
            get { return X * Y; }
        }
        public int Sum {
            get { return X + Y; }
        }
    }
}



 

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/gushwell/52412629