nekoTheShadow’s diary

技術ブログとして始めたはずが、読書&愚痴ブログになりました(´・ω・`)

「コードトライアスロン」提出コードの振り返り&反省

 就活がつらいです(´・ω・`)最近はとくにエントリーシート提出の締め切りが続いていて本当につらい(´・ω・`)

 だれか代わりに書いてくれないかしら。「エントリーシート代行会社」とかあればもうかりそう。最近は、塾通いや習い事で忙しい子供向けの「宿題代行会社」なるものがあるのだから、「エントリーシート代行会社」があってもおかしくないよね。世間は空前のベンチャー企業ブームらしいし、だれか作りませんかね――作りませんよねそうですよね。

 ぐちはさておきそろそろ本題に入っていきます(現実逃避) 

コードトライアスロンとは

 コードトライアスロン……それは太古の昔より伝わる禁断の秘術……16世紀のはじめ、錬金術師パラケラススによって大成され、以降は《能力者》の一族にのみ伝えられてきたという……

 ――と冗談はさておき、「コードトライアスロン」はリクルートキャリア社が運営する「コード転職サイト」CodeIQの企画です。無料とはいえ会員制のサイトですのでここに詳しいことを書くことは控えておきます。詳しいことを知りたい方はCodeIQに登録しよう!(ステマ)

 というわけで今日はわかる人だけにしかわからない謎の記事になっています。

提出コード

 使用言語はRuby。2回目の提出で合格。primeライブラリは利用せず、実行時間は0.15秒でした。

感想と反省

 提出コードを張り付けるだけでもよいのですが、自分自身の復習のためにも解答手順についてメモを残しておきます。せっかくのブログですし。

第1問

 1問目はペラン数(フィードバックで知った)の問題。

 提出コードの解き方としてはまずペラン数の第n項(n>1)P(n)として、a(n),b(n),c(n)を次のように定義します。

  • a(n) = P(n)
  • b(n) = P(n+1)
  • c(n) = P(n+2)

 これを直感的に理解しやすいよう、実際の数字を使って表にしてみます。

n a(n) b(n) c(n)
2 2 3 2
3 3 2 5
4 2 5 5
5 5 5 7

 この表をよく眺めていると次のようなことがわかってくるはず。

  • a(n) = b(n-1)
  • b(n) = c(n-1)
  • c(n) = a(n-1) + b(n-1)

 これを実際のコードに落とし込んでやるだけです。

a,b,c = 2,3,2
(2..Float::INFINITY).each do |n| 
    a # これが第n項目のペラン数
    a,b,c = b,c,a+b
end

第2問

 第2問目は素因数分解の問題です。

 自然数nの素因数は2から\sqrt{n}の間の素数にあらわれますが、必ずしも「素数生成→試し割り」という順番をとる必要はありません。実は2から\sqrt{n}の間の「整数」で試し割りをするだけで大丈夫です。

 たとえばn=60として、実際に起こりうる過程を表に起こしてみます。

整数 n 素因数 試し割り後のn
2 60 2,2 15
3 15 2,2,3 5
4 5 2,2,3 5
5 5 2,2,3,5 5

 この方法だと合成数(上記の例なら4など)が混ざってきそうな気もしますが、実際には起こりえないということが確認できました。

 以上が提出コードでの考え方。ついで反省点ですが、大きく分けて2点。

  • 素因数分解専用(?)のメソッドを作ればよかった
  • 求める「最大の素因数」は必ず配列の一番最後になるにも関わらずArray#maxを使っている

 この反省点を生かして該当部分を書き換えてみました。

def prime_division(num)
    factors = []
    (2..Math.sqrt(num)).each do |factor|
        while num % factor == 0
            factors << factor
            num = num / factor
        end
        break if num == 1
    end
    factors
end

prime_division(p).last

第3問

 第3問目はみんな大好き素数の問題です。

 本問では素数の列挙が必要となります。そして素数列挙とくれば「エラトステネスのふるい」ですね。

 ではまず「べた」に「エラトステネスのふるい」を書いてみましょう。

def erato(upper_bound)
    nums = (2..upper_bound).to_a
    primes = []

    while nums[0] <= Math.sqrt(upper_bound)
        prime = nums.shift
        primes << prime
        nums.delete_if{|num| num % prime == 0}
    end

    primes + nums
end

 しかしこれでは列挙するまでに時間がかかってしまいます。しかも本問では最低2回は素数列挙を行わねばならないので、「エラトステネスのふるい」の高速化に取り組む必要があります。

 というわけで上記の書き方では何が「ボトルネック」になっていたのかをあぶりだしていくと――

  • 配列numsから先頭の要素nums[0]を配列primesに移しているのがまずい
    • ひとつの配列で完結する方法を考える
    • とどのつまり「素数でないものをふるいおとす」のが「エラトステネスのふるい」の肝だから、合成数と確定したものをnilに変えていくというのはどうだ
  • Array#delete_ifはレシーバの要素すべてにブロックを実行するが、明らかにむだ
    • 整数iが合成数とわかった場合、次いで合成数と確定するのは2i,3i,4i,...である
    • Range#stepなどを利用できないだろうか

 以上の反省点をふまえてできたのが提出コードのような「エラトステネスのふるい」です。

def eratosthenes(upper_bound)
    nums = (0..upper_bound).to_a
    nums[0] = nums[1] = nil
    nums.each do |num|
        next unless num
        break if num > Math.sqrt(upper_bound)
        (num*2..upper_bound).step(num){|idx| nums[idx] = nil}
    end
    nums.compact
end

 ――とここまであたかも自分で考えたかのように書いていますが、実は昔どこかで見たものの受け売り。ただ肝心の「元ネタ」がどこにあったのかを忘れちゃいました。てへぺろ(・ω<)。もしかしたらRuby以外のプログラミング言語で書かれた記事だったかも……

まとめ

 提出した当時は解けたことに舞い上がっていたので、時間がたって改めて見てみると結構反省点が多いですね。世にいう「賢者タイム」とはこのことかしら。

 ちなみに以下が反省点を生かして書き直したコードです。今の自分にとっては最善のコードですが――将来の自分が見たらどう思うことやら。「将来このコードを見て不出来を恥じる」そうなるよう勉強していきたいと思います。