Deciding if a hand forms a gin or not?

Questions / Help
,
1

I am trying to write a little function to determine whether a given hand of cards forms a gin.

Here are the rules:

  • A hand contains 10 cards from a standard 52-card deck.
  • A run is formed if it contains at least 3 cards or more of the same suit and their value increases without gaps.
  • A set is formed if it contains at least 3 or more cards of the same value.
  • A hand is a gin if every card in the hand either belongs to a set or a run.

I am curious to see alternative ways of coding this in idiomatic Elixir.

2

What have you tried?

1 Like
3

“Alternatives” means there’s a first reference implementation against which they will be compared.

Where’s your code?

4

I haven’t provided any code not to influence anyone.

My solution is a simple backtracking algorithm that more or less goes like the following:

I take the first card in the hand and then try to find a set of 4, if found, then remove the members of the set and recurse into the remaining. If not found, then try to find a set of 3, if found, remove them and recurse into the remaining. If not, then try to find a run, if found, recurse into the remaining, if not then return false.

However, I quickly realised that matching a set of 4 whenever I can doesn’t work for some cases where one member of the set can help to complete a straight, so I ended up trying out the permutations of the set. I have later on made a similar observation about matching the longest runs doesn’t help when the last elements of the run can actually complete a set, etc.

I ended up special casing so many things in the end, which prompted me to see what people could come up with.

I hope this gives some direction.

5

You will not. Let’s see your try at it and discuss it.

6

My code is like the following:

  @spec is_gin(hand :: list(Card.t())) :: boolean()
  def is_gin(hand) do
    sorted = hand |> Enum.sort(&(&2.value > &1.value))
    is_gin?(sorted, [])
  end

  defp is_gin?([], _), do: true

  defp is_gin?([h | rest], used) do
    others = Enum.filter(rest, &(&1.value == h.value))

    cond do
      length(others) == 2 ->
        is_gin?(rest -- others, [[h | others] | used])

      length(others) == 3 ->
        [s1, s2, s3] = others

        # try permutations
        is_gin?(rest -- [s1, s2], [[h, s1, s2] | used]) or
          is_gin?(rest -- [s2, s3], [[h, s2, s3] | used]) or
          is_gin?(rest -- [s1, s3], [[h, s1, s3] | used]) or
          is_gin?(rest -- [s1, s2, s3] ++ [h], [[s1, s2, s3] | used])

      [] ->
        case find_run(h, rest) do
          nil ->
            false

          run ->
            for size <- Enum.to_list(length(run)..3) do
              slice = run |> Enum.reverse() |> Enum.take(size)
              is_gin?(rest -- slice, [slice | used])
            end
            |> Enum.any?(& &1)
        end
    end
  end

  defp find_run(_, rest) when length(rest) < 2, do: nil

  defp find_run(card, rest) do
    candidates =
      Enum.filter(rest, &Card.same_suit?(card, &1))
      |> Enum.sort(&(&2.value > &1.value))

    run =
      for c <- candidates, reduce: [card] do
        acc ->
          prev = hd(acc)
          if c.value - 1 == prev.value, do: [c | acc], else: acc
      end

    if length(run) >= 3, do: run, else: nil
  end

I used the following test case to verify that it is working as expected.

    test "various gins" do
      hands = [
        {[h(1), s(1), d(1), s(5), h(5), c(5), s(2), s(3), s(4), c(1)], true},
        {[h(6), s(6), d(6), c(1), c(2), c(3), c(4), c(6)], true},
        {[h(1), h(2), h(3), h(4), h(6)], false},
        {[h(1), h(2), h(3), h(4), h(5), h(6), h(7), h(8), h(9), h(10)], true},
        {[c(1), h(2), h(3), h(4), h(5), h(6), h(7), h(8), h(9), h(10)], false}
      ]

      for {hand, expected} <- hands do
        assert GameState.is_gin(hand) == expected
      end
    end
7

The tricky part is dealing with cards that could be in either a set or a run - for instance if you have 5/6/7/8 of diamonds, 5 of clubs and 5 of hearts.

I’d implement this check by first rewriting it into a recursive definition:

* A hand is a gin if:
  * there is a set of 4 cards, and one of the following:
    * the remaining cards are a gin
    * the remaining cards plus one of the 4 from the set are a gin
  * there is a set of 3 cards, and one of the following:
    * the remaining cards are a gin
    * the whole hand is a gin ignoring this set of 3 cards
  * there is a run of at least 3 cards, and:
    * the remaining cards are a gin
  * the hand is empty

Some of these clauses are trickier than others:

  • the case where a candidate set of four cards isn’t used as a set is ignored, since having four runs would require 12 cards!
  • the “not a set” branch for 3 cards needs to track which values have been tried as a set, or else the definition will loop forever

There’s a corresponding clause in GinCalc.gin? for all the bullet points above:

defmodule GinCalc do
  def gin?(hand, ignored \\ [])
  def gin?([], _), do: true
  def gin?(hand, ignored) do
    case split_set(hand, ignored) do
      {run, rest} when length(run) == 4 ->
        if gin?(rest, ignored) do
          true
        else
          Enum.any?(run, &gin?([&1 | rest], ignored))
        end
      {[{_, v} | _] = run, rest} when length(run) == 3 ->
        if gin?(rest, ignored) do
          true
        else
          gin?(hand, [v | ignored])
        end
      {nil, rest} ->
        case split_run(rest) do
          {nil, _} -> false
          {_, without_run} -> gin?(without_run, ignored)
        end
    end
  end

  def split_set(hand, ignored) do
    grouped = Enum.group_by(hand, &elem(&1, 1))

    set_key =
      grouped
      |> Map.keys()
      |> Enum.reject(& &1 in ignored)
      |> Enum.find(fn k -> length(grouped[k]) > 2 end)

    if set_key do
      set = grouped[set_key]

      {set, hand -- set}
    else
      {nil, hand}
    end
  end

  def split_run(hand) do
    sorted = Enum.sort(hand)

    candidate_run =
      Enum.reduce_while(sorted, [], fn
        {suit, value}, [{suit, prev_value} | _] = acc when value == prev_value + 1 ->
          {:cont, [{suit, value} | acc]}
        _, acc when length(acc) > 2 ->
          {:halt, acc}
        {suit, value}, _ ->
          {:cont, [{suit, value}]}
      end)

    if length(candidate_run) > 2 do
      {candidate_run, hand -- candidate_run}
    else
      {nil, hand}
    end
  end
end

GinCalc.split_set([{:h, 5}, {:h, 6}, {:h, 7}, {:s, 5}, {:d, 5}], []) |> IO.inspect()
GinCalc.gin?([{:h, 5}, {:s, 5}, {:d, 5}, {:c, 5}, {:h, 6}, {:h, 7}]) |> IO.inspect()

I used tuples to represent cards because they Enum.sort in a reasonable way (grouped into suits, then by number) and are easy to pattern-match, but using structs would only require light modifications.

2 Likes
8

You might find this approach to ranking poker hands helpful. Playing Poker with Elixir (pt. 1)

1 Like
9

Nice! It looks better than mine.

I like the usage of reduce_while for halting the loop early. I might steal that :slight_smile:

10

Thanks! That’s exactly what I was looking for! Pity the blog doesn’t exist anymore.