C# Advent Calendar で 覆面算

この記事は、「C# Advent Calendar 2011」の22日目の記事です。

さて、勢いで申し込んだものの人様に披露するに適当なTipsもないので困りもの。
で、いろいろ悩んでいるときに、ふと気づきました。C# Advent Calendarって10文字種！

ってことは覆面算をC#で解くか、それで行こう。

C# 〇 ADVENT 〇 CALENDAR = 2011

〇に適切な演算子を入れて覆面算に仕立て上げればOK。って、プログラムを組むまでもなく、解なしですよね。
では、

C# 〇 ADVENT 〇 CALENDAR = 20111222

なら、どうだろう。可能性はあるかもしれない。というわけで、チャレンジです。
前回、小町数を作成した時はAggregateを使ったんですが、今回はneueさんの記事を参考に作ってみました。
覆面算なら、こっちのほうがわかりやすいですね。

var digit = Enumerable.Range(0, 10).Select(dg => dg.ToString()).ToList();

var parts = from c in digit
            where c != "0"
            from s in digit.Except(new[] { c })
            from a in digit.Except(new[] { c, s })
            where a != "0"
            from d in digit.Except(new[] { c, s, a })
            from v in digit.Except(new[] { c, s, a, d })
            from e in digit.Except(new[] { c, s, a, d, v })
            from n in digit.Except(new[] { c, s, a, d, v, e })
            from t in digit.Except(new[] { c, s, a, d, v, e, n })
            from l in digit.Except(new[] { c, s, a, d, v, e, n, t })
            from r in digit.Except(new[] { c, s, a, d, v, e, n, t, l })
            let cs = long.Parse(c + s)
            let advent = long.Parse(a + d + v + e + n + t)
            let calendar = long.Parse(c + a + l + e + n + d + a + r)
            select new { cs, advent, calendar };

これで、C#とADVENTとCALENDARの数値の全組み合わせが取得できます。ここから、演算子を当てはめていく作業です。
数値と演算子を並べて逆ポーランドで計算すると、（）による演算順序などを気にせずに全パターン検索できるのですが、所詮並び順固定の数値３つと演算子２つなので、個別対応しました。

まず、２数の四則演算結果をすべて返すメソッドを用意します。割算で割り切れない場合は、正しい結果を返さないけどご愛嬌。

static IEnumerable<Tuple<long, string>> Calc(long x, long y)
{
    yield return Tuple.Create(x + y, "+");
    yield return Tuple.Create(x - y, "-");
    yield return Tuple.Create(x * y, "*");
    if (y != 0)
    {
        yield return Tuple.Create(x / y, "/");
    }
}

次に、前を先に計算する場合と、後を先に計算する場合を連結して終了。
※ちょっと考えると後から計算して答えが出るパターンはないのがわかるんですが気にしない。

var result1 = from x in parts
              from y in Calc(x.cs, x.advent)
              from z in Calc(y.Item1, x.calendar)
              select new 
              {
                  Result = z.Item1, 
                  Expression = string.Format("( {0} {1} {2} ) {3} {4}", x.cs, y.Item2, x.advent, z.Item2, x.calendar) 
              };

var result2 = from x in parts
              from y in Calc(x.advent, x.calendar)
              from z in Calc(x.cs, y.Item1)
              select new 
              {
                  Result = z.Item1, 
                  Expression = string.Format("{0} {1} ( {2} {3} {4} )", x.cs, z.Item2, x.advent, y.Item2, x.calendar) 
              };

var result = result1.Concat(result2);

で、実行です。

foreach (var item in result.Where(r => r.Result == 20111222))
{
    Console.WriteLine(item);
}

残念ながら、解なし。仕方がないので、単項マイナスも許可してみます。
途中に、下記一文を挟みます。（計算量がどんどん増えていく…）

parts = from a in parts
        from i in Enumerable.Range(0, 8)
        let cs = a.cs * ((i & 1) * 2 - 1)
        let advent = a.advent * ((i & 2) - 1)
        let calendar = a.calendar * ((i & 4) / 2 - 1)
        select new { cs, advent, calendar };

やっぱり解なし。残念でなりません。
仕方がないので、他の日だったら解があったかを検証してみます。

foreach (var item in result.Where(r => r.Result >= 20111201 && r.Result <= 20111231))
{
    Console.WriteLine(item);
}

結果は以下の通り。

－ C# × ADVENT ＋ CALENDAR = 20111207
－ C# × ADVENT ＋ CALENDAR = 20111212
の2パターンは解があるようです。そっか、12/07か12/12に記事書いてたらよかったんですね（違）。

以下、ソースコード全文です。パフォーマンスを全く気にしていないので、低スペックマシンだとかなり時間がかかってしまいます。あしからず。

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

namespace ConsoleApplication
{
    class Program
    {
        static void Main(string[] args)
        {
            var digit = Enumerable.Range(0, 10).Select(dg => dg.ToString()).ToList();

            var parts = from c in digit
                        where c != "0"
                        from s in digit.Except(new[] { c })
                        from a in digit.Except(new[] { c, s })
                        where a != "0"
                        from d in digit.Except(new[] { c, s, a })
                        from v in digit.Except(new[] { c, s, a, d })
                        from e in digit.Except(new[] { c, s, a, d, v })
                        from n in digit.Except(new[] { c, s, a, d, v, e })
                        from t in digit.Except(new[] { c, s, a, d, v, e, n })
                        from l in digit.Except(new[] { c, s, a, d, v, e, n, t })
                        from r in digit.Except(new[] { c, s, a, d, v, e, n, t, l })
                        let cs = long.Parse(c + s)
                        let advent = long.Parse(a + d + v + e + n + t)
                        let calendar = long.Parse(c + a + l + e + n + d + a + r)
                        select new { cs, advent, calendar };

            parts = from a in parts
                    from i in Enumerable.Range(0, 8)
                    let cs = a.cs * ((i & 1) * 2 - 1)
                    let advent = a.advent * ((i & 2) - 1)
                    let calendar = a.calendar * ((i & 4) / 2 - 1)
                    select new { cs, advent, calendar };

            var result1 = from x in parts
                          from y in Calc(x.cs, x.advent)
                          from z in Calc(y.Item1, x.calendar)
                          select new
                          {
                              Result = z.Item1,
                              Expression = string.Format("( {0} {1} {2} ) {3} {4}", x.cs, y.Item2, x.advent, z.Item2, x.calendar)
                          };

            var result2 = from x in parts
                          from y in Calc(x.advent, x.calendar)
                          from z in Calc(x.cs, y.Item1)
                          select new
                          {
                              Result = z.Item1,
                              Expression = string.Format("{0} {1} ( {2} {3} {4} )", x.cs, z.Item2, x.advent, y.Item2, x.calendar)
                          };

            var result = result1.Concat(result2);

            foreach (var item in result.Where(r => r.Result >= 20111201 && r.Result <= 20111225))
            {
                Console.WriteLine(item);
            }

            Console.ReadLine();
        }

        static IEnumerable<Tuple<long, string>> Calc(long x, long y)
        {
            yield return Tuple.Create(x + y, "+");
            yield return Tuple.Create(x - y, "-");
            yield return Tuple.Create(x * y, "*");
            if (y != 0)
            {
                yield return Tuple.Create(x / y, "/");
            }
        }
    }
}