python - Python：递归一维游戏（跳跃电流索引（N）次重复向右或向左直到找到列表的最后一个索引）

Question

考虑这个输入列表：

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

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

---

这是我第一次使用堆栈溢出来提问，所以请原谅我在格式和简洁方面缺乏知识。

我有两个函数move_right()，move_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 条件中的优先顺序，由于function 为 false ，因此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()尽可能多次地调用该函数以找到任何数字列表中的最后一个数字。如果我可以一直遍历到正确方向的尽头，每次可能向左移动，那么我可以打印正确的输出。如果没有可能的解决方案，则用户实际上输掉了游戏。如果有人可以帮助我解决这个问题，我将不胜感激！如果您还有其他问题，请告诉我。

标签： pythonpython-3.xrecursion

Answer 1

您可以使用带有参数的递归函数，该参数以索引和最后一个索引对跟踪路径，如果索引到达棋盘末端，则产生路径中的索引，如果索引超出范围，则避免进一步递归，如果当前图块为 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] => []