Project Euler with Befunge


Fork me on GitHub
2015-01-28

Problem 054: Poker hands

Description:

In the card game poker, a hand consists of five cards and are ranked, from lowest to highest, in the following way:

  • High Card: Highest value card.
  • One Pair: Two cards of the same value.
  • Two Pairs: Two different pairs.
  • Three of a Kind: Three cards of the same value.
  • Straight: All cards are consecutive values.
  • Flush: All cards of the same suit.
  • Full House: Three of a kind and a pair.
  • Four of a Kind: Four cards of the same value.
  • Straight Flush: All cards are consecutive values of same suit.
  • Royal Flush: Ten, Jack, Queen, King, Ace, in same suit.

The cards are valued in the order: 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King, Ace.

If two players have the same ranked hands then the rank made up of the highest value wins; for example, a pair of eights beats a pair of fives (see example 1 below). But if two ranks tie, for example, both players have a pair of queens, then highest cards in each hand are compared (see example 4 below); if the highest cards tie then the next highest cards are compared, and so on.

Consider the following five hands dealt to two players:

Hand Player 1 Player 2 Winner
1 5H 5C 6S 7S KD 2C 3S 8S 8D TD Player 2
  Pair of Fives Pair of Eights  
2 5D 8C 9S JS AC 2C 5C 7D 8S QH Player 1
  Highest card Ace Highest card Queen  
3 2D 9C AS AH AC 3D 6D 7D TD QD Player 2
  Three Aces Flush with Diamonds  
4 4D 6S 9H QH QC 3D 6D 7H QD QS Player 1
  Pair of Queens Pair of Queens  
  Highest card Nine Highest card Seven  
5 2H 2D 4C 4D 4S 3C 3D 3S 9S 9D Player 1
  Full House Full House  
  With Three Fours with Three Threes  

The file, poker.txt, contains one-thousand random hands dealt to two players. Each line of the file contains ten cards (separated by a single space): the first five are Player 1's cards and the last five are Player 2's cards. You can assume that all hands are valid (no invalid characters or repeated cards), each player's hand is in no specific order, and in each hand there is a clear winner.

How many hands does Player 1 win?


Solution:
>096p"~"8*1+04p906p036p 116p   v

###############

$
$  $
$$ $$$$$ $
$$

8C TS KC 9H 4S 7D 2S 5D 3S AC
5C AD 5D AC 9C 7C 5H 8D TD KS
3H 7H 6S KC JS QH TD JC 2D 8S
TH 8H 5C QS TC 9H 4D JC KS JS               >"A"v
7C 5H KC QH JD AS KH 4C AD 4S  >36g06gg36g3%|
5H KS 9C 7D 9H 8D 3S 5D 5C AH               >"0"-55+\:89+-!#v_:39*-!#v_:"!"-!#v_ :892*+-!#v_:66*-!#v_\$v
6H 4H 5C 3H 2H 3S QH 5S 6S AS                   >          v>$1+    0>$1+    0>$1+       0>$1+    0>$1+v
TD 8C 4H 7C TC KC 4C 3H 7S KS          vp63+1g63           >#     #<                                   v
7C 9C 6D KD 3H 4C QS QC AC KH  |-g40g60<                           |-*65g63                 pg60-/3:g63<
JC 6S 5H 2H 2D KD 9D 7C AS JS  8       ^p60+1g60p630 pg60-/3:g63" "<
AD QH TH 9D 8H TS 6D 3S AS AC  0                 v  61g64p64+**"23"!!+++!-g65**+"$~ll"!-g65*9*93!-g<
2H 4S 5C 5S TC KC JD 6C TS 3C                    g   v$_v#!\-1:                                   <6       v<
QD AS 6H JS 2C 3D 9H KC 4H 8S                    7  > 3*> :2g:1-*48*8**46g+46p ::2g\1+2g*!!35g+35p^5       1g
KD 8S 9S 7C 2S 3S 6D 6S 4H KC  6                 p  5>46g66g+76g35**+35g4-!"A'"*5+*+7::*:**56g-!48*^       +2
3C 8C 2D 7D 4D 9S 4S QH 4H JD  p        >         v p  v_v#!\-1:<  v                 _v#!%+55p63:+2g63p2g50<g
8C KC 7S TC 2D TS 8H QD AC 5C  >16g!:16p|p61:!g61<>#5 88+> :0\2p^  #                               >g6v     5
3D KH QD 6C 6S AD AS 8H 2H QS           >06g1+06pv^ 3  >$$  16g55+*36p046p156p066p076p>36g06gg05p3v5v6<     0
6S 8D 4C 8S 6C QH TC 6D 7D 9D  vg71g70 _v#-g40g60<p ^0             <                  vg65gg60+1g6<0p       ^  p67g50<
2S 8D 8C 4C TS 9S 9D 9C AC 3D  >`96g+96v>07g17g`96 g+:96p.@                           >*56p05g66g` |>05g2g!#^_05g76g`|
3C QS 2S 4H JH 3D 2D TD 8S 9H          >          ^                                                >^       ^        <
5H QS 8S 6D 3C 8C JD AS 7H 7D
.  .  .
.  .  .
.  .  .
.  .  .
This program is too big to display/execute here, click [download] to get the full program.

Explanation:

Yep, I hate this problem.
Not only is there an enormous amount of input data that makes our program huge in size. But it contains a lot of different cases, rules and logic that needs be represented in our program

But none the less I tried to come up with an compact algorithm for scoring a set of cards

Get(@"https://projecteuler.net/project/resources/p054_poker.txt")
    .Where(p => GetScore(p.deck_1) > GetScore(p.deck_2))
    .Count()
    .Dump();
int GetScore(Card[] cards) {
    List<long> SUMS = new List<long>{ H*H*H*H*H, C*C*C*C*C, S*S*S*S*S, D*D*D*D*D };

    int[] array = new int[15];
    int score = 0;
    int flushSum = 1;
    int highCard = 0;
    int highGroup = 0;
    int straightIndex = 0;

    foreach(Card c in cards) {
        highCard = Math.Max(highCard, c.value);
        flushSum *= c.suit;
        if (array[c.value] > 0)
            highGroup = Math.Max(highGroup, c.value);
        array[c.value]++;
    }

    for(int i = 1; i < 15; i++)
    {
        score += (array[i]-1)*(array[i])*256;

        if (array[i] > 0 && array[i-1] > 0)
            straightIndex++;
    }
    score += highCard;
    score += highGroup * 15;

    if (straightIndex == 4)
        score += 2540;
    if (SUMS.Contains(flushSum))
        score += 2550;

    return score;
}

The different values are carefully crafted in such a way, that you can compare the score of two hands and get the winner

Card Calculation Score
High Card {0-14} * [1] = {0-14}
High Card (in Group) {0-14} * [15] = {0-210}
One Pair 2 * [256] = 512 (+ HighCard) (+ HighGroup)
Two Pairs 4 * [256] = 1024 (+ HighCard) (+ HighGroup)
Three of a Kind 6 * [256] = 1536 (+ HighCard) (+ HighGroup)
Straight [2540] = 2540 (+ HighCard) (+ HighGroup)
Flush [2550] = 2550 (+ HighCard) (+ HighGroup)
Full House 10 * [256] = 2560 (+ HighCard) (+ HighGroup)
Four of a Kind 12 * [256] = 3072 (+ HighCard) (+ HighGroup)
Straight Flush [2540] + [2550] = 5090 (+ HighCard) (+ HighGroup)
Royal Flush [2540] + [2550] = 5090 (+ HighCard) (+ HighGroup)

One last side note: A royal flush is not really a independent rank. Because of the "highest card in the rank" rule a royal flush is always better than a straight flush (because the highest card is an ace)


Interpreter steps: 5 949 695
Execution time (BefunExec): 2.54s (2.34 MHz)
Program size: 118 x 1009
Solution: 376
Solved at: 2015-01-28



made with vanilla PHP and MySQL, no frameworks, no bootstrap, no unnecessary* javascript