3 min read

http://www.checkio.org/mission/task/info/anagrams-by-stacks/python-27/

这个任务是incinerator的最后一个任务(截至Sep. 13. 2013),题目的要求从配图来看一目了然:

总结下来有这么几点:

  1. 1,2两个stack是单词长度;
  2. 0固定长度为1
  3. 只能移动最后一个字母(这是废话,要不怎么用stack)


我们当然可以设置三个stack,然后递归解决。不过我想了想,既然要求的是——最小步数,而非“成功的达成目标”。那么如果自己写递归还要比较各个方法的优劣的问题,太麻烦了〜如果把最小步数理解成最短路径,这不就变成寻路了吗!而且寻路算法,只要拿出A*就好了啊!
至于A*,我以前题目里面用过的线程的代码可以拿出来:

有了这个,我们只需要实现puzzle和node就可以了。而puzzle相当简单:
class AnagramsPuzzle(AStar):
   """ description """
   def __init__(self, goal):
       super(AnagramsPuzzle, self).__init__(goal)

   def Heuristic(self, Node):
       return 0

   def getResult(self, Node):
       result = []
       while Node.Parent:
           result.append(Node.Comment)
           Node = Node.Parent
       result.reverse()
       return ','.join(result)这里需要说到两点:

  1. Heuristic在不明确会不会对分析造成影响的前提下,建议直接返回0即可
  2. Node.Comment是每次移动对应的命令,在Node里面会看到。

下面就是要实现node了。node最核心的地方就是每个节点可能有那些下一步,虽然重要,但是实现难度并不大。代码如下:class AnagramsPuzzleNode(AStarNode):
   """ description """
   def __init__(self, Status, G, Parent):
       super(AnagramsPuzzleNode, self).__init__(Status, G, Parent)

   def PossibleNextNodes(self):
       Result = []
       one_stack = self.Status[0]
       zero_stack = self.Status[1]
       two_stack = self.Status[2]

       if last_char(one_stack)[0] != '':
           # 10
           if last_char(zero_stack)[1] != 0:
               new_one_stack = deepcopy(one_stack)
               new_zero_stack = deepcopy(zero_stack)
               new_zero_stack[0] = last_char(new_one_stack)[0]
               new_one_stack[last_char(new_one_stack)[1]] = ''
               temp = [new_one_stack, new_zero_stack, two_stack]
               new_node = AnagramsPuzzleNode(temp, self.G + 1, self)
               new_node.Comment = '10'
               Result.append(new_node)
           # 12
           if last_char(two_stack)[1] != len(two_stack)-1:
               new_one_stack = deepcopy(one_stack)
               new_two_stack = deepcopy(two_stack)
               new_one_stack[last_char(one_stack)[1]] = ''
               new_two_stack[two_stack.index('')] = last_char(one_stack)[0]
               temp = [new_one_stack, zero_stack, new_two_stack]
               new_node = AnagramsPuzzleNode(temp, self.G + 1, self)
               new_node.Comment = '12'
               Result.append(new_node)
       if last_char(zero_stack)[0] != '':
           # 01
           if last_char(one_stack)[1] != len(one_stack)-1:
               new_one_stack = deepcopy(one_stack)
               new_zero_stack = deepcopy(zero_stack)
               new_one_stack[one_stack.index('')] = zero_stack[0]
               new_zero_stack[0] = ''
               temp = [new_one_stack, new_zero_stack, two_stack]
               new_node = AnagramsPuzzleNode(temp, self.G + 1, self)
               new_node.Comment = '01'
               Result.append(new_node)
           # 02
           if last_char(two_stack)[1] != len(two_stack)-1:
               new_two_stack = deepcopy(two_stack)
               new_zero_stack = deepcopy(zero_stack)
               new_two_stack[two_stack.index('')] = zero_stack[0]
               new_zero_stack[0] = ''
               temp = [one_stack, new_zero_stack, new_two_stack]
               new_node = AnagramsPuzzleNode(temp, self.G + 1, self)
               new_node.Comment = '02'
               Result.append(new_node)
       if last_char(two_stack)[0] != '':
           # 21
           if last_char(one_stack)[1] != len(one_stack)-1:
               new_two_stack = deepcopy(two_stack)
               new_one_stack = deepcopy(one_stack)
               new_one_stack[new_one_stack.index('')] = last_char(new_two_stack)[0]
               new_two_stack[last_char(new_two_stack)[1]] = ''

               temp = [new_one_stack, zero_stack, new_two_stack]
               new_node = AnagramsPuzzleNode(temp, self.G + 1, self)
               new_node.Comment = '21'
               Result.append(new_node)
           # 20
           if last_char(zero_stack)[1] != 0:
               new_two_stack = deepcopy(two_stack)
               new_zero_stack = deepcopy(zero_stack)
               new_two_stack[last_char(two_stack)[1]] = ''
               new_zero_stack[0] = last_char(two_stack)[0]
               temp = [new_one_stack, zero_stack, new_two_stack]
               new_node = AnagramsPuzzleNode(temp, self.G + 1, self)
               new_node.Comment = '20'
               Result.append(new_node)
       return Result请先不要吐槽这个丑陋的代码,确定有简化的写法来实现,不过在说tricky方法之前,这个无非是最直观的代码了。把实现和优化分开还是比较简单的。

有了以上的代码,我们剩下的就是定义开始和结束状态,然后默默的等结果就行啦
def checkio(data):
   """ description """
   start_position, end_position = data.split('-')
   start_position = [list(start_position), [''], ['']*len(list(start_position))]
   end_position = [['']*len(list(end_position)), [''], list(end_position)]
   puzzle = AnagramsPuzzle(end_position)
   start_node = AnagramsPuzzleNode(start_position, 0, None)
   return puzzle.search(start_node)
好啦,综合起来,完整的代码如下:

说起来我要吐槽一下,这个代码的check实在太慢了——20多分钟一次完整的check,完成check后如果publish,他又要在check一次……

Ken lai

Read more posts by this author.