Python:递归一维游戏(Leap Current Index (N) 次重复向右或向左直到找到列表的最后一个索引)

Question

考虑这个输入列表:

Index:       0, 1, 2, 3, 4, 5, 6, 7, 8

Input List:  1, 2, 6, 3, 2, 2, 1, 3, 1

---

这是我第一次使用stack overflow提问，所以请原谅我在格式和简洁性方面的知识不足。

我有两个函数 move_right() 和 move_left() 从列表的初始位置向右或向左移动。每次调用 right 或 left 函数时，变量 current_index 和 current_element 都会更新。

从我的列表 1 中索引为 0 的第一个元素开始，move_right() 函数替换并打印当前索引通过向右移动当前元素的次数(在本例中为 1)。 move_right() 函数调用更新了 current_index = 1。 move_right() 的下一个函数调用会更改 current_index = 3，因为我们将当前元素向右移动 2 次。如果 move_right() 函数在列表范围内保持返回 true，我的递归函数末尾将打印的位置是:

0, 1, 3, 6, 7

---

move_left() 函数与上面的算法相同，但方向相反。查看这段代码:

global game_board, start_position, end_postion, current_element, current_index, previous_index, repeated_index

game_board = input().split()

try:
        for index in range(len(game_board)):
                game_board[index] = int(game_board[index])
except ValueError:
        print ('Error: Invalid list of numbers!')
        sys.exit(1)

    previous_index = 0
    current_index = previous_index
    start_position = game_board[0]
    end_position = len(game_board)-1
    current_element = game_board[current_index]
    repeated_index = []

    def move_right():
            global current_index
            global current_element
            global previous_index
            global repeated_index
            # Track repeated indexes on seperate list
            repeated_index.append(current_index)
            current_element = game_board[current_index]
            right_sum = 0
            # Increment current element times to right 
            for right_sum in range(0, current_element):
                    right_sum += 1
            previous_index = right_sum
            current_index += right_sum
            right_sum = 0
            if (current_element == 0):
                    return False
            # Return true unless out of range (right direction)
            if (current_index <= end_position):
                    print(current_index, end = ' ')
                    return True
            else:
                    return False

    def move_left():
            global current_index
            global current_element
            global previous_index
            global current_new_index
            # Access to current new element
            current_new_index = current_index - previous_index
            current_element = game_board[current_new_index]
            left_sum = 0
            # Traverse in negative direction
            for left_sum in range(0, current_element):
                    left_sum += 1
            previous_index = current_new_index
            current_new_index -= left_sum
            left_sum = 0
            if (current_element == 0):
                    return False
            if (current_new_index < 0):
                    return False
            # Return true unless out of bounds (left direction)
            if (previous_index >= start_position):
                    print(current_new_index, end = ' ')
                    current_index = current_new_index
                    return True
            else:
                    return False

---

现在下面这个move_right()函数的递归函数遍历列表，直到我们超出列表的范围。根据使用逻辑 or 运算符的 if 条件中的优先顺序，现在调用 move_left() 函数，因为 move_right() 函数是错误的。现在我们在列表中向左移动以找到到达最终索引或列表结束位置的解决方案的不同路径，在我们的例子中是 8。这个递归函数只向左移动一次，然后继续向右移动尽可能多的次数，直到我们到达最终数字或超出界限。这是递归函数和输出:

    def can_win(): 
            # Lost the game if no possible actions from current postion
            for repeat in repeated_index:
                    if (current_element <= 0 or current_index > end_position or repeat == current_index or current_index < 0):     
                            print('<br />', 'No more actions possible! You lost! (Either out of bounds, or landed on a zero number, or stepped on a repeated number, or entered a negative number)')
                            print('<br />', '<br />')
                            sys.exit(0)
            # Won the game if last postion found
            if (current_index == end_position):
                    print('<br />', 'Landed on the last number! You won!')
                    print('<br />', '<br />')
                    sys.exit(0)
            once = True
            # Move right or left until both functions return false
            if (move_right() or move_left() or once == True):
                    can_win()
                    once = False

if (current_element <= 0):
            print('<br />', 'You lost! (First number is either negative or zero!)')
            print('<br />', '<br />')
            sys.exit(0)
if (game_board):
            print('List of positions:', current_index, end = ' ')
            can_win()

---

Resulting Output: 0, 1, 3, 6, 7, 4, 6 (No more actions possible! You lost!)

虽然实际输出应该是:

Real Output: 0, 1, 3, 6, 7, 4, 2, 8 (Landed on the last number! You won!)

---

我想不出任何其他替代方案，因为目标是使用递归函数找到解决方案。使用这种方法的第一种做法显然行不通:

if (move_right() or move_left() or once == True):
            can_win()

---

下一步是调用 move_left() 函数两次，然后继续调用 move_right() 函数以找到最后一个索引。如果有一组不同的数字，那么我需要尽可能多地多次调用 move_left() 函数以找到任何数字列表中的最后一个数字。如果我可以一直遍历到正确方向的尽头，每次可能向左移动，那么我就可以打印正确的输出。如果没有可能的解决方案，那么用户实际上输了游戏。如果有人能帮我解决这个问题，我将不胜感激!如果您有任何其他问题，请告诉我。

Answer 1

您可以使用带有参数的递归函数，该函数以索引和最后一个索引对的形式跟踪路径，如果索引到达板的末尾，则产生路径中的索引，如果索引是，则避免进一步递归超出范围，如果当前图 block 为 0，或者如果建议的下一个索引和当前索引对已经是路径的一部分:

def move(board, path=((0, None),)):
    index = path[-1][0]
    if index == len(board) - 1:
        yield [i for i, _ in path]
    if 0 <= index < len(board) and board[index]:
        for direction in 1, -1:
            new = index + board[index] * direction
            if (new, index) not in path:
                yield from move(board, path + ((new, index),))

使得下面的测试用例:

game_boards = [
    [1, 2, 6, 3, 2, 2, 1, 3, 1],
    [1, 1, 1, 2, 4, 1, 1, 7, 0],
    [1, 2, 3, 1, 10, 2, 10, 0],
    [1, 2, 3, 1, -1, 2, 10, 0],
    [1, 2, 6, 3, 2, 2, 1, 3, 1],
    [3, 3, 3, 2, 2, 2, 0], # the same index might be worth revisiting
    [3, 3, 4, 3, 3, 3, 4], # there could be valid paths beyond the end
    [2, 4, 3, 5]
]
for game_board in game_boards:
    print('%s => %s' % (game_board, list(move(game_board))))

将输出:

[1, 2, 6, 3, 2, 2, 1, 3, 1] => [[0, 1, 3, 6, 7, 4, 2, 8], [0, 1, 3, 6, 5, 7, 4, 2, 8]]
[1, 1, 1, 2, 4, 1, 1, 7, 0] => [[0, 1, 2, 3, 5, 6, 5, 4, 8], [0, 1, 2, 3, 5, 4, 8]]
[1, 2, 3, 1, 10, 2, 10, 0] => [[0, 1, 3, 2, 5, 7]]
[1, 2, 3, 1, -1, 2, 10, 0] => [[0, 1, 3, 4, 3, 2, 5, 7], [0, 1, 3, 4, 5, 7], [0, 1, 3, 4, 5, 3, 2, 5, 7], [0, 1, 3, 2, 5, 7], [0, 1, 3, 2, 5, 3, 4, 5, 7]]
[1, 2, 6, 3, 2, 2, 1, 3, 1] => [[0, 1, 3, 6, 7, 4, 2, 8], [0, 1, 3, 6, 5, 7, 4, 2, 8]]
[3, 3, 3, 2, 2, 2, 0] => [[0, 3, 5, 3, 1, 4, 6], [0, 3, 1, 4, 6]]
[3, 3, 4, 3, 3, 3, 4] => [[0, 3, 6], [0, 3, 6, 2, 6]]
[2, 4, 3, 5] => []

编辑:由于您现在在评论中提到您希望索引而不是移动，因此我修改了上述解决方案以仅跟踪路径中的索引:

def move(board, path=(0,)):
    index = path[-1]
    if index == len(board) - 1:
        yield path
    if 0 <= index < len(board) and board[index]:
        for direction in 1, -1:
            new = index + board[index] * direction
            if new not in path:
                yield from move(board, path + (new,))

因此给定与第一个解决方案相同的测试用例，输出:

[1, 2, 6, 3, 2, 2, 1, 3, 1] => [(0, 1, 3, 6, 7, 4, 2, 8), (0, 1, 3, 6, 5, 7, 4, 2, 8)]
[1, 1, 1, 2, 4, 1, 1, 7, 0] => [(0, 1, 2, 3, 5, 4, 8)]
[1, 2, 3, 1, 10, 2, 10, 0] => [(0, 1, 3, 2, 5, 7)]
[1, 2, 3, 1, -1, 2, 10, 0] => [(0, 1, 3, 4, 5, 7), (0, 1, 3, 2, 5, 7)]
[1, 2, 6, 3, 2, 2, 1, 3, 1] => [(0, 1, 3, 6, 7, 4, 2, 8), (0, 1, 3, 6, 5, 7, 4, 2, 8)]
[3, 3, 3, 2, 2, 2, 0] => [(0, 3, 1, 4, 6)]
[3, 3, 4, 3, 3, 3, 4] => [(0, 3, 6)]
[2, 4, 3, 5] => []