Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to validate a Rummikub combination with Jokers

In the game of Rummikub, for those who don't know it, you have tiles in 4 colours and with 13 different numbers on them (so 4 x 13 = 52 unique tiles) which you must use to make groups. There are two kinds of groups:

  • Different colours, same numbers (e.g. R1-B1-G1)
  • Same colours, sequence of numbers (e.g. G6-G7-G8)

I'm writing code that takes a list of tiles and checks if it's a valid combination. So far it works and is pretty straightforward.

It gets difficult when we introduce Joker tiles. You can use these as any tile to complete a combination (e.g. G6-R6-J) and you can use multiple (e.g. R4-R5-J-J-R8).

I figured that I'd validate combinations with Jokers in two steps:

  1. Replace all Jokers with the tile they are standing in for.
  2. Validate the "normalized" group with the existing code (unless step 1 threw an error because it already saw the combination is invalid).

Now, how to do step 1? I think it's fairly simple if only one Joker is allowed per group:

  • If the tiles adjacent to the joker are of the same colour and the right one is 2 higher than the left one, replace with the number inbetween
  • If the adjacent tiles have the same number but different colours, replace with a colour that is not yet present.
  • And the same but modified a bit if the Joker is at the beginning or end

Unfortunately, multiple Jokers are allowed, which makes this a bit more complex, and I'm stuck on how to solve that.

like image 928
Bart van Heukelom Avatar asked Dec 29 '22 07:12

Bart van Heukelom


1 Answers

If you insist to perform step 1 as the first thing you do, you're making trouble for yourself. It's simply computationally inefficient to approach the problem from that angle. What you would end up doing with that approach, is to try all combinations of stand-ins for the jokers. That is a bad idea.

Here's an alternative approach that will work with little effort:

  1. Does the group contain 0 or 1 non-joker, and does the group contain at least three pieces then success.
  2. Are all colors of the non-jokers have the same color, then success.
  3. Does all the pieces lay like (1, 2, joker, 4) where all jokers automatically take the value one higher than the preceding piece. If so, then success.
  4. If none of the above were true, then fail.

Perform all those checks in turn, and you will find if a group of pieces is a valid group.

For step 3 in this, you have to consider that some sequences could be in reverse, say (joker, 3, 2, 1). to detect such cases, you can do a quick scan over the non-jokers, to see if they increment or they decrement, and then take that into account (the jokers will then have the value one less than the previous).

Notice that only in step 2 are the colors significant, and only in step 3 are the numbers significant.

like image 110
Zuu Avatar answered Jan 25 '23 23:01

Zuu