プロジェクト・オイラー(031-035)

• 考えたこと
  • 典型的なナップザック問題 動的計画法（ナップサック問題） ?
  • と、思ったけどどうやら違うみたいだ…結局泥縄的な全探索を書いた…
  • 計算量的には O(N!) , AtCoderだとこれは通りませんね・・・
  • 2017/12/31 追記 動的計画法でのプログラムを書いた

全探索

めっちゃ遅い、3.9秒かかる

#
# There are 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
#

#        a, b, c, d , e , f , g  , h
COINS = [1, 2, 5, 10, 20, 50, 100, 200]
#        0, 1, 2,  3,  4,  5,   6,   7
ans   = []
sum   = 0

def sum_coin(h=0,g=0,f=0,e=0,d=0,c=0,b=0,a=0)
  a*1 + b*2 + c*5 + d*10 + e*20 + f*50 + g*100 + h*200
end

for h in 0..200/COINS[7]
  next if sum_coin(h) > 200
  for g in 0..200/COINS[6]
    next if sum_coin(h,g) > 200
    for f in 0..200/COINS[5]
      next if sum_coin(h,g,f) > 200
      for e in 0..200/COINS[4]
        next if sum_coin(h,g,f,e) > 200
        for d in 0..200/COINS[3]
          next if sum_coin(h,g,f,e,d) > 200
          for c in 0..200/COINS[2]
            next if sum_coin(h,g,f,e,d,c) > 200
            for b in 0..200/COINS[1]
              next if sum_coin(h,g,f,e,d,c,b) > 200
              for a in 0..200/COINS[0]
                sum = sum_coin(h,g,f,e,d,c,b,a)
                next if sum > 200
                if sum == 200
                  puts "#{a},#{b},#{c},#{d},#{e},#{f},#{g},#{h}"
                  ans << "a = #{a},b = #{b},c = #{c},d = #{d},e = #{e},f = #{f},g = #{g},h = #{h}"
                end
              end
            end
          end
        end
      end
    end
  end
end

puts ans.length

• これは コイン問題 の応用でした
  • ここを参考に　→　C#練習日記 - Project Euler 31

動的計画法

0.09秒

COINS = [1, 2, 5, 10, 20, 50, 100, 200]
INF   = 1 << 25

def coin(amount,kind,coins)
  dp = Array.new(amount+1, 0)
  dp[0] = 1
  for i in 0...kind
    for j in coins[i]..amount
      dp[j] += dp[j - coins[i]]
    end
  end
  dp
end

N,M = 200,COINS.length
dp = coin(N,M,COINS)
p dp
puts dp[N]

• 問題に出てくる掛け算は \( 0,1,2,3,4,5,6,7,8,9,=,* \) を順列として並べたらすべて探索できる
• 探索したらエラーは無視して右辺と左辺が等しいものを数え上げればよい
• 4分ぐらいかかったので、もっと速い方法はありそうだ

def detect_pandigital(digit_arr)
  is_pandigital = nil
  begin
    eval("is_pandigital = (#{digit_arr.join})")
  rescue SyntaxError
  end

  if is_pandigital
    p "ans = (#{digit_arr.join})"

    formula = digit_arr.join
    l,r = formula.split("==")
    product = l.include?('*') ? r : l
    tmp = l.include?('*') ? l : r
    small,large = tmp.split('*').min,tmp.split('*').max
    return product,small,large
  end

  [nil,nil,nil]
end

ans = {}
pandigitals = ('1'..'9').to_a + ['*', "=="]
pandigitals.permutation(11).with_index(0) do |result,index|
  prod,small,large = detect_pandigital(result)

  if prod!=nil
    ans.merge!({prod => [small, large]})
  end
end

p ans
p ans.map{|k,v| k.to_i}.inject(&:+)

正答後のスレッドを参考にして、コードを再作成してみた

数学的な観点まとめ => Project Euler Problem 32 「パンデジタル積」

DIGITS = (1..9).to_a
ans = {}

(1..9999).each do |a|
  a_digits = a.to_s
  for b_digit in (4.5 - a_digits.size).to_i..(5 - a_digits.size)
    tmp_digits = DIGITS - a_digits.split("").map(&:to_i).to_a

    tmp_digits.permutation(b_digit) do |b_arr|
      c_arr = tmp_digits - b_arr

      next if b_arr.size==0

      b = b_arr.join.to_i
      c = a * b
      a_arr = a.to_s.split("").map(&:to_i)
      c_arr = c.to_s.split("").map(&:to_i)

      digits = a_arr + b_arr + c_arr
      if DIGITS.all? {|d| digits.include? d } && [a_arr.size,b_arr.size,c_arr.size].inject(&:+)==9
        puts "#{a} * #{b} = #{c}"

        # product => [small, large]
        ans.merge!({c => [[a,b].min, [a,b].max]})
      end
    end
  end
end

p ans.map{|k,v| k.to_i}.inject(&:+)

• 0! = 1 ということを知らなかったので時間がかかった 0の階乗を1と定義する理由
• Project Euler Q34 【桁の階乗】

def fact(n)
  if n == 0 or n == 1
    1
  else
    n * fact(n-1)
  end
end

facts = {}

# 3..2540160
ans = (3..2540160).to_a.select do |n|
  answer = []
  answer << "n = #{n}"
  tmp = n.to_s.split("").map do |d|
    debug = fact(d.to_i)
    answer << "  => #{d}! = #{debug}"
    debug
  end.inject(&:+)
  answer << "  SUM = #{tmp}"

  puts answer.join("\n") if n == tmp
  n == tmp
end

p ans

p ans.inject(&:+)

• またエラストステネスの篩で素数出して、Rubyの小技でちょいちょいなのです 数論

def erastosthenes(n)
  array = (2..n).to_a
  threshold = Math.sqrt(n)
  count = 2
  while threshold > count
    array.reject!{|n| n != count and n % count == 0}
    count += 1
  end
  array
end

def circular_prime?(n, prime_numbers)
  if prime_numbers.include?(n)
    rolling_num(n).all?{|pn| prime_numbers.include?(pn)}
  else
    false
  end
end

def rolling(str)
  arr = str.to_s.split("")
  ans = []
  for i in 0...arr.length
    ans << arr[i...arr.length].concat(arr[0...i]).flatten
  end
  ans
end

def rolling_num(n)
  rolling(n).map{|arr| arr.join.to_i}
end

PN = erastosthenes(1000000)
ans = PN.count{|pn| circular_prime?(pn,PN)}
puts "Prime numbers under 1-million: #{PN.length}"
puts "Circular prime numbers under 1-million: #{ans}"