磨剑（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()