2012年6月24日日曜日

Project Euler-Problem14をgroovyで解いてみる

問題

正の整数に以下の式で繰り返し生成する数列を定義する。

n → n/2 (n が偶数)

n → 3n + 1 (n が奇数)

13からはじめるとこの数列は以下のようになる。

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
13から1まで10個の項になる。 この数列はどのような数字からはじめても最終的には 1 になると考えられているが、まだそのことは証明されていない(コラッツ問題)

さて、100万未満の数字の中でどの数字からはじめれば一番長い数列を生成するか。

注意: 数列の途中で100万以上になってもよい

問題を解いたプログラム

最初何も考えずに作ったら終わる気配が全くなく・・・。次にListで生成した数列自体をキャッシュしたが、全く意味がなく。最後に、Hashに生成した数列のサイズをキャッシュするように。これでなんとか処理が終わるようになった。
result = [:]

def next(long num) {
  num % 2 == 0 ? num / 2 : num * 3 + 1
}

def makeNumSeq(long num) {
  def count = 0
  long temp = num
  while (temp > 1) {
    temp = next(temp)
    def cacheCount = result[temp]
    if (cacheCount) {
      count += cacheCount
      break
    }
    count++
  }
  result[num] = count
}

(999999..1).each {it
  makeNumSeq(it)
}

println result.max {it.value}
時刻: