Coding4Fun - 小三數學題

在同事的 LINE 群組看到這個據說是小三的趣味數學題(是國小三年級啦，有人是衝著狐狸精才點進來看的嗎?)。

請在下列方格內填入 1-9 的數字以滿足等式：

應該可以用相乘、相加不可超過百位數的限制先過濾掉一些組合再嘗試排列求解，BUT...

小孩子才用紙筆，我偏要用 Coding

早上晨跑腦袋閒著開始解題，這個小題目跑遞迴可輕鬆解決，跑著跑著演算法成形，回家連澡都沒洗，急著把程式寫出來，花十分鐘寫好第一個版本：

using System;

namespace MathGame
{
    public class Attacker
    {
        protected bool[] used = new bool[11];
        protected byte[] ans = new byte[11];
        protected bool printResult = true;

        public void Fire(bool print = true)
        {
            printResult = print;
            Explore(1);
        }

        public virtual void Explore(int pos)
        {
            if (pos == 10)
            {
                if (Check() && printResult)
                    PrintAnswer();
                return;
            }
            for (byte i = 1; i < 10; i++)
            {
                if (used[i]) continue;
                used[i] = true;
                ans[pos] = i;
                Explore(pos + 1);
                used[i] = false;
            }
        }

        public bool Check()
        {
            if ((ans[1] * 10 + ans[2]) * ans[3] != ans[4] * 10 + ans[5])
                return false;
            if (ans[4] * 10 + ans[5] + ans[6] * 10 + ans[7] != ans[8] * 10 + ans[9])
                return false;
            return true;
        }

        public void PrintAnswer()
        {
            Console.WriteLine($@"
  {ans[1]} {ans[2]}
x   {ans[3]}
-----
  {ans[4]} {ans[5]}
+ {ans[6]} {ans[7]}
-----
  {ans[8]} {ans[9]}");
        }
    }
}

薑! 薑! 薑! 薑~~ 答案出爐：

想了一下，有個地方可以改善，排列組合到第五個數字其實就該可先檢查上方的乘法等式，若不相等後面就不用試了，小調一下可省下大量無謂計算，於是我再改了第二個版本：

using System;

namespace MathGame
{
    public class AttackerV2 : Attacker
    {
        public override void Explore(int pos)
        {
            if (pos == 10)
            {
                if (ChkAdd() && printResult)
                    PrintAnswer();
                return;
            }
            for (byte i = 1; i < 10; i++)
            {
                if (used[i]) continue;
                used[i] = true;
                ans[pos] = i;
                if (pos != 5 || ChkMultiple())
                {
                    Explore(pos + 1);
                }
                used[i] = false;
            }
        }
        public bool ChkMultiple()
        {
            if ((ans[1] * 10 + ans[2]) * ans[3] != ans[4] * 10 + ans[5])
                return false;
            return true;

        }
        public bool ChkAdd() 
        { 
            if (ans[4] * 10 + ans[5] + ans[6] * 10 + ans[7] != ans[8] * 10 + ans[9])
                return false;
            return true;
        }
    }
}

既然有改良就該做比較，用 BenchmarkDotNet 測一下：

using BenchmarkDotNet.Attributes;

namespace MathGame
{
    public class Tester
    {
        [Benchmark]
        public void TestAttacker()
        {
            var attacker = new Attacker();
            attacker.Fire(false);
        }

        [Benchmark]
        public void TestAttackerV2()
        {
            var attacker = new AttackerV2();
            attacker.Fire(false);
        }
    }
}

實測結果，用 Core i5 暴力攻擊解這個小三數學問題是大砲打小鳥無誤，無腦攻擊版只花了 15.94ms，而簡單改良省去部分無效計算後更是再提升到 0.26ms：

演算法是否還有優化空間？當然有，但花時間改善耗時 0.26ms 的計算投資報酬率實在太低，就此打住。

2020-05-09 更新：原本程式有 Bug，只算到第八個數字就當成結束，故組合中會出現 0 而 1-9 缺一個。天大的 Bug! 謝謝讀者 wilber, 吳 提醒。(掩面)

For fun, I write a C# recursive function to solve a math question of primary school.