息抜き

「1からスタートして与えられた整数nまで何回の操作でたどり着けるかこたえなさいに手をつけてみた。

16の扱いに問題がある。(1, 4)になったほしいのだが、(1, 2, 2)にしてしまう。まあ、opに4をいれればいいのだが、４乗は２乗の２乗だし・・・。opsからopを選んで作って試すというやり方なのだが、opの選び方が効率よく計算するときの鍵だろうなぁ、ということだけは見当がついた。それから単に目標値と現在の値の差で評価関数を組んでしまうと、243(3の５乗)みたいな数で256から減らしていこうとしてしまうので厄介。

おそらくはステップ数が進んでから調整しようとするほどペナルティがかかる評価関数を組む必要がありそうだ。
ひょっとしてこれは最寄のn乗数を発見する問題かなぁ？

123を計算させると、(1, 2, 1, 3, -1, -1)
121を計算させると、(1, 1, 2, 1, 1, 2)

'''
  find count of step to get N from 1 using 
  a) add 1
  b) sub 1
  c) i th pow of N 

'''
def decode(i):
  if i == -1:
    def op_dec(x):
      return x-1
    return op_dec
  elif i == 1:
    def op_inc(x):
      return x+1
    return op_inc
  elif i > 1:
    def op_pow(x):
      return pow(x, i)
    return op_pow
  else:
    assert False
  
def calc(xs, n):
  for op in xs:
    f = decode(op)
    print n
    n = f(n)
  return n


def gen_ix(n):
  '''\
  >>> gen_ix(1)
  ()
  >>> gen_ix(2)
  (1,)
  >>> gen_ix(3)
  (1, 1)
  >>> gen_ix(4)
  (1, 2)
  >>> gen_ix(5)
  (1, 2, 1)
  >>> gen_ix(10)
  (1, 1, 2, 1)

  '''
  ixs = {1:(True, ())}
  ops = (-1, 1, 2, 3, 5, 7, 11)
  while n not in ixs:# or not ixs[n][0]:
    xs = [(key, item) for key, item in ixs.items()]
    for i, (done, ix) in xs:
      for op in ops:
        f = decode(op)
        j = f(i)
        if j > 0 and j not in ixs:
          ixs.update({j: (False, ix + (op,))})

  return ixs[n][1]


#print gen_ix(10)
#print calc(gen_ix(10), 1)
#print gen_ix(16)
if __name__ == '__main__':
  import doctest
  doctest.testmod()