Python: Sorting Marbles with switch and rotate - Need help in optimizing a working solution

Question

I have made a couple modifications to the switch/rotate routine for the classic Marbles game. The modifications are

1. Using a random_select method that can help pick either switch or rotate
2. Create a method called first_two that rotates l[0] and l[1] and avoids the switch as that would be counter productive

With these two changes, I was able to significantly cut down the number of steps (by a factor of 5+)

I am trying one final enhancement; ie using a control_list to avoid duplicates. This is to skip combinations that already exist. And this is where I need help.

Game Rules: In a particular board game, there is exactly one row and it comprises N spaces, numbered 0 through N - 1 from left to right. There are also N marbles, numbered 0 through N - 1, initially placed in some arbitrary order. After that, there are two moves available that only can be done one at a time:

• Switch: Switch the marbles in positions 0 and 1.
• Rotate: Move the marble in position 0 to position N - 1, and move all other marbles one space to the left (one index lower).

The objective is to arrange the marbles in order, with each marble i in position i.

-- Invocation: MarblesBoard(3,6,7,4,1,0,8,2,5)

Code for both Classes is below. I have tried a variation of https://stackoverflow.com/questions/54840758/sorting-numbers-with-mix-of-switch-and-rotate-in-python

import random
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 " ".join(map(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):
 """
 Rotates item in position o to position N-1. All remaning items are moved as a result (1 step to the left)
 """
 self.board = self.board[1:] + [self.board[0]]
 return self.board
 
 def is_solved(self):
 return self.board == sorted(self.board)
 
 def random_select(self):
 # used a random generator for True/False -- used to select Switch or Rotate
 return random.choice([True, False])
 def first_two(self):
 return self.board[0] < self.board[1]

class Solver:
 """solves the marble sorting game when given a marble board as input"""
 def __init__(self, marbles_board):
 self.marbles_board = marbles_board
 
 def solve(self):
 steps = 0
 myboard = self.marbles_board
 control_list = []
 control_list.append(str(myboard))
 print(control_list)
 while not self.marbles_board.is_solved():
 if self.marbles_board.first_two():
 self.marbles_board.rotate()
 if str(self.marbles_board) in control_list: pass
 else:control_list.append((str(self.marbles_board)))
 if self.marbles_board.is_solved(): break
 else:
 self.marbles_board.switch()
 if str(self.marbles_board) in control_list: pass
 else:control_list.append((str(self.marbles_board)))
 if self.marbles_board.is_solved(): break
 if self.marbles_board.random_select():
 self.marbles_board.rotate()
 if str(self.marbles_board) in control_list: pass#self.marbles_board.switch()
 else:control_list.append((str(self.marbles_board)))
 if self.marbles_board.is_solved(): break
 
 steps += 1
 print(control_list)
 print(f"Number of steps: {steps}")
```

• AJNeufeld: Please include a description of what the "Marble game" is, what are the rules, etc.
• Reinderien: Please also include invocation. There is no entry point here, and no indication of what marble_sequence needs to contain.
• gaurav8936: Thanks for the comments - I have updated the description with the rules and the invocation. Hope that clarifies
• Reinderien: I don't understand the meaning of omitting a move from the control list if it's a duplicate. This represents a physical process: there are only two moves, and those moves are applied in sequence. Why would a move be omitted from the control list when it's a duplicate, even though in reality it will have been applied anyway?

Answer 1

Algorithm Complexity

You have \$N\$ marbles, which may appear in any of \$N!\$ permutations. Your solver may not visit all of the \$N!\$ states, but it gives us the size of the search space.

At each state, you call self.marbles_board.is_solved(), which tests self.board == sorted(self.board). Since each sort is \$O(N \log N)\$, and we do the sort at each state, the overall complexity of the algorithm would be \$O(N! \cdot N \log N)\$.

We would characterize this a "very slow" algorithm.

We can significantly speed this up by realizing sorted(self.board) will return the same value every time: \$[0, 1, 2, 3, ... N-1]\$. We don’t need to repeatedly sort the board; we can sort it once, and store the result as the solved_state:

class MarblesBoard:
 def __init__(self, marbles_sequence):
 self.board = list(marbles_sequence)
 self.solved_state = sorted(self.board)
 def is_solved(self):
 return self.board == self.solved_state

Alternately, you can use the condition "each marble i in position i" directly:

 def is_solved(self):
 return all(marble == position for position, marble in enumerate(self.board))

Without the sort at every step, the algorithm will be closer to \$O(N!)\$.

Avoiding Duplicates

 if str(self.marbles_board) in control_list: pass
 else:control_list.append((str(self.marbles_board)))

First, this is horrible coding practice. Never put the statements on the same line after the colon. The following is much more readable:

 if str(self.marbles_board) in control_list:
 pass
 else:
 control_list.append((str(self.marbles_board)))

Better would be to avoid the "pass" statement:

 if str(self.marbles_board) not in control_list:
 control_list.append((str(self.marbles_board)))

Still better would be to avoid the second call to str(self.marbles_board) which wastes time.

 state = str(self.marbles_board)
 if state not in control_list:
 control_list.append(state)

Even better would be to add the state to a set instead of appending it to a list, since state not in control_list would be \$O(1)\$ time, instead of \$O(N)\$.

Further analysis shows you are only using control_list for printing; you aren’t actually controlling anything with it. Therefor, it can be removed entirely:

 while not self.marbles_board.is_solved():
 if self.marbles_board.first_two():
 self.marbles_board.rotate()
 if self.marbles_board.is_solved():
 break
 else:
 self.marbles_board.switch()
 if self.marbles_board.is_solved():
 break
 if self.marbles_board.random_select():
 self.marbles_board.rotate()
 if self.marbles_board.is_solved():
 break
 steps += 1
 print(f"Number of steps: {steps}")

Or moving common statements out of the if...else... blocks:

 while not self.marbles_board.is_solved():
 if self.marbles_board.first_two():
 self.marbles_board.rotate()
 else:
 self.marbles_board.switch()
 if self.marbles_board.is_solved()
 break
 if self.marbles_board.random_select():
 self.marbles_board.rotate()
 if self.marbles_board.is_solved():
 break
 steps += 1
 print(f"Number of steps: {steps}")

Bug: miscounted steps

With the clutter removed, we can now see that each loop will either do the rotate or switch action (1-step), and the optionally do the rotate step. So, each time through the loop, we do either 1 or 2 step, yet at most we count 1.

Yes, at most. A move which results in self.board.is_solved() being True breaks out of the loop without counting that move.

Organization

MarblesBoard is a function which deals with the state of the marble board. It can rotate the marbles, swap the first two marbles, and report if the first to marbles are ordered properly.

What is random_select()? Seems to have nothing to do with the MarblesBoard, and more likely should be part of Solver.

Rotate

To rotate the board, you use slicing, which copies all of the elements of the board. \$O(N)\$ time complexity.

It would be better to use a collections.deque, which supports \$O(1)\$ push/pop at either end. Rotate would become: self.board.append(self.board.popleft()), or simply self.board.rotate(-1).

Improvements

Consider MarblesBoard([6, 0, 1, 2, 3, 4, 5]). It requires one move to solve: a "rotate". What does your algorithm do? Since 6 < 0 is False, first_two() return False and the first move becomes a "switch"! Whoops. Can you think of a better heuristic?

Answer 2

If marble_sequence is indeed a sequence, then

a. your claim that invocation looks like MarblesBoard(3,6,7,4,1,0,8,2,5) is incorrect because the parameter is not *variadic, and

b. you don't need the comprehension [x for x in marble_sequence]; you only need to construct a tuple(). It should be a tuple and not a list.

Don't write "%r " % (self.board); just repr(self.board). However, given how you're using this function, the entire function should go away and you should use self.board directly as the board state representation.

Don't return anything from switch and rotate; those functions should choose to either mutate a member variable or return a changed copy, not both.

is_solved and first_two can be @property. first_two is a slightly confusing name and may be more clear as first_two_sorted.

solve(), let's assume, should be most useful as a function that yields all of the steps in the solution, doesn't print, and doesn't skip any step even if it's been seen before. With this in mind, it would be best expressed as two functions: a generator that produces unlimited steps, and a control loop that terminates once the solution is found.

The algorithm itself is pretty rough but AJNeufeld has already correctly commented on that. For illustration, I show your original algorithm but expressed in a slightly saner way.

Suggested

import random
from typing import Iterable, Iterator
def random_select() -> bool:
 # used a random generator for True/False -- used to select Switch or Rotate
 return random.choice((True, False))
class MarblesBoard:
 """creates a marble board with number marbles in specific spots"""
 def __init__(self, marble_sequence: Iterable[int]) -> None:
 self.board = tuple(marble_sequence)
 self.is_target = tuple(sorted(self.board)).__eq__
 def __str__(self) -> str:
 return " ".join(map(str, self.board))
 def __repr__(self) -> str:
 return repr(self.board)
 def switch(self) -> None:
 """switch the marbles in position 0 and 1"""
 self.board = self.board[1::-1] + self.board[2:]
 def rotate(self) -> None:
 """
 Rotates item in position o to position N-1. All remaining items are moved as a result (1 step to the left)
 """
 self.board = self.board[1:] + self.board[:1]
 @property
 def is_solved(self) -> bool:
 return self.is_target(self.board)
 @property
 def first_two_sorted(self) -> bool:
 return self.board[0] < self.board[1]
class Solver:
 """solves the marble sorting game when given a marble board as input"""
 def __init__(self, marbles_board: MarblesBoard) -> None:
 self.marbles_board = marbles_board
 def steps(self) -> Iterator[tuple[int, ...]]:
 board = self.marbles_board
 while True:
 if board.first_two_sorted:
 board.rotate()
 else:
 board.switch()
 yield board.board
 if random_select():
 board.rotate()
 yield board.board
 def solve(self) -> Iterator[tuple[int, ...]]:
 steps = self.steps()
 while not self.marbles_board.is_solved:
 yield next(steps)
def test() -> None:
 # random.seed(0)
 board = MarblesBoard((3, 6, 7, 4, 1, 0, 8, 2, 5))
 solver = Solver(board)
 steps = tuple(solver.solve())
 print(len(steps))
if __name__ == '__main__':
 test()