Az S. 28. feladat (2007. szeptember)

S. 28. A römi játék egy változatát két csomag francia kártyával játsszák. A játékot az nyeri, aki elsőként tudja a kezében lévő kártyákat az előírt szabályok szerint az asztalra rakni. A lerakás szabályai a következők:

1. A kártyákat legalább három lapból álló csoportokban lehet az asztalra helyezni úgy, hogy abban a lapok vagy azonos színű sorozatot alkotnak, vagy különböző színűek, de azonos számot vagy figurát tartalmaznak. Az első esetre példa a Kör 3-as, Kör 4-es, Kör 5-ös, Kör 6-os lapokból álló négyes, a másodikra példa a Kör király, Káró király, Pikk király lapokból álló hármas csoport. Nem helyes azonban a Kör 4-es, Kör 5-ös, Káró 6-os, vagy a Pikk ász, Pikk ász, Treff ász csoport.

2. A sorozatok csak azonos színű kártyákból állhatnak, a lapok sorrendje 2-es, 3-as, ..., 9-es, 10-es, bubi, dáma, király, ász, vagy ász, 2-es, 3-as, ..., 9-es, 10-es, bubi, dáma, király. Az ász kártya tehát vagy kezdő, vagy záró tagja egy sorozatnak. Helyes sorozat például a Treff 10, Treff bubi, Treff dáma, vagy a Kör ász, Kör 2-es, Kör 3-as, Kör 4-es; nem megfelelő a Pikk király, Pikk ász, Pikk 2-es.

3. A csoportok képzésénél tetszőleges lap helyettesíthető Joker kártyával, de a csoportban a nem Joker lapok száma nagyobb kell, hogy legyen a Joker lapok számánál. Helyes csoport példaként a Kör 9-es, Kör 10-es, Joker, Joker, Kör király sorozat, de nem helyes a Joker, Pikk 4-es, Joker, vagy a Kör 5-ös, Joker, Joker, Kör 8-as.

A játékosok játék közben a kezükben lévő lapokat tehetik le az asztalra, illetve a már az asztalon lévő lapokat rendezhetik át úgy, hogy a lapok az átrendezés után is a leírt szabályoknak megfelelően helyezkedjenek el. Legyen például az asztalon a Kör 5-ös, Káró 5-ös, Treff 5-ös, Pikk 5-ös lapnégyes, a játékos kezében pedig a Treff 4-es és a Treff 6-os. Ekkor a játékos kialakíthat egy Kör 5-ös, Káró 5-ös, Pikk 5-ös, illetve egy Treff 4-es, Treff 5-ös és Treff 6-os csoportot - így a kezében lévő két kártyát az asztalon lévő lapok átrendezésével lerakhatja.

A soron következő játékos az asztalról lapot nem vehet fel, és amennyiben nem tud letenni, úgy a még ki nem osztott lapokból húznia kell. Készítsünk programot s28 néven, amely az asztalon és a játékos kezében található lapok esetén a lehető legtöbb kártya asztalra helyezését végzi el. A program olvassa be a parancssorban megadott első állományából az asztalon lévő lapokat, a második állományból a játékos kezében lévő lapokat, és írja a standard kimenetre az asztal átrendezés és lerakás utáni helyzetét, valamint a kezében lévő lapokat.

A bemeneti állományokban és a kimeneten a francia kártya Kör, Káró, Treff, Pikk színét a K, R, T, P betű, a lapok értékét a 2, 3, ..., 9, 0 szám, illetve a J, Q, K, A betű jelölje. A K4 tehát a Kör 4-es, az RA a Káró ász, a T0 a Treff 10-es, a PJ a Pikk bubi, a PQ a Pikk dáma jelölése. A Joker lapoknak nincs színük, jelölésük JJ.

Az első bemeneti állomány az asztalon található lapokat csoportonként egy-egy sorban, laponként egymástól szóközzel elválasztva, a sorozatok tagjait növekvő sorrendben tartalmazza. A bemeneti állomány lehet üres, ekkor az asztalon még nincs lerakva egy kártya sem. A második bemeneti állomány a játékos kezében lévő lapokat tartalmazza egy sorban, egymástól szóközzel elválasztva. Ez az állomány nem lehet üres, legkevesebb egy kártyát tartalmaz. A kimenet először az asztalon lévő kártyákat adja meg csoportonként egy-egy sorban, egymástól szóközzel elválasztva, a sorozatok kártyáit növekvő sorrendben, majd a kézben maradt lapokat egy sorban, szóközzel elválasztva.

Példa: Legyen az asztalon található lapokat megadó szöveges fájl (a.txt) tartalma:

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

A játékos kezében lévő kártyákat leíró (b.txt) tartalma:

K5 K5 JJ TK T0

Ekkor a program az s28 a.txt b.txt meghívás eredményeként a kimenetre a következőket írja:

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

Beküldendő a program forráskódja (s28.pas, s28.cpp, ...), valamint a program rövid dokumentációja (s28.txt, s28.pdf, ...), amely tartalmazza a megoldás rövid leírását, és megadja, hogy a forrásállomány melyik fejlesztő környezetben fordítható.

(10 pont)

A beküldési határidő 2007. október 15-én LEJÁRT.

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.

Statisztika:

3 dolgozat érkezett.
9 pontot kapott:	Szirmay-Kalos Barnabás.
1 pontot kapott:	2 versenyző.

A KöMaL 2007. szeptemberi informatika feladatai