Project Euler #54 Solution

Question

This is not the latest question in iterative code review of this program. You can find the latest answer here.

Here's my solution to Project Euler #54. Click the link for the full project description (abbreviated here):

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?

9 classes but most of them are short enums.

Note: You will need to put the data file poker.txt on your classpath.

Card.java

package problem54;
public class Card implements Comparable<Card> {
 private final Value value;
 private final Suit suit;
 public Card(Value value, Suit suit) {
 this.value = value;
 this.suit = suit;
 }
 public Card(String s) {
 this(Value.of(s.charAt(0)), Suit.of(s.charAt(1)));
 }
 public Value getValue() {
 return value;
 }
 public Suit getSuit() {
 return suit;
 }
 @Override
 public int compareTo(Card o) {
 return value.compareTo(o.value);
 }
 @Override
 public String toString() {
 return String.format("%s_%s", value.getChar(), suit.getChar());
 }
}

Hand.java (the Heavy Lifting is here)

package problem54;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
public class Hand implements Comparable<Hand> {
 private final List<Card> cards;
 private final ValueRanking ranking;
 public Hand(List<Card> cards) {
 List<Card> temp = new ArrayList<>(cards);
 temp.add(new Card(Value.NULL, Suit.NULL));
 Collections.sort(temp);
 this.cards = Collections.unmodifiableList(temp);
 ValueRanking straightRanking = straightRanking();
 if(straightRanking != null) {
 ranking = straightRanking;
 } else {
 ranking = pairRanking();
 }
 }
 public List<Card> getCards() {
 return cards;
 }
 private ValueRanking straightRanking() {
 if(isStraight() && isFlush()) {
 return new ValueRanking(Ranking.STRAIGHT_FLUSH, cards.get(4).getValue(), (Value) null, Collections.<Value>emptyList());
 } else if(isFlush()) {
 List<Value> kickers = new LinkedList<Value>();
 kickers.add(cards.get(2).getValue());
 kickers.add(cards.get(1).getValue());
 kickers.add(cards.get(0).getValue());
 return new ValueRanking(Ranking.FLUSH, cards.get(4).getValue(), cards.get(3).getValue(), kickers);
 } else if(isStraight()) {
 return new ValueRanking(Ranking.STRAIGHT_FLUSH, cards.get(4).getValue(), (Value) null, Collections.<Value>emptyList());
 } else {
 return null;
 }
 }
 public ValueRanking getRanking() {
 return ranking;
 }
 private ValueRanking pairRanking() {
 Value v = null;
 int counter = 0;
 int pair = 0, trips = 0, quads = 0;
 Value primary = null;
 Value secondary = null;
 List<Value> kicker = new LinkedList<>();
 for(Card c : cards) {
 Value current = c.getValue();
 if(v != current) {
 switch(counter) {
 case 2:
 pair++;
 if(primary == null) {
 primary = v;
 } else if(trips > 0 || primary.compareTo(current) > 0) {
 secondary = current;
 } else {
 secondary = primary;
 primary = v;
 }
 break;
 case 3:
 trips++;
 secondary = primary;
 primary = v;
 break;
 case 4:
 quads++;
 primary = v;
 break;
 default:
 if(v != null) kicker.add(v);
 }
 v = current;
 counter = 1;
 } else {
 counter++;
 }
 }
 if(quads > 0) {
 return new ValueRanking(Ranking.QUADS, primary, secondary, kicker);
 } else if(trips > 0) {
 if(pair > 0) return new ValueRanking(Ranking.FULL_HOUSE, primary, secondary, kicker);
 else return new ValueRanking(Ranking.TRIPS, primary, secondary, kicker);
 } else if(pair == 2) {
 return new ValueRanking(Ranking.TWO_PAIR, primary, secondary, kicker);
 } else if(pair == 1) {
 return new ValueRanking(Ranking.PAIR, primary, secondary, kicker);
 } else {
 return new ValueRanking(Ranking.HIGH_CARD, primary, secondary, kicker);
 }
 }
 private boolean isStraight() {
 for(int i = 0; i < 4; i++) {
 if(cards.get(i).getValue().ordinal() + 1 != cards.get(i+1).getValue().ordinal()) return false;
 }
 return true;
 }
 private boolean isFlush() {
 for(int i = 0; i < 4; i++) {
 if(cards.get(i).getSuit() != cards.get(i+1).getSuit()) return false;
 }
 return true;
 }
 @Override
 public int compareTo(Hand o) {
 return ranking.compareTo(o.ranking);
 }
}

Parser.java

package problem54;
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
public class Parser implements Closeable {
 private final BufferedReader reader;
 public Parser(InputStream in) {
 this.reader = new BufferedReader(new InputStreamReader(in));
 }
 public Round getNextRound() throws IOException {
 String nextLine = reader.readLine();
 String[] cardStrings = nextLine.split(" ");
 List<Card> cardList = new LinkedList<>();
 for(String cardString : cardStrings) {
 cardList.add(new Card(cardString));
 }
 return new Round(cardList);
 }
 public void close() throws IOException {
 reader.close();
 }
 public boolean hasNext() throws IOException {
 return reader.ready();
 }
}

Problem.java (Main method)

package problem54;
import java.io.IOException;
import java.io.InputStream;
public class Problem {
 public static void main(String... args) throws IOException {
 InputStream is = Problem.class.getResourceAsStream("/p054_poker.txt");
 Parser p = new Parser(is);
 int counter = 0;
 while(p.hasNext()) {
 Round r = p.getNextRound();
 if(r.playerOneWins()) counter++;
 }
 System.out.println(counter);
 p.close();
 }
}

Ranking.java

public enum Ranking {
 HIGH_CARD,
 PAIR,
 TWO_PAIR,
 TRIPS,
 STRAIGHT,
 FLUSH,
 FULL_HOUSE,
 QUADS,
 STRAIGHT_FLUSH;
}

Round.java

package problem54;
import java.util.List;
public class Round {
 public final Hand playerOne;
 public final Hand playerTwo;
 public Round(List<Card> cardList) {
 List<Card> firstCards = cardList.subList(0, 5);
 this.playerOne = new Hand(firstCards);
 List<Card> secondCards = cardList.subList(5, 10);
 this.playerTwo = new Hand(secondCards);
 }
 public boolean playerOneWins() {
 return playerOne.compareTo(playerTwo) > 0;
 }
}

Suit.java

package problem54;
import java.util.HashMap;
import java.util.Map;
public enum Suit {
 HEART ('H'),
 DIAMOND ('D'),
 SPADE ('S'),
 CLUB ('C'),
 NULL ('x');
 private final char suitChar;
 private static final Map<Character, Suit> valueMap = new HashMap<>();
 static {
 for(Suit c : Suit.values()) {
 valueMap.put(c.getChar(), c);
 }
 }
 private Suit(char cardString) {
 this.suitChar = cardString;
 }
 public char getChar() {
 return suitChar;
 }
 public static Suit of(char value) {
 Suit s = valueMap.get(value);
 if(s == null) return NULL;
 return s;
 }
}

Value.java

package problem54;
import java.util.HashMap;
import java.util.Map;
public enum Value {
 TWO ('2'),
 THREE ('3'),
 FOUR ('4'),
 FIVE ('5'),
 SIX ('6'),
 SEVEN ('7'),
 EIGHT ('8'),
 NINE ('9'),
 TEN ('T'),
 JACK ('J'),
 QUEEN ('Q'),
 KING ('K'),
 ACE ('A'),
 NULL ('x');
 private final char valueChar;
 private static final Map<Character, Value> valueMap = new HashMap<>();
 static {
 for(Value c : Value.values()) {
 valueMap.put(c.getChar(), c);
 }
 }
 private Value(char cardString) {
 this.valueChar = cardString;
 }
 public char getChar() {
 return valueChar;
 }
 public static Value of(char value) {
 Value v = valueMap.get(value);
 if(v == null) return NULL;
 return v;
 }
}

ValueRanking.java

package problem54;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class ValueRanking implements Comparable<ValueRanking> {
 private final Ranking rank;
 private final Value primary;
 private final Value secondary;
 private final List<Value> kicker;
 public ValueRanking(Ranking rank, Value primary, Value secondary, List<Value> kicker) {
 this.rank = rank;
 this.primary = primary == null ? Value.NULL : primary;
 this.secondary = secondary == null ? Value.NULL : secondary;
 List<Value> kickerTemp = new ArrayList<>(kicker);
 try {
 Collections.sort(kickerTemp);
 } catch (NullPointerException e) {
 System.out.println(kicker);
 throw e;
 }
 Collections.reverse(kickerTemp);
 this.kicker = Collections.unmodifiableList(kickerTemp);
 }
 public Ranking getRank() {
 return rank;
 }
 public Value getPrimary() {
 return primary;
 }
 public Value getSecondary() {
 return secondary;
 }
 public List<Value> getKicker() {
 return kicker;
 }
 @Override
 public int compareTo(ValueRanking o) {
 if(rank.compareTo(o.rank) != 0) return rank.compareTo(o.rank);
 else if(primary.compareTo(o.primary) != 0) return primary.compareTo(o.primary);
 else if(secondary.compareTo(o.secondary) != 0) return secondary.compareTo(o.secondary);
 else {
 for(int i = 0; i < kicker.size(); i++) {
 if(kicker.get(i).compareTo(o.kicker.get(i)) != 0) return kicker.get(i).compareTo(o.kicker.get(i));
 }
 return 0;
 }
 }
 @Override
 public String toString() {
 return String.format(
 "[%s,%s,%s,%s]",
 rank, primary, secondary, kicker);
 }
}

• barq: What is primary and secondary? These don't seem to be standard poker terms and is hard to understand what you are doing without comments.
• durron597: @barq For Q227Q, Value.QUEEN is primary, Value.TWO is secondary, and Value.Seven is a kicker. Similarly, for 2QQ22, Value.TWO would be primary, Value.QUEEN would be secondary. This is how I compare Q227Q to Q553Q, Q = Q, then 5 > 2.
• durron597: Whoops I forgot to remove some debugging code in the ValueRanking class

Answer 1

For the most part, this is beautiful code. The way you lay out the classes is logical, the implementation is clean, following good practices, even the formatting is almost impeccable. But if I look closer, some odd elements do pop up, and in the end it looks as if you rushed the second half of the implementation.

Parsing

The Parser class is very nicely written. But it doesn't fully complete its job. The fact that the first 5 cards per line belong to one player and the second 5 cards belong to another is dealt with here, and left for Round to handle. It would be better if all the logic related to parsing the input into program objects was encapsulated in Parser (= hidden from the rest of the program). The Round class could just be in charge of holding the Hands of players, and oblivious to the fact that the hands come from a set of 10 cards, and the implied magic number 5.

Storing cards in a LinkedList

I noticed with suspicion in the Parser that cards are added to a LinkedList. A linked list is great when you frequently add or delete the first or last element. But in modeling a poker game it's not really obvious when and how this would be useful. On closer look, I see that you're not taking advantage of the cards being in a LinkedList. In fact there are lots of random accesses of elements.

And it gets worse. The Round class creates the hands using .subList on the original LinkedList of 10 cards. The consequence of that is when you do cards.get(2) later in the program on the hand that comes from cardList.subList(5, 10), the underlying LinkedList will be traversed from the first element to the 7th.

There are two important points here:

• Use the List implementation appropriate for the purpose. In the program an ArrayList would be better than a LinkedList.
• Be careful when using .subList, and consider carefully how it really works, and its consequences

UPDATE: As you pointed out, the "damage" is not so bad as it seemed at first, since the Hand constructor converts the linked lists to array lists quite early on. Even so, it would have been better to not use a better storage from the start. Interestingly, if Parser was fully in charge of parsing and creating the Hand objects, then there wouldn't be a question of using sublists in the first place, and the whole issue just vanish.

Duplicated evaluations

There are several .compareTo calls that are evaluated twice, for example here:

if(rank.compareTo(o.rank) != 0) return rank.compareTo(o.rank);
else if(primary.compareTo(o.primary) != 0) return primary.compareTo(o.primary);
else if(secondary.compareTo(o.secondary) != 0) return secondary.compareTo(o.secondary);

Although the cost of this is probably tiny, for the sake of clean coding, and to avoid repeating yourself, I suggest to rewrite in a way to eliminate duplication, for example:

int compare = rank.compareTo(o.rank);
if (compare != 0) return compare;
compare = primary.compareTo(o.primary);
if (compare != 0) return compare;
compare = secondary.compareTo(o.secondary);
if (compare != 0) return compare;

Coding style

For the most part, the coding style is great. But then, things get a bit out of hand at a few places. I have some suggestions to apply consistently everywhere:

• Avoid extremely long lines, by adding more line breaks appropriately
• Avoid single-letter variable names
• Use braces even with single-statement if
• Put a space before ( in if conditions and for loops

Misc

Instead of this:

if(v == null) return NULL;
return v;

I suggest using the ternary operator:

return v == null ? NULL : v;

I don't think this is too cryptic (I'm strongly against cryptic code), and it has the advantage of not writing return twice.

---

You put the input file in the resources root:

InputStream is = Problem.class.getResourceAsStream("/p054_poker.txt");

I'd recommend to put it in a /data/ directory, rather than the root. If you have just one file it may not matter much, but having files lying around in the root dir just seem sloppy.

---

In the ValueRanking constructor, I'm not sure what to make of this:

try {
 Collections.sort(kickerTemp);
} catch (NullPointerException e) {
 System.out.println(kicker);
 throw e;
}

It's not really clear what's going on here, at least a comment explaining would be nice.

• durron597: I agree separating the hands as input to Round should really have been done in the Parser, and further I agree with the duplicated compareTo calls observation. However, if you notice, I convert the input cards from a LinkedList into an unmodifiable ArrayList within the Hand constructor. I typically use a LinkedList when I know I'm going to be calling tail .add repeatedly, though in this case I could have just used a prespecified list size.
• janos: @durron597 Dang! I overlooked that. Still, despite the conversion to ArrayList quite early, you still pay a high price for the second .subList. I'll rephrase that point, but in any case, an ArrayList with a suitable size would make more sense from the start.
• durron597: Actually, per your first point, TWO ArrayList of suitable sizes make more sense from the start. Then I don't have to call .subList ever ;) I definitely rushed that part of the code.
• janos: True. I updated with regards to this point, and added a few more minor points at the end, about coding style and some oddities.
• durron597: per that last bit, it was debugging code that I forgot to remove. I mentioned it in a comment under the original post.

Answer 2

You have a bug in straightRanking() in you Hand class.

else if(isStraight()) {
 return new ValueRanking(Ranking.STRAIGHT_FLUSH, cards.get(4).getValue(), (Value) null, Collections.<Value>emptyList());

You should be passing Ranking.STRAIGHT here instead of Ranking.STRAIGHT_FLUSH.

Also, the method isStraight can be optimized/simplified, taking advantage of the fact that your cards are already sorted:

private boolean isStraight() {
 return cards.get(i).getValue().ordinal() + 4 == cards.get(i+4).getValue().ordinal());
}

This is simply making your code simpler. However, I think you might be missing the case where a straight starts with an ace.

Also, in Hand you are using ints for quads, and trips. These variables are only ever 0 or 1, so using a boolean would be more appropriate and especially make the code easier to understand.

• durron597: Fixed. Odd that Project Euler said I got the right answer, they need better test cases :)
• barq: Please don't edit questions after answers have been given. See meta.codereview.stackexchange.com/questions/1763/…
• durron597: oh. Sorry about that
• barq: added simpler version of isStraight()
• barq: Are you accounting for straights starting with ace?