CodeIQ 挑戦の記録 : 「プライム・ホッパー」問題

CodeIQというサイトで問題に挑戦した記録です。

問題文を要約すると下記の通り

• ある素数に対し、変換１と２を次の通り定義する。
  変換１：元の数の右または左に1～9のいずれかの数字一つをつなげる。
  変換２：元の数の右端または左端の数字一つを取り除く。
  (ただし、最上位桁が0で始まる数値への変換は不可)
• 標準入力から素数とが与えられる。()
  素数から始めて、変換１または２を繰り返してを作る最小の交換回数を解答する。
  (途中の数は全て以下の素数)
• 

方針

幅優先探索を用いる。
qまでの配列を用意し、初期値として素数の項を0、合成数の項を-1とする。
題意の通り変換できる限り素数を変換していき、使用していない素数であればキューに追加し、幅優先探索で探索する。
同時に何回めの変換かを配列に記録する。
変換した数がqと一致すると配列に記入した回数を解答する。

実装(Ruby)

では、


Sponsored Link