磨剑(7)末日迷宫
Tags:
iq
题目
如下图所示的迷宫,左进右出。
有几条规则如下
- 在迷宫中行走,遇到算术,就执行。
- 可以转圈,但不能回头。
- 如果当前数字为奇数,不能走“÷2”这条路。
你能走出去吗?
分析
最初是从云风的博客看到它。原题在这里,http://www2.stetson.edu/~efriedma/holiday/2011/index.html。稍微手算几步,就感觉出来,这不是人脑能解决的。因为它实在是无规律可循。
这得靠计算机,将问题抽象为算法问题。
首先注意到两点:
<p>入口的2011是奇数,所以第一步只能走+7,变为2018。</p>
<p>出口的2012不是3的倍数,所以最后一步只可能是-5。</p>
那么问题可以演变成:
2018这个数字站在迷宫中间,转来转去回到中间值变成了2017。它是怎么转的?
处在中间时,我们有四种走法回到原地。
- +7,/2
- /2,+7
- x3,-5
- -5,x3
每种走法会产生一个新的数字,而每个新的数字又有四种走法产生四个数字。类推下来,正好对应了一棵四叉树。如果这棵树的某个叶子值正好等于2017,我们就找到了一个解。
# http://www2.stetson.edu/~efriedma/holiday/2011/index.html # http://shello.name/blog/iq-2012-maze import sys mazelist = [] mazelist.append(2018) total = 0 def dump(l): global total total = total + 1 solution = [] i = len(l)-1 while i>0: #print(i) if i%4 == 1: solution.append(" /2 +7") elif i%4 == 2: solution.append(" +7 /2") elif i%4 == 3: solution.append(" *3 -5") else: solution.append(" -5 *3") i = int((i-1)/4) print("solution %d: 2011 +7"%(total),end="") for i in range(len(solution)): print(solution.pop(), end="") print(" -5 = 2012") sys.exit() def search(): cursor = 0 while True: #print(len(mazelist)) node = mazelist[cursor] if node == None: mazelist.extend([None,None,None,None]) cursor = cursor + 1 continue # child 1 if cursor%4 == 2 or node%2 == 1: mazelist.append(None) else: subnode = node/2+7 if subnode == 2017: dump(mazelist) mazelist.append(subnode) # child 2 if cursor%4 == 1 or cursor == 0 or node%2 !=1: mazelist.append(None) else: subnode = (node+7)/2 if subnode == 2017: dump(mazelist) mazelist.append(subnode) # child 3 if cursor%4 == 0 and cursor != 0: mazelist.append(None) else: subnode = node*3-5 mazelist.append(subnode) # last step should not be -5, no need to check # child 4 if cursor%4 == 3: mazelist.append(None) else: subnode = (node-5)*3 if subnode == 2017: dump(mazelist) mazelist.append(subnode) cursor = cursor + 1
在网上看到一个解法,同样是用广度优先,同样是python,速度竟然比我快10倍。证明我的python只能算入门。我只是一个使用者,还不能称为掌握它。有时间要补一补性能和结构优化这些东西。
好了,忽然想起来,填个坑。下面的版本在同样电脑上,比原代码约20倍。
除了流程上略有优化外,最重要的进步在于对python语言本身的理解提高了,知道怎么写有效率的代码了。。。
import sys start=2011 end=2012 def dump(l): solution = [] i = l paths = ["-5*3","+7/2","/2+7","*3-5"] while i>0: solution.append(paths[i%4]) i = int((i-1)/4) print("{0}+7".format(start),end="") for i in range(len(solution)-1, -1, -1): print(solution[i], end="") print("-5 = %d (%d steps, searched %d nodes)"%(end, len(solution)*2+2, l)) def search(onlyone = True): p1 = lambda x,i:(x+7)/2 if x%2==1 and i%4 != 2 and i!=0 else None p2 = lambda x,i:x/2+7 if x%2==0 and i%4 != 1 else None p3 = lambda x,i:x*3-5 if i%4 != 0 else None p4 = lambda x,i:(x-5)*3 if i%4 != 3 else None cursor = 0 _maze = [(start+7,0)] # (node value, node idx) while 1: node,idx = _maze[cursor] cursor += 1 children = [p1(node,idx),p2(node,idx),p3(node,idx),p4(node,idx)] for i in range(4): if children[i]: _maze.append((children[i], idx*4+i+1)) if i!=2 and children[i] == (end+5): dump(idx*4+i+1) if onlyone: return if __name__ == "__main__": search()