Variation on Bubble Sort infinite loop error

Question

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.

The code I wrote works for the example posted on the problem (1 3 0 2), but when I add the extra number 4 randomly to the list the while loop never terminates. Looking at the sorted sequence, it seems to loop through a number of the same sequence repeatedly. I am not sure why it would work for one series but not the next one.

Bonus, I can't seem to figure out how to print the output as numbers separated by a space vs. as a list with brackets and commas. The problem asks that we print the output as numbers separated by spaces. Any help on that would be appreciated.

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)

With regards to output, the code works fine for the example output here:

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

However, if I add a 4 into the starting board:

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]

Note that 3 0 1 2 4 repeats as the second iteration and the last listed iteration. Due to the structure of the while loop, since the same sequence occurs, the same steps get implemented and the loop continues infinitely.

Your is_sorted method can simply be return self.board == sorted(self.board). Glad you didn't return False when the condition is True. — Pedro Rodrigues
– Pedro Rodrigues, Commented Oct 18, 2019 at 20:35

Paul M. · Accepted Answer · 2019-10-18 21:22:21Z

So, how is it a variation on Bubble Sort exactly? Most sorts have a way of keeping the sorted and unsorted data in separate areas, so that it's clear what has already been sorted. This sort doesn't seem to do that.

It looks the like the only criteria for a switch to occur is when board[0] > board[1]. Is that really all there is?

My suggestions for the code are below:

class MarblesBoard: def __init__(self, marble_sequence): self.board = [x for x in marble_sequence]

Isn't that a bit redundant? Why not:

class MarblesBoard: def __init__(self, marble_sequence): self.board = marble_sequence

I can't seem to figure out how to print the output as numbers separated by a space

That takes me to your implementation of __str__:

def __str__(self): return str(self.board)

That won't do. Take a look at the string I get back when I try to do something similar in the shell:

>>> str([1, 2, 3]) '[1, 2, 3]' >>>

You're better off using str.join:

def __str__(self): return " ".join(map(str, self.board))

Your switch method looks fine, except for the fact that you don't need to return anything from it. Just swap the elements and that's all you need to do.

If I've understood the rotate method correctly, it can be simplified:

def rotate(self): self.board.append(self.board.pop(0))

Again, you don't need to return anything from this function.

Your is_sorted can be simplified as well:

def is_sorted(self): return self.board == sorted(self.board)

I would also maybe add a method called should_rotate to your MarblesBoard class, which returns True or False depending on whether or not the solver should rotate or switch. It's meant to be used by the solver later:

def should_rotate(self): return self.board[0] > self.board[1]

Next, the Solver class. First the __init__ method:

By naming the parameter MarblesBoard, (the same name as the class), you are shadowing the identifier of the class - so I wouldn't call the parameter that. I think marbles_board is a better name.

Second, I don't see a good reason for explicitly making steps an instance variable in your __init__, since the only place you're using it is in the solve method. I would just get rid of it for now.

Third, I don't think it's a good idea to bind self.board to the board object of the MarblesBoard instance. If your Solver class basically just wraps around a MarblesBoard.board, you might as well not even make this class and just do all your solving in the MarblesBoard class. Again, you don't need to explicitly return from your __init__.

class Solver: def __init__(self, marbles_board): self.marbles_board = marbles_board

The solve can be simplified a bit as well:

def solve(self): number_of_steps = 0 while not self.marbles_board.is_sorted(): if self.marbles_board.should_rotate(): self.marbles_board.rotate() else: self.marbles_board.switch() number_of_steps += 1 print(f"Number of steps: {number_of_steps}")

It's kind of funny that your implementation of solve worked as well as it did, seeing as how you are passing in self (the Solver object) as an argument for the rotate and switch methods.

My understanding is that traditional bubble sort looks at index [0] and [1] and sorts that before moving to index [1] and [2] and sorts that...all the way until index [n-1] and [n]. Then it repeats this up to index [n-2] and [n-1] and so on. This version switches only index [0] and [1] but can shift down the list using the rotate function. I would liken it to a changed reference frame. Instead of moving the index down the line, you move the list.
Thanks for all your help! There is still an infinite while loop when add a 4, but this code is so much easier to read now.

Collectives™ on Stack Overflow

Variation on Bubble Sort infinite loop error

1 Answer 1

2 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Linked

Related