8-28 油分け算4 平等な乾杯

問題

ある日、3人の友人同士がパーティーに集まった。
彼女らの前にはちょうど12パイントのワインが入った容器があり、
これを正確に4パイントずつ3等分したいと考えている。

しかし、あいにく彼女らは5パイントと3パイント入りのジョッキしか持ち合わせていない。

全員が平等に4パイントずつ飲むにはどうすればよいか。

平等な乾杯 : クイズ＆パズルの部屋「Quizzical Days.」

ソース

using System;
using System.Collections.Generic;

class Program
{
    struct JyoutaiDef
    {
        internal int Youki12;
        internal int Youki05;
        internal int Youki03;
        internal int[] NondaRyouArr;
        internal List<string> Log;
    }

    static void Main()
    {
        var que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.Youki12 = 12;
        WillEnqueue.Youki05 = WillEnqueue.Youki03 = 0;
        WillEnqueue.NondaRyouArr = new int[3];
        WillEnqueue.Log = new List<string>();
        WillEnqueue.Log.Add(MakeOneLog(12, 0, 0, WillEnqueue.NondaRyouArr));
        que.Enqueue(WillEnqueue);

        int MaxLevel = int.MaxValue;
        int AnswerCnt = 0;
        while (que.Count > 0) {
            JyoutaiDef Dequeued = que.Dequeue();
            if (MaxLevel < Dequeued.Log.Count) continue;

            if (Array.TrueForAll(Dequeued.NondaRyouArr, X => X == 4)) {
                Console.WriteLine("解{0}を発見しました。", ++AnswerCnt);
                Dequeued.Log.ForEach(X => Console.WriteLine(X));
                if (MaxLevel > Dequeued.Log.Count)
                    MaxLevel = Dequeued.Log.Count;
                continue;
            }

            Action<int, int, int, int[]> Enq1 = (pYouki12, pYouki05, pYouki03, pNondaRyouArr) =>
            {
                WillEnqueue.Youki12 = pYouki12;
                WillEnqueue.Youki05 = pYouki05;
                WillEnqueue.Youki03 = pYouki03;
                WillEnqueue.NondaRyouArr = pNondaRyouArr;

                string NewLog = MakeOneLog(pYouki12, pYouki05, pYouki03, pNondaRyouArr);
                if (Dequeued.Log.Contains(NewLog)) return;

                WillEnqueue.Log = new List<string>(Dequeued.Log);
                WillEnqueue.Log.Add(NewLog);
                que.Enqueue(WillEnqueue);
            };

            Action<int, int, int> Enq2 = (pYouki12, pYouki05, pYouki03) =>
            {
                Enq1(pYouki12, pYouki05, pYouki03, Dequeued.NondaRyouArr);
            };

            if (Dequeued.Youki12 > 0) {
                if (Dequeued.Youki05 < 5) {
                    int Aki = 5 - Dequeued.Youki05;
                    int Fill = Math.Min(Aki, Dequeued.Youki12);
                    Enq2(Dequeued.Youki12 - Fill, Dequeued.Youki05 + Fill, Dequeued.Youki03);
                }
                if (Dequeued.Youki03 < 3) {
                    int Aki = 3 - Dequeued.Youki03;
                    int Fill = Math.Min(Aki, Dequeued.Youki12);
                    Enq2(Dequeued.Youki12 - Fill, Dequeued.Youki05, Dequeued.Youki03 + Fill);
                }
            }
            if (Dequeued.Youki05 > 0) {
                if (Dequeued.Youki12 < 12) {
                    int Aki = 12 - Dequeued.Youki12;
                    int Fill = Math.Min(Aki, Dequeued.Youki05);
                    Enq2(Dequeued.Youki12 + Fill, Dequeued.Youki05 - Fill, Dequeued.Youki03);
                }
                if (Dequeued.Youki03 < 3) {
                    int Aki = 3 - Dequeued.Youki03;
                    int Fill = Math.Min(Aki, Dequeued.Youki05);
                    Enq2(Dequeued.Youki12, Dequeued.Youki05 - Fill, Dequeued.Youki03 + Fill);
                }
            }
            if (Dequeued.Youki03 > 0) {
                if (Dequeued.Youki12 < 12) {
                    int Aki = 12 - Dequeued.Youki12;
                    int Fill = Math.Min(Aki, Dequeued.Youki03);
                    Enq2(Dequeued.Youki12 + Fill, Dequeued.Youki05, Dequeued.Youki03 - Fill);
                }
                if (Dequeued.Youki05 < 5) {
                    int Aki = 5 - Dequeued.Youki05;
                    int Fill = Math.Min(Aki, Dequeued.Youki03);
                    Enq2(Dequeued.Youki12, Dequeued.Youki05 + Fill, Dequeued.Youki03 - Fill);
                }
            }

            List<int> NomuKouhoIndList = DeriveNomuKouhoIndList(Dequeued.NondaRyouArr);
            if (1 <= Dequeued.Youki12 && Dequeued.Youki12 <= 4) {
                foreach (int EachInd in NomuKouhoIndList) {
                    if (Dequeued.NondaRyouArr[EachInd] + Dequeued.Youki12 > 4)
                        continue;
                    int[] WillEnQueueArr = (int[])Dequeued.NondaRyouArr.Clone();
                    WillEnQueueArr[EachInd] += Dequeued.Youki12;
                    Enq1(0, Dequeued.Youki05, Dequeued.Youki03, WillEnQueueArr);
                }
            }
            if (1 <= Dequeued.Youki05 && Dequeued.Youki05 <= 4) {
                foreach (int EachInd in NomuKouhoIndList) {
                    if (Dequeued.NondaRyouArr[EachInd] + Dequeued.Youki05 > 4) continue;
                    int[] WillEnQueueArr = (int[])Dequeued.NondaRyouArr.Clone();
                    WillEnQueueArr[EachInd] += Dequeued.Youki05;
                    Enq1(Dequeued.Youki12, 0, Dequeued.Youki03, WillEnQueueArr);
                }
            }
            if (1 <= Dequeued.Youki03 && Dequeued.Youki03 <= 4) {
                foreach (int EachInd in NomuKouhoIndList) {
                    if (Dequeued.NondaRyouArr[EachInd] + Dequeued.Youki03 > 4) continue;
                    int[] WillEnQueueArr = (int[])Dequeued.NondaRyouArr.Clone();
                    WillEnQueueArr[EachInd] += Dequeued.Youki03;
                    Enq1(Dequeued.Youki12, Dequeued.Youki05, 0, WillEnQueueArr);
                }
            }
        }
    }

    static List<int> DeriveNomuKouhoIndList(int[] pNondaRyouArr)
    {
        var WillReturnList = new List<int>();
        for (int I = 0; I <= pNondaRyouArr.GetUpperBound(0); I++) {
            if (pNondaRyouArr[I] == 4) continue;
            if (I >= 1 && pNondaRyouArr[I] == pNondaRyouArr[I - 1])
                continue;

            WillReturnList.Add(I);
        }
        return WillReturnList;
    }

    static string MakeOneLog(int pYouki12, int pYouki05, int pYouki03, int[] pNondaRyouArr)
    {
        var sb = new System.Text.StringBuilder();
        sb.AppendFormat("容器12={0,2},容器5={1},容器3={2},", pYouki12, pYouki05, pYouki03);
        sb.Append("飲んだ量={");
        Array.ForEach(pNondaRyouArr, X => sb.AppendFormat("{0},", X));
        sb.Append("}");
        return sb.ToString();
    }
}

実行結果

省略
解12を発見しました。
容器12=12,容器5=0,容器3=0,飲んだ量={0,0,0,}
容器12= 7,容器5=5,容器3=0,飲んだ量={0,0,0,}
容器12= 7,容器5=2,容器3=3,飲んだ量={0,0,0,}
容器12= 7,容器5=0,容器3=3,飲んだ量={2,0,0,}
容器12= 7,容器5=3,容器3=0,飲んだ量={2,0,0,}
容器12= 4,容器5=3,容器3=3,飲んだ量={2,0,0,}
容器12= 0,容器5=3,容器3=3,飲んだ量={2,4,0,}
容器12= 0,容器5=5,容器3=1,飲んだ量={2,4,0,}
容器12= 0,容器5=5,容器3=0,飲んだ量={2,4,1,}
容器12= 0,容器5=2,容器3=3,飲んだ量={2,4,1,}
容器12= 0,容器5=2,容器3=0,飲んだ量={2,4,4,}
容器12= 0,容器5=0,容器3=0,飲んだ量={4,4,4,}

解説

Array.TrueForAllメソッドで、終了条件を満たしたかをチェックしてます。
MSDN --- Array.TrueForAll<T>メソッド

引数違いの2つのActionデリゲートで、省略引数もどきを実装してます。