Finding the shortest path to solve colored water sorting games

Question

So my aunt plays this now popular mobile game, shown in the picture below. She got stuck on a certain level and asked me if I can solve it. Knowing that I'm not smart enough to find patterns or a strategy to solve it, and knowing only the basics in Python, I thought I should try to solve it by writing a script, and that it's the perfect opportunity to learn new stuff, I started my journey of 2 weeks.

The game consists of a number of bottles, full with layers of different colored bottles, and generally one or two empty bottles, and the goal is to make all bottles uniformly colored. A move consists of taking a bottle full of at least on layer and pouring it in another bottle. Main rules are you can pour any color in an empty bottle, and you only can pour a layer on another layer if they are the same color.

My first approach to solving it, was by creating a new class bottle, implemented all the rules in it, which means because I knew only the basics, it took me a lot of time and it was really not optimized (I didn't know about stacks and had to write down so many if.. elif.. else statements to specify when a bottle can pour in another bottle). After I finished that I tried to write some code that can solve it. I didn't have many ideas on how the code would know which bottle to pick and where to pour it, so I went for the easy solution: pick them randomly. And it solved it instantly (kinda) for a small number of bottles, last one I tried was with 10 bottles, but with 15 bottles or more, it couldn't.

So then my second thought was maybe calculating every single possibility and move, i.e. make the game tree, and then use a search algorithm to find the shortest path, i read a bit about game trees and graph's searching algorithms and decided to use a breadth-first search(afterwards I learned that the graph I work with is a directed acyclic graph, so it's better to work with topological sorting, I'm not sure tho). The nodes in the game tree are the different states the bottles are in after pouring them in each other, and the edges are the moves that get you from one state to another. Here is how I generated the game tree in somewhat of a pseudocode:

take the first bottle A
create a list of bottles, list A, that bottle A can pour in
for each bottle B in list A, we pour bottle A in bottle B, and get a new state of bottles C
check if state C is already a node in the graph, or a permutation of a node(see explanation after the code) and add it to the graph if not
do what we did to bottle A, to all other bottles in the current node
then move to the children nodes and do the same

What I meant by checking permutations of a node is, for example, (bottle(1,2,1), bottle(0,0,0), bottle(2,1,2)) would be different from (bottle(1,2,1), bottle(2,1,2), bottle(0,0,0)), so when I left the permutations in, graphs that would have just 3000 nodes get as big as 200000 nodes.

The problem with the code I wrote was that it takes too much time to generate the game tree, last time I tried, it took 5 hours to generate the game tree for a 16 bottles level, which I think is a lot, and it can be done much much faster. A friend of mine suggested using Numpy, so each state or node in the graph would be a single matrix, and because Numpy can do things much much faster, it might be the way to do it, but me not being savvy at Numpy, I thought I can ask here for general good practices that can help me solve my problem, e.g. how to make checking if the node is already on the graph, or if a permutation of it, in this case, it would be checking if two matrices are equivalent up to permutation of columns or something like that.

So my question would be: how would you solve this if you were on my shoes, and how do you think I can get my code better optimized? Any advice would be much appreciated.

Answer 1

Very interesting problem! I do have some suggestions

• Firstly in my opinion searching a huge configuration tree like this without a clear idea where you're going is at best inefficient. Why not prefer "directions" that lead to more bottles being filled or filled more highly in the same color. See my __iter__ below.

• I think it could be worthwhile to recognize two states of the puzzle to be the same if the bottles only vary in order. You could do that by having the colors in the bottles represented by tuples of integers and saving a set of those (since the set does not safe the order). See set_rep below.

I couldn't resist to code this up. As a basis I have used Raymond Hettinger's Generic Puzzle Solver. Especially my solve method is strongly influenced by his.

The actual code

import numpy as np
from collections import deque


class ColoredWater:
    def __init__(self, pos):
        self.pos = pos

    @staticmethod
    def get_first_non_zero(arr):
        try:
            return arr[arr != 0][0]
        except IndexError:
            return 0

    @staticmethod
    def get_first_non_zero_index(arr):
        try:
            return np.where(arr != 0)[0][0]
        except IndexError:
            return 3

    @staticmethod
    def get_last_zero_index(arr):
        try:
            return np.where(arr == 0)[0][-1]
        except IndexError:
            return 3

    def get_legal_moves_to(self, moveable_to):
        first_non_zero = self.first_non_zero
        n = first_non_zero.shape[0]
        if first_non_zero[moveable_to] == 0:
            return np.where((first_non_zero != 0) & (np.arange(n) != moveable_to))[0], moveable_to
        else:
            return np.where((first_non_zero == first_non_zero[moveable_to]) & (np.arange(n) != moveable_to))[0], moveable_to

    def swap(self, i, j):
        out = self.pos.copy()
        idx_from = (self.get_first_non_zero_index(self.pos[:, i]), i)
        idx_to = (self.get_last_zero_index(self.pos[:, j]), j)
        out[idx_from], out[idx_to] = out[idx_to], out[idx_from]
        return ColoredWater(out)

    def isgoal(self):
        return np.array_equiv(self.pos, self.pos[0])

    def __iter__(self):
        self.first_non_zero = np.apply_along_axis(self.get_first_non_zero, 0, self.pos)
        moveable_to = np.where(self.pos[0] == 0)[0]
        legal_moves = tuple(map(self.get_legal_moves_to, moveable_to))

        out = [self.swap(origin, target)
               for origins, target in legal_moves
               for origin in origins]   

        def number_of_full_stacks(pos):
            return np.sum(np.all((pos == [pos[0]]), axis=0))

        def fillings_of_stacks(game):
            pos = game.pos
            return number_of_full_stacks(pos), number_of_full_stacks(pos[1:]), number_of_full_stacks(pos[2:])

        return iter(sorted(out, key=fillings_of_stacks, reverse=True))

    def set_rep(self):
        return frozenset(map(tuple, self.pos.T))

    def __repr__(self):
        return repr(self.pos)

    def solve(pos, depthFirst=False):
        queue = deque([pos])
        trail = {pos.set_rep(): None}
        solution = deque()
        load = queue.append if depthFirst else queue.appendleft

        while not pos.isgoal():
            for m in pos:
                if m.set_rep() in trail:
                    continue
                trail[m.set_rep()] = pos
                load(m)
            pos = queue.pop()

        while pos:
            solution.appendleft(pos)
            pos = trail[pos.set_rep()]

        return list(solution)

How to run it

First I run it on your example. In run with depthFirst=True it gives a solution in 117 moves in 376 ms. When I run it with depthFirst=False it gives an optimal solution in 55 moves in 9.42 s.

from ColoredWater import ColoredWater
import numpy as np

ColoredWater(np.array([[ 0,  1,  0,  5,  8,  9,  7,  4,  2,  8,  2,  5,  5, 10, 12],
                       [ 0,  2,  0,  6,  3, 10,  9,  7, 11,  3, 11, 12,  3,  6, 13],
                       [ 0,  3,  0,  7,  4,  2, 11, 11,  6, 12, 12, 13,  1, 13,  1],
                       [ 0,  4,  0,  5,  9,  9,  7,  6,  8,  8, 13,  1,  4, 10, 10]]))\
.solve(depthFirst=True) 

I have also tested it on a "random" example:

def sort_zeros(x):
    return sorted(x, key=lambda x:x != 0)


n = 15

arr = np.broadcast_to(np.array([0,0,*range(n)]),(4,n+2)).copy()
np.random.shuffle(arr.reshape(-1))
arr = np.apply_along_axis(sort_zeros,0,arr)
print(ColoredWater(arr).solve(depthFirst=True))

Answer 2

You may take a look at kociemba.org/themen/waterball/colorsort.html

The algorithm is explained here in detail and there also is a Github link to the code and a link to a win64 exe file.