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

mu chance or much chance ?

日々の戯れ言

Project Euler 42

Project Euler

Problem42を解きました.

  • Coded triangle numbers

The nth term of the sequence of triangle numbers is given by, tn = ½n(n+1); so the first ten triangle numbers are:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t10. If the word value is a triangle number then we shall call the word a triangle word.

Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words?

https://projecteuler.net/problem=42

問題は「https://projecteuler.net/project/resources/p042_words.txtにある単語の中で三角数になっている数は何個あるか求めよ.単語SKYのスコアは19(S)+11(K)+25(Y) = 55となる.」.

strAlpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
data = []

File.open('p042_words.txt') do |file|
  file.each_line do |str|
    data = str.delete('"').split(',')
  end
end

# 最長文字列を調べる
maxLen = 0
data.length.times do |i|
  maxLen = data[i].length if maxLen < data[i].length
end

# 必要な三角数の項数を求める
triangle = {}
n = 1
loop do
  tn = n * (n + 1) / 2
  triangle[n] = tn
  break if tn > maxLen * 26
  n += 1
end

# アルファベットと数値の関係を求める
alpha = {}
strAlpha.length.times do |i|
  alpha[strAlpha[i]] = i + 1
end

# 単語の値を求める
count = 0
data.length.times do |i|
  value = 0
  data[i].length.times do |j|
    value += alpha[data[i][j]]
  end
  count += 1 if triangle.value?(value)
end

p count

p042_words.txtを同じディレクトリに置いてください.
単語のスコアの最大値を予め求めておき,
必要な三角数をハッシュに格納します.
各単語の値がハッシュにあればカウントする流れです.