{"id":611,"date":"2012-08-09T10:16:19","date_gmt":"2012-08-09T14:16:19","guid":{"rendered":"http:\/\/www.joshho.com\/blog\/?p=611"},"modified":"2012-09-07T16:07:34","modified_gmt":"2012-09-07T20:07:34","slug":"project-euler-problem-54","status":"publish","type":"post","link":"https:\/\/www.joshho.com\/blog\/2012\/08\/09\/project-euler-problem-54\/","title":{"rendered":"Project Euler &#8211; Problem 54"},"content":{"rendered":"<p>Problem 54:<br \/>\nThe file, <a href='http:\/\/archiver.joshho.com\/display.php?full=1&#038;q=https:\/\/projecteuler.net\/project\/poker.txt' target='_blank'>poker.txt<\/a>, 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&#8217;s cards and the last five are Player 2&#8217;s cards. You can assume that all hands are valid (no invalid characters or repeated cards), each player&#8217;s hand is in no specific order, and in each hand there is a clear winner.<\/p>\n<p>How many hands does Player 1 win?<br \/>\n<!--more--><br \/>\n<code><\/p>\n<pre lang='java'>\r\npublic class Card implements Comparable<Card> {\r\n\tbyte n,s;\r\n\t\/**\r\n\t * \r\n\t * @param n Number\r\n\t * @param s Suit\r\n\t *\/\r\n\tpublic Card(byte n, byte s){\r\n\t\tthis.n = n; this.s = s;\r\n\t}\r\n\t@Override\r\n\tpublic int compareTo(Card o) {\r\n\t\tif(o.n == this.n)\r\n\t\t\treturn this.s - o.s;\r\n\t\treturn this.n-o.n;\r\n\t}\r\n\t\r\n\tpublic Card clone(){\r\n\t\treturn new Card(n,s);\r\n\t}\r\n\t\r\n\tpublic String toString(){\r\n\t\treturn n+\" \"+s;\r\n\t}\r\n}\r\n<\/pre>\n<p><\/code><br \/>\n<code><\/p>\n<pre lang='java'>\r\nimport java.io.BufferedReader;\r\nimport java.io.FileReader;\r\nimport java.io.IOException;\r\nimport java.util.Arrays;\r\nimport java.util.Vector;\r\n\r\nclass runner\r\n{\t\r\n\tprivate static byte isSameSuite(Card[] arr){\r\n\t\tbyte suit = arr[0].s;\r\n\t\tfor(byte i=1; i<arr.length; i++){\r\n\t\t\tif(suit != arr[i].s)\r\n\t\t\t\treturn -1;\r\n\t\t}\r\n\t\treturn suit;\r\n\t}\r\n\r\n\tprivate static byte consecutiveLowestNumber(Card[] normalized){\r\n\t\tif(normalized.length != 5) return -1;\r\n\t\tCard[] normalizedcopy = new Card[5];\r\n\t\tfor(byte i=0; i<normalized.length; i++){\r\n\t\t\tnormalizedcopy[i] = normalized[i];\r\n\t\t}\r\n\t\tArrays.sort(normalizedcopy);\r\n\t\tif((normalizedcopy[0].n+1 == normalizedcopy[1].n) \r\n\t\t\t\t&#038;&#038; (normalizedcopy[1].n+1 == normalizedcopy[2].n)\r\n\t\t\t\t&#038;&#038; (normalizedcopy[2].n+1 == normalizedcopy[3].n)\r\n\t\t\t\t&#038;&#038; (normalizedcopy[3].n+1 == normalizedcopy[4].n))\r\n\t\t\treturn normalizedcopy[0].n;\r\n\t\treturn -1;\r\n\t}\r\n\r\n\t\/**\r\n\t * \r\n\t * @param cards\r\n\t * @return [0] NumberOfDupe [1] Value of Card\r\n\t *\/\r\n\tprivate static byte[] numOfHighestDuplicate(Card[] cards){\r\n\t\tbyte[] arr = new byte[13];\r\n\t\tbyte[] result = new byte[2]; \r\n\r\n\t\tbyte max = 0, highcard = -1;\r\n\t\tfor(byte i=0; i<cards.length; i++){\r\n\t\t\tbyte ch = cards[i].n;\r\n\t\t\tbyte y = ++arr[ch];\r\n\t\t\tif(max < y){\r\n\t\t\t\thighcard = ch;\r\n\t\t\t\tmax = y;\r\n\t\t\t}else if(max == y){\r\n\t\t\t\tif(highcard < ch){\r\n\t\t\t\t\thighcard = ch;\r\n\t\t\t\t}\r\n\t\t\t}\r\n\t\t}\r\n\t\tresult[0]=max;result[1]=highcard;\r\n\t\treturn result;\r\n\t}\r\n\r\n\tprivate static byte normalizeNumbers(char x){\r\n\t\tif(x=='A') return 12;\r\n\t\tif(x=='K') return 11;\r\n\t\tif(x=='Q') return 10;\r\n\t\tif(x=='J') return 9;\r\n\t\tif(x=='T') return 8;\r\n\t\treturn (byte)(x - 50);\/\/48-0, 49-1, 50-2\r\n\t}\r\n\r\n\tprivate static byte normalizeSuit(char x){\r\n\t\tif(x=='S') return 3;\r\n\t\tif(x=='H') return 2;\r\n\t\tif(x=='C') return 1;\r\n\t\treturn 0;\r\n\t}\r\n\r\n\tprivate static Card[] normalizeArr(String[] arr){\r\n\t\tCard[] result = new Card[arr.length];\r\n\t\tfor(int i=0; i<arr.length;i++){\r\n\t\t\tresult[i] = new Card(normalizeNumbers(arr[i].charAt(0)), normalizeSuit(arr[i].charAt(1)));\r\n\t\t}\r\n\t\treturn result;\r\n\t}\r\n\r\n\tprivate static Card[] filterArr(Card[] arr, byte[] filterNum){\r\n\t\tVector<Card> tmp = new Vector<Card>();\r\n\t\tfor(int i=0;i<arr.length;i++){\r\n\t\t\tboolean found = false;\r\n\t\t\tfor(int j=0;j<filterNum.length;j++){\r\n\t\t\t\tif(arr[i].n == filterNum[j]){\r\n\t\t\t\t\tfound = true; break;\r\n\t\t\t\t}\r\n\t\t\t}\r\n\t\t\tif(!found){\r\n\t\t\t\ttmp.add(arr[i].clone());\r\n\t\t\t}\r\n\t\t}\r\n\t\tCard[] result = new Card[tmp.size()];\r\n\t\tfor(int i=0; i<result.length; i++){\r\n\t\t\tresult[i] = tmp.get(i);\r\n\t\t}\r\n\t\treturn result;\r\n\t}\r\n\r\n\tpublic static boolean winner(String[] raw1, String[] raw2){\r\n\t\tCard[] cards1 = normalizeArr(raw1), cards2 = normalizeArr(raw2);\r\n\t\treturn winner_aux(cards1, cards2);\r\n\t}\r\n\r\n\t\/\/true is player 1\r\n\tpublic static boolean winner_aux(Card[] cards1, Card[] cards2){\r\n\t\t\/\/Gets the number of duplicates and the card that is being duplicated\r\n\t\tbyte[] dupeAndCard1 = numOfHighestDuplicate(cards1), dupeAndCard2 = numOfHighestDuplicate(cards2);\r\n\t\tbyte[] filterTripleOrPair1 = {dupeAndCard1[1]}, filterTripleOrPair2 = {dupeAndCard2[1]};\r\n\t\tCard[] leftOverCards1 = filterArr(cards1, filterTripleOrPair1), leftOverCards2 = filterArr(cards2, filterTripleOrPair2);\r\n\t\tbyte[] dupeOfLeftOverCards1 = numOfHighestDuplicate(leftOverCards1), dupeOfLeftOverCards2 = numOfHighestDuplicate(leftOverCards2);\r\n\r\n\t\tif(cards1.length == 5){\/\/they should have the same # of cards\r\n\t\t\tbyte samesuit1 = isSameSuite(cards1), samesuit2 = isSameSuite(cards2);\r\n\t\t\tbyte consecLow1 = consecutiveLowestNumber(cards1), consecLow2 = consecutiveLowestNumber(cards2);\r\n\r\n\t\t\t\/\/check for royal flush\r\n\t\t\tif(consecLow1 == 8 &#038;&#038; consecLow2 == 8){\r\n\t\t\t\tif(samesuit1 > samesuit2) return true;\r\n\t\t\t\treturn false;\r\n\t\t\t}else if(consecLow1 == 8) return true;\r\n\t\t\telse if(consecLow2 == 8) return false;\r\n\r\n\t\t\t\/\/check for Straight Flush\r\n\t\t\tif(consecLow1 != -1 && consecLow2 != -1 && samesuit1 != -1 && samesuit2 != -1){\r\n\t\t\t\tif(consecLow1 == consecLow2){\r\n\t\t\t\t\tif(samesuit1 > samesuit2) return true;\r\n\t\t\t\t\telse return false;\r\n\t\t\t\t}else if(consecLow1 > consecLow2) return true;\r\n\t\t\t\treturn false;\r\n\t\t\t}else if(consecLow1 != -1 && samesuit1 != -1 ) return true;\r\n\t\t\telse if(consecLow2 != -1  && samesuit2 != -1 ) return false;\r\n\r\n\t\t\t\/\/Check for four of a kind\r\n\t\t\tif(dupeAndCard1[0] == 4 && dupeAndCard2[0] == 4){\r\n\t\t\t\tif(dupeAndCard1[1] > dupeAndCard2[1]) return true;\r\n\t\t\t\telse if(dupeAndCard1[1] < dupeAndCard2[1]) return false;\r\n\t\t\t\telse{\/\/check for next 'highest card'\r\n\t\t\t\t\tSystem.out.println(\"invalid! \");\r\n\t\t\t\t\treturn false;\r\n\t\t\t\t}\r\n\t\t\t}else if(dupeAndCard1[0] == 4) return true;\r\n\t\t\telse if(dupeAndCard2[0] == 4) return false;\r\n\r\n\t\t\t\/\/Full House\r\n\t\t\tif((dupeAndCard1[0] == 3 &#038;&#038; dupeOfLeftOverCards1[0] == 2) &#038;&#038; (dupeAndCard2[0] == 3 &#038;&#038; dupeOfLeftOverCards2[0] == 2)){ \/\/Either have triples.\r\n\t\t\t\tif(dupeAndCard1[1] > dupeAndCard2[1]) return true;\r\n\t\t\t\treturn false;\r\n\t\t\t\t\/\/Keep going if it's only a triple.\r\n\t\t\t}else if(dupeAndCard1[0] == 3 && dupeOfLeftOverCards1[0] == 2) return true;\r\n\t\t\telse if(dupeAndCard2[0] == 3 && dupeOfLeftOverCards2[0] == 2) return false;\r\n\t\t\t\r\n\r\n\t\t\t\/\/Flush\r\n\t\t\tif(samesuit1 != -1 && samesuit2 != -1){\/\/Both have flushes... check for high card\r\n\t\t\t\tif(dupeAndCard1[1] > dupeAndCard2[1]) return true;\r\n\t\t\t\treturn false;\r\n\t\t\t}else if(samesuit1 != -1) return true;\r\n\t\t\telse if(samesuit2 != -1) return false;\r\n\r\n\t\t\t\/\/Straight\r\n\t\t\tif(consecLow1 > -1 || consecLow2 > -1){\r\n\t\t\t\tif(consecLow1 == consecLow2){\r\n\t\t\t\t\t\/\/tie... we should check suit, but Q. does not have that as answer.\r\n\t\t\t\t\tSystem.out.println(\"not supposed to get here... straight tie\");\r\n\t\t\t\t}else if(consecLow1 > consecLow2) return true;\r\n\t\t\t\treturn false;\r\n\t\t\t}\r\n\t\t}\r\n\r\n\t\tif(cards1.length >= 3){\r\n\t\t\t\/\/Three of a Kind:\r\n\t\t\tif(dupeAndCard1[0] == 3 &&dupeAndCard2[0] == 3){\r\n\t\t\t\t\/\/Full house is out of the equation, just highcard of triple.\r\n\t\t\t\tif(dupeOfLeftOverCards1[1] > dupeOfLeftOverCards2[1]) return true;\r\n\t\t\t\treturn false;\r\n\t\t\t}else if(dupeAndCard1[0] == 3) return true;\r\n\t\t\telse if(dupeAndCard2[0] == 3) return false;\r\n\t\t}\r\n\r\n\t\tif(cards1.length >= 4){\r\n\t\t\t\/\/Two Pairs: Two different pairs.\r\n\t\t\tif((dupeAndCard1[0] == 2 && dupeOfLeftOverCards1[0] == 2) && (dupeAndCard2[0] == 2 && dupeOfLeftOverCards2[0] == 2)){\r\n\t\t\t\t\/\/both sides have two pair\r\n\t\t\t\tif(dupeAndCard1[1] > dupeAndCard2[1]) return true;\r\n\t\t\t\telse if(dupeAndCard1[1] < dupeAndCard2[1]) return false;\r\n\t\t\t\telse{\/\/they are equal.. check second pair\r\n\t\t\t\t\tif(dupeOfLeftOverCards1[1] > dupeOfLeftOverCards2[1]) return true;\r\n\t\t\t\t\telse if(dupeOfLeftOverCards1[1] < dupeOfLeftOverCards2[1]) return false;\r\n\t\t\t\t\telse{\/\/both pairs are the same.. check highcard... \r\n\t\t\t\t\t\tbyte[] filterHighCard1 = {dupeAndCard1[1], dupeOfLeftOverCards1[1]}, filterHighCard2 = {dupeAndCard2[1], dupeOfLeftOverCards2[1]};\r\n\t\t\t\t\t\tCard[] highCard1 = filterArr(cards1, filterHighCard1), highCard2 = filterArr(cards2, filterHighCard2);\r\n\t\t\t\t\t\t\/*if(highCard1[0].n > highCard2[0].n) return true;\r\n\t\t\t\t\t\telse if(highCard1[0].n < highCard2[0].n) return false;\r\n\t\t\t\t\t\telse{\/\/same card as well wtf. check highcard suite.\r\n\t\t\t\t\t\t\tif(highCard1[0].s > highCard2[0].s) return true;\r\n\t\t\t\t\t\t\treturn false;\r\n\t\t\t\t\t\t}*\/\r\n\t\t\t\t\t\treturn winner_aux(highCard1, highCard2);\r\n\t\t\t\t\t}\r\n\t\t\t\t}\r\n\t\t\t}else if(dupeAndCard1[0] == 2 && dupeOfLeftOverCards1[0] == 2) return true;\r\n\t\t\telse if(dupeAndCard2[0] == 2 && dupeOfLeftOverCards2[0] == 2) return false;\r\n\t\t}\r\n\r\n\t\tif(cards1.length >= 2){\r\n\t\t\t\/\/Single Pair\r\n\t\t\tif(dupeAndCard1[0] == 2 && dupeAndCard2[0] == 2){\r\n\t\t\t\tif(dupeAndCard1[1] > dupeAndCard2[1]) return true;\r\n\t\t\t\telse if(dupeAndCard1[1] < dupeAndCard2[1]) return false;\r\n\t\t\t\telse{\r\n\t\t\t\t\tif(dupeOfLeftOverCards1[1] > dupeOfLeftOverCards2[1]) return true;\r\n\t\t\t\t\telse if(dupeOfLeftOverCards1[1] < dupeOfLeftOverCards2[1]) return false;\r\n\t\t\t\t\telse{\/\/two more cards to check.. will need to filter again\r\n\t\t\t\t\t\tbyte[] filterTwoCards1 = {dupeAndCard1[1], dupeOfLeftOverCards1[1]}, filterTwoCards2 = {dupeAndCard2[1], dupeOfLeftOverCards2[1]};\r\n\t\t\t\t\t\tCard[] lastTwoCards1 = filterArr(cards1, filterTwoCards1), lastTwoCards2 = filterArr(cards2, filterTwoCards2);\r\n\t\t\t\t\t\tbyte[] dupeAndCardOfTwo1 = numOfHighestDuplicate(lastTwoCards1), dupeAndCardOfTwo2 = numOfHighestDuplicate(lastTwoCards2);\r\n\t\t\t\t\t\tif(dupeAndCardOfTwo1[1] > dupeAndCardOfTwo2[1]) return true;\r\n\t\t\t\t\t\telse if(dupeAndCardOfTwo1[1] < dupeAndCardOfTwo1[1]) return false;\r\n\t\t\t\t\t\telse{\/\/one more card to check...\r\n\t\t\t\t\t\t\tbyte[] filterLastCard1 = {dupeAndCardOfTwo1[1]}, filterLastCard2 = {dupeAndCardOfTwo1[1]};\r\n\t\t\t\t\t\t\tCard[] lastCard1 = filterArr(lastTwoCards1, filterLastCard1), lastCard2 = filterArr(lastTwoCards2, filterLastCard2);\r\n\t\t\t\t\t\t\tif(lastCard1[0].n > lastCard2[0].n) return true;\r\n\t\t\t\t\t\t\treturn false;\r\n\t\t\t\t\t\t}\r\n\t\t\t\t\t}\r\n\t\t\t\t}\r\n\t\t\t}else if(dupeAndCard1[0] == 2) return true;\r\n\t\t\telse if(dupeAndCard2[0] == 2) return false;\r\n\t\t}\r\n\r\n\t\t\/\/Single\r\n\t\tif(dupeAndCard1[1] == dupeAndCard2[1]){\r\n\t\t\tbyte[] filterCard1 = {dupeAndCard1[1]}, filterCard2 = {dupeAndCard2[1]};\r\n\t\t\tCard[] lastCards1 = filterArr(cards1, filterCard1), lastCards2 = filterArr(cards2, filterCard2);\r\n\t\t\treturn winner_aux(lastCards1, lastCards2);\r\n\t\t}else if(dupeAndCard1[1] > dupeAndCard2[1]) return true;\r\n\t\telse return false;\r\n\t}\r\n\r\n\r\n\tpublic static void testing(String p1, String p2, boolean winner){\r\n\t\tboolean result = winner(p1.split(\" \"), p2.split(\" \"));\r\n\t\tSystem.out.println(\"Test - P1:\"+p1+\" P2:\"+p2+\" Expected:\"+winner+\" actual:\"+result+\" \\tNet:\"+(result==winner));\r\n\t}\r\n\t\r\n\tpublic static void main (String[] args) throws java.lang.Exception\r\n\t{\r\n\t\tlong time = System.currentTimeMillis();\r\n\r\n\t\t\r\n\t\tint c=0;\r\n\t\ttry {\r\n\t\t    BufferedReader in = new BufferedReader(new FileReader(\"http:\/\/archiver.joshho.com\/display.php?full=1&q=https:\/\/projecteuler.net\/project\/poker.txt\"));\r\n\t\t    String str;\r\n\t\t    while ((str = in.readLine()) != null) {\r\n\t\t        String[] cur = str.split(\" \");\r\n\t\t        boolean result = winner(Arrays.copyOfRange(cur, 0, 5),Arrays.copyOfRange(cur, 5, cur.length));\r\n\t\t    \tSystem.out.println(str + \" \" + result);\r\n\t\t        if(result){\r\n\t\t        \tc++;\r\n\t\t        }\r\n\t\t    }\r\n\t\t    in.close();\r\n\t\t} catch (IOException e) {\r\n\t\t}\r\n\t\tSystem.out.println(\"c:\"+c);\r\n\r\n\t\tSystem.out.println(\"time: \"+(System.currentTimeMillis() - time));\r\n\t}\r\n}\r\n<\/pre>\n<p><\/code><br \/>\nNote: Once again, not my best effort.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem 54:<br \/>\nThe file, <a href='http:\/\/archiver.joshho.com\/display.php?full=1&#038;q=https:\/\/projecteuler.net\/project\/poker.txt' target='_blank'>poker.txt<\/a>, 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&#8217;s cards and the last five are Player 2&#8217;s cards. You can assume that all hands are valid (no invalid characters or repeated cards), each player&#8217;s hand is in no specific order, and in each hand there is a clear winner.<\/p>\n<p>How many hands does Player 1 win?<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[56],"tags":[],"_links":{"self":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/611"}],"collection":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/comments?post=611"}],"version-history":[{"count":0,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/611\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/media?parent=611"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/categories?post=611"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/tags?post=611"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}