Python Solution of Puzzle #7 of Professor Layton: Azran Legacy

azran_legacy_puzzle_07.py

# sample input: [1, -1, 0, -1, -1]
# means one sailor on the first plank, the third plank
# is the one with nothing and the left are pirates.

# sample output:
# 00 [1, -1, 0, -1, -1]
# 01 [0, 1, 1, -1, -1]
# 02 [-1, -1, -1, 0, -1]
# 03 [-1, 0, 1, -1, -1]
# 04 [-1, -1, -1, 1, 0]
# 05 [-1, -1, 0, -1, -1]
# 06 [0, 1, -1, -1, -1]
# 07 [-1, -1, 1, 0, -1]
# 08 [-1, 0, -1, -1, -1]
# 09 [-1, -1, 1, 1, 0]
# 10 [-1, -1, 0, -1, 1]
# 11 [0, 1, -1, -1, 1]
# 12 [-1, -1, 1, 0, 1]
# 13 [-1, 0, -1, -1, 1]
# 14 [-1, 1, 1, 1, 0]
# 15 [0, -1, -1, -1, -1]
# 16 [-1, 1, 0, -1, -1]
# 17 [-1, 1, -1, 1, 0]
# 18 [0, -1, 1, -1, -1]
# 19 [1, 1, 0, -1, -1]
# 20 [1, 1, -1, 1, 0]
# 21 [0, -1, 1, -1, 1]
# 22 [1, 1, 0, -1, 1]
# 23 [1, 1, 1, 1, 0]

def is_finished(list_):
    return sum(list_) == len(list_) - 1

def jump(start, end, list_):
    start, end = (start, end) if start < end else (end, start)
    for j in range(start + 1, end):
        list_[j] = -list_[j]
    list_[start], list_[end] = list_[end], list_[start]

def is_in_history(move, stack) :
    for _move in stack:
        if _move == move:
            return True
    return False

def gen_moves(list_):
    list_ = list(list_)
    blank_plank = list_.index(0)
    for i in range(len(list_)):
        if abs(i - blank_plank) >= 2:
            jump(i, blank_plank, list_)
            yield list(list_)
            jump(blank_plank, i, list_)

def preorder_traverse(list_, stack=None):
    if is_finished(list_):
        return stack

    if not stack:
        stack = [list_]

    for move in gen_moves(list_):
        if not is_in_history(move, stack):
            stack.append(move)
            return preorder_traverse(move, stack)
    stack.pop()

if __name__ == "__main__":
    for i, val in enumerate(preorder_traverse([1, -1, 0, -1, -1])):
        print("%02d" % i, val)