hossy online - といぼっくす

_ [プログラミング] Project Euler 172

やねうらお氏のはてなダイアリー [美しすぎるプログラムを解読せよの巻] で、[Project Euler: Problem 172] が取り上げられていました。プログラムからどういう問題を考えるもので、面白いです。

パズル系プログラマとしてはお祭りに参加してみることに。

方法1: C#で

手元の Visual C# 2010 Express で、そのまま書き直しました。Cのマクロは使えないからと、かわりにラムダ式を。

using System;
using System.Linq.Expressions;
 
namespace Euler172
{
    class Program
    {
        static void Loop(Action<int, int, int, int, int, int, int, int, int, int> expr)
        {
            for (int i0 = 0; i0 < 4; i0++)
                for (int i1 = 0; i1 < 4; i1++)
                    for (int i2 = 0; i2 < 4; i2++)
                        for (int i3 = 0; i3 < 4; i3++)
                            for (int i4 = 0; i4 < 4; i4++)
                                for (int i5 = 0; i5 < 4; i5++)
                                    for (int i6 = 0; i6 < 4; i6++)
                                        for (int i7 = 0; i7 < 4; i7++)
                                            for (int i8 = 0; i8 < 4; i8++)
                                                for (int i9 = 0; i9 < 4; i9++)
                                                    expr(i0, i1, i2, i3, i4, i5, i6, i7, i8, i9);
        }
 
        static void Main(string[] args)
        {
            long[, , , , , , , , , ,] dp = new long[18, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4];
 
            Loop((int i0, int i1, int i2, int i3, int i4, int i5, int i6, int i7, int i8, int i9) => dp[0, i0, i1, i2, i3, i4, i5, i6, i7, i8, i9] = 1);
 
            for (int r = 1; r <= 17; r++) 
            {
                Loop((int i0, int i1, int i2, int i3, int i4, int i5, int i6, int i7, int i8, int i9) =>
                {
                    if (i0 > 0) dp[r, i0, i1, i2, i3, i4, i5, i6, i7, i8, i9] += dp[r - 1, i0 - 1, i1, i2, i3, i4, i5, i6, i7, i8, i9];
                    if (i1 > 0) dp[r, i0, i1, i2, i3, i4, i5, i6, i7, i8, i9] += dp[r - 1, i0, i1 - 1, i2, i3, i4, i5, i6, i7, i8, i9];
                    if (i2 > 0) dp[r, i0, i1, i2, i3, i4, i5, i6, i7, i8, i9] += dp[r - 1, i0, i1, i2 - 1, i3, i4, i5, i6, i7, i8, i9];
                    if (i3 > 0) dp[r, i0, i1, i2, i3, i4, i5, i6, i7, i8, i9] += dp[r - 1, i0, i1, i2, i3 - 1, i4, i5, i6, i7, i8, i9];
                    if (i4 > 0) dp[r, i0, i1, i2, i3, i4, i5, i6, i7, i8, i9] += dp[r - 1, i0, i1, i2, i3, i4 - 1, i5, i6, i7, i8, i9];
                    if (i5 > 0) dp[r, i0, i1, i2, i3, i4, i5, i6, i7, i8, i9] += dp[r - 1, i0, i1, i2, i3, i4, i5 - 1, i6, i7, i8, i9];
                    if (i6 > 0) dp[r, i0, i1, i2, i3, i4, i5, i6, i7, i8, i9] += dp[r - 1, i0, i1, i2, i3, i4, i5, i6 - 1, i7, i8, i9];
                    if (i7 > 0) dp[r, i0, i1, i2, i3, i4, i5, i6, i7, i8, i9] += dp[r - 1, i0, i1, i2, i3, i4, i5, i6, i7 - 1, i8, i9];
                    if (i8 > 0) dp[r, i0, i1, i2, i3, i4, i5, i6, i7, i8, i9] += dp[r - 1, i0, i1, i2, i3, i4, i5, i6, i7, i8 - 1, i9];
                    if (i9 > 0) dp[r, i0, i1, i2, i3, i4, i5, i6, i7, i8, i9] += dp[r - 1, i0, i1, i2, i3, i4, i5, i6, i7, i8, i9 - 1];
                }
                );
            }
 
            Console.Out.WriteLine(dp[17, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2] * 9);
        }
    }
}

確かにDPだなぁと。下の○から◎までの最短経路が何通りあるか、という問題でこの方法を使います。交差点のマスへの行き方は、上の交差点の行き方と左のそれの合計値。いくら答えが大きくなってしらみつぶしに調べるのが大変そうでも、計算の回数はマスの数だけに抑えられる、というものです。

○─┬───┐  ○─ 1───┐
│　│　　　│  │　│　　　│
├─┼─┬─┤   1─ 2─ 2─ 3
│　│　│　│  │　│　│　│
├─┴─┼─┤   1─ 3─ 5─ 8
│　　　│　│  │　　　│　│
└───┴─◎  └─── 6─14

Euler 172だと10+1次元と多いですけれど、考え方は同じです。1桁の結果を使って2桁、2桁の結果を使って3桁、と順番に進めていけばと。詳細はやねうらお氏の解説を。このプログラムは各配列の意味を "i0 = 2: (3-2)回以下の出現数" からそのまま "2回以下の出現数" に書き換えています。

うちの Core i7 2.80GHzでは、デバッグ実行で7秒ほど。速度の事を考えると、その場にべたっと2回の10重ループを書いた方が良いと思います。

さて、元エントリの「美しすぎる」は、後半の dp[r, i0, i1, i2, i3, i4, i5, i6, i7, i8, i9] += ... のまるで行列計算のような場所に対して言っているようです。けれど、個人的にはあまり好きではないです... コーディングする人がうっかり属性持ちだと、コピーペーストの際に i1 をうっかり i0 のまま残したりして、気付きにくいバグの原因に（汗）。

方法1': Rubyで

というわけで、同じ方針のまま i0〜i9 を使わないように、Ruby 1.9.1 で書き直してみました。。

def f(r, ary)
  ary.inject(r){|s, x| s*4 + x}
end
 
def g ary
  if ary.size == 10
    yield ary
  else
    4.times do |i|
      g (ary + [i]) {|ary| yield ary}
    end
  end
end
 
dp = [1] * f(1, [0]*10) + [0] * f(17, [0]*10)
 
(1..17).each do |r|
  g([]) do |ary|
    10.times do |i|
      unless ary[i].zero?
        ary2 = ary.dup
        ary2[i] -= 1
        dp[f(r, ary)] += dp[f(r-1, ary2)] 
      end
    end
  end
end
 
puts dp[f(17, [3]*9+[2])] * 9

...結果が返ってくるまでに30分ほどかかりました。遅い遅い。i0〜i9を消すために配列にしたり、yieldを多用したりと、確かに重そうです。rubyで多次元配列が使えないからと dp[f()] で一次元に落とすのも読みづらくてなんだかなぁと。

それでも、10重ループで一次変数の数を増やすよりは、このようにしたくなります。

方法2

Euler 172を見たときに思い浮かんだのは別の方法でした。

class Integer
  def factorial
    (1..self).inject(1, :*)
  end
  
  def combination x
    self.factorial / (x.factorial * (self - x).factorial)
  end
end
 
def count ary
  result = 10.combination(ary.count(1))
  result *= (10-ary.count(1)).combination(ary.count(2))
  result *= (10-ary.count(1)-ary.count(2)).combination(ary.count(3))
  result *= 18.factorial / ary.inject(1){|r, i| r*i.factorial} * 9 / 10
end
 
def solve ary
  result = 0
  (1..3).each do |i|
    if (ary.empty? || ary[-1]<=i)
      ary.push i 
      result += count ary if ary.inject(:+) == 18
      result += solve ary if ary.size < 10
      ary.pop
    end
  end
  result
end
 
puts solve []

方針はこんな感じ。

solve():

[1,2,2,2,2,3,3,3], [3,3,3,3,3,3] のように、18桁の数字のうち同じ数字が何個ずつ現れるかの配列を作る。

それぞれの出現数がいくつかを count() で求め、それらを足し合わせる。

count() [1,2,2,2,2,3,3,3] の場合:

(0〜9)の10個中で1個の1回出る数字、(10-1)個中4個の2回出る数字、(10-1-4)個中3個の3回出る数字の組み合わせの積を考える。

それぞれ18桁の場所に入れる。同じ数字を複数回計算しないように個数分で割る。18! / (1! * (2!)^4 * (3!)^3)) 通りある。

最初の桁が0にならないよう、最後に0.9倍する。

この方法だと一瞬で終わります。

count() は、もし (1..3) より数が多ければこんな感じにまとめると思います。3回だと余計読みづらくなっている感じがして、べたっと書きました。

def count ary
  (1..3).inject(1) { |s, i|
    s *= (10 - (1...i).inject(0){|r, j| r+ary.count(j)} ).combination(ary.count(i))
  } * 18.factorial / ary.inject(1){|r, i| r*i.factorial} * 9 / 10
end

最後に

視覚的に美しいプログラムをだいなしにするネタエントリでした。