僕のYak Shavingは終わらない

車輪の再発明をやめたらそこには壮大なYakの群れが

ProjectEuler 001 倍数の和を求める

いきなりだけどProjectEulerの解説を始めたいと思う。いつまで続くかわからないけど、会社の人達と一緒にやれている間は続くと思う。

ちなみに日本語のWikiもある。


問題文は以下

Problem 1 †
10未満の自然数のうち、3 もしくは 5 の倍数になっているものは 3, 5, 6, 9 の4つがあり、 これらの合計は 23 になる。

同じようにして、1,000 未満の 3 か 5 の倍数になっている数字の合計を求めよ。

まずはRubyでのオーソドックスな回答。

# while文を使って書いてみる
def sum_while (max, num1, num2)
  n = 0
  sum = 0
  while n < max
    sum += n if n % num1 == 0 || n % num2 == 0
    n += 1
  end
  return sum
end

p sum_while(10, 3, 5) # => 23
p sum_while(1000, 3, 5)

どのプログラミング言語プログラマーでも読み下しやすいように思う。
でもこれだとRubyっぽくないよね。

ということでinjectを使ってみる。

# inject文を使って書いてみる
def sum_inject (max, num1, num2)
  return (1..(max - 1)).inject(0) {|sum, n|
    (n % num1 == 0 || n % num2 == 0) ? sum + n : sum
  }
end

p sum_inject(10, 3, 5) # => 23
p sum_inject(1000, 3, 5)

う~ん、いいんだけど、三項演算子とか使ってしまってることと、injectであまり複雑なことやると読みづらいよね。

とういうことでinjectには加算だけやってもらって、selectで加算する数をあらかじめフィルタリングするようにする。

# select文もかませたinject文を使って書いてみる
def sum_select_inject (max, num1, num2)
  return (1..(max - 1)).select {|n|n % num1 == 0 || n % num2 == 0}.inject(&:+)
end

p sum_select_inject(10, 3, 5) # => 23
p sum_select_inject(1000, 3, 5)

injectの部分で(&:+)とか使っているのが読みやすい?という議論があるかもしれないけど簡単な処理ならむしろわかりやすくていいんじゃないかなって思っている。この使い方はリファレンスにも載っているしね。少なくとも真ん中の例よりも最後の方がわかりやすい要素は多いと思う。

そしてワンライナーも示しておく。

 $ ruby -e 'p (1..999).select{|n|n%3==0||n%5==0}.inject(:+)'

実はこの問題は会社のSkype部屋に投稿したらみんな載ってきて楽しかった(投稿したのは部長だけどw)。

ちなみにPerlでも書いてみた。

#!/usr/bin/env perl
use strict;
use warnings;
# use Time::HiRes qw/gettimeofday tv_interval/;
# my $start = [gettimeofday];
sub sum  {
    my $max = $_[0];
    my $num1 = $_[1];
    my $num2 = $_[2];
    my $sum = 0;
    for (1..($max - 1)) {
        if ($_ % $num1 == 0 or $_ % $num2 == 0) {
            $sum += $_;
        }
    }
    $sum;
}
print sum(1000, 3, 5), "\n";
# my $end = [gettimeofday];
# printf "time = %.3f", tv_interval($start, $end);

うーん、subを使うと途端に長ったらしくなるのはどうにかならないものか。自分のPerl力の低さも伺えますね。

ついでにInline Cという、C言語Perlスクリプトに埋め込めるモジュールを使ってみた。これ面白いね。使う場面があったら検討したい。今回の問題だと全然使う意味ないんだけどね、処理少なすぎて。

#!/usr/bin/env perl
# use strict; # Inline C を使っているとエラーになってしまう
use warnings;
use Time::HiRes qw/gettimeofday tv_interval/;
use Inline C;
my $start = [gettimeofday];
print sum(1000, 3, 5), "\n";
my $end = [gettimeofday];
printf "time = %.3f", tv_interval($start, $end);
__END__
__C__
double sum(int max, int num1, int num2) {
    double sum = 0;
    int i = 0;
    for(i = 1 ; i < max ; i++) {
        if (i % num1 == 0 || i % num2 == 0) {
            sum += i;
        }
    }
    return sum;
}

こんな感じで一つの問題でも沢山の実装方法がやって面白いです。

そしてRubyのProjectEulerの親和性が高すぎる件に対してはホント脱帽です。
この後の問題では素数を扱うのですがそのためのモジュールもちゃんと完備されています(遅いから使わないけど)。あと順列・組み合わせとか最小公倍数・最大公約数を求めるモジュールも標準であったりしてw

Perlでやろうとするとやっぱりたくさん書かないといけなくて、CPANにあるっちゃあるんだけど標準じゃないからめんどくさかったり。

少なくともProjectEulerに関してはRubyが圧勝なんじゃないかなって思う昨今です。

まとめ

  • ProjectEulerをRubyで解くと楽しい
  • 一つの問題を色んな方法で解くと楽しい
  • 同じ問題をみんなで解くと楽しい
  • 色々な言語で実装するとさらに楽しい!

といったところでしょうか。

初回から飛ばすとあとが続かないので今日はこのへんで。

今日のコードはgithubに上がっています。他の問題も、ではでは
https://github.com/kazuph/ProjectEuler