Cマガ電脳クラブ(第064回) 1996

問題

Fig.1は1996年にちなんだ何の変哲もない式に見える。
ところがこの式、本誌を逆さまに見ても成り立っているのだ！

3桁までの数を6個も使っているのが少々野暮ったいので、
2桁までの数を5個以内、演算記号は×と＋だけとして、
逆からも成り立つ式をすべて見つけてほしい。

積や和の順序を入れ換えただけのものは同じとみなすことにする。もちろん右辺は1996だ。

また、3や80などの数は使えない。3は逆から読めないし、80は08という変な表記になるからだ。

Fig.1 1996

ソース

using System;
using System.Collections.Generic;

class Program
{
    struct JyoutaiDef
    {
        internal int NumCnt;
        internal string Expression;
        internal int CalcResult;
        internal bool IsAscAll; //各項の値が昇順が昇順で、掛け算も昇順か？
        internal bool IsAscOmitLast; //各項の値(最後の項以外)が昇順が昇順で、掛け算も昇順か？
        internal bool IsSyokouOver; //最初の項が1996/2以下か？
        internal bool Is2kouOver; /*最初の項+2項目 < 1996の場合
                                    最初の項+2項目*2 >1996 でないか？*/
        internal bool MustKakezanIsOK; //掛け算を行った後の、単項の加算がないか？
    }

    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;

        //各項の候補になる2桁までの数の配列
        int[] KouhoNumArr = DeriveKouhoNumArr();

        WillPush.Expression = ""; WillPush.CalcResult = 0;

        WillPush.NumCnt = 1;
        WillPush.IsAscAll = WillPush.IsAscOmitLast = true;
        WillPush.IsSyokouOver = false;
        WillPush.Is2kouOver = false;
        WillPush.MustKakezanIsOK = true;
        foreach (int EachNum in KouhoNumArr) {
            WillPush.Expression = EachNum.ToString();
            WillPush.CalcResult = EachNum;
            stk.Push(WillPush);
        }

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

            if (++WillOutInfoCnt == 1000000) {
                WillOutInfoCnt = 0;
                Console.WriteLine("経過時間={0}。{1}を検証中", sw.Elapsed, Popped.Expression);
            }

            if (IsAnswer(Popped)) {
                AnswerCnt++;
                Console.WriteLine("解{0}を発見。{1}=1996", AnswerCnt, Popped.Expression);
                Console.WriteLine("逆さまに見たら。9661={0}", DeriveRevExpression(Popped.Expression));
                continue;
            }

            //数値の数で枝切り
            if (Popped.NumCnt == 5) {
                continue;
            }

            WillPush.NumCnt = Popped.NumCnt + 1;

            Action<string> PushSyori = (pExpression) =>
            {
                WillPush.Expression = pExpression;
                CheckExpression(ref WillPush);

                if (IsEdakiri(WillPush) == false)
                    stk.Push(WillPush);
            };

            foreach (int EachNum in KouhoNumArr) {
                if (Popped.NumCnt != 4) { //4個目の演算子は必ず*
                    //+をつなぐパターン
                    PushSyori(Popped.Expression + "+" + EachNum.ToString());
                }

                //*をつなぐパターン
                PushSyori(Popped.Expression + "*" + EachNum.ToString());
            }
        }
    }

    //各項の候補になる2桁までの数値の配列を返す
    static int[] DeriveKouhoNumArr()
    {
        var KouhoNumList = new List<int>();

        int[] KouhoNumArr = { 1, 2, 5, 6, 8, 9 };

        foreach (int EachNum1 in KouhoNumArr) {
            KouhoNumList.Add(EachNum1);
            foreach (int EachNum2 in KouhoNumArr) {
                KouhoNumList.Add(EachNum1 * 10 + EachNum2);
            }
        }
        return KouhoNumList.ToArray();
    }

    //枝切り判定を行う
    static bool IsEdakiri(JyoutaiDef pWillPush)
    {
        if (pWillPush.IsAscOmitLast == false) return true;
        if (pWillPush.CalcResult > 1996) return true;
        if (pWillPush.IsSyokouOver) return true;
        if (pWillPush.Is2kouOver) return true;

        return false;
    }

    //解に到達したかを返す
    static bool IsAnswer(JyoutaiDef pWillPush)
    {
        //1996になる式は、必ず3つの数値が必要
        //1996を素因数分解すると 2*2*409のため、2桁の数同士の掛け算では作成できないから
        if (pWillPush.NumCnt <= 2) return false;

        //1996になる式には、必ず+と*がある
        if (pWillPush.Expression.Contains("+") == false) return false;
        if (pWillPush.Expression.Contains("*") == false) return false;

        if (pWillPush.IsAscAll == false) return false;
        if (pWillPush.MustKakezanIsOK == false) return false;

        //左辺の計算式の計算結果が1996であること
        if (pWillPush.CalcResult != 1996) return false;

        //逆さまに見た左辺の計算結果が9661であること
        string RevExpression = DeriveRevExpression(pWillPush.Expression);
        if (CalcExpression(RevExpression) != 9661) return false;

        return true;
    }

    //+でsplitしてから*でsplitして、数式をチェックして状態Defを更新する
    static void CheckExpression(ref JyoutaiDef pWillPush)
    {
        pWillPush.CalcResult = 0;
        pWillPush.IsAscAll = pWillPush.IsAscOmitLast = true;
        pWillPush.IsSyokouOver = false;
        pWillPush.Is2kouOver = false;
        pWillPush.MustKakezanIsOK = true;

        var KouValList = new List<int>();

        bool AppearKakezan = false;
        string[] wkArr1 = pWillPush.Expression.Split(new char[] { '+' });
        foreach (string EachStr1 in wkArr1) {
            string[] wkArr2 = EachStr1.Split(new char[] { '*' });

            //掛け算を行った後の、単項の加算がないこと
            if (wkArr2.Length >= 2) AppearKakezan = true;
            if (AppearKakezan && wkArr2.Length == 1) {
                pWillPush.MustKakezanIsOK = false;
            }

            int ProdVal = 1;
            int IntValCurr = 0, IntValPrev;
            for (int I = 0; I <= wkArr2.GetUpperBound(0); I++) {
                IntValPrev = IntValCurr;
                IntValCurr = int.Parse(wkArr2[I]);

                if (I >= 1) {
                    //掛け算の各値が昇順であること
                    if (IntValCurr < IntValPrev) {
                        pWillPush.IsAscAll = false;
                        pWillPush.IsAscOmitLast = false;
                        return; //処理終了
                    }
                }
                ProdVal *= IntValCurr;
            }
            KouValList.Add(ProdVal);
            //最初の項は半分以下でなければならない
            if (KouValList.Count == 1 && KouValList[0] > 1996 / 2) {
                pWillPush.IsSyokouOver = true;
                return; //処理終了
            }
            //項が2つの場合
            if (KouValList.Count == 2) {
                if (KouValList[0] + KouValList[1] < 1996) {
                    if (KouValList[0] + KouValList[1] * 2 > 1996) {
                        pWillPush.Is2kouOver = true;
                        return; //処理終了
                    }
                }
            }
        }
        for (int I = 0; I <= KouValList.Count - 1; I++) {
            if (I >= 1 && KouValList[I] < KouValList[I - 1])
                pWillPush.IsAscAll = false;
            if (I >= 1 && I < KouValList.Count - 1 && KouValList[I] < KouValList[I - 1])
                pWillPush.IsAscOmitLast = false;
            pWillPush.CalcResult += KouValList[I];
        }
    }

    //逆さまに見た文字列を返す
    static string DeriveRevExpression(string pExpression)
    {
        var sb = new System.Text.StringBuilder();
        for (int I = pExpression.Length - 1; I >= 0; I--) {
            if (pExpression[I] == '9') sb.Append('6');
            else if (pExpression[I] == '6') sb.Append('9');
            else sb.Append(pExpression[I]);
        }
        return sb.ToString();
    }

    //文字列の計算結果を返す
    static int CalcExpression(string pExpression)
    {
        int WillReturn = 0;

        string[] wkArr1 = pExpression.ToString().Split(new char[] { '+' });
        foreach (string EachStr1 in wkArr1) {
            string[] wkArr2 = EachStr1.Split(new char[] { '*' });

            int ProdVal = 1;
            Array.ForEach(wkArr2, X => ProdVal *= int.Parse(X));
            WillReturn += ProdVal;
        }
        return WillReturn;
    }
}

実行結果

省略
経過時間=00:04:44.7141471。2*5+99+12*68を検証中
経過時間=00:05:06.2688903。19+29+59+59を検証中
経過時間=00:05:30.2862645。16+56+68+88を検証中
解1を発見。16+12*22+26*66=1996
逆さまに見たら。9661=99*92+22*21+91
経過時間=00:05:54.3804522。12+9*19+11*18を検証中
経過時間=00:06:19.5641152。11+22*22+9*19を検証中
経過時間=00:06:42.0344211。1*29+91+18*66を検証中

解説

使える数字は、125689だけとなりますので、
これらの数字を組み合わせた2桁までの数の配列を事前に作成してます。