В конкретной настольной игре ровно одна строка содержит N пробелов, пронумерованных от 0 до N - 1 слева направо. Есть также N шариков, пронумерованных от 0 до N - 1, изначально расположенных в произвольном порядке. После этого доступны два хода, которые можно выполнять только по одному:
- Переключатель: переключение шариков в позиции 0 и 1.
- Поворот: перемещение мрамора впереместите 0 в положение N - 1 и переместите все остальные шарики на одну клетку влево (на один индекс ниже).
Цель состоит в том, чтобы расположить шарики по порядку, чтобы каждый мрамор i находился в положении i. .
Написанный мною код работает для примера, размещенного в задаче (1 3 0 2), но когда я добавляю дополнительное число 4 случайным образом в список, цикл while никогда не завершается. Глядя на отсортированную последовательность, кажется, что она циклически повторяет несколько одинаковых последовательностей. Я не уверен, почему это будет работать для одной серии, но не для следующей.
Бонус, я не могу понять, как распечатать вывод в виде чисел, разделенных пробелом, и в виде списка с квадратными скобками и запятыми. Проблема требует, чтобы мы распечатали выходные данные как числа, разделенные пробелами. Любая помощь по этому вопросу будет оценена.
class MarblesBoard:
"""creates a marble board with number marbles in specific spots"""
def __init__(self, marble_sequence):
self.board = [x for x in marble_sequence]
def __str__(self):
return str(self.board)
def __repr__(self):
return "%r " % (self.board)
def switch(self):
"""switch the marbles in position 0 and 1"""
self.board[0], self.board[1] = self.board[1], self.board[0]
return self.board
def rotate(self):
"""Move the marble in position 0 to position N - 1, and move all other marbles one space to the left (one index lower)"""
copy_board = self.board.copy()
copy_board[len(self.board)-1] = self.board[0]
for x in range(1, len(self.board)):
copy_board[x - 1] = self.board[x]
self.board = copy_board
return self.board
def is_sorted(self):
return self.board == sorted(self.board):
class Solver:
"""solves the marble sorting game when given a marble board as input"""
def __init__(self, MarblesBoard):
self.steps = 0
self.board = MarblesBoard.board
return
def solve(self):
n = len(self.board)
# print("n = ", n)
print(self.board)
while MarblesBoard.is_sorted(self) == False:
if self.board[0] > self.board[1]:
MarblesBoard.rotate(self)
print(self.board)
self.steps += 1
else:
MarblesBoard.switch(self)
print(self.board)
self.steps += 1
print("total steps: ", self.steps)
Что касается вывода, код отлично работает для примера вывода здесь:
board2 = MarblesBoard((1,3,0,2))
solver = Solver(board2)
solver.solve()
[1, 3, 0, 2]
[3, 1, 0, 2]
[1, 0, 2, 3]
[0, 2, 3, 1]
[2, 0, 3, 1]
[0, 3, 1, 2]
[3, 0, 1, 2]
[0, 1, 2, 3]
total steps: 7
Однако, если я добавлю 4 в стартовую плату:
board2 = MarblesBoard((1,3,0,2,4))
solver = Solver(board2)
solver.solve()
[1, 3, 0, 2, 4]
[3, 1, 0, 2, 4]
[1, 0, 2, 4, 3]
[0, 2, 4, 3, 1]
[2, 0, 4, 3, 1]
[0, 4, 3, 1, 2]
[4, 0, 3, 1, 2]
[0, 3, 1, 2, 4]
[3, 0, 1, 2, 4]
[0, 1, 2, 4, 3]
[1, 0, 2, 4, 3]
[0, 2, 4, 3, 1]
[2, 0, 4, 3, 1]
[0, 4, 3, 1, 2]
[4, 0, 3, 1, 2]
[0, 3, 1, 2, 4]
[3, 0, 1, 2, 4]
Обратите внимание, что 3 0 1 2 4 повторяется как вторая итерация и последняя из перечисленных итераций. Из-за структуры цикла while, поскольку происходит одна и та же последовательность, выполняются одни и те же шаги, и цикл продолжается бесконечно.