2
\$\begingroup\$

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}")
```
\$\endgroup\$
4
  • 3
    \$\begingroup\$ Please include a description of what the “Marble game” is, what are the rules, etc. \$\endgroup\$
    – AJNeufeld
    Commented Oct 12, 2022 at 6:35
  • 2
    \$\begingroup\$ Please also include invocation. There is no entry point here, and no indication of what marble_sequence needs to contain. \$\endgroup\$
    – Reinderien
    Commented Oct 12, 2022 at 13:36
  • \$\begingroup\$ Thanks for the comments - I have updated the description with the rules and the invocation. Hope that clarifies \$\endgroup\$
    – gaurav8936
    Commented Oct 12, 2022 at 16:14
  • \$\begingroup\$ 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? \$\endgroup\$
    – Reinderien
    Commented Oct 12, 2022 at 17:53

2 Answers 2

2
\$\begingroup\$

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?

\$\endgroup\$
0
2
\$\begingroup\$

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()
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.