Sorting Balls and Water: Equivalence and Computational Complexity

We first prove that the problems $\mathsf{BSP}$ and $\mathsf{WSP}$ are actually equivalent. By their definitions, a yes-instance of $\mathsf{WSP}$ is a yes-instance of $\mathsf{BSP}$ as well. Thus our technical contribution here is to prove the opposite direction. As a byproduct, we show that a yes-instance of the problems admits a reconfiguration sequence of length polynomial in $n+h$ as a yes-certificate. This implies that the problems belong to NP. We also show that $\mathsf{BSP}$ and $\mathsf{WSP}$ are solvable in time $O(h^{n})$.

We next show that $\mathsf{BSP}$ and $\mathsf{WSP}$ are indeed NP-complete. By slightly modifying this proof, we also show that even for some kind of trivial yes-instances of $\mathsf{WSP}$, it is NP-complete to find a shortest reconfiguration to a sorted configuration.

We show that if the capacity $h$ is $2$ and the number of colors is $n$, then $\mathsf{BSP}$ and $\mathsf{WSP}$ are polynomial-time solvable. In this case, we present an algorithm that finds shortest reconfiguration sequences for yes-instances.

We also consider the following question: how many empty bins do we need to ensure that all initial configurations can reach a sorted configuration? Observe that $\mathsf{BSP}$ and $\mathsf{WSP}$ are trivial if $k\geq hn$. It is not difficult to see that $k\geq n$ is also sufficient by using an idea based on bucket sort. By improving this idea, we show that $k\geq\lceil\frac{h-1}{h}n\rceil$ is sufficient for all instances. We also show that some instances need $k\geq\lfloor\frac{19}{64}\min\{n,h\}\rfloor$ empty bins.

Various forms of sorting problems have been studied over the years. For example, sorting by reversals is well investigated in the contexts of sorting network [6, Sect. 5.2.2], pancake sort [2], and ladder lotteries [8]. There is another extension of sorting problem from the viewpoint of recreational mathematics defined as follows. For each $i\in\{1,\dots,n\}$, there are $h$ balls labeled $i$. These $hn$ balls are given in $n$ bins in which each bin is of capacity $h$. In one step, we are allowed to swap any pair of balls. Then how many swaps do we need to sort the balls? This sorting problem was first posed by Peter Winker for the case $h=2$ in 2004 [7], and an almost optimal algorithm for that case was given by Ito et al. in 2012 [4].

The ball/water sorting puzzles are interesting also from the viewpoints of not only just puzzles but also combinatorial reconfiguration. Recently, the reconfiguration problems attracted the attention in theoretical computer science (see, e.g., [5]). These problems arise when we need to find a step-by-step transformation between two feasible solutions of a problem such that all intermediate results are also feasible and each step abides by a fixed reconfiguration rule, that is, an adjacency relation defined on feasible solutions of the original problem. In this sense, the ball/water sort puzzles can be seen as typical implementations of the framework of reconfiguration problems, while their reconfiguration rules are non-standard. In most reconfiguration problems, representative reconfiguration rules are reversible; that is, if a feasible solution $A$ can be reconfigured to another feasible solution $B$, then $B$ can be reconfigured to $A$ as well (see e.g., the puzzles in [3]). In the ball sort puzzle, we can reverse the last move if we have two or more balls of the same color at the top of the source bin, or there is only one ball in the source bin. Otherwise, we cannot reverse the last move. That is, some moves are reversible while some moves are one-way in these puzzles. (In Figure 1, only the last move is reversible.) In the water sort puzzle, basically, we cannot separate units of water of the same color once we merge them, however, there are some exceptional cases. An example is given in Figure 2; the move from configuration (2) to configuration (3) is reversible, but the other moves are not.

Let $B$ and $C$ be finite sets of bins and colors, respectively. The set of sequences of colors of length at most $h$ is denoted by $C^{\leq h}$. A sequence of $c\in C$ of length $l$ is called monochrome and denoted by $c^{l}$. The empty sequence is denoted as $\varepsilon$, which is, in our terminology, also called monochrome. A configuration is a map $S\colon B\to C^{\leq h}$. An instance of $\mathsf{BSP}$ and $\mathsf{WSP}$ is a configuration $S$ such that $|S(b)|\in\{h,0\}$ for all $b\in B$. A bin $b$ is sorted under $S$ if $S(b)\in\{\varepsilon,c^{h}\}$ for some $c\in C$. A configuration $S$ is sorted or goal if all bins are sorted under $S$. Sometimes we identify $b\in B$ with $S(b)$ when $S$ is clear from the context.

The $i$th element of a sequence $\alpha$ is denoted by $\alpha[i]$ for $1\leq i\leq|\alpha|$. The top color of a color sequence $\alpha$ is $\mathrm{TC}(\alpha)=\alpha[|\alpha|]$ if $\alpha$ is not empty. In case $\alpha$ is empty, $\mathrm{TC}(\alpha)$ is defined to be $\varepsilon$. A border in $\alpha$ is a non-negative integer $i$ such that either $1\leq i<|\alpha|$ and $\alpha[{i}]\neq\alpha[{i+1}]$ or $i=0$, and the set of borders of $\alpha$ is denoted by $\mathcal{D}(\alpha)$. We count non-trivial borders under $S$ as $D(S)=\sum_{b\in B}|\mathcal{D}(S(b))\setminus\{0\}|$. For example, in Figure 2, the values of $D$ are $4,3,3,3$ in (0), (1), (2), (3), respectively.

We now turn to define a move of the sort puzzles with the terminologies introduced above. Intuitively, we pick up two bins $b_{1}$ and $b_{2}$ from $B$, and pour the top item(s) from $b_{1}$ to $b_{2}$ if $b_{2}$ is empty or the top item of $b_{2}$ has the same color. The quantity of the items are different in the cases of balls and water. In the ball case, a unit is moved if possible. On the other hand, two or more units of water of the same color move at once until all units are moved or $b_{2}$ becomes full. We define the move more precisely below.

A ball-move can modify a configuration $S$ into $S^{\prime}$, denoted as $S\rightarrow S^{\prime}$, if there are $b_{1},b_{2}\in B$ and $c\in C$ such that

• •

  $S(b_{1})=S^{\prime}(b_{1})\cdot c$, $\mathrm{TC}(S(b_{2}))\in\{c,\varepsilon\}$, $S^{\prime}(b_{2})=S(b_{2})\cdot c$, and

• •

  $S(b)=S^{\prime}(b)$ for all $b\in B\setminus\{b_{1},b_{2}\}$.

A water-move can modify $S$ into $S^{\prime}$, denoted as $S\Rightarrow S^{\prime}$, if there are $m\geq 1$, $b_{1},b_{2}\in B$ and $c\in C$ such that

• •

  $S(b_{1})=S^{\prime}(b_{1})\cdot c^{m}$, $\mathrm{TC}(S(b_{2}))\in\{c,\varepsilon\}$, and $S^{\prime}(b_{2})=S(b_{2})\cdot c^{m}$,

• •

  either $\mathrm{TC}(S^{\prime}(b_{1}))\neq c$ or $\left|S^{\prime}(b_{2})\right|=h$, and

• •

  $S(b)=S^{\prime}(b)$ for all $b\in B\setminus\{b_{1},b_{2}\}$.

The reflexive and transitive closures of $\rightarrow$ and $\Rightarrow$ are denoted as $\rightarrow^{*}$ and $\Rightarrow^{*}$, respectively. Clearly any single water-move can be simulated by some number of ball-moves. Thus we have ${\Rightarrow^{*}}\subseteq{\rightarrow^{*}}$.

Hereafter we fix an arbitrary initial configuration $S_{0}$. Some notions introduced below are relative to $S_{0}$, though it may not be explicit. The top-border table of a configuration $S$ is a map $\mathrm{TB}_{S}\colon B\to\{0,1,\dots,h-1\}$ defined as $\mathrm{TB}_{S}(b)=\max\mathcal{D}(S(b))$.

The main object of this section is to observe that top-border tables play an essential role in analyzing the solvability of an instance. Note that $\mathrm{TB}_{S}(b)=0$ if and only if $b$ is monochrome. Once we have reached a configuration with $\mathrm{TB}_{S}(b)=0$ for all $b\in B$, we can achieve a goal configuration by trivial moves. Figure 3 illustrates some notions introduced in this section.

By the definition of moves, one can easily observe the following properties. {observation} If $S\rightarrow^{*}T$, the following holds for all bins $b\in B$:

1. 1.

   Moves monotonically remove borders from top to bottom:

   $$\mathcal{D}(T(b))=\{\,i\in\mathcal{D}(S(b))\mid i\leq\mathrm{TB}_{T}(b)\,\}\,;$$

2. 2.

   The contents below the top borders of $T$ do not change:

   $$T(b)[i]=S(b)[i]\text{ for all }i\leq\mathrm{TB}_{T}(b)\,;$$

3. 3.

   If $b$ is not monochrome in $T$, the colors of all the units above the border in $T$ are the color of the unit just above that border in $S$:

   $$\mathrm{TC}(T(b))=S(b)[\mathrm{TB}_{T}(b)+1]\text{ if\/ $\mathrm{TB}_{T}(b)\neq 0$.}$$

We first give a necessary condition for $S_{0}\rightarrow^{*}S$.

Recall that throughout the game play, the total number of units of each color does not change, i.e., if $S_{0}\rightarrow^{*}S$, it holds for every color $c\in C$,

Since the units under the top border of each bin have not been moved (Observation 2.2-2), the total numbers of units of each color $c$ above the borders of $\mathrm{TB}_{S}$ coincide in $S_{0}$ and $S$. We count those units of color $c$ as

Those units may have been moved, but units of color $c$ can go only to empty bins or bins whose top color is $c$ in $S$. Let us partition the bins into $|C|+1$ groups with respect to $S$, where

• •

  $B_{\varepsilon}(\mathrm{TB}_{S})=\{\,b\in B\mid\mathrm{TB}_{S}(b)=0\,\}$: monochrome bins,

• •

  $B_{c}(\mathrm{TB}_{S})=\{\,b\in B\setminus B_{\varepsilon}\mid S_{0}(b)[\mathrm{TB}_{S}(b)+1]=c\,\}$: non-monochrome bins with the top color $c$.

Note that if $b\notin B_{\varepsilon}(\mathrm{TB}_{S})$, the top color of $b$ in $S$ is $\mathrm{TC}(S(b))=S(b)[\mathrm{TB}_{S}(b)+1]=S_{0}(b)[\mathrm{TB}_{S}(b)+1]$. Since each bin $b\in B_{c}$ may have at most $h-\mathrm{TB}_{S}(b)$ units of color $c$ above the border $\mathrm{TB}_{S}(b)$, there are

units of color $c$ can be on the top layer of non-monochrome bins. Thus, we must have at least

monochrome bins in $B_{\varepsilon}$ which have some units of color $c$. Therefore, it is necessary that

We remark that the values of the functions introduced above, namely $\mathcal{F}_{c}$, $B_{c}$, $\mathcal{M}_{c}$, are all determined by the top-border table $\mathrm{TB}_{S}$. Those values coincide for $S$ and $S^{\prime}$ if $\mathrm{TB}_{S}=\mathrm{TB}_{S^{\prime}}$. Let us say that $S$ is consistent with $S_{0}$ if and only if $\mathrm{TB}_{S}$ satisfies Eq. (1). Moreover, $S$ is tight if $S$ has exactly $\mathcal{M}_{c}(\mathrm{TB}_{S})$ monochrome bins with at least one unit of every color $c\in C$.

Of course $\mathrm{TB}_{S}$ being consistent with $S_{0}$ does not imply $S_{0}\rightarrow^{*}S$. Suppose $S_{0}\rightarrow^{*}S\rightarrow S^{\prime}$ with $\mathrm{TB}_{S}\neq\mathrm{TB}_{S^{\prime}}$, where $S^{\prime}$ has one less border than $S$ by moving a unit above the top border of some bin $b$ to some other bins. Note that $S(b)$ is not monochrome. During the move, the bin $b$ can keep units below its top border only. Therefore, the number of necessary monochrome bins of each color $c$ for this move is

and it is necessary that

Those conditions depend on top-border configuration of $S$. For two top-border tables $\tau$ and $\tau^{\prime}$ and a bin $b\in B$, we write $\tau\stackrel{{\scriptstyle b}}{{\Rrightarrow}}\tau^{\prime}$ if

• •

  $\tau(a)=\tau^{\prime}(a)$ for all $a\in B\setminus\{b\}$,

• •

  $\tau(b)>0$ and $\tau^{\prime}(b)=\max\{\,i\in\mathcal{D}(S_{0}(b))\mid 0\leq i<\tau(b)\,\}$,

• •

  $\sum_{c\in C}\mathcal{M}_{c}^{b}(\tau)\leq|B_{\varepsilon}(\tau)|$.

We write $\tau\stackrel{{\scriptstyle}}{{\Rrightarrow}}\tau^{\prime}$ if $\tau\stackrel{{\scriptstyle b}}{{\Rrightarrow}}\tau^{\prime}$ for some $b\in B$. Figure 4 may help intuitive understanding the above argument.

If $\tau\stackrel{{\scriptstyle b}}{{\Rrightarrow}}\tau^{\prime}$, from the values $\mathcal{F}_{c}(\tau)$ and $\mathcal{G}_{c}(\tau)$, one can compute $\mathcal{F}_{c}(\tau^{\prime})$ and $\mathcal{G}_{c}(\tau^{\prime})$ in constant time, by preprocessing $S_{0}$, using the following equations:

A solution for an instance is essentially an order of borders of the instance to remove.