4
$\begingroup$

I have just played a few games of Rummikub and the manipulations I made during my turns became more and more complex transactions. A few turns reordered the whole field, so that other players did not recognize anything and had to plan their turns again.

As always, I thought about representing this in a computer program and having an algorithm that can put in the most pieces on my deck possible. I considered the various transactions that are possible and leave the field valid. However, there is no need for this. We only do little transaction because rearranging the whole field on the table is a bunch of work, especially if one made a mistake.

Basically I only need to find some legal arrangement for the set of pieces already on the table and the ones that I want to get rid of. So there is no actual need for transforming the current game state into a new one.

I do not see how to proceed, though. My background is more in numerical methods, and this is a combinatoric problem. Basically I want this:

Let $T$ be the set of pieces $(c, n)$ with a color $c \in \{ 1, 2, 3, 4 \}$ and a number $n \in \{ 1, \ldots, 13 \}$ on the table. This is not really a set as each piece can occur multiple times. In a second iteration of this question one could also include two joker pieces $J$ that can substitute for everything.

The player has additional pieces in the set $P$. Ideally we would find an arrangement for $T \cup P$, but just finding an arrangement for $n \leq |P|$ elements of $P$, like $T \cup \{p_1, \ldots, p_n \}$, would also be a good step forward for one move.

One arrangement $A$ is a set of set of pieces such each of these sets satisfies these conditions:

  • At least three pieces
  • A set is either a “run” where the color $c$ is the same and the numbers are consecutive or it is a “group” where all colors are different and the numbers are the same.

A “group” can only contain four pieces at maximum whereas the “run” can contain up to 13 pieces. If one plays with periodicity, then they can be longer.

A brute force algorithm would just take all possible partitions of the pieces and then check the validity. I would presume that this get out of hand rather quickly.

Some guided approach might be to first try to find the largest consecutive “runs” and group everything that is left as “groups”. But often I have found in the game that taking away pieces from “runs” to make “groups” allows one to integrate a new piece. Sometimes it is the other way around, so there has to be some interplay.

I fear that this question is overload broad in its naivity, but how would I proceed to construct an algorithm that finds a valid arrangement for a set of pieces?

$\endgroup$
  • $\begingroup$ You are asking two things: 1) An algorithm to decide whether a collection of tiles has a valid arrangement and 2) An algorithm to find a maximum size subcollection such that the subcollection has a valid arrangement . I gave a answer for 1. An algorithm for 2 seems more difficult. (other than brute-force using 1). I suggest you make another question for 2. $\endgroup$ – Discrete lizard Dec 27 '17 at 13:46
3
$\begingroup$

Note that I'll use slightly different notation for my convenience.

First, I'll describe an algorithm to determine whether some collection has a valid arrangement assuming we have 4 colours, no jokers and all tiles are distinct. We'll extend this into the general case afterwards.


Given are four lists $a_1,a_2,\ldots, a_A ; b_1,b_2,\ldots, b_B ; c_1,c_2,\ldots, c_C; d_1,d_2,\ldots,d_D$ with elements distinct in $\mathbb{N}$ for some $A,B,C,D\in \mathbb{N}$. These four lists correspond to tiles of the four colours $A,B,C,D$. Assume that these lists are sorted from small to large. (If not, we can sort them before starting the algorithm; this will usually take less time than the other parts, most certainly so if the lists are of equal length)

Now, define $R[w,x,y,z]:= \text{true}$ if the lists $a_1,a_2,\ldots, a_w ; b_1,b_2,\ldots, b_x ; c_1,c_2,\ldots, c_y; d_1,d_2,\ldots,d_z$ have a valid arrangement and $\text{false}$ otherwise. We'll choose $R[0,0,0,0]:=\text{true}$ and $R[w,x,y,z]:=\text{false}$ if one of the indices $w,x,y,z$ is negative.

To get a recursive formulation for $R$, consider when a collection has a valid arrangement if we add a few tiles to it. We can add a single tile to complete (or extend) a run of the same colour with size at least $3$ and make some valid arrangement on the remaining tiles. Note that our new tile must be at the end of the run, since we assume in our definition of $R$ that all tiles on the board have a smaller value. A formalisation of this for colour $A$ is the statement $\bigvee_{i=0}^{w-2} (\text{Run}(i,w,A)\wedge R[i-1,x,y,z])$, where $\text{Run}(i,j,X)$ is true if and only if the tiles $x_i,x_{i+1},\ldots,x_j$ form a valid run.

The other way to get a valid arrangement by adding some tiles is add a group of size $3$ or $4$ and make an arrangement on the remaining tiles. This can be formalised as $a_w=b_x=c_y\ \wedge R[w-1,x-1,y-1,z]$ if we make a group of $3$, excluding the colour $D$ and as $a_w=b_x=c_y=d_z\ \wedge R[w-1,x-1,y-1,z-1]$ if we make a group of $4$.

As these are the only methods to construct valid arrangements, the following recursive formula holds:

$$ R[w,x,y,z] = \begin{cases}\bigvee_{i=0}^{w-2} (\text{Run}(i,w,A)\wedge R[i-1,x,y,z])\\ \vee\bigvee_{i=0}^{x-2} (\text{Run}(i,x,B)\wedge R[w,i-1,y,z])\\ \vee\bigvee_{i=0}^{y-2} (\text{Run}(i,y,C)\wedge R[w,x,i-1,z])\\ \vee\bigvee_{i=0}^{z-2} (\text{Run}(i,z,D)\wedge R[w,x,y,i-1])\\ \vee (a_w=b_x=c_y\ \wedge R[w-1,x-1,y-1,z])\\ \vee (a_w=b_x=d_z\ \wedge R[w-1,x-1,y,z-1])\\ \vee (a_w=c_y=d_z\ \wedge R[w-1,x,y-1,z-1])\\ \vee (b_x=c_y=d_z\ \wedge R[w,x-1,y-1,z-1])\\ \vee (a_w=b_x=c_y=d_z\ \wedge R[w-1,x-1,y-1,z-1])\\ \end{cases} $$

As the right-hand side of the formula only references $R$ with smaller indices than the left-hand side, we can use this formula to compute our result $R[A,B,C,D]$. To compute the result efficiently, we use dynamic programming, which gives an $O(ABCD(A+B+C+D))$ time algorithm if we pre-compute $\text{Run}$. Note that in this recurrence, we compute $\text{Run}(i,x,B)\wedge R[w,i-1,y,z]$ multiple time. We can change the recurrence to ensure this occurs only once while maintaining correctness, which leads to $O(1)$ time for every 'cell' in the DP-table, so we can compute our result in $O(ABCD)$ time. As usual with dynamic programming, we can get the actual solution by reading the DP-table or storing the decisions made while we construct the table.


Now, what happens when the values of our tiles are no longer unique? We get in trouble with constructing runs, as won't always use consecutive tiles to construct a run due to the adjacent duplicates. So, instead, we split a list for a single colour into multiple sub-lists such that the sub-lists have distinct tiles, order those sub-lists and merge them back into one list again. Now, we can try to use the recurrence as before, but now be careful to only use a single sub-list in every run.

However, we now get the problem that we no longer only have to remember whether prefixes of a sub-list have a valid run, but also for suffixes! (e.g. we can construct an arrangement with $1,2,3,4,5;3$ as we can append $3$ to $\{1,2\}$ and $\{3,4,5\}$ is valid, but not with $1,2,3,4;3$, as $\{3,4\}$ is invalid. So we must indeed check the suffix) Fortunately, we can also compute the validity of all suffixes of the first sub-list similarly to how we did with the prefixes.*

So, our new algorithm, after splitting in sub-lists, is as follows: for every sub-list except the last, compute the validity of all prefixes and suffixes as before (possibly using the values from the previous sub-list). For the final sub-list, compute only the prefixes and find the answer. Since we 'only' compute parts of our list twice, the asymptotic running time stays $O(ABCD)$.


How can we handle jokers? As we may use a joker at any place in our arrangement, we add an additional index $j$ such that $R[w,x,y,z,j]$ indicates whether there is a valid arrangement for $R[w,x,y,z]$ using (exactly) $j$ jokers. The recursion remains the same if $j$ doesn't change, but now the right-hand side may contain $R[w',x',y',z',j-1]$ for some change that would be valid by using a joker (as we still either make runs or groups, this is similar to the cases already described). The final value is now at $R[A,B,C,D,J]$ and we can compute this value similar to above in $O(ABCDJ)$ time.


*: You may wonder why we still can assume our new tile is at the end of a run. This is because if we would place our tile somewhere else, we can simply 'swap' with our earlier tile, which was placed at the end of a run.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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