Cマガ電脳クラブ(第106回) 楊貴妃問題

問題

88リットルの容器に水がいっぱい入っている。
これを、49リットルと18リットル入るふたつの空の容器をほかに使って、
79リットルと9リットルに分けたい (この9リットルは18リットルの容器に残す) 。
最低何回の水の移し替えが必要か。

なお、各容器には目盛りなどは付いておらず、
前述したように「いっぱいにしたときに何リットル」ということしかわかっていない。
(88, 0, 0)から(79, 0, 9)までの過程をすべて示していただきたい。

ソース

using System;
using System.Collections.Generic;

class Program
{
    const int LimitA = 88;
    const int LimitB = 49;
    const int LimitC = 18;

    struct JyoutaiDef
    {
        internal int Level;
        internal int CurrA;
        internal int CurrB;
        internal int CurrC;
        internal List<string> Log;
    }

    static void Main()
    {
        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.Level = 0;
        WillPush.CurrA = LimitA;
        WillPush.CurrB = WillPush.CurrC = 0;
        WillPush.Log = new List<string>();

        string wkStr1 = ABCToStr(WillPush.CurrA, WillPush.CurrB, WillPush.CurrC);
        WillPush.Log.Add(wkStr1);
        stk.Push(WillPush);

        var MinTesuuDict = new Dictionary<string, int>();
        MinTesuuDict.Add(wkStr1, 0);

        int AnswerLevel = int.MaxValue;
        var AnswerLog = new List<string>();

        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();

            //下限値枝切り
            if (Popped.Level > AnswerLevel) continue;

            //クリア判定
            if (Popped.CurrA == 79 && Popped.CurrC == 9) {
                AnswerLevel = Popped.Level;
                Console.WriteLine("レベル{0}の解候補を発見", AnswerLevel);
                AnswerLog = Popped.Log;
                continue;
            }

            Action CopyAct = () =>
            {
                WillPush.CurrA = Popped.CurrA;
                WillPush.CurrB = Popped.CurrB;
                WillPush.CurrC = Popped.CurrC;
            };

            Action PushSyori = () =>
            {
                WillPush.Level = Popped.Level + 1;

                string wkStr2 = ABCToStr(WillPush.CurrA, WillPush.CurrB, WillPush.CurrC);
                int MinTesuu;
                if (MinTesuuDict.TryGetValue(wkStr2, out MinTesuu)) {
                    if (MinTesuu < WillPush.Level) return;
                }
                MinTesuuDict[wkStr2] = WillPush.Level;

                WillPush.Log = new List<string>(Popped.Log);
                WillPush.Log.Add(wkStr2);
                stk.Push(WillPush);
            };

            CopyAct();
            if (MoveWater(ref WillPush.CurrA, ref WillPush.CurrB, LimitB)) {
                PushSyori();
            }
            CopyAct();
            if (MoveWater(ref WillPush.CurrA, ref WillPush.CurrC, LimitC)) {
                PushSyori();
            }
            CopyAct();
            if (MoveWater(ref WillPush.CurrB, ref WillPush.CurrA, LimitA)) {
                PushSyori();
            }
            CopyAct();
            if (MoveWater(ref WillPush.CurrB, ref WillPush.CurrC, LimitC)) {
                PushSyori();
            }
            CopyAct();
            if (MoveWater(ref WillPush.CurrC, ref WillPush.CurrA, LimitA)) {
                PushSyori();
            }
            CopyAct();
            if (MoveWater(ref WillPush.CurrC, ref WillPush.CurrB, LimitB)) {
                PushSyori();
            }
        }
        Console.WriteLine("最低{0}回の水の移し替えが必要で、手順は下記です", AnswerLevel);
        AnswerLog.ForEach(X => Console.WriteLine(X));
    }

    //A,B,CをString型で表現
    static string ABCToStr(int pA, int pB, int pC)
    {
        return string.Format("{0},{1},{2}", pA, pB, pC);
    }

    //FromからToに水を移す
    static bool MoveWater(ref int pFrom, ref int pTo, int pToLimit)
    {
        int MoveWater = Math.Min(pFrom, pToLimit - pTo);
        if (MoveWater == 0) return false;

        pFrom -= MoveWater;
        pTo += MoveWater;
        return true;
    }
}

実行結果

レベル67の解候補を発見
レベル66の解候補を発見
最低66回の水の移し替えが必要で、手順は下記です
88,0,0
39,49,0
39,31,18
57,31,0
57,13,18
75,13,0
75,0,13
26,49,13
26,44,18
44,44,0
44,26,18
62,26,0
62,8,18
80,8,0
80,0,8
31,49,8
31,39,18
49,39,0
49,21,18
67,21,0
67,3,18
85,3,0
85,0,3
36,49,3
36,34,18
54,34,0
54,16,18
72,16,0
72,0,16
23,49,16
23,47,18
41,47,0
41,29,18
59,29,0
59,11,18
77,11,0
77,0,11
28,49,11
28,42,18
46,42,0
46,24,18
64,24,0
64,6,18
82,6,0
82,0,6
33,49,6
33,37,18
51,37,0
51,19,18
69,19,0
69,1,18
87,1,0
87,0,1
38,49,1
38,32,18
56,32,0
56,14,18
74,14,0
74,0,14
25,49,14
25,45,18
43,45,0
43,27,18
61,27,0
61,9,18
79,9,0
79,0,9

解説

プログラマ脳を鍛える数学パズル Q44 グラスの水を半分にをベースにしてます。

メモ化探索で解いてます。