読者です 読者をやめる 読者になる 読者になる

プロジェクト・オイラーで遊ぶ(3)

Ruby 数学

ここの続きです。Ruby でやっています。
※追記 本家サイトに登録すると、答えがチェックできるのですね。ここまではすべて正しいことを確認しました。答えは消しておきます。

(問17)
1 から 5 までの数字を英単語で書けば one, two, three, four, five であり, 全部で 3 + 3 + 5 + 4 + 4 = 19 の文字が使われている.
では 1 から 1000 (one thousand) までの数字をすべて英単語で書けば, 全部で何文字になるか.
注: 空白文字やハイフンを数えないこと. 例えば, 342 (three hundred and forty-two) は 23 文字, 115 (one hundred and fifteen) は20文字と数える. なお, "and" を使用するのは英国の慣習.

class NumberLetterCounts
  def initialize
    number = {one: 1, two: 2, three: 3, four: 4, five: 5, six: 6, seven: 7,
      eight: 8, nine: 9, ten: 10, eleven: 11, twelve: 12, thirteen: 13,
      fourteen: 14, fifteen: 15, sixteen: 16, seventeen: 17, eighteen: 18,
      nineteen: 19, twenty: 20, thirty: 30, forty: 40, fifty: 50, sixty: 60,
      seventy: 70, eighty: 80, ninety: 90, hundred: 100, thousand: 1000}.invert
    @len = Hash.new
    number.each_key {|i| @len.store(i, number[i].length)}
    @sum = 0
  end

  def ty_one_to_nine
    s = 0
    1.upto(9) {|i| s += @len[i]}
    s
  end
  
  def count
    1.upto(19) {|i| @sum += @len[i]}
    20.step(90, 10) do |i|
      @sum += @len[i]
      @sum += @len[i] * 9 + ty_one_to_nine
    end
    a = @sum
    100.step(900, 100) do |i|
      @sum += (b = @len[i / 100] + @len[100])
      @sum += (b + "and".length) * 99 + a
    end
    @sum += @len[1] + @len[1000]
    puts @sum
  end
end

NumberLetterCounts.new.count

どこかミスをしていないか、気になります。答えの確かめ方がわからない。

(問18)
以下の三角形の頂点から下まで移動するとき, その数値の和の最大値は23になる.
      3
    7 4 
  2 4 6
8 5 9 3
この例では 3 + 7 + 4 + 9 = 23.
以下の三角形を頂点から下まで移動するとき, その最大の和を求めよ.
                                          75
                                       95 64
                                    17 47 82
                                 18 35 87 10
                              20 04 82 47 65
                           19 01 23 75 03 34
                        88 02 77 73 07 63 67
                     99 65 04 28 06 16 70 92
                  41 41 26 56 83 40 80 70 33
               41 48 72 33 47 32 37 16 94 29
            53 71 44 65 25 43 91 52 97 51 14
         70 11 33 28 77 73 17 78 39 68 17 57
      91 71 52 38 17 14 91 43 58 50 27 29 48
   63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
注: ここではたかだか 16384 通りのルートしかないので, すべてのパターンを試すこともできる. 
Problem 67 は同じ問題だが100行あるので, 総当りでは解けない. もっと賢い方法が必要である.
class Triangle
  def initialize
    @tri = []
    Num.times do
      @tri << DATA.readline.split.map {|j| j.to_i}
    end
    @max = Array.new(Num - 1)
    0.upto(Num - 1) {|i| @max[i] = Array.new(i)}
    @max[0][0] = @tri[0][0]
  end
  
  def max(i, j)
    val = @tri[i][j]
    return @max[i - 1][0] + val if j.zero?
    return @max[i - 1][i - 1] + val if j == i
    if (a = @max[i - 1][j - 1]) >= (b = @max[i - 1][j])
      a + val
    else
      b + val
    end
  end
  
  def add
    for i in 1..(Num - 1)
      for j in 0..i
        @max[i][j] = max(i, j)
        print "max(#{i}, #{j}) = #{@max[i][j]};  " 
      end
    end
    puts "\nmax = #{@max[Num - 1].max}"
  end
end

Num = 15
Triangle.new.add

__END__
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

これは悩みました。問題67でも通用するようにしたかったので。幸い、うまいやり方が見つかりました。
問題67(参照)はこれが 100列になっているのですが、同様にできるので省略します。ちなみに、どちらの問題でも一瞬で計算が終わります。

(問19)
次の情報が与えられている.
・1900年1月1日は月曜日である.
・9月, 4月, 6月, 11月は30日まであり, 2月を除く他の月は31日まである.
・2月は28日まであるが, うるう年のときは29日である.
・うるう年は西暦が4で割り切れる年に起こる. しかし, 西暦が400で割り切れず100で割り切れる年はうるう年でない.
20世紀(1901年1月1日から2000年12月31日)中に月の初めが日曜日になるのは何回あるか?

require 'date'

counter = 0
for year in 1901..2000
  for month in 1..12
    counter += 1 if Date.new(year, month, 1).wday.zero?
  end
end
puts counter

殆どインチキですが、Ruby の力を利用しました。Date クラスを初めて使ってみたわけです。

(問20)
n × (n - 1) × ... × 3 × 2 × 1 を n! と表す.
例えば, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800 となる.
この数の各桁の合計は 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27 である.
では, 100! の各桁の数字の和を求めよ.

puts (1..100).inject(:*).to_s.each_char.inject(0) {|sum, j| sum += j.to_i}

1行で終わりです。

(問21)
d(n) を n の真の約数の和と定義する. (真の約数とは n 以外の約数のことである. )
もし, d(a) = b かつ d(b) = a (a ≠ b のとき) を満たすとき, a と b は友愛数(親和数)であるという.
・例えば, 220 の約数は 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 なので d(220) = 284 である.
・また, 284 の約数は 1, 2, 4, 71, 142 なので d(284) = 220 である.
それでは
10000未満の友愛数の和を求めよ.

class Integer
  def divide2(include1=false)
    ar = []
    s = include1 ? 1 : 2 
    for i in s..(self ** 0.5)
      ar.push([i, self / i]) if (self % i).zero?
    end
    ar
  end
  
  def divisors
    divide2(true).flatten.uniq.sort
  end
end

def add_divisors(n)
  a = n.divisors
  a.pop
  a.inject(:+)
end

num = Array.new(9999)
for i in 2...10000
  num[i] = add_divisors(i)
end
ami_num = []
for i in 2...10000
  a = num[i]
  next if a > 9999
  ami_num << i if num[a] == i and num[i] != i
end
puts ami_num.inject(:+)

ここでも、前にも使った自作の約数を求めるメソッド参照)を使っています。