プロジェクト・オイラー(041-045)

• 考えたこと
  • 問題文から、9桁以上のパンデジタル素数はなさそう
  • なので9〜1桁まで下降していき、それぞれの桁数を1回だけ使った数字を素数判定すればOKか

def prime(n, primes)
  if n == 1
    return false,primes
  elsif primes.include?(n)
    return true,primes
  else
    m = Math.sqrt(n).round
    2.upto(m) do |step|
      if step != 2 and step % 2 == 0
        next
      else
        if n % step == 0
          return false,primes
        else
          next
        end
      end
    end
    primes << n
    return true,primes
  end
end

primes=[]

9.downto(1) do |digit|
  (1..digit).to_a.permutation(digit) do |arr|
    n = arr.join.to_i
    is_prime,primes = prime(n, primes)
    if is_prime
      p n
    end
  end
end

puts primes.max

• 考えたこと
  • 先に三角数のテーブルを作り確保しておく
  • 「単語の値」の値もメモ化してとっておく

ALPHA_TABLE = ('a'..'z').to_a
$word_value_table = {}

def C(n)
  n*(n+1)/2
end

$triangles = (1..10**3).map do |n|
  {n=>C(n)}
end

def word_value(s)
  word = s.split("").map do |c|
    c.downcase
  end.sort

  unless $word_value_table.has_key?(word)
    wv = word.map do |c|
      ALPHA_TABLE.index(c)+1
    end.inject(&:+)
    $word_value_table[word] = wv
  end

  $word_value_table[word]
end

#wv = word_value("SKY")
#puts $triangles.detect{|hash| hash.values.include? wv}.keys
ans = 0

File.open("p042_words.txt", "r") do |f|
  s = f.read.gsub(/\"/, "")
  s.split(",").each do |word|
    wv = word_value(word)
    triangle = $triangles.detect{|hash| hash.values.include? wv}
    unless triangle.nil? or triangle.empty?
      ans += 1
    end
  end
end

puts ans

• 考えたこと
  • 順列を出して、条件に合わないものを排除するだけ

ans = []

(0..9).to_a.permutation do |arr|
  next unless arr[1, 3].join.to_i % 2 == 0
  next unless arr[2, 3].join.to_i % 3 == 0
  next unless arr[3, 3].join.to_i % 5 == 0
  next unless arr[4, 3].join.to_i % 7 == 0
  next unless arr[5, 3].join.to_i % 11 == 0
  next unless arr[6, 3].join.to_i % 13 == 0
  next unless arr[7, 3].join.to_i % 17 == 0

  puts arr.join.to_i
  ans << arr.join.to_i
end

puts ""
puts ans.inject(&:+)

• 考えたこと
  • 愚直に五角数を出して計算しても計算量がかかりすぎてだめっぽい

• 考えたこと
  • それぞれの数列を集合と考えれば、求める「三角数かつ五角数かつ六角数な数」はその積集合になるはず
  • n=1～10^5までの数列のテーブルを作って、積集合を求めた中で40755以上になるものをとればよい

def T(n)
  n*(n+1)/2
end
def P(n)
  n*(3*n-1)/2
end
def H(n)
  n*(2*n-1)
end

TT = (1..10**5).map{|n| T(n)}
PT = (1..10**5).map{|n| P(n)}
HT = (1..10**5).map{|n| H(n)}

p (TT&PT&HT).detect{|x| x>40755}