【Project EulerにRubyで挑戦シリーズ】問9:Special Pythagorean triplet

スポンサーリンク

今回の問題

Special Pythagorean triplet

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a ** 2 + b ** 2 = c ** 2

For example, 32 + 42 = 9 + 16 = 25 = 52.
There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

ピタゴラス数(ピタゴラスの定理を満たす自然数)とは a < b < c で以下の式を満たす数の組である.
a ** 2 + b ** 2 = c ** 2
例えば, 32 + 42 = 9 + 16 = 25 = 52 である.
a + b + c = 1000 となるピタゴラスの三つ組が一つだけ存在する.
これらの積 abc を計算しなさい.

書いた内容

3つの自然数を upto メソッドでぐるぐる回して、
足し合わせて1000になる かつ 2数の2乗の和が残りの数の2乗になる
ものだけを配列に入れてかけ合わせました。

とりあえず答えは出ますが、無駄な計算しすぎです。

array = []
1.upto(998) do |l|
  (l + 1).upto(998) do |m|
    (m + 1).upto(998) do |n|
      if l + m + n == 1000 && l ** 2 + m ** 2 == n ** 2
        array.push(l, m, n)
      end
    end
  end
end
puts array.inject(:*)
#=> 31875000

そもそも最後の数のループは不要で、 c = 1000 – (a + b) と定義すればよかった。

array = []
1.upto(998) do |a|
  (a + 1).upto(998) do |b|
    c = 1000 - (a + b)
    if a ** 2 + b ** 2 == c ** 2
        array.push(a, b, c)
    end
  end
end
puts array.inject(:*)

次に色々とメソッド化しました。
加えて、変数cが正の数になる条件をつけました。

また、ピタゴラスの定理の名前の通り、
3数のうち最大の数であるcは三角形の最長辺になるので
【c < a + b】という法則も成り立ちます。

def pythagorean_triplet?(a, b, c)
  a ** 2 + b ** 2 == c ** 2
end

def calculation
  1.upto(998) do |a|
    (a + 1).upto(1000 - a) do |b|
      if a + b < 1000
        c = 1000 - (a + b)
        if c < a + b
          if pythagorean_triplet?(a, b, c)
            return a * b * c
          end
        end
      end
    end
  end
end

puts calculation

ネストが複雑になりましたが、結果これが一番処理が速かったです。
※Project Eulerのリポジトリ

この記事の内容が役に立ったと思いました、SNSで記事を共有していただけますと幸いです。