CodeIQの「西暦年を平成年に変換する数学パズル！」に挑戦しました

結果は最短ステップの７に至らず９ステップ。

[2]014->40[14]->40[19]6->40[3]616->(4096)16->6[41]6->6(16)(81)6->6(49)6->(676)->26

解答はプログラムで最短の候補を出してそれを手計算で更に縮める方法をとったが、どうやら出した最短の候補に最短ステップに至る解答がなかったらしく正解に至らず。

複数箇所を計算するプログラムを書くのがめんどくさくて１箇所だけを計算させてやる手段に逃げたのが間違いだったかな−と思うけど、それを実装する余裕がなかったのでまた機会があれば実装して再検討してみたい。

ちなみ最短候補を出すのに書いたのはこんなコードでした。

require "mathn"

MAX_DEPTH = 8
MAX_LENGTH = 9
ANS = "26"

def rec(ans,  records)
  return if records[ans].size > MAX_DEPTH
  return if ans.size > MAX_LENGTH

  ans.size.times do |i|
    (i...ans.size).each do |j|
      head = ans[0...i]
      part = ans[i..j].to_i
      last = ans[j+1..-1]

      next if ans[i] == '0' or part == 1

      if (sqrt = Math.sqrt(part)).is_a? Integer
        change = [head,  sqrt,  last].join
        if records.include?(change)
          next if records[change].size <= records[ans].size + 1
        end
        path = records[ans] + [head + "(#{part})" + last]
        records[change] = path
        if change == ANS
          puts (records[change] + [ANS]).join('->')
          return
        end
        rec(change,  records)
      end

      pow = part ** 2
      change = [head,  pow,  last].join
      if records.include?(change)
        next if records[change].size <= records[ans].size + 1
      end

      path = records[ans] + [head + "[#{part}]" + last]
      records[change] = path
      if change == ANS
        puts (records[change] + [ANS]).join('->')
        return
      end
      rec(change,  records)
    end
  end
end

ans = "2014"
rec(ans, {ans => []})

深さ（ステップ）上限と、幅（数字の長さ）上限を設けて計算量を減らしましたが、
深さか幅を上げようもんなら、計算量が増えて答え出すまでに時間がかかりすぎて断念した。

もっとアルゴリズムとか勉強せなあかん・・・