C#で数学パズル - LINQで組み合わせを列挙して小町算を解く

小町算とは

「小町算(こまちざん)」とは、1～9までの数字と＋、－、×、÷ の記号を使って、計算結果が100になる式を作る数学パズルです。江戸時代にはすでに知られていたということで、歴史あるパズルです。

例えば、

123 + 4 - 5 + 67 - 89 = 100

はその正解の一つです。

このパズルの変形として、＋、－だけ使うものとか、（）を認めるものとか、色々あるようです。

ここでは、＋、－だけを使って100になるような式を求めています。

どうやって解くのか　

解き方はいろいろあると思いますが、１□２□３□４□５□６□７□８□９の四角の中に、＋、－、空文字を入れてゆき、その計算結果が100になるものを求めという方法を採用します。

例えば、四角の中に、順に　"", "", "+", "-", "+", "", "-", "" を入れていけば、次のような式が出来上がります。

123+4-5+67-89

この式が、100になるかを確かめれば良いことになります。これをすべてのパターンで調べるわけですね。

LINQで組み合わせを列挙する

「四角の中に、＋、－、空文字を入れる」というのは、実は、組合せの一種です。
この組合せを求めるのに再帰処理を使う方法もありますが、今回は、LINQのクエリ式で組合せを求めています。

例えば、

var nums = Enumerable.Range(1, 2);
var q = from i in nums
        from j in nums
        from k in nums
        select new { i, j, k };
foreach (var x in q) {
    Console.WriteLine("{0} {1} {2}", x.i, x.j, x.k);
}

普段クエリ形式のLINQって書かないのですが、これは、クエリ式使ったほうがすっきりと簡単に書けますね。

上のコードを実行すると、

1 1 1
1 1 2
1 2 1
1 2 2
2 1 1
2 1 2
2 2 1
2 2 2

という結果を得られます。このように個数が事前に分かっている場合は、LINQのfromを複数使ったクエリ式を使うととても簡単です。LINQすごいです。

つまり、

string[] operators = { "", "+", "-" };

という配列に対し、

    var q = from c1 in operators
            from c2 in operators
            from c3 in operators
            from c4 in operators
            from c5 in operators
            from c6 in operators
            from c7 in operators
            from c8 in operators
    select new { c1, c2, c3, c4, c5, c6, c7, c8 };

とすれば、１□２□３□４□５□６□７□８□９の四角の中に入れる組合せを求めることが出来るというわけです。
そして、以下のコードで、計算式としても文字列を組み立てます。

string exp = string.Format("1{0}2{1}3{2}4{3}5{4}6{5}7{6}8{7}9",
                      x.c1, x.c2, x.c3, x.c4, x.c5, x.c6, x.c7, x.c8);

これで、"1234+5-678-9" のような文字列が出来上がります。

この計算式をコンピュータに計算させれば良いわけです。この計算をするのに、C#:逆ポーランド記法を利用した数式の計算とか C#:Roslynを使って数式を計算するクラスを作成してみたで示した、Expressionクラスを使います。

出来上がったソースコード

   class Program {
        static void Main(string[] args) {
            KomachiSolver sol = new KomachiSolver();
            int n = sol.Solve();
            Console.WriteLine("{0}個の解が見つかりました", n);
            Console.ReadLine();
        }
    }

    class KomachiSolver {
        private string[] operators = { "", "+", "-" };
        public int Solve() {
            var q = from c1 in operators
                    from c2 in operators
                    from c3 in operators
                    from c4 in operators
                    from c5 in operators
                    from c6 in operators
                    from c7 in operators
                    from c8 in operators
                    select new { c1, c2, c3, c4, c5, c6, c7, c8 };
            int count = 0;
            foreach (var x in q) {
                string exp = string.Format("1{0}2{1}3{2}4{3}5{4}6{5}7{6}8{7}9",
                    x.c1, x.c2, x.c3, x.c4, x.c5, x.c6, x.c7, x.c8);
                var r = (int)Expression.Calculate(exp);
                if (r == 100) {
                    Console.WriteLine(exp);
                    count++;
                }
            }
            return count;
        }
    }

実行結果

123+45-67+8-9
123+4-5+67-89
123-45-67+89
123-4-5-6-7+8-9
12+3+4+5-6-7+89
12+3-4+5+67+8+9
12-3-4+5-6+7+89
1+23-4+56+7+8+9
1+23-4+5+6+78-9
1+2+34-5+67-8+9
1+2+3-4+5+6+78+9
11個の解が見つかりました

×、÷ も含めた小町算を解くには

×、÷ も含めた小町算を解くには、割り算で、切り捨てにならないように注意する必要がありますね。

こことか

    private string[] operators = { "", "+", "-" };

こことか

    string exp = string.Format("1{0}2{1}3{2}4{3}5{4}6{5}7{6}8{7}9",
        x.c1, x.c2, x.c3, x.c4, x.c5, x.c6, x.c7, x.c8);
    var r = (int)Expression.Calculate(exp);

に少し手を加えれば、たぶんできると思います。

Expressionクラスのコード

いちおう、C#:Roslynを使って数式を計算するクラスを作成してみたで示した、Expressionクラスのコードも掲載しておきます。

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Loader;
using Microsoft.CodeAnalysis;
using Microsoft.CodeAnalysis.CSharp;
using Microsoft.CodeAnalysis.Emit;

...

 public class Expression {

    private const string _sourceCode = @"
        using System;
        namespace Gushwell {{
            public class ExpressionCalculator {{
                public object Calculate() {{
                    return {0};
                }}
            }}
        }}";


    public static object Calculate(string exp) {
        var sourceCode = CreateSourceCode(exp);
        var compilation = CreateCompilation(sourceCode);
        return RunCode(compilation);
    }


    private static object RunCode(CSharpCompilation compilation) {
        using (var ms = new MemoryStream()) {
            EmitResult result = compilation.Emit(ms);                

            if (result.Success) {
                ms.Seek(0, SeekOrigin.Begin);
                var assembly = AssemblyLoadContext.Default.LoadFromStream(ms);
                var instance = assembly.CreateInstance("Gushwell.ExpressionCalculator");
                var type = assembly.GetType("Gushwell.ExpressionCalculator");
                var method = type.GetMember("Calculate").First() as MethodInfo;
                var ans = method.Invoke(instance, null);
                return ans;
            } else {
                IEnumerable<Diagnostic> failures = result.Diagnostics.Where(diagnostic =>
                    diagnostic.IsWarningAsError || diagnostic.Severity == DiagnosticSeverity.Error);
                string message = "";
                foreach (var diagnostic in failures) {
                    message += $"\t{diagnostic.Id}: {diagnostic.GetMessage()}";
                }
                throw new InvalidOperationException(message);
            }
        }
    }

    private static CSharpCompilation CreateCompilation(string sourceCode) {
        var syntaxTree = CSharpSyntaxTree.ParseText(sourceCode);

        string assemblyName = Path.GetRandomFileName();
        var references = new MetadataReference[] {
            MetadataReference.CreateFromFile(typeof(object).GetTypeInfo().Assembly.Location)
        };
        var compilation = CSharpCompilation.Create(
            assemblyName,
            syntaxTrees: new[] { syntaxTree },
            references: references,
            options: new CSharpCompilationOptions(OutputKind.DynamicallyLinkedLibrary));
        return compilation;
    }

    private static string CreateSourceCode(string exp) {
        return string.Format(_sourceCode, exp);
    }
}

---

この記事は、Gushwell's C# Programming Pageで公開したものをに大幅に加筆・修正したものです。