Project Euler : Problem 32 『Pandigital products』

ますだ製パン / Sig.

問題

適合する式を探す

　1～9までの値をまんべんなく使うということは、桁の制限があるということ。
例えば、1桁×1桁の場合、答えは9桁引く2桁(1桁+1桁)の7桁ないといけない。
だけど、1桁×1桁はどうコロコロしても7桁にはならない。
桁上がりしてもせいぜい2桁。
よって、1桁×1桁 = 7桁は成立しない。

　今A桁×B桁=C桁として
1桁×1桁からだーっと調べた結果、

A桁	B桁	C桁	桁の総和
1	1	1	3
1	2	2	5
1	3	3	7
1	4	4	9
1	5	5	11
1	6	6	13
1	7	7	15
2	2	3	7
2	3	4	9
2	4	5	11
2	5	6	13
2	6	7	15
3	3	5	11
3	4	6	13
3	5	7	15
4	4	7	15

　以上の結果から
　1桁×4桁=4桁
　2桁×3桁=4桁
の2つだけが使える数式だとわかった(桁上がりは全滅した)

　よって、それぞれをしらみつぶしに調べて重複してる解を削除したのち総和を取る。

コード

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

namespace Problem32
{
    class Program
    {
        //使う数字
        int[] Numbers = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

        static void Main(string[] args)
        {
            Debug.WriteLine(PandigitalProducts());
        }

        static Int64 PandigitalProducts()
        {
            List<int> answers = new List<int>();

            CreateFormula(1, 9, 1234, 9876, answers);
            CreateFormula(12, 98, 123, 987, answers);

            //重複を削除して総和を取る
            return answers.Distinct().Sum();
        }

        //数式の作成
        static void CreateFormula(int amin, int amax, int bmin, int bmax, List<int> ans)
        {
            StringBuilder sb = new StringBuilder();

            for (int a = amin; a <= amax; a++)
            {
                for (int b = bmin; b <= bmax; b++)
                {
                    int c = a * b;

                    if (c.ToString().Length == 4)
                    {
                        sb.Append(a.ToString());
                        sb.Append(b.ToString());
                        sb.Append(c.ToString());

                        if (CheckNumbers(sb.ToString().ToArray()) == true)
                        {
                            Debug.WriteLine(a + "*" + b + "=" + c);
                            ans.Add(c);
                        }
                    }

                    sb.Clear();
                }
            }
        }

        //式のチェック
        static bool CheckNumbers(char[] n)
        {
            Array.Sort(n);

            for (int i = 1; i <= 9; i++)
            {
                if (n[i - 1] - 48 != i) return false;
            }

            return true;
        }
    }
}