project-euler

https://projecteuler.net/
Log | Files | Refs | README

Euler_54.cpp (6076B)

      1 #include <algorithm>
      2 #include <fstream>
      3 #include <functional>
      4 #include <unordered_set>
      5 
      6 #include "Euler.h"
      7 
      8 struct hand
      9 {
     10     int handValue;
     11     std::vector<int> cardValues;
     12 };
     13 
     14 struct game
     15 {
     16     hand hands[2];
     17 };
     18 
     19 char order[] = {'2', '3', '4', '5', '6', '7', '8', '9', 'T', 'J', 'Q', 'K', 'A'};
     20 
     21 bool isFlush(std::vector<std::string>& hand)
     22 {
     23     char c = hand[0][1];
     24 
     25     for (uint64_t i = 1; i < hand.size(); ++i)
     26         if (hand[i][1] != c)
     27             return false;
     28 
     29     return true;
     30 }
     31 
     32 bool isStraight(std::vector<int> indices)
     33 {
     34     for (uint64_t i = 1; i < indices.size(); ++i)
     35         if (indices[i] != indices[i - 1] - 1)
     36             return false;
     37 
     38     return true;
     39 }
     40 
     41 std::vector<int> getCardValues(std::vector<std::string>& hand)
     42 {
     43     std::vector<int> indices;
     44 
     45     for (uint64_t i = 0; i < hand.size(); ++i) {
     46         for (int j = 0; j < 13; ++j)
     47         {
     48             char c = hand[i][0];
     49             if (c == order[j])
     50             {
     51                 indices.push_back(j);
     52                 break;
     53             }
     54         }
     55     }
     56 
     57     std::sort(indices.begin(), indices.end(), std::greater<int>());
     58 
     59     return indices;
     60 }
     61 
     62 int determineNoOfRepeats(std::unordered_set<int>& us, std::vector<int>& cardValues, int t, int def, int high)
     63 {
     64     for (int j : us)
     65     {
     66         int total = 0;
     67 
     68         for (uint64_t k = 0; k < cardValues.size(); ++k)
     69             if (j == cardValues[k])
     70                 ++total;
     71 
     72         if (total == t)
     73             return high;
     74     }
     75 
     76     return def;
     77 }
     78 
     79 int determineRepeat(std::unordered_set<int>& us, std::vector<int>& cardValues, int rep, bool skip)
     80 {
     81     for (int j : us)
     82     {
     83         int total = 0;
     84 
     85         for (uint64_t k = 0; k < cardValues.size(); ++k)
     86             if (j == cardValues[k])
     87                 ++total;
     88 
     89         if (total == rep)
     90         {
     91             if (skip)
     92                 skip = false;
     93             else
     94                 return j;
     95         }
     96     }
     97 
     98     return -1;
     99 }
    100 
    101 void determinePriorityOrder(hand& h, std::unordered_set<int>& us)
    102 {
    103     if (h.handValue == 4 || h.handValue == 0)
    104         return;
    105 
    106     std::vector<int> values(h.cardValues);
    107     int rep1, rep2, no = 0;
    108 
    109     switch(h.handValue)
    110     {
    111     case 1:
    112         rep1 = determineRepeat(us, h.cardValues, 2, false);
    113 
    114         for (uint64_t i = 0; i < h.cardValues.size(); ++i) {
    115             if (h.cardValues[i] == rep1)
    116                 std::swap(h.cardValues[no++], h.cardValues[i]);
    117         }
    118 
    119         std::sort(h.cardValues.begin() + 2, h.cardValues.end(), std::greater<int>());
    120         break;
    121     case 2:
    122         rep1 = determineRepeat(us, h.cardValues, 2, true);
    123         rep2 = determineRepeat(us, h.cardValues, 2, false);
    124 
    125         if (rep2 > rep1)
    126             std::swap(rep1, rep2);
    127 
    128         for (uint64_t i = 0; i < h.cardValues.size(); ++i)
    129         {
    130             if (h.cardValues[i] == rep1)
    131                 std::swap(h.cardValues[no++], h.cardValues[i]);
    132         }
    133 
    134         for (uint64_t i = 0; i < h.cardValues.size(); ++i)
    135             if (h.cardValues[i] == rep2)
    136                 std::swap(h.cardValues[no++], h.cardValues[i]);
    137         break;
    138     case 3:
    139         rep1 = determineRepeat(us, h.cardValues, 3, false);
    140 
    141         for (uint64_t i = 0; i < h.cardValues.size(); ++i) {
    142             if (h.cardValues[i] == rep1)
    143                 std::swap(h.cardValues[no++], h.cardValues[i]);
    144         }
    145 
    146         std::sort(h.cardValues.begin() + 3, h.cardValues.end(), std::greater<int>());
    147         break;
    148     case 6:
    149         rep1 = determineRepeat(us, h.cardValues, 3, false);
    150         for (uint64_t i = 0; i < h.cardValues.size(); ++i)
    151             if (h.cardValues[i] == rep1)
    152                 std::swap(h.cardValues[no++], h.cardValues[i]);
    153 
    154         break;
    155     case 7:
    156         rep1 = determineRepeat(us, h.cardValues, 4, false);
    157 
    158         for (uint64_t i = 0; i < h.cardValues.size(); ++i)
    159             if (h.cardValues[i] == rep1)
    160                 std::swap(h.cardValues[no++], h.cardValues[i]);
    161         break;
    162     }
    163 }
    164 
    165 game determineHands(std::vector<std::string>& cards)
    166 {
    167     game g;
    168 
    169     std::vector<std::string> hands[2];
    170 
    171     hands[0] = std::vector<std::string>(cards.begin(), cards.begin() + 5);
    172     hands[1] = std::vector<std::string>(cards.begin() + 5, cards.end());
    173 
    174     for (int i = 0; i < 2; ++i)
    175     {
    176         g.hands[i].cardValues = getCardValues(hands[i]);
    177 
    178         if (isFlush(hands[i]))
    179         {
    180             g.hands[i].handValue = isStraight(g.hands[i].cardValues) ? (g.hands[i].cardValues[4] == 12 ? 9 : 8) : 5;
    181         }
    182         else
    183         {
    184             std::unordered_set<int> us;
    185 
    186             for (int j : g.hands[i].cardValues)
    187                 us.insert(j);
    188 
    189             switch(us.size())
    190             {
    191             case 2:
    192                 g.hands[i].handValue = determineNoOfRepeats(us, g.hands[i].cardValues, 4, 6, 7);
    193                 break;
    194             case 3:
    195                 g.hands[i].handValue = determineNoOfRepeats(us, g.hands[i].cardValues, 3, 2, 3);
    196                 break;
    197             case 4:
    198                 g.hands[i].handValue = 1;
    199                 break;
    200             case 5:
    201                 g.hands[i].handValue = isStraight(g.hands[i].cardValues) ? 4 : 0;
    202                 break;
    203             }
    204 
    205             determinePriorityOrder(g.hands[i], us);
    206         }
    207 
    208 
    209     }
    210 
    211     return g;
    212 }
    213 
    214 bool determineWinner(game g) //assumes no draws
    215 {
    216     if (g.hands[0].handValue > g.hands[1].handValue)
    217         return false;
    218 
    219     if (g.hands[1].handValue > g.hands[0].handValue)
    220         return true;
    221 
    222     for (uint64_t i = 0; i < g.hands[0].cardValues.size(); ++i)
    223     {
    224         if (g.hands[0].cardValues[i] > g.hands[1].cardValues[i])
    225             return false;
    226 
    227         if (g.hands[1].cardValues[i] > g.hands[0].cardValues[i])
    228             return true;
    229     }
    230 
    231     return true;
    232 }
    233 
    234 int Euler::PokerHands()
    235 {
    236     int scores[2] = {0, 0};
    237 
    238     std::ifstream fin;
    239     fin.open("files/p054_poker.txt");
    240 
    241     for (std::string line; std::getline(fin, line);) {
    242         std::vector<std::string> tokens = EulerUtility::strTokenizer(line, ' ');
    243         ++scores[determineWinner(determineHands(tokens))];
    244     }
    245 
    246     fin.close();
    247 
    248     return scores[0];
    249 }