2013-07-29

Project Eulerを再開してみる

大学学部一年のころだったかな。友達と二人でProject Eulerというサイトでよく遊んでいた。これは計算機科学的な問題が大量に掲載されているサイトで、登録すれば自分が解いた問題を集計してくれたり他の人の回答を眺めたりできる。

ずいぶんとアクセスしていなかったのだけど、最近になってふと思い出した。どうせ暇なので昔は解けなかった問題を潰していこうと思って一日に数問ずつ回答していってる。

普通に解くと何百時間も掛ってしまう問題を数秒で解くための工夫が必要になる問題が多いので結構歯ごたえがある。

とってもきれいに解けたり、

text.map! do |r|
  roman = r
  roman.gsub!('IV', 'IIII')
  roman.gsub!('IX', 'VIIII')
  roman.gsub!('XL', 'XXXX')
  roman.gsub!('XC', 'LXXXX')
  roman.gsub!('CD', 'CCCC')
  roman.gsub!('CM', 'DCCCC')

  (roman.count('I') +
   roman.count('V') * 5 +
   roman.count('X') * 10 +
   roman.count('L') * 50 +
   roman.count('C') * 100 +
   roman.count('D') * 500 +
   roman.count('M') * 1000)
end

text.map! do |n|
  t = sprintf("%04d", n).chars.map(&:to_i)

  roman = "#{'M' * t[0]}"

  case t[1]
  when 4 then roman += "CD"
  when 9 then roman += "CM"
  else roman += "#{'D' if t[1] >= 5}#{'C' * (t[1]%5)}"
  end

  case (n%100).div(10)
  when 4 then roman += "XL"
  when 9 then roman += "XC"
  else roman += "#{'L' if t[2] >= 5}#{'C' * (t[2]%5)}"
  end

  case t[3]
  when 4 then roman += "IV"
  when 9 then roman += "IX"
  else roman += "#{'V' if t[3] >= 5}#{'I' * (t[3]%5)}"
  end
end

新しい知識を得たり（トポロジカルソートなんて初めて使った）

require 'tsort'

class Hash
  include TSort
  alias tsort_each_node each_key
  def tsort_each_child(node, &block)
    fetch(node).each(&block)
  end
end

hash = Hash.new
log = File.read('keylog.txt').split.map{|k| k.split(//).map(&:to_i)}

log.each do |l|
  hash[l[0]] = [] unless hash[l[0]]
  hash[l[0]] << l[1] unless hash[l[0]].include?(l[1])
  hash[l[1]] = [] unless hash[l[1]]
  hash[l[1]] << l[2] unless hash[l[1]].include?(l[2])
end

hash[0] = []

puts hash.tsort.reverse.join

するのは楽しい。でも数学的に美しい解き方が見つからなくて、無理矢理に近い形で解いたとしてももちろんクリアにはなるけどイマイチ腑に落ちない。

プログラミングの腕ってプログラムしていないとどんどん落ちていくものだと実感する。もうC言語でプログラミングなんてネットで検索しながらじゃないと厳しいだろうなぁ（笑）