把数字串变成2012玛雅密码

问题：

    玛雅密码是一串由0、1、2组成的密码，这串数字中如果包含2012，就可以解开末日的大门。给定一串由0、1、2组成的字符串，只有相邻的数字可以交换，求通过最少多少次变换可以得到玛雅密码，并给出这串密码。

 

思路：

    经过很久很久的尝试，放弃了一次性拼凑2012的想法，改用预处理得到所有数字范围中符合玛雅密码的部分，再递归遍历给定的数字串，得到该串所有可能的变换，并比较每个变换的结果需要的步数。

 

 

import sys
def find_all_transfers(str):
    result={}
    if len(str) == 0:
        result[str] = 0
    for index in range(0, len(str)):
        first=str[index]
        next_str=str[0:index] + str[index+1:len(str)]
        next_result=find_all_transfers(next_str)
        #print("next_result is: ")
        #print(next_result)
        for key in next_result:
            steps = index+next_result[key]
            if first+key not in result or steps < result[first+key]:
                result[first+key] = steps
    return result

 def build_map():
     map={}
     for i in range(0, 3**13-1):
         if check_2012(i):
             map[i] = True
     return map

 def check_2012(number):
     while number >= 59:
         if number%81 == 59:
             return True
         number /= 3
     return False

 def from_3_to_10(str):
     count=0
     iterator = range(0, len(str))
     for i in iterator:
         count+=int(str[-i-1])*(3**i)
     return count

 map = build_map()
 #print(map)
 str=raw_input("input string from 0,1,2: ")
 print("str is %s"%str)
 result = find_all_transfers(str)
 #print(result)
 min = sys.maxint
 min_key = ""
 for key in result:
     number = from_3_to_10(key)
     #print("value of %s is %d"%(key, number))
     if check_2012(number):
         #print("min is %d"%min)
         #print("result[key] is %d"%result[key])
         if min > result[key]:
             min = result[key]
             min_key = key
 print("min steps is %d, final string is %s"%(int(min), min_key))