[パズル]:Gushwell's Dev Notes

2015年04月15日

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

「どう書く？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; }
        }
    }
}

Posted by gushwell at 22:30 │Comments(0) │TrackBack(0)

2015年04月12日

C#で水の移し替えパズルを解く

「どう書く？orgに感謝を込めて」シリーズその84

■問題（出題者:光成さん）

A, B, Cの容器があり，それぞれ水が4L, 2L, 10L入っている．ここで次の操作を繰り返す．

(*)「A, B, Cのどれか二つの容器から水を1Lずつくみ上げ，残りの容器に移す．」
たとえばA, Bから1Lずつくみ上げて移せばA=3L, B=1L, C=12Lとなる．くみ上げる前の容器には必ず水が入っているとする．
(*)を繰り返してどれか一つの容器にのみ水がはいっている状態にする最小手数を求めよ．
可能ならA=827392L，B=65536L，C=122880Lのときも求めよ．

まず、移動を表す Moveクラスと、現在の３つの容器の状態を表す State クラスを定義します。

class State {
    public State(int[] buckets, State prev) {
        Buckets = (int[])buckets.Clone();
        PrevState = prev;
        Times = (prev == null) ? 0 : prev.Times + 1;
    }
    public int Times { get; private set; }
    public State PrevState { get; private set; }
    public int[] Buckets { get; private set; }
}

class Move {
    public byte From1 { get; set; }
    public byte From2 { get; set; }
    public byte To { get; set; }
}

次に、これを使って、愚直に幅優先の探索で解を求める BfSolver クラスを定義してみました。

class BfSolver  {
    public State Search(State state) {

        // 最初に訪問するノードをキューに入れる
        Queue<State> queue = new Queue<State>();
        queue.Enqueue(state);
        while (queue.Count != 0) {
            //キューの先頭からノード currentNode を取り出す
            State current = queue.Dequeue();
            if (IsFinish(current.Buckets)) {
                return current;
            }

            foreach (var mv in GetMoves()) {
                if (!IsOK(mv, current.Buckets))
                    continue;
                int[] next = new int[3];
                next[mv.From1] = current.Buckets[mv.From1] - 1;
                next[mv.From2] = current.Buckets[mv.From2] - 1;
                next[mv.To] = current.Buckets[mv.To] + 2;
                State newstate = new State(next, current);
                if (IsLoop(current, newstate))
                    continue;
                if (ExistsInQueue(queue, newstate))
                    continue;
                queue.Enqueue(newstate);
            }
        }
        // 見つからなかった。
        return null;
    }

    private bool IsFinish(int[] buckets) {
        return buckets.Count(n => n == 0) == 2;
    }

    private IEnumerable<Move> GetMoves() {
        yield return new Move { From1 = 0, From2 = 1, To = 2 };
        yield return new Move { From1 = 0, From2 = 2, To = 1 };
        yield return new Move { From1 = 1, From2 = 2, To = 0 };
    }
    private bool IsOK(Move mv, int[] buckets) {
        if (buckets[mv.From1] <= 0)
            return false;
        if (buckets[mv.From2] <= 0)
            return false;
        return true;
    }

    private bool ExistsInQueue(Queue<State> queue, State state) {
        return queue.Any(x => x.Buckets.SequenceEqual(state.Buckets));
    }

    private bool IsLoop(State state1, State state2) {
        if (state1 == null)
            return false;
        if (state1.Buckets.OrderBy(n => n).SequenceEqual(state2.Buckets.OrderBy(n => n)))
            return true;
        return IsLoop(state1.PrevState, state2);
    }
}

Searchメソッドの戻り値は、 Stateオブジェクトとなり、この Times プロパティを見れば、移動回数が分かります。
Stateがnull の時には、解が見つからなかったことを示しています。

今回は、回数だけを求めればいいので、その状態推移を表示するコードは書いていませんが、 Stateには、PrevStateがあるので、これを辿れば、容器のリットル数がどう変化していったのかが分かるようになっています。

しかし、このプログラムは、A=3L, B=1L, C=12L 程度ならば、問題ないですが、 A=827392L，B=65536L，C=122880Lとなると、調べる手があまりにも多すぎて、永遠に終わりそうにありません。
試しに、A=171L, B=162L, C=180L と３桁の値でやってみたら、１０分経っても終わらないので、あきらめて途中で終了させてしまいました。

そこで、コンピュータに考えさせるのではなく、もうすこし自分で考えてみました。
そうしたら、意外と単純な問題であることに気が付きました。
そのコードを以下に示します。

class SmartSolver {
    public int Calc(State state) {
        var nums = state.Buckets.OrderBy(n => n).ToArray();
        if ((nums[1] - nums[0]) % 3 == 0)
            return nums[1];
        if ((nums[2] - nums[1]) % 3 == 0)
            return nums[2];
        if ((nums[2] - nums[0]) % 3 == 0)
            return nums[2];
        return -1;
    }
}

なんと、これだけでした。これならば、A=827392L，B=65536L，C=122880Lのときも一瞬で求まります。
答えは 827392です。

ざっと説明すると、
例えば、最終的な状態が、

A=0L, B=0L, C=xL
のような状態になるのですから、そのひとつ前は、

A=1L, B=1L, C=(x-2)L

そのひとつ前は

A=2L, B=2L, C=(x-4)L

そのひとつ前は

A=3L, B=3L, C=(x-6)L or A=3L, B=0L, C=(x-3)L

つまり、最終的に 0になる AとBの、水の増減は (+1,+1) (+1,-2) (-2,+1) となるわけです。ここから、A =B か、A と B の差が３の倍数かのどちらかであることが分かります。
そして、水は１Lずつしか減らないので、どんなに頑張っても、A とBの大きい数だけ、水の移動回数が必要となります。
これらのことから、上のコードが導きだせるということになります。

これが正しいかを確認するために、最初に書いた BfSolver と SmartSolver の結果が同じになるか確認してみました。
以下が、そのコードと実行結果です。

class Program {
    static void Main(string[] args) {
        Test(4, 2, 10);
        Test(5, 2, 10);
        Test(2, 8, 11);
        Test(1, 2, 3);
        Test(12, 8, 11);
        Test(7, 16, 51);
        Test(44, 22, 15);
        Test(53, 22, 1);
        Test(8, 8, 7);
        Test(20, 20, 23);
        Console.ReadLine();
    }

    private static void Test(int n1, int n2, int n3) {
        State state = new State(new int[] { n1, n2, n3 }, null);

        var sol = new SmartSolver();
        int n = sol.Calc(state);
        Console.Write("{0}\t",n);

        BfSolver s = new BfSolver();
        State last = s.Search(state);
        if (last == null)
            Console.WriteLine(-1);
        else
            Console.WriteLine(last.Times);       
    }
}

■実行結果

途中結果を表示する機能がありませんが、原理が分かっているので、 SmartSolver に途中結果を表示させる機能をつけるのも、それほど難しくはないですね。

Posted by gushwell at 23:30 │Comments(0) │TrackBack(0)

このページの上へ▲

Microsoft MVP

Gushwell へ連絡を取る Twitter : @gushwell

記事検索

コンテンツ

C#プログラミングレッスン書庫
C#デザインパターン目次
C#でパズルを解こう
C#プログラム小品集
LINQ to Objectサンプル目次
EntityFramework 目次
LINQ to XML 目次
LINQ to SQL 番外編目次
FxCopに学ぶ番外編目次
Interactive Extensions(Ix) 目次
WPFサンプル目次
WPF Chartサンプル目次
どう書く?Org 目次
記事一覧(History View)

気ままな読書ノート
Gushwellのtwilog