Charlie’s path to dEAth

从Davies大侠那里看到这个问题。这个问题是Thumbjive招聘工程师时要求随简历要一同提交。去年春天我还没毕业时，也解了这个问题，并且去Thumbjive面试了。当时也是用Python解的，面试我的法国工程师还很高兴我懂Python这个东西。实际上当时刚刚接触Python，现在看起来当时写的代码，实在是太不Python style了。

参考Davies的解法，总结一下这个问题的解决过程。

原题在Thumbjive网站的招聘页面中。

You have four colored cubes. Each side of each cube is a single color, and there are four colors: blue (B), red (R), green (G) and yellow (Y) Describing the six faces as front, back, left, right, top, bottom, the cube colors are:

The objective is to find ways to stack the four cubes as a vertical column so that each side of the column is showing all four colors.

有四个立方体，每个有六个面，涂上了四种颜色。要求摞成一个长条，并使其四个侧面都有四种不同的颜色。

我想这里主要要解决两个事情：

1. 立方体的表示。包括对其运动（旋转）的描述。并且要有一个描述立方体所有可能位置的集合，很容易看出每个立方体有24种可能的位置。
2. 对四个立方体所有可能位置进行排列，找出满足要求的排列。

对于1，Davies定义了两个立方体的动作，侧面转一圈和翻个。 然后汇成一个角的三个面作为初始状态，分别翻个，转一圈。正好得到了24种可能位置。比我当时考虑的强，我定义了x,y轴两个方向的旋转，并且用这两个动作连续旋转立方体，虽然能遍历所有的状态，但是显然有冗余。

我定义的旋转遍历：

# a serial of cube rotation
# make sure that the cube placed in all possible position
all_seq = [2,1,1,1,1, # following with 4 transform 1 means unchanged
2,1,1,1,1,
2,1,1,1,1,
2,1,1,1,1, # no position change
1,2,
1,1,1,1,
1,1,
1,1,1,1]

对于2，Davies枚举了所有可能排列，应该是一种宽度优先算法吧。如果只要求得到一个解，而不给出所有解的前提下，深度优先搜索能更快。不过我原来的脚本写得太滥了，运行速度明显慢很多。于是在他的脚本基础上，我写了个深度优先的算法solve2，可以代替Davies的solve来用。

def solve2(belows, aboves=[[]]):
”’ 060805, charlie, depth first solution ”’
belows = [b for b in belows] # copy object as a ‘pass-by-value’ argu of function
nodes = combine(aboves, turn(belows.pop(0)))
if not nodes: return False
if not belows: return nodes # all cubes placed
return reduce( lambda x,n: x or solve2(belows, [n]),
nodes , False )

实际效果上也没快多少，可能是搜索树的深度比较浅，没啥效果吧。

另外有写得不好的地方，就是搞不懂pass-by-value传参应该怎么弄比较好；和找不到一个代替逻辑运算符or的函数， 只好lambda了一个。

最后贴一下去年我写的脚本，不值得一看，权且留念。

#
# Describe a cube’s faces with a list as:
# [Left, Front, Right, Behind, Bottom, Top]
#
class Cube:
“A Cube with 6 colored faces.”
Color = [];
def __init__(self, ColorSeq):
self.Color = ColorSeq[2]+ColorSeq[0]+ColorSeq[3] \
+ColorSeq[1]+ColorSeq[5]+ColorSeq[4]
def Show(self):
return self.Color[:4]+’ - ‘+self.Color[4:]
def Rotate(self, direction):
if direction == 0:
return
elif direction == 1:
self.Color = self.Color[1:4] + self.Color[0] + self.Color[4:]
return
elif direction == 2:
tmp = self.Color[1]
self.Color = self.Color[0] +self.Color[5] + self.Color[2] \
+ self.Color[4] +self.Color[1] + self.Color[3]
#
# a serial of cube rotation
# make sure that the cube placed in all possible position
all_seq = [2,1,1,1,1, # following with 4 transform 1 means unchanged
2,1,1,1,1,
2,1,1,1,1,
2,1,1,1,1, # no position change
1,2,
1,1,1,1,
1,1,
1,1,1,1]

#
# main progress, includes all actions
def Start():
#
# 4 cubes with face colors initialized
cubes = [Cube(CS)
for CS in ['RBGYBY',
'RGGYBB',
'YBRGYR',
'YGBRRR'
# 'YRRGBB' # instead cube 4 mush easier for debug
] ]

#
# Rotate cube at certain level, then check if Stack reach the solution
# iterative called through the 4 cubes to construct a solution tree
def RotateStack(level): # level: 0~3, the four cubes
# print(’ ==— ‘+str(level)+’ — ==’)
for s in all_seq: # rotate this cubes(level)
cubes[level].Rotate(s)
if CheckStack(4,4): # check it out
print ‘bingo’
return True
if level < len(cubes)-1 and CheckStack(level+1,4):
# not leaf and possible solution branch
if RotateStack(level+1): # iterate function
return True

return False

#
# Check if each char in the string is unique
# called by CheckStack
def NoSame(s):
for c in s:
if s.find(c, s.find(c)+1) > 0:
return False
return True

#
# if the Stack reaches solution
# arguements for debug, reduced # of cubes and stack faces
def CheckStack(L=4, F=4):
## if L==4:
## print(’ …’ ) # print to debug the progress
## for c in cubes: print(c.Show() )
for f in range(F):
s = ”
for l in range(L):
s += cubes[l].Color[f]
if not NoSame(s):
return False
#print ‘checkStack: ‘ + str(L) + ‘,’+str(F)
return True

#
# the result
if RotateStack(0):
print ‘ … Got it! … ‘
print ‘cube color displayed as [front right behind left - bottom top]‘
for c in cubes: print(c.Show() )

else:
print ‘ … CAN NOT Get a Solution … ‘

if __name__ == “__main__”:
import time
t = time.time()
Start()
print time.time() - t

Filed by charlie at 6:50 pm under Engineer, Python