Rummy Card Game
## description
## Rummy Card Game
Rummy is a two-player card game played in a series of rounds. At the beginning of each round, each player is dealt a 10-card hand from a 36-card deck.
Each card in the deck is uniquely composed of the following two attributes:
One of 4 “suits” (Spades ‘S’, Hearts ‘H’, Clubs ‘C’, or Diamonds ‘D’) One of 9 “ranks” (the numbers 1-9)
The goal of the game is to group cards into groups (melds) of 3 or more cards of matching rank, which can either be:
- –“sets”: 3+ cards of the same rank (ex: 9D, 9S, 9C since they all have rank 9)
- –“runs”: 3+ cards of consecutive values within the same suit. Consecutive values are any values in the sequence of 1,2,3,4,5,6,7,8,9 (ex: 1-2-3-4 is consecutive, 1-2-4-5 is not).
Given an input of a hand of cards with suits and ranks, return all possible sets and runs that could be formed.
Example 1:
1Input: cards = ["1C", "9C", "8C", "7C", "5C", "4C", "9D", "9S", "1D", "1H"]
2Output: [["1C", "1D", "1H"], ["9C", "9D", "9S"], ["7C", "8C", "9C"]]Example 2:
1Input: ["4C", "2C", "3C", "1C", "8D", "6C", "9D", "9C", "1D", "1H"]
2Output: [["1C", "1D", "1H"], ["1C", "2C", "3C"], ["2C", "3C", "4C"], ["1C", "2C", "3C", "4C"]]## notes
### Intuition
Rummy melds are either sets (same rank, different suits) or runs (consecutive ranks, same suit). Group cards by rank and suit separately, then generate all valid combinations.
### Implementation
Build two hashmaps: one grouping cards by rank, another by suit. For sets, find ranks with 3+ cards and generate all combinations of size 3, 4, etc. For runs, sort each suit's cards by rank, find consecutive segments, and generate all windows of size 3+ within each segment.
### Edge-cases
After processing consecutive cards, there may be a final segment that didn't trigger the flush logic—handle it after the loop.
- –Time: O(n²) — generating combinations; acceptable for small card counts
- –Space: O(n²) — storing all possible melds
### Complexity
## solution
1from typing import List, Tuple
2from collections import defaultdict
3from itertools import combinations
4
5class Solution:
6 def findMelds(self, cards: List[str]) -> List[List[str]]:
7 def parseCard(card: str) -> Tuple[int, str]:
8 return (int(card[0]), card[1])
9
10 # Group cards by rank and suit
11 # Space: O(n) -> all cards are stored
12 by_rank = defaultdict(list)
13 by_suit = defaultdict(list)
14 # Time: O(n)
15 for card in cards:
16 rank, suit = parseCard(card)
17 by_rank[rank].append(card)
18 by_suit[suit].append(card)
19
20
21 result = []
22
23 # Find sets
24 for rank in by_rank:
25 rank_cards = by_rank[rank]
26 # Only care about ranks that have 3 or more cards
27 if len(rank_cards) < 3:
28 continue
29 # Create sets using combinations of 3+ cards
30 for n in range(3, len(rank_cards) + 1):
31 for combo in combinations(rank_cards, n):
32 result.append(list(combo))
33 # Find runs
34 for suit in by_suit:
35 suit_cards = by_suit[suit]
36 # Only care about suits that have 3 or more cards
37 if len(suit_cards) < 3:
38 continue
39 # Sort cards by rank
40 ranked = sorted([(parseCard(c)[0], c) for c in suit_cards], key=lambda x: x[0])
41
42 # Build consecutive segments
43 segments: List[Tuple[int, str]] = []
44
45 for r, c in ranked:
46 if not segments:
47 segments.append((r, c))
48 else:
49 prev_r = segments[-1][0]
50 if r == prev_r + 1:
51 segments.append((r, c))
52 else:
53 # Add windows of consecutive segments to result and flush
54 if len(segments) >= 3:
55 seg_cards = [card for _, card in segments]
56 m = len(seg_cards)
57 for i in range(m):
58 for j in range(i + 3, m + 1):
59 result.append(seg_cards[i:j])
60 segments = [(r, c)]
61 # Flush the any remaining segment
62 if len(segments) >= 3:
63 seg_cards = [card for _, card in segments]
64 m = len(seg_cards)
65 for i in range(m):
66 for j in range(i + 3, m + 1):
67 result.append(seg_cards[i:j])
68
69 return result
70
71if __name__ == "__main__":
72 # Include one-off tests here or debugging logic that can be run by running this file
73 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
74 solution = Solution()
75 test = ["1C", "9C", "8C", "7C", "5C", "4C", "9D", "9S", "1D", "1H"]
76 print(solution.findMelds(test))
77