Linqと総当り

2010-12-28

各所でAdvent Calendarも終了し皆様お疲れさまでした。自分のよく知っている言語はもちろんですが、他の言語を見ていても非常に楽しめて良いですね、特に普段自分の書かない言語で、入門からちょっと突っ込んだものまでまとめて見れるというのは非常に良い機会でした。

そんな中で見かけたScalaによるリストモナドを使ってみる - みずぴー日記という記事。おお、スッキリかっこよく求まりますね、Scalaカコイイ。さて、総当り。非決定性計算。リストモナド。といったら、Linq、クエリ式。そんな風に反射的に連想が成りたつならもう立派なLinq使いですね！いやまあ、クエリ式で総当たり - NyaRuRuの日記で読んだことがあるから、というだけの話なのですがー。ほとんど直訳でいけるとあるように、Scalaで書かれたsend + more = moneyもまた、直訳で書けました。

var digits = Enumerable.Range(0, 10);

var solve = from s in digits
            from e in digits.Except(new[] { s })
            from n in digits.Except(new[] { s, e })
            from d in digits.Except(new[] { s, e, n })
            from m in digits.Except(new[] { s, e, n, d })
            from o in digits.Except(new[] { s, e, n, d, m })
            from r in digits.Except(new[] { s, e, n, d, m, o })
            from y in digits.Except(new[] { s, e, n, d, m, o, r })
            where s != 0
            where m != 0
            let send = int.Parse("" + s + e + n + d)
            let more = int.Parse("" + m + o + r + e)
            let money = int.Parse("" + m + o + n + e + y)
            where send + more == money
            select new { send, more, money };

foreach (var item in solve) Console.WriteLine(item);

ちゃんちゃん。こういうの見ると、各言語は同じとこに向かってる感がありますね。微妙に表現は違いますが、同じ発想が通じるし同じように書ける。その点はC#もScalaもF#も同じパラダイム、同じ未来を目指して向かってるのではないかと思います。Javaは微妙に落伍している気がしますが、もう少し何とかなって欲しいものです。

と、いうだけなのもアレなので、 int.Parse("" + s + e + n + d) の部分について。数字を文字列的な並びとして解釈したい、というわけですが、手段をまとめるとこんな感じになるかしらん。

// という数字があった時に123にしたい
var x = 1;
var y = 2;
var z = 3;

// ダルい
var xyz1 = int.Parse(x.ToString() + y.ToString() + z.ToString());
// 複数ある時はこちらで
var xyz2 = int.Parse(string.Concat(x, y, z));
// コンパイル後の結果はxyz2と一緒
var xyz3 = int.Parse("" + x + y + z);
// 文字列変換しない
var xyz4 = x * 100 + y * 10 + z;
// ↑のは桁数が多い時に泣くのでこうしてやる
var xyz5 = new[] { x, y, z }.Aggregate((a, b) => a * 10 + b);

文字列にして並べてintに変換するのがお手軽なわけですが、.ToString()を並べていくのはダルいわけですよね！というわけで、そんな時はstring.Concatを使うと全部まとめて結合出来ます。しかし int.Parse(string.Concat と並ぶのすらダルい、とかいう不届き者は先頭に""と足し合わせることでstring.Concatで結合したのと同じ結果を得られます。これは、演算子は左から適用されていきますが、文字列と数値を+で足すと文字列として足される、以下繰り返し。の結果。キモチワルイといえばキモチワルイので、積極的に使うかというと悩ましいところですが……。

そもそも数字を扱うのに文字列に変えてー、とかが邪道だという話も割とある。効率的な意味でも。なので、そういうときは2の桁は10倍、3の桁は100倍……。とかやっていると桁数が多いときはどうするのどうもしないの？という話なので、Aggregateを使うという手もあります。Aggregateは一般的な関数型言語でいうfoldlに相当。左からの畳み込み演算。ところで、では右からの畳み込みはどうすればいいの？つまりはfoldrはどうなのか、というと、これは.Reverse().Aggregate() のようで。右からなら逆にすればいいぢゃない。

ところで、C#のLinqで出来ることはJavaScriptのlinq.js - LINQ for JavaScriptでも出来ますよ？やってみます？

var digits = Enumerable.Range(0, 10);

var solve = digits
    .SelectMany(function(s){ return digits.Except([s])
    .SelectMany(function(e){ return digits.Except([s, e])
    .SelectMany(function(n){ return digits.Except([s, e, n])
    .SelectMany(function(d){ return digits.Except([s, e, n, d])
    .SelectMany(function(m){ return digits.Except([s, e, n, d, m])
    .SelectMany(function(o){ return digits.Except([s, e, n, d, m, o])
    .SelectMany(function(r){ return digits.Except([s, e, n, d, m, o, r])
    .Select(function (y) { return { s: s, e: e, n: n, d: d, m: m, o: o, r: r, y: y} })})})})})})})})
    .Where("$.s != 0")
    .Where("$.m != 0")
    .Select(function(x){ return { 
        send: parseInt("" + x.s + x.e + x.n + x.d),
        more: parseInt("" + x.m + x.o + x.r + x.e),
        money: parseInt("" + x.m + x.o + x.n + x.e + x.y)}})
    .Where(function (x) { return x.send + x.more === x.money });

solve.ForEach(function (x) { document.writeln(x.send + ":" + x.more + ":" + x.money) });

C#クエリ式からの変換のポイントは、from連鎖をSelectManyの連鎖で、但しカッコは閉じず変数のキャプチャを内包したままで最後にSelectで一旦整形してやるというところです。正確なクエリ式の再現とはなりませんが、この程度ならば、まあ何とか書けなくもないレベルとなります（正確なクエリ式の変形結果の再現をやると手では到底書けないものになる）。

ちなみに総当りなので結構時間がかかってIEだと泣きます。Chromeなら、まあそれなりな速度で求まるかなー。

Linqと総当り

Profile

Archive