磨剑(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。它是怎么转的?

处在中间时,我们有四种走法回到原地。

  1. +7,/2
  2. /2,+7
  3. x3,-5
  4. -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 = ["-53","+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:x3-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], idx4+i+1)) if i!=2 and children[i] == (end+5): dump(idx4+i+1) if onlyone: return

if name == "main": search()