プロジェクト・オイラー(061-065)

• 考えたこと
  • 対象の数値が4桁の数限定なので元となる数の集合は少なく、全探索できそうな雰囲気がある
  • 再帰的な関数を定義して数え上げることで実装できた
    • 各種集合を重複無く数え上げるためにハッシュマップの値に配列をもたせてみた

• 後で見たときのため、処理内容を以下に示す
  • 三角数〜八角数までをp3,p4,p5,p6,p7,p8で定義しておく
  • 答えとなる巡回数列は、どの数値から始めてもいいので三角数からはじめるものとして、三角数の全ての要素でループを開始
    • ループ内部で再帰関数に三角数の１要素をスタックの形で渡す
    • 再帰関数内部で三角数〜八角数までをループして、スタックの最後の要素の下二桁が上二桁と一致する数値があれば取得する
    • 取得した数値をスタックにpushし再帰関数に渡すことを繰り返す、その際に使用したN角数の配列は削除しておく
    • 再帰関数内で三角数〜八角数の配列が空であれば答えとなる巡回数列が揃ったことになるので記録する

p3,p4,p5,p6,p7,p8 = [],[],[],[],[],[]

(1..10**5).each do |n|
  _p3 = n*(n+1)/2
  p3 << _p3 if 999 < _p3 and _p3 < 10000
  _p4 = n**2
  p4 << _p4 if 999 < _p4 and _p4 < 10000
  _p5 = n*(3*n-1)/2
  p5 << _p5 if 999 < _p5 and _p5 < 10000
  _p6 = n*(2*n-1)
  p6 << _p6 if 999 < _p6 and _p6 < 10000
  _p7 = n*(5*n-3)/2
  p7 << _p7 if 999 < _p7 and _p7 < 10000
  _p8 = n*(3*n-2)
  p8 << _p8 if 999 < _p8 and _p8 < 10000
end

@ans = []

def rec_search(arr, stack)

  if arr.empty?
    puts "#{stack} #{'<--- !!!' if stack.last.values[0].to_s[2,2] == stack.first.values[0].to_s[0,2]}"
    @ans = stack.dup if stack.last.values[0].to_s[2,2] == stack.first.values[0].to_s[0,2]
    return
  end

  arr.each do |k, v|
    matched = v.select{|val| stack.last.values[0].to_s[2,2] == val.to_s[0,2]}

    dup_arr = arr.dup
    dup_arr.delete(k)

    matched.each do |new_key|
      next if stack.any?{|stack_k, stack_v| stack_k==k}
      stack.push({k => new_key})
      puts "#{stack}"
      rec_search(dup_arr, stack)
      stack.pop()
    end
  end
end

arr = {p3: p3, p4: p4, p5: p5, p6: p6, p7: p7, p8: p8}
arr_dup = arr.dup
arr_dup.delete(:p3)

arr[:p3].each do |key|
  puts "#{{p3: key}}"
  rec_search(arr_dup, [].push({p3: key}))
end

puts "---"
p @ans
p @ans.map {|e| e.values[0]}.inject(&:+)

• 考えたこと
  • 立方数のテーブルを先に作っておいて全探索したら早そうに見える
  • 立方数のテーブル内の数値を文字列化し、ソートしてやったやつをキーにgroup_byしたものを作成（→ハッシュマップ）
  • 上記をやると立方数のなかで並び替えたら同じになるものがまとまる
  • あとはそのハッシュマップの中で5つの立方数を持つものを検索してやればいい

cubes = (1..10**5).to_a.map do |n|
  n**3
end.group_by do |n|
  n.to_s.split("").sort.join
end.to_a

cubes.select do |elem|
  elem[1].size.to_i == 5
end.take(1).each do |elem|
  p elem
end

• 考えたこと
  • べき乗の指数に対してべき乗される自然数を洗い出すプログラムを考えると意外と簡単に解ける
  • 自然数の総数はたくさんあるが、べき乗の桁数はべき乗が少し大きくなると天元突破するのでそれほどたくさん数はない

def pow_eql_exp(exp)
  count = 0
  n = 1
  loop {
    pow = n**exp
    if pow.to_s.length == exp
      count += 1
    elsif pow.to_s.length > exp
      break
    end
    n += 1
  }
  count
end

ans = (1..200).to_a.map do |n|
  pow_eql_exp(n)
end.inject(&:+)

puts ans

• 考えたこと

• 考えたこと