Hand of Straights
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Can the cards be split into groups of groupSize consecutive numbers (like 3,4,5)?
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1If the number of cards is not a multiple of the group size, is it possible?
- Hint 2Count each number. Take the smallest number that still has cards.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Sorting a deck into runs like 4-5-6. Spread the cards on the table grouped by number. Take the smallest number on the table: nothing smaller exists to come before it, so it must start a run. Lay down that run. If a card for the run is missing, the hand can never be split. Repeat with the next smallest card that is still left.
- The obvious way
Try every grouping with backtracking: exponential.
- The key insight
Count cards per value. Go through the values from small to large. If value v still has c cards, c runs must start at v, so every value from v to v + groupSize - 1 needs at least c cards; subtract c from each. If any is short, return False. If you finish, True.
- The algorithm
- Cards % groupSize != 0: False.
- Count how many of each value.
- For each value from smallest: if cards remain, start that many runs.
- Each run needs the next groupSize - 1 values; a missing one means False.
Watch it run
Examplehand = [1,2,3,6,2,3,4,7,8], groupSize = 3 (sorted: 1 2 2 3 3 4 6 7 8)
Smallest is 1: it starts a run 1-2-3. Use one each of 1, 2 and 3.
runs: 1-2-3
Where people slip
- Check len(hand) % group_size first, it avoids needless work.
- Subtract the whole count c at once for all c runs starting at a value.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
from collections import Counter
def is_n_straight_hand(hand, group_size):
if len(hand) % group_size != 0:
return False
count = Counter(hand) # how many cards of each number
for card in sorted(count):
runs_starting_here = count[card]
if runs_starting_here > 0:
for next_card in range(card, card + group_size):
if count[next_card] < runs_starting_here:
return False # a card for the run is missing
count[next_card] -= runs_starting_here
return TrueNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.