Combining sub sets to larger sets if they share common value

Question

I'm trying to create a method that would return largest set of cards which has neighbors. For example if I have list<RANK> rankList = [FIVE, QUEEN, KING, ACE, TEN] it would return [KING, ACE, QUEEN]. I haven't fully implemented it, but I got that part with splits one set in multiple smaller sets.

private boolean isStraight(List<Card> cards) {
        Set<RANK> rankList = cards.stream()
            .map(Card::getRank)
            .distinct()
            .collect(Collectors.toSet());


        List<Set<RANK>> subSets = new ArrayList<>();

        for(RANK rank : rankList) {
            int currRankValue = rank.getValue();
            RANK prevRank = RANK.getRank(currRankValue - 1);
            RANK nextRank = RANK.getRank(currRankValue + 1);

            if(!subSets.stream().anyMatch(set -> set.contains(rank))) {
                Set<RANK> newSet = new HashSet<>();
                newSet.add(rank);
                subSets.add(newSet);
            }

            subSets.stream()
                .filter(set -> (set.contains(prevRank) || set.contains(nextRank)))
                .forEach( set -> set.add(rank));
        }

        System.out.print(subSets);
        return false;
    }

Card.java:

 public static enum RANK {
        NONE(0),
        TWO(2), THREE(3), FOUR(4), FIVE(5),
        SIX(6), SEVEN(7), EIGHT(8), NINE(9),
        TEN(10), JACK(11), QUEEN(12), KING(13), ACE(14);

        private final int value;

        private RANK(int value) {
            this.value = value;
        }

        public int getValue() {
            return value;
        }

        public static RANK getRank(int value) {
            for(RANK r : RANK.values() ) {
                if (r.getValue() == value)
                    return r;
            }
            return NONE;
        }
    }

And before I check if there is 5 or more cards that could make a straight I have combine sub sets which has at least one common value. How can I do it? I'cant think of anything that wouldn't involve many loops.

EDITED

Added whole Card.java:

ppackage deck;

public class Card implements Comparable {

    public static enum SUIT {
        SPADES,
        HEARTS,
        CLUBS,
        DIAMONDS
    }

    public static enum RANK {
        NONE(0),
        TWO(2), THREE(3), FOUR(4), FIVE(5),
        SIX(6), SEVEN(7), EIGHT(8), NINE(9),
        TEN(10), JACK(11), QUEEN(12), KING(13), ACE(14);

        private final int value;

        private RANK(int value) {
            this.value = value;
        }

        public int getValue() {
            return value;
        }

        public static RANK getRank(int value) {
            for(RANK r : RANK.values() ) {
                if (r.getValue() == value)
                    return r;
            }
            return NONE;
        }
    }

    private final RANK rank;
    private final SUIT suit;

    public Card(RANK rank, SUIT suit) {
        this.rank = rank;
        this.suit = suit;
    }

    public RANK getRank() {
        return rank;
    }

    public SUIT getSuit() {
        return suit;
    }

    @Override
    public String toString() {
        return "Card{" +
            "rank=" + rank +
            ", suit=" + suit +
            '}';
    }

    @Override
    public int compareTo(Object that) {
        return this.rank.getValue() - ((Card) that).rank.getValue();
    }
}

EDITED

Added solution with loops: adding this before return in the method.

for(int index = 0; index < subSets.size(); index++) {
           for(int index2 = 1; index2 < subSets.size(); index2++) {
               if(!Collections.disjoint(subSets.get(index), subSets.get(index2)) && index != index2) {
                    subSets.get(index).addAll(subSets.remove(index2));
                    index2--;
               }
           }
       }

I saw that you spelled which as with twice. (Not related to your question). Can you show the card class? — Chetan Kinger, Apr 23 '15 at 14:48
I'm thinking I could use something similiar to `.reduce()` method, which would do calculation 1 to everyone after it, not 1 to next. — Artūrs, Apr 23 '15 at 14:52
Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/76077/discussion-between-artrs-and-bot). — Artūrs, Apr 23 '15 at 14:55
`compareTo` is used for sorting. `equals` is used for checking equality. Does your code do what it is supposed to even before you move to implementing the remaining parts? — Chetan Kinger, Apr 23 '15 at 14:55
Yes everything works fine. At one point I had some issues when debugging mode return different results then production mode. — Artūrs, Apr 23 '15 at 14:57
Also I'm mapping `getRank()` result with is enum and `distinct()` is removing duplicates with has same rank value. — Artūrs, Apr 23 '15 at 14:59
Like I said, `compareTo` is not used for checking equality. The assumptions based on which you wrote your program are wrong so I doubt it does what is supposed to. You have not overriden `equals` in the `Card` class. — Chetan Kinger, Apr 23 '15 at 14:59

score 4 · Answer 1 · answered Apr 23 '15 at 17:53

Assuming that a “straight” consists of five adjacent RANKs, we should not think too complicated but just test whether we find such a range:

boolean isStraight(List<Card> cards) {
    BitSet set=cards.stream().map(Card::getRank).mapToInt(Card.RANK::ordinal)
        .collect(BitSet::new, BitSet::set, BitSet::or);
    for(int s=set.nextSetBit(0), e; s>=0; s=set.nextSetBit(e)) {
        e=set.nextClearBit(s);
        if(e-s >= 5) return true;
    }
    return false;
}

This code is not bound to a specific hand size and could be easily adapted to other straight sizes.

Dealing with ordinal() and BitSets might look a bit low-level, and I really wished there was a solution using EnumSet or EnumMap as simple as that, however, these higher level classes are not that helpful here (they don’t even implement SortedSet/SortedMap)…

Note that this method returns a boolean as the code in your question. So it doesn’t care what actual cards make up the straight. Afaik, in most Poker variants it indeed doesn’t matter.

However, taking your question’s introduction literally, getting the “largest set of cards which has neighbors” can be done as follows:

Set<Card> largestStraightCandidate(List<Card> cards) {
    BitSet set=cards.stream().map(Card::getRank).mapToInt(Card.RANK::ordinal)
        .collect(BitSet::new, BitSet::set, BitSet::or);
    int min=0, max=0;
    for(int s=set.nextSetBit(0), e; s>=0; s=set.nextSetBit(e)) {
        e=set.nextClearBit(s);
        if(e-s >= max-min) {
            min=s;
            max=e;
        }
    }
    if(max==min) return Collections.emptySet();// cards was empty
    Card.RANK[] all=Card.RANK.values();
    EnumSet<Card.RANK> rankSet=EnumSet.range(all[min], all[max-1]);
    return cards.stream().filter(card-> rankSet.contains(card.getRank()))
      .collect(Collectors.toSet());
}

The difference is that we now remember the largest range instead of returning once we found a sufficiently large one. Then, we reconstitute the cards by filtering the original card list for all cards within that range.

This implies that

for multiple largest set, the set with the higher ranks will be returned as due to the loop over the BitSet, i.e. the order within the list doesn’t matter
if multiple cards of the same RANK within the range exists, all of them are included in the Set of Cards; don’t use its size to decide about the straight’s size, you have to convert to a Set of RANKs first, or well, if you look closely at the code, you see that the Set of RANKs already exists before the Set of Cards is built…

score 4 · Accepted Answer · edited May 23 '17 at 12:06

I'm focusing on the aspect of the problem relating to the "largest set of cards which has neighbors." If the list of card rank values is sorted, this turns into the problem of segmenting the list runs and then picking the longest run(s) from those segments.

Astute readers will note the similarity to this question. I'll use a technique similar to my answer to that question.

First, let's start off with an input list containing as in the OP's example. The following technique should work for any input, though.

    List<Rank> rankList = [FIVE, QUEEN, KING, ACE, TEN];

Let's sort and make this list have unique elements:

    List<Rank> sorted = rankList.stream()
        .distinct()
        .sorted()
        .collect(toList());

[FIVE, TEN, QUEEN, KING, ACE]

Now let's compute the location where the list should be split to separate runs of consecutive rank values. This occurs at locations where values adjacent to each other in the list are not consecutive rank values. We do this by indexing the list (starting from 1) and filtering the indexes by examining adjacent values from the list:

    List<Integer> splits = IntStream.range(1, sorted.size())
        .filter(i -> sorted.get(i).ordinal() != sorted.get(i-1).ordinal() + 1)
        .boxed()
        .collect(toCollection(ArrayList::new));

[1, 2]

These are the locations between the runs. This is almost enough information to create sublists, but it omits the index for the start of the first sublist and for the end of the last sublist. To add these, we just add 0 at the front and size at the end:

    splits.add(0, 0);
    splits.add(list.size());

[0, 1, 2, 5]

Now we can use each pair of indexes to generate the sublists containing each run:

    List<List<Rank>> runs = IntStream.range(1, splits.size())
        .mapToObj(i -> list.subList(splits.get(i-1), splits.get(i)))
        .collect(toList());

[[FIVE], [TEN], [QUEEN, KING, ACE]]

We can find the longest run and then print out the runs that match its length:

    int longest = runs.stream()
        .mapToInt(list -> list.size())
        .max()
        .getAsInt();
    runs.stream()
        .filter(list -> list.size() == longest)
        .forEach(System.out::println);

[QUEEN, KING, ACE]

Putting it all together, we have:

static void split(List<Rank> rankList) {
    List<Rank> sorted = rankList.stream()
        .distinct()
        .sorted()
        .collect(toList());

    List<Integer> splits = IntStream.range(1, sorted.size())
        .filter(i -> sorted.get(i).ordinal() != sorted.get(i-1).ordinal() + 1)
        .boxed()
        .collect(toCollection(ArrayList::new));

    splits.add(0, 0);
    splits.add(sorted.size());

    List<List<Rank>> runs = IntStream.range(1, splits.size())
        .mapToObj(i -> sorted.subList(splits.get(i-1), splits.get(i)))
        .collect(toList());

    int longest = runs.stream()
        .mapToInt(list -> list.size())
        .max()
        .getAsInt();

    runs.stream()
        .filter(list -> list.size() == longest)
        .forEach(System.out::println);
}

If you are interested in only one largest run, you may use `runs.stream().max(Comparator.comparingInt(List::size))`… — Holger, Apr 24 '15 at 08:17

score 2 · Answer 3 · answered Apr 23 '15 at 16:54

(I am still having troubles with the coding style of the java functional API.) I would use a distinct sorted stream, and use Lists to make sub-lists. The distinct list is split into sub-lists of consecutive ranks. I would like to see a better solution with flatMap, reduce or whatever.

static boolean isStraight(List<Card> cards) {
    List<List<Rank>> rankList = cards.stream()
            .map(Card::getRank)
            .sorted(Comparator.comparingInt(Rank::getValue))
            .distinct()
            .collect(LinkedList::new,
                    (list, rank) -> {
                        boolean startNextList = false;
                        if (list.isEmpty()) {
                            startNextList = true;
                        } else {
                            List<Rank> priorRanks = list.get(list.size() - 1);
                            if (priorRanks.get(priorRanks.size() - 1).getValue()
                                       < rank.getValue() - 1) {
                                startNextList = true;
                            }
                        }
                        if (startNextList) {
                            List<Rank> priorRanks = new LinkedList<>();
                            list.add(priorRanks);
                        }
                        List<Rank> priorRanks = list.get(list.size() - 1);
                        priorRanks.add(rank);
                    },
                    (list1, list2) -> {
                        list1.addAll(list2);
                    });

A dump:

    rankList.stream().forEach((list) -> {
        System.out.printf("# %d - ", list.size());
        list.stream().forEach((r) -> System.out.printf("%s, ", r));
        System.out.println();
    });
    ...

See [my answer](http://stackoverflow.com/a/29839295/1441122). You might find it familiar. :-) — Stuart Marks, Apr 24 '15 at 05:20

score 2 · Answer 4 · answered Apr 23 '15 at 23:27

Given that there are so few possible straights, have you considered a simpler approach of just precomputing them all?

// using .ordinal() instead of .value to keep it short.  
// Shouldn't be too hard to change it to use values
final Set<EnumSet<RANK>> STRAIGHTS = EnumSet.range(TWO, TEN).stream()
        .map(rank -> EnumSet.range(rank, RANK.values()[rank.ordinal() + 4]))
        .collect(toSet());

and then

boolean isStraight(List<Card> cards) {
    EnumSet<RANK> ranks = cards.stream()
        .map(Card::getRank)
        .collect(toCollection(() -> EnumSet.noneOf(RANK.class)));

    return STRAIGHTS.contains(ranks);
}

Combining sub sets to larger sets if they share common value

4 Answers4