Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem S. 28. (September 2007)

S. 28. A version of rummy is played with two standard decks of 52 cards. The object of the game is to dispose of all the cards in your hand. You can get rid of cards as follows.

1.a). One puts one or more sequences down. (A sequence consists of three or more cards of the same suit in consecutive order. Example: Heart 3, 4, 5 and 6. But the group Heart 4, 5 and Diamond 6 is not a sequence.) Or 1.b). One puts one or more sets down (A set consists of three or four cards of the same rank. Example: Heart King, Diamond King and Spade King. But the group Spade Ace, Spade Ace and Club Ace is not a set.)

2. A sequence consists of cards of the same suit. The order of the cards is 2, 3, ..., 9, 10, Jack, Queen, King, Ace or Ace, 2, 3, ..., 9, 10, Jack, Queen, King, so Ace is either the first or the last card of a sequence. Valid sequences are, for example: Club 10, Club Jack, Club Queen, or Heart Ace, Heart 2, Heart 3 and Heart 4. The sequence Spade King, Spade Ace and Spade 2 is, however, invalid.

3. A Joker can substitute any of the cards in a sequence or a set, however, the number of non-Jokers must be greater than the number of Jokers. For example, Heart 9, Heart 10, Joker, Joker and Heart King is a valid sequence. The sequence Joker, Spade 4 and Joker is invalid. Heart 5, Joker, Joker and Heart 8 is also an invalid sequence.

Players put down cards from their hands and, optionally, they can also rearrange cards already on the table according to the above rules. Example: Heart 5, Diamond 5, Club 5 and Spade 5 are on the table in a group, while Club 4 and Club 6 are in a player's hand. The player then can form a group of Heart 5, Diamond 5 and Spade 5 on the table, and another group of Club 4, 5 and 6 - this way the player can put down both cards simultaneously.

The next player can not take any card from the table. If he or she is unable to put down any cards, then that player draws one card from the talon (that is, from the remainder of the deck after the deal).

You should create a program s28 that gets rid of as many cards as possible. The first input parameter of your program is the name of a file describing cards on the table. The second input parameter points to a file containing cards in the hand of the player. The standard output of the program is the content of the table (after cards have been put down and possibly rearranged) and the remaining cards in the player's hand.

Suits of the cards are abbreviated by their first letters H(eart), D(iamond), C(lub) and S(pade). The ranks of the cards are denoted by 2, 3, 9, 0, J(ack), Q(ueen), K(ing) and A(ce). So, for example, H4 means Heart 4, C0 means Club 10 and SQ means Spade Queen. Jokers have no suits, and they are denoted by JJ.

The first input file contains cards on the table. Each line contains a group of cards separated by spaces and in increasing order. (If there are no cards on the table, then the input file is empty.) The second input file contains cards in the player's hand. It has only one line and the name of the cards are separated by spaces. This file can not be empty, it contains at least 1 card.

The output first gives cards on the table, one group per line. Cards are separated by spaces and are in increasing order. The second part of the output finally gives cards that could not be disposed of. This part consists of a single line and cards are separated by spaces.

Example. The file a.txt contains cards on the table:

K4 JJ K6 K7
PQ KQ TQ
TA T2 T3 T4 T5

The file b.txt contains cards in the player's hand:

K5 K5 JJ TK T0

Upon executing s28 a.txt b.txt, the output is:

K4 K5 K6 K7
TQ TK TA
PQ KQ JJ
T2 T3 T4
K5 T5 JJ
T0

The source code (s28.pas, s28.cpp, ...) of the program together with a short documentation (s28.txt, s28.pdf, ...) should be submitted, specifying also which developer environment can be used to compile your program.

(10 pont)

Deadline expired on October 15, 2007.


Sorry, the solution is available only in Hungarian. Google translation

Megoldás: A feladat igen nehéz volt, mindössze egy jó program érkezett - Szirmay-Kalos Barnabás budapesti diák munkája.

A megoldás menete a versenyző leírásában: A megvalósításhoz három osztályt definiáltam, amik később a kártyákkal való műveleteket tették egyszerűbbé.

1. Card - egy kártyát (színét, számát) reprezentáló osztály

2. Set - egy kártyasor (kártyákat tartalmaz)

3. Layout - egy kártyaelrendezés (kártyákat tartalmaz)

És ezekkel a tí­pusokkal lehet alapvető műveleteket végezni.

A program futásának elején elkészí­tjük a deck és all_set tömböket Card illetve Set tí­pusokból. A deckben az 52*2 lap, az all_set tömbben pedig az összes elfogadható kártyarendezés ( pl: KA K2 K3, PQ KQ RQ TQ ) talalhátó: először a hármas sorozatok, utána a hármas egyformák, utána a négyes egyformák, majd hosszúság szerint növekvő sorrendben a többi sorozat.

A program a helyes megoldást keres minden olyan esetben amikor különböző kártyák maradnak a kezünkben, a kézben nem maradó kártyától, az összes kártya kézbenmaradásáig. Elkészí­t az egyes esetekhez egy Layout objektumot és a split függvénnyel megpróbálja rendezni azt.

A split függvény egy backtrace algoritmus. Az all_set tömb elrendezésből (az elrendezés a bemeneti paraméterként kapott Layout objektum) kivehető elemeit kiveszi és rekurzí­van meghí­vja a megmaradt kártyákra önmagát. Ha a sikerül olyan all_set tömb elemet találni aminél a megmaradó kártyák elrendezhetők, akkor ezt a Set objektumot hozzáfűzi a rekurzí­v meghí­vás eredményeként kapott lánchoz, és visszatér egy eggyel hosszabb lánccal. Ha nem sikerül elrendezni semelyik all_set elem kí­vétele után akkor megpróbálkozik 1,2... annyi joker felhasználásával ahány jokert, mint joker_count paraméter kapott. Ha jokerek felhasználásával sem sikerül megoldani az elrendezést akkor egy NULL_CARD szí­nű és számú lapot ad vissza.

Ha a split függvénynek sikerül valamelyik asztal + kéz variációt felosztania csoportokra akkor megoldást kaptunk. Ha kártyák száma > jokerek számának kétszerese akkor még tudnánk az asztalra jokereket rakni. Amennyiben maradnak jokerek a kezünkben, azaz kevesebb joker felhasználásával is sikerült felosztania a split függvénynek az elrendezést (ez előfordulhat, mert minél kevesebb joker felhasználására törekszik), akkor megpróbáljuk ezeket a jokereket az asztalon lévő lapokhoz hozzárakni.

Ekkor minden joker és nem jokerlapot leraktunk ha le lehet rakni, ezzel a soron következő játékosnak lehető legtöbb kártyáját az asztalra helyeztük.

A megoldást tartalmazó C++ fájl: s28.cpp.


Statistics:

3 students sent a solution.
9 points:Szirmay-Kalos Barnabás.
1 point:2 students.

Problems in Information Technology of KöMaL, September 2007