Color Ball Sorting - LO Man Hei

# Algorithm to the Color Ball Sorting Game

#### Background

- Once upon a time, I accidentally installed a mobile game called Color Ball Sorting. I thought it is a good exercise for me to program the solving algorithm.
 
 - It was first written in Python and was later rewritten in JavaScript.

#### Game Description

1. The game is initialize with **n** tubes with capacity **c**. **m** of the **n** tubes are fully filled with **m** shuffled color of ball.

- - The following set is initialize with **n = 4, c = 4, m = 3**.
 - - ![Color Ball Sort 1!](/assets/images/blog/color-ball-sort-1.png "Color Ball Sort 1")
 
2. The player is allowed to move one of the balls from the top of the tubes to either an empty tube, or a non-fully-filled tube with the color of the upper ball matches the color of the taken ball.

- - Moving a yellow ball to an empty tube.
 - - ![Color Ball Sort 2!](/assets/images/blog/color-ball-sort-2.png "Color Ball Sort 2")
 
 
 - - Moving a yellow ball to a non-fully-filled tube.
 - - ![Color Ball Sort 3!](/assets/images/blog/color-ball-sort-3.png "Color Ball Sort 3")
 
3. The goal is to sort the color balls into separate tubes.

- - Same color of balls in the same tube
 - - ![Color Ball Sort 4!](/assets/images/blog/color-ball-sort-4.png "Color Ball Sort 4")
 
#### Solution

##### Code

1\. Define classes for the tubes and the game:
```python
# Define the class of Tube
class Tube:
    def __init__(self, volumn, balls):
        self.balls = balls
        self.volumn = volumn      
        
    def drop(self):
         return self.balls.pop() if self.balls != 0 else False
        
    def add(self, ball):
        self.balls.append(ball)
        return
    
    def last_ball(self):
        return self.balls[-1] if len(self.balls) != 0 else None
    
    def consecute_color(self):
        if len(self.balls) == 0:
            return 0
        result = 0
        for _ in self.balls[::-1]:
            if _ == self.last_ball():
                result += 1
            else:
                return result
        return result
    
    def free_space(self):
        return self.volumn - len(self.balls)  
    
# Define the class of Game  
class Game:
    def __init__(self, tube_size, tubes_data):
        tubes = [ Tube(tube_size,_) for _ in tubes_data]
        self.tubes = tubes
        self.max_score = sorted([len(_.balls) for _ in tubes])
        self.solution = []
        color_stat = {}
        for tube in tubes:
            for ball in tube.balls:
                if ball in color_stat:
                    color_stat[ball] += 1
                else:
                    color_stat[ball] = 1
        print(color_stat.values())
        
    def move(self, id_from, id_to, num_ball):
        for _ in range(num_ball):
            self.tubes[id_to].add(self.tubes[id_from].drop())
            
    def get_stat(self):
        return {
            "top_balls": [_.last_ball() for _ in self.tubes],
            "consecute_colors": [_.consecute_color() for _ in self.tubes],
            "free_spaces": [_.free_space() for _ in self.tubes]
        }
    
    def __repr__(self):
        return str([_.balls for _ in self.tubes])
    
    def get_tubes(self):
        return [_.balls for _ in self.tubes]
```

2\. Define functions for finding the solution:
```python
import copy
def reduce_list(input_list):
    a = input_list.copy()
    dropped_num = 0
    for i in range(1,len(a)):
        idx = i+dropped_num
        if a[idx][0] == a[idx-1][1] and a[idx][1] == a[idx-1][0]:
            a.pop(idx-1)
            dropped_num -= 1
        elif a[idx][0] == a[idx-1][1]:
            a[idx-1] = (a[idx-1][0],a[idx][1])
    return a

def iterate(game, max_score, solution, history_move = [], history_tubes = [], direction = 1):
    tube_indexes = list(range(len(game.tubes)))
    #random.shuffle(tube_indexes)
    for i in tube_indexes[::direction]:
        if ( game.tubes[i].last_ball() == None):
            continue
        selected_ball = game.tubes[i].last_ball()
        num_selected_ball = game.tubes[i].consecute_color()
        #print(selected_ball,num_selected_ball)
        for j in tube_indexes[::-direction]:
            if ( i == j or 
                game.tubes[j].free_space() < num_selected_ball or 
                game.tubes[j].last_ball() not in [None, selected_ball] ):             
                continue
            if ( game.tubes[j].consecute_color() == 0 and
                 game.tubes[i].consecute_color() == len(game.tubes[i].balls)):
                continue
            from_id = i
            to_id = j
            temp_game = copy.deepcopy(game)
            tube_i_remain = len(temp_game.tubes[i].balls) - num_selected_ball
            if ( temp_game.tubes[i].balls[:tube_i_remain] == temp_game.tubes[j].balls[:tube_i_remain] and
                 temp_game.tubes[j].consecute_color() <= temp_game.tubes[i].free_space() and
                 temp_game.tubes[i].consecute_color() > temp_game.tubes[j].consecute_color() > 0 ):
                from_id = j
                to_id = i
                num_selected_ball = temp_game.tubes[j].consecute_color()
            temp_game.move(from_id,to_id,num_selected_ball)
            current_score = sorted(temp_game.get_stat()["consecute_colors"]) 
            current_tubes = temp_game.get_tubes()
            if current_tubes in history_tubes:
                return False
            if current_score == max_score:     
                return history_move+[(from_id+1,to_id+1)]
            else:
                result = iterate(temp_game,max_score,solution,history_move+[(from_id+1,to_id+1)],history_tubes+[current_tubes])
                if result:
                    if isinstance(result, list):
                        solution.append(reduce_list(result))
                    if len(solution) > sum(max_score)**2:
                        return True
```

3\. Example Usage
```python
## Init Game
# Game(tube_size, tubes_data)
# tube_size is the capacity of the tubes, assumed every tube with the same capacity
# tubes_data is a list, storing the color code of the balls of every tubes from the bottoming to the top. Empty tube is []
game = Game(4,[[3,2,1,2],[2,3,1,1],[1,2,3,3],[],[]])

## Run the iterate function to find some solutions
iterate(game,game.max_score,game.solution)

## Get the best solution from the searched space
best_sol = sorted([reduce_list(_) for _ in game.solution] ,key=lambda x : len(x))[0]
print(len(best_sol))
print(best_sol)
```

#### Demo

**Link**: [Color Ball Sorting](https://lomanhei.com/apps/color-ball-sorting/) (written in JavaScript)

#### Source Code

**Link**: [Color Ball Sorting Jupyter Notebook](https://lomanhei.com/notebook/Color-Ball-Sorting/)

Back to Contents

Loading