Play Big 2 by yourself, as fast as you can

Question

Introduction

Big 2 is a card game popular in East Asia and South East Asia, in which 4 players are dealt 13 cards each (ie, an equal division of a standard deck without jokers). The goal is to empty your hand before any of the other players. Players take turns playing combinations of a Big 2 subset of standard poker hands until their hands are empty. When cards are played, they are considered to be in a discard pile and cannot be reused.

The challenge here is to determine the fewest number of poker hands needed to completely empty a starting hand assuming that there are no other players. In other words, given 13 cards, produce a list of the poker hands that would empty your hand the fastest (ie, the fewest number of 'turns').

Challenge

Given a list of 13 cards of the format <rank><suit>, produce a delimited combination of Big 2 poker hands that would allow the player to empty their hands as fast as possible. Assume that the given hand can be realistically produced from a single deck of cards (ie, you won't receive 10 aces in your hand).

Inputs

• An unsorted list of 13 cards, meaning that the ranks and suits are not in any patterned/sorted order
  • The ranks can be any of A,2,3,4,5,6,7,8,9,0,J,Q,K, where '0' is a 10. You may use rank 10 in your program if that suits you better.
  • The suits can be any of D,C,H,S, which correspond to diamonds, clubs, hearts, and spades, respectively.
  • Sample cards would be AD for ace of diamonds, or 0H for 10 of hearts.
• For this example, the inputs are separated by commas, but you can delimit the string however you like, or even use an entirely different representation of a deck of cards that suits your fancy

Outputs

• A list (or some delimited string) of cards that indicate play order of your cards. For example the following output formats are valid:

  2H, 3D, 4H, 5C, 6S
  7S, 7D, 7H
  0D, JD, QD, KD, AH
  

  • or [[2H, 3D, 4H, 5C, 6S], [7S, 7D, 7H], [0D, JD, QD, KD, AH]]

  • or 2H3D4H5C6S, 7S7D7H, 0DJDQDKDAH

  • or anything else that can delineate hand combinations (aka convenient inputs and outputs)

• All three sample outputs indicate that 13 cards were played in the following order: a straight from 2-6, a triplet of 7s, and then a straight from 10-A

• When outputting a 5 card combination, such as for straights or full houses, the cards' ranks/suits do not have to be sorted or grouped in any way - they're mostly shown here for legibility. For example, the straight 2S3S4S5S6S is equivalent to 6S4S2S5S3S. (23456 == 64253)
• The actual order of moves does not matter as cards cannot be reused anyways

Big 2 Poker Hands

In Big 2, the following poker hands are legal:

• A single card
• A pair of cards, meaning two cards of the same rank regardless of suit
• A triplet of cards, meaning three cards of the same rank regardless of suit
• A straight, a 5 card combination of consecutive ranks regardless of suit.
  • Straights cannot start from a jack, queen, or king (ie, the straights of ranks (regardless of suit) JQKA2, QKA23, and KA234 are invalid)
  • Straights can start from any other rank
  • Aces can either be the high card or the low card in a straight, but it cannot appear in the middle of a straight. Namely, the only 2 valid straights that include an ace are 0JQKA and A2345.
• A full house, a 5 card combination made of three cards of the same rank, and 2 cards of the same, but different rank.
  • For example, 000QQ is a full house with triplet 10s and a pair of queens, but the combination 000KQ is invalid because a pair is needed to complete the triplet
• A quad, a 5 card combination made of four cards of the same rank, plus any card of a different rank
• A flush, a 5 card combination of 5 cards of the same suit regardless of rank
• And just for completion's sake: a straight flush, a 5 card combination where the 5 cards are a straight in terms of ranks but also share the same suit.
  • Note the straight flush can be computed from either the definition of a straight or a flush, meaning its own distinct definition here isn't necessary for the completion of this challenge.

Tests

Input: AS,4H,6D,8C,7C,3S,5H,8D,4C,2S,0C,AD,AH

Sample output: ASAHAD8D8C, 2S3S4H5H6D, 4C, 7C, 0C OR 7C, 2S6D3S5H4H, 0C, 4C, 8C8DASAHAD

Explanation: Given the above input, it's possible to generate 2 distinct 5-card combination poker hands. After we play those 2 hands, we only have 3 remaining singles. Thus, the minimum amount of hands we must play is 5. Again, the output card hand combinations do not have to be sorted or played in this specific order (or even in this format) - just leaving it here for legibility.

---

Input: 2D,0H,5S,0S,4H,AS,4C,6C,6H,KC,8H,5H,8S

Sample output: 5S5H, 4H4C, 0S0H, 6C6H, 8H8S, KC, AS, 2D

Explanation: In this case, it is faster to output 5 pairs instead of a flush (of 5H4H0H6H8H) because the flush would create 5 dangling single cards that must be played one at a time. Playing the flush would yield 9 turns (1 for flush + 5 singles created from flush + 3 standalone singles), whereas the pair method would require 8 turns (5 turns for 5 pairs, 3 for the leftover singles)

---

Input: 4D,4S,4H,4C,5H,5D,5C,5S,9S,9D,9H,9C,AD

Sample output: 4D4S4H4CAD, 5D5H5C5S9S, 9D9H9C

Explanation: Outputting quads using the dangling AD is more efficient than picking the quad's last card from another quad because we can finish off with a triplet.

Rules

• Standard loopholes are forbidden
• Convenient inputs and outputs are allowed
• This is codegolf, so shortest code in bytes wins

Answer 1

JavaScript (ES6),  298 ... 256  253 bytes

Takes input as a list of integers in \$[0..51]\$, where the suit is encoded in the 2 least significant bits and the rank in the 4 upper bits.

Returns a list of lists in the same format.

f=(a,k=2)=>(F=(a,H=[])=>H[k]?a+a?0:O=H:a.reduce((a,x)=>[...a,...a.map(y=>[...y,x])],[[]]).some(h=>[b=c=m=s=0,h.map(x=>(c++,b+=m!=(m|=1<<x/4),s|=1<<x%4)),b<2,b<2,,b<3|m==4111|m==31*(m&-m)|8%s<1][c]&&F(a.filter(n=>!h.includes(n)),[...H,h])))(a)?O:f(a,k+1)

Try it online!

This is rather inefficient when more than 5 or 6 turns are required. The 2nd test case completes in a bit less than 2 minutes on my laptop and times out on TIO.

How?

Wrapper code

The wrapper code invokes the search function \$F\$ for a maximum number of turns \$k+1\$. This threshold is incremented until the call is successful. We start with \$k=2\$ because we need at least 3 turns to get rid of all cards.

f = (                 // f is the main function taking:
  a,                  //   a[] = list of cards
  k = 2               //   k   = maximum number of turns, minus 1
) =>                  //
  (F = ...)(a) ?      // invoke the search function F; if successful:
    O                 //   return the output
  :                   // else:
    f(a, k + 1)       //   try again with k + 1

Generating the hands

In the search function, we first build the powerset of the input \$a[\:]\$:

a.reduce((a, x) =>
  [ ...a,
    ...a.map(y => [...y, x])
  ],
  [[]]
)

That is, we build all possible hands, including invalid ones made of more than 5 cards.

Hand variables

We then iterate over each hand \$h\$, and each card \$x\$ in this hand to set up the following variables:

• \$c\$ is the number of cards in the hand
• \$m\$ is a 13-bit rank bitmask
• \$s\$ is a 4-bit suit bitmask
• \$b\$ is the number of bits set in \$m\$, i.e. the number of distinct ranks in the hand

h.map(x => (       // for each card x in h[]:
  c++,             //   increment c
  b +=             //   increment b if
    m != (         //   the current value of m is different from
      m |=         //     the updated value of m
        1 << x / 4 //     where the new rank bit is set
    ),             //
  s |= 1 << x % 4  //   update s with the suit bit
))                 // end of map()

Example

^{a random hand, courtesy of random.org}

c = 5

m = 0101010010000 (binary value)
     K J 9  6

b = 4

s = 1110 (binary value)
    SHD 

Hand validation

We finally figure out whether the hand is valid by picking the result of the relevant test from a lookup table, according to the number of cards \$c\$:

• \$0\$ card: always invalid (variables are initialized to \$0\$ in this slot)
• \$1\$ card: always valid (the above map() is performed in this slot and returns a truthy value)
• \$2\$ cards: valid if \$b<2\$ (there's only one rank, which means that we have a pair)
• \$3\$ cards: valid if \$b<2\$ (there's only one rank, which means that we have a three-of-a-kind)
• \$4\$ cards: always invalid (undefined slot)

• \$5\$ cards, valid if:

  • \$b<3\$ because both a quad + another card and a full house lead to \$b=2\$ (two distinct ranks in the hand) while all other patterns result in \$b\ge3\$
  • OR \$m=4111\$ (1000000001111 in binary), which represents the special straight A,2,3,4,5

  • OR \$m\$ has 5 consecutive bits set, which means that we have a standard straight

    m == 31 * (m & -m)
    

  • OR \$s\$ has only one bit set, which means that we have a flush

    8 % s < 1
    

• more than \$5\$ cards: always invalid (undefined slots)

Recursion

If the hand is valid, we do a recursive call to \$F\$ with all cards in \$h[\:]\$ removed from \$a[\:]\$.

F(                  // recursive call:
  a.filter(n =>     //   keep only in a[] ...
    !h.includes(n)  //     ... the cards that do not appear in h[]
  ),                //
  [...H, h]         //   append h[] to the list of hands
)                   // end

We know that we have reached the maximum number of turns when \$H[k]\$ is defined. If we have no more cards when this happens, it means that \$H\$ is a valid list of hands, which is saved in the output variable \$O\$ and eventually returned by the wrapper code.

Answer 2

05AB1E, 38 bytes

{æʒ€þ©Ùgyg5Qi3‹y€áË®¥ć8%šPΘ)à]æé.Δ˜I¢P

Try it online!

Input/output uses 1 for Ace, 10 for 10, 11 for Jack, 12 for Queen, 13 for King.

Runtime is exponential in the number of possible hands, making it timeout for all test cases. The TIO link shows an 8 card input, but the algorithm would theoretically work for inputs of any size, including the specified 13.

# The first step is to get a list of all valid hands

{                               # sort the input
 æ                              # all subsets of the input (aka all hands)
  ʒ                          ]  # filter:
   €þ                           #  get the rank of each card in the suit
     ©                          #  save that in the register, without popping
      Ù                         #  uniquify
       g                        #  length (=> number of distinct ranks in the hand)
        yg5Qi                ]  #  if the hand has exactly 5 cards:
             3‹                 #   is the number of distinct ranks < 3? (full house or quad)
               y€áË             #   are all suits of the hand equal? (flush)
                   ®¥           #   deltas of the list of ranks (restored from the register)
                     ć8%š       #   mod 8 the first one (to handle the A0JQK case)
                         PΘ     #   is the product equal to 1? (straight)
                           )    #   wrap those three tests in an array
                            à   #   keep the hand if the maximum is 1 (one of the tests was true)
                                #  else (implicit):
                                #   keep the hand if number of distinct ranks is 1
                                #   this catches singles, pairs, and triplets

æ                               # get all subsets of the list of valid hands
 é                              # sort those subsets by length
  .Δ                            # find the first one such that:
    ˜                           #  deep flattened
     I¢                         #  count occurences of each card of the input in the result
       P                        #  product is 1