問題：
瑪雅密碼是一串由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)) 
