8重ループでも十分速い

euler ruby c

なんだかイライラしたので、心を落ち着けるためのProject Euler。31問目。イギリスのコインには、2ペンスとか20ペンスという偶数のものがあるらしく、いろいろ組み合わせて、ちょうど2ポインド（200ペンス）になるコインの組み合わせの数は？ という問題。

最初はかなりゴージャスな力技。各種類のコインを200ペンス以下となるだけの枚数用意して、この組み合わせを全部順に調べる。

coins = [1, 2, 5, 10, 20, 50, 100, 200]
coin_pool = coins.map do |c|
  [c] * (200 / c)
end.flatten

count = 0

(1..200).each do |n|
  puts "checking #{n} coins combination"
  coin_pool.combination(n).each do |coins|
    if coins.inject(:+) == 200
      puts coins
      count += 1
    end
  end
end

p count

全く終わる気配がない。ということを、コードを書く前に気付けよと思う。combinationをなめたらあかん。

1から200ペンスまでの各金額について、可能なコインの組み合わせを下から調べるという動的計画法にしないと無駄が多いかなとも思ったけど、このぐらいならガツンとやれば終わるかも、と思って素直にループを8重に開いた。

count = 0
(0..200).step(1).each do |a|
  (0..200).step(2).each do |b|
    (0..200).step(5).each do |c|
      (0..200).step(10).each do |d|
        (0..200).step(20).each do |e|
          (0..200).step(50).each do |f|
            (0..200).step(100).each do |g|
              (0..200).step(200).each do |h|
                if a + b + c + d + e + f + g + h == 200
                puts "1(%d), 2(%d), 5(%d), 10(%d), 20(%d), 50(%d), 100(%d), 200(%d)" % [a, b / 2, c / 5, d / 10, e / 20, f / 50, g / 100, h / 200]
                count += 1
                end
              end
            end
          end
        end
      end
    end
  end
end

puts "number of combinations: #{count}"

と書いた。endが面倒くさすぎる……。さすがにこれならCでいいんじゃないのと思って、Rubyで計算途中にCで書き始めて、gcc、a.outとしたら、Rubyの実行が5分の1ぐらいのところでCの計算結果が出てしまった。Ruby遅い……。

#include <stdio.h>

int main(void) {
  int a, b, c, d, e, f, g, h;
  int count = 0;

  for(a = 0; a <= 200; a++) {
    for(b = 0; b <= 200; b += 2) {
      for(c = 0; c <= 200; c += 5) {
	for(d = 0; d <= 200; d += 10) {
	  for(e = 0; e <= 200; e += 20) {
	    for(f = 0; f <= 200; f += 50) {
	      for(g = 0; g <= 200; g += 100) {
		for(h = 0; h <= 200; h += 200) {
		  if (a + b + c + d + e + f + g + h == 200) {
		    printf("1(%3d), 2(%3d), 5(%3d), 10(%3d), 20(%3d), 50(%3d), 100(%3d), 200(%3d)\n", a, b, c, d, e, f, g, h);
		      count++;
		    }
		}
	      }
	    }
	  }
	}
      }
    }
  }
  printf("number of combinations: %d\n", count);
}

細かなタイポに悩んだりして、30分ほどキーボードを叩く間に、すっかり気分は落ち着いた。しかし、間違えて閉じブレース（}）を、endと書いてしまうなんて、なんてRuby脳だ。