CheckIO - Anagrams By Stacks

September 13, 2013   CheckIO , Programming , Python

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一次……