Tävlingsprogrammering/Uppgifter/Poker
Poker
Poker är ett kortspel som spelas med en vanlig kortlek där vardera av de 52 korten har en av fyra "färger" och en av 13 valörer, från 1 till 13. Man har alltid fem kort på handen, och dessa kort brukar kallas en "pokerhand". Spelet går ut på att få en så "bra" hand som möjligt, där en hand värderas enligt en speciell skala. (I verkligheten handlar spelet mer om att värdera chansen att man har bättre hand än motspelarna men det behöver vi inte bekymra oss om här.) Man förändrar handen genom att slänga ett valfritt antal av sina kort (0, 1, 2, 3, 4 eller 5 stycken) och ta upp lika många nya från toppen av den återstående kortleken. Ett sådant byte av valfritt antal kort kallar vi för en "omgång". De åtta handtyper som finns är:
- Par: minst två kort av samma valör
- Två par: minst två kort av en valör och minst två kort av en annan valör
- Triss: minst tre kort av samma valör
- Stege: alla fem korten med valörer i följd, t.ex. 1,2,3,4,5 eller 7,8,9,10,11. (men inte t.ex. 10,11,12,13,1)
- Färg: alla fem korten av samma färg
- Kåk: tre kort av en valör och två av en annan valör
- Fyrtal: fyra kort av samma valör
- Färgstege: en stege där alla korten har samma färg
Observera att med våra definitioner kan man exempelvis räkna en triss som ett par om man så önskar.
Kurt spelar ofta poker med sig själv. Han är besatt av att räkna ut hur många omgångar han minst måste byta kort i sin pokerhand för att uppnå olika handtyper, om han vet hur korten ligger ordnade i kortleken. Skriv ett program som, givet hans starthand och ordningen på korten i kortleken, räknar ut detta åt honom.
Indata
52 rader med en bokstav och ett tal på varje rad, separerade med blanksteg. Varje rad beskriver ett kort. Bokstaven kan vara R, S, H eller K och anger kortets färg, medan talet ligger i intervallet 1 till 13 och anger kortets valör. De fem första raderna beskriver de fem korten Kurt har i sin starthand. De återstående raderna beskriver övriga kort i den ordning de ligger i kortleken. Den sjätte raden beskriver alltså det första kortet han kan byta till sig o.s.v. Varje möjligt kort återfinns exakt en gång.
Utdata
En rad med 8 heltal, antalet bytesomgångar som behövs för att uppnå var och en av de åtta handtyperna i listan ovan (i denna ordning). Talet 0 betyder att starthanden redan är av denna handtyp.
Exempel: Indata
R 1 S 10 H 10 K 8 R 3 K 4 S 3 K 1 R 6 S 9 H 3 R 8 S 5 S 12 R 10 S 2 K 9 H 11 H 4 R 5 H 6 R 11 K 12 H 12 S 7 H 2 K 10 R 13 R 4 K 13 S 4 S 1 H 9 S 13 K 7 H 13 H 5 K 3 R 2 K 5 H 8 K 2 K 11 H 1 R 7 S 11 S 6 S 8 K 6 R 9 H 7 R 12
Exempel: Utdata
0 1 2 4 3 3 7 11
Exempel: Förklaring
Kurt har redan par i 10:or. För att få två par byter han 1:an och 8:an och får en 4:a och en andra 3:a. För att få triss slänger han däremot sitt par och samlar bara på 3:or. Och så vidare...
Lösning[redigera]
Antalet pokerhänder man kan bilda från en vanlig kortlek, (52 över 5), är faktiskt "bara" 2 598 960. Därför är det lättaste sättet att lösa uppgiften att generera samtliga händer och för varje hand dels kolla vilken typ den är och dels beräkna hur många gånger man måste ha bytt för att få exakt den handen. Det sistnämnda kan göras genom att loopa sig fram en omgång i taget, kolla hur många (k) av målhandens kortindex som redan är uppnådda, och stega fram (5-k) steg i kortleken.
Man kan också lösa uppgiften utan att generera alla händerna, genom att söka efter den "första" handen av varje typ. Det visar sig dock att det inte är helt lätt att veta vilka kort man ska välja för att få den första handen. Exempelvis, även om man försöker få par i fyror kan det ibland vara smart att slänga en fyra för att kunna stega fram fortare i högen till de andra fyrorna. Så i slutändan blir denna metod mycket krångligare.
Lösning i C:
#include <stdio.h>
int MIN(int p, int q) {return p<q?p:q;}
char f[52][2];
int v[52],p[5],ma[8];
int rounds(int p[]) { //Hur många byten krävs för att få denna hand?
int found=0,r,next=0;
for(r=0;found<5;r++) {
next+=5-found;
while (p[found]<next && found<5) found++;
}
return r-1;
}
int flush(int p[]) { // Är det en flush?
int i;
for(i=1;i<5;i++) if(f[p[i]][0]!=f[p[0]][0]) return 0;
return 1;
}
int straight(int p[]) { // Är det en stege?
int i,j,taken[14],ok;
for(i=1;i<=13;i++) taken[i]=0;
for(i=0;i<5;i++) taken[v[p[i]]]=1;
for(j=1;j<=9;j++) {
for(i=0;i<5;i++) if(!taken[j+i]) break;
if(i==5) return 1;
}
return 0;
}
int maxcount(int p[]) { // Vad är det högsta antalet kort av samma valör i handen?
int taken[14],i,m,bra;
for(i=1;i<=13;i++) taken[i]=0;
for(i=0;i<5;i++) taken[v[p[i]]]++;
m=0;
for(i=1;i<=13;i++) if(taken[i]>m) {
m=taken[i];
bra=i;
}
for(i=1;i<=13;i++) if(taken[i]==2 && i!=bra) return -m; // Om det dessutom finns ett par av en annan valör så returnera antalet negativt istället
return m;
}
int handtype(int p[]) { // Vad har handen för maximal typ
if(flush(p)) {
if(straight(p)) return 7; //Färgstege
else return 4; //Färg
}
if(straight(p)) return 3; //Stege
switch(maxcount(p)) {
case 2: return 0; //Par
case 3: return 2; //Triss
case 4: return 6; //Fyrtal
case -2: return 1; //Två par
case -3: return 5; //Kåk
default: return -1; //Ingenting
}
}
void MLX(int nr, int now) { //Rekursiv funktion som genererar händerna
int c;
if(nr==5) { //Om vi har genererat en hel hand så
c=handtype(p); //...kolla vilken typ den är
if(c>=0)
ma[c]=MIN(ma[c],rounds(p)); //...och kolla om antalet omgångar som behövdes för att uppnå den var mindre än tidigare funnet för typen
return;
}
for(p[nr]=now;p[nr]<52;p[nr]++) MLX(nr+1,p[nr]+1); //Om vi inte har genererat en hel hand så rekursera
}
int main() {
int i;
for(i=0;i<52;i++) scanf("%s %d", f[i],&v[i]);
for(i=0;i<8;i++) ma[i]=100;
MLX(0,0); //Generera händerna och hitta ma-värden för alla 8 typerna
ma[0]=MIN(MIN(MIN(MIN(ma[0],ma[1]),ma[2]),ma[5]),ma[6]); //Slutligen tar vi hänsyn till att vissa handtyper kan räknas som lägre.
ma[1]=MIN(ma[1],ma[5]);
ma[2]=MIN(MIN(ma[2],ma[5]),ma[6]);
ma[3]=MIN(ma[3],ma[7]);
ma[4]=MIN(ma[4],ma[7]);
for(i=0;i<8;i++) printf("%d ", ma[i]);
printf("\n");
return 0;
}