Practice Recursion and Sets with the exercise "Rummikub 2"

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Statement

Goal

This is part 2 of the two-part Rummikub puzzle. In part 1 (www.codingame.com/training/medium/rummikub-1), the basic dynamics are introduced. Part 2 works as a stand-alone puzzle, but for simpler examples it is advised to first solve part 1.

Rummikub is a game played with tiles numbered 1-13 in four colors: Blue, Green, Red and Yellow. There are two tiles of each number-color combination. There are also Joker tiles, more on that below. Players play their tiles to form runs (same-colored uninterrupted range of numbers) or sets (same-numbered tiles all of a unique color). A valid run or set consists of at least three tiles, and a maximum of four (set) or thirteen (run). Example of a run: 3G 4G 5G 6G. Example of a set: 4B 4G 4R.

You will get a table with valid runs and sets (rows), and one tile (goalTile) to put on the table in as few actions as possible. You must output all actions needed to put the tile on the table (becoming part of a valid run or set), and the new rows of the table after those actions.

Actions
One action can be one of:
• TAKE tile rowid: take a tile from a row, or
• PUT tile rowid: put a tile in a row, or
• COMBINE rowid_1 rowid_2: combine two rows.

Apply the actions according to the following rules:
• Each TAKE action must always immediately be followed by a PUT action of the same tile. (While possible in the real game, in this puzzle you are not allowed to take another tile before putting away the already taken tile)
• After each PUT action, the table should only contain valid runs and/or sets.
• Your final action is always to PUT goalTile.
• A COMBINE action can be used to merge two runs into one longer valid run. Order the rowids from the two rows numerically. The new run gets the lowest rowid (rowid1), the other rowid (rowid2) becomes unused (and cannot be attributed to new runs).

You are allowed to split one valid run into two valid runs by a PUT or TAKE action. For example: TAKE the middle tile of a run of seven tiles, or PUT a tile in the middle of a run of five tiles. In case of a split, the new run with the highest numerical tile values gets a new rowid (highest rowid that ever existed + 1), and the other run keeps the original rowid.

Some examples of valid actions and their result on table rows:
Starting table
1 1G 2G 3G 4G
2 5G 6G 7G
3 4B 4R 4Y
ACTION 1: COMBINE 1 2 (This action creates a long run with lowest rowid1, higher rowid2 row is deleted)
Table after action 1:
1 1G 2G 3G 4G 5G 6G 7G
3 4B 4R 4Y
ACTION 2: TAKE 4G 1 (This action splits row 1; the run with highest numeric values gets a new rowid)
ACTION 3: PUT 4G 3 (A TAKE should directly be followed by a PUT)
Table after actions 2 and 3:
1 1G 2G 3G
3 4B 4G 4R 4Y
4 5G 6G 7G

Runs are always displayed from low to high value. Sets are always displayed in the order B G R Y.

Joker
In some cases, there can be a Joker (denoted as J) in a run or set. A joker can represent any number and color tile value. So, after a valid TAKE J rowid, the J can be added to any set or run that still has place. A joker is always displayed at the most right place (3R 4R J instead of J 3R 4R), except if it fills a space inside a run (3R J 5R). The actual value of J is never fixed (while displayed as 3R 4R J, it is not fixed whether J is 2R or 5R in this run; also, adding 5R to the run 3R 4R J 6R 7R does not split the run, since J is not fixed as 5R).

Action selection and order
When different series of actions would lead to the same output, follow the rules below:
1. Always select the least number of actions;
2. COMBINE always as early as possible;
3. COMBINE lower-numbered rowids before higher-numbered rowids (e.g. COMBINE 1 2 before COMBINE 1 3);
4. Never TAKE and/or PUT a J if it can also be done without;
5. If needed, TAKE and/or PUT a J as early as possible (but, if also rule 2 applies, COMBINE goes first).

Note
The real Rummikub allows for more complex actions (multiple TAKE after each other, after a single PUT the runs or sets do not need to be valid yet, as long as more PUTs are coming). To reduce difficulty of this puzzle, this is left out (the creator of the puzzle was not able to solve this).
Two important consequences of these rules (hint): 1) It is never possible to create a new set. It is only possible to make a set longer or shorter. 2) It is never possible to create a new run, except if it is created by splitting one run into multiple smaller valid runs.

CREDITS to Cedricdd for coming up with several of the cases

Input

Line 1: string goalTile: non-Joker tile to put on the table. A non-Joker tile is a combination of a numeric value (1-13) and a single letter indicating the color (one of R, G, B or Y) .
Line 2: integer nrow: number of rows (sets or runs) on the table.
Next nrow lines: row: the rowid (1-nrow), followed by space separated strings representing tiles (a non-Joker tile or a Joker tile, indicated by J), that form a valid run or set.

Output

naction lines: the actions needed to put goalTile on the table (one action per line), in the format: PUT tile rowid, TAKE tile rowid or COMBINE rowid1 rowid2.
nrow_new lines: the new rows that are formed after putting goalTile on the table (one row per line). The new rows have either their original rowid, or a new rowid (if it was a new row as a result from splitting an original row). Rows that became unused due to a COMBINE action should be skipped.

Constraints

There is never more than 1 Joker.
Cases have been constructed such that there is always only one solution after following the action selection and order rules.

Example

Input

3G
5
1 4G 4R 4Y
2 6G 6R 6Y
3 4B 5B 6B 7B 8B 9B
4 7G 8G 9G
5 5G 5R 5Y

Output

TAKE 4B 3
PUT 4B 1
TAKE 5B 3
PUT 5B 5
TAKE 6B 3
PUT 6B 2
TAKE 6G 2
PUT 6G 4
TAKE 5G 5
PUT 5G 4
TAKE 4G 1
PUT 4G 4
PUT 3G 4
1 4B 4R 4Y
2 6B 6R 6Y
3 7B 8B 9B
4 3G 4G 5G 6G 7G 8G 9G
5 5B 5R 5Y

Solve it

A higher resolution is required to access the IDE