Skip to content

Camicia

Play out a game of Camicia, a beggar-my-neighbour card game, from two starting decks, and report whether it finishes or loops, how many cards were played and how many tricks were taken.

Adapted from Exercism’s problem specification (MIT). Listed under Games & Simulation.

// FILE: camicia.nomi
//# Camicia, a two-player card game of the beggar-my-neighbour family,
//# played out from two starting decks until one player holds every card or
//# the decks come round to a shape they had before.

/// How a game ended: one player holds every card, or the game would go on
/// for ever.
pub enum Status
    Finished
    Loop
end

/// The end of a game: how it ended, how many cards were played and how many
/// times a player collected the pile.
pub struct Game
    status: Status
    cards:  Int
    tricks: Int
end

/// The two players. A starts.
enum Side
    A
    B
end

/// Both players' cards, each from the top of the deck down.
struct Hands
    a: List<String>
    b: List<String>
end

/// Plays a game from the decks `player_a` and `player_b`, each from the top
/// down. Cards are `"2"` to `"10"`, `"J"`, `"Q"`, `"K"` and `"A"`.
pub fn simulate_game(player_a: List<String>, player_b: List<String>) -> Game
    hands: Hands = {a: player_a, b: player_b}

    rounds(hands, leader: .A, seen: [shape(hands)], cards: 0, tricks: 0)
end

/// Plays tricks from `hands`, `leader` playing first, until a player holds
/// every card or the hands take a shape already in `seen`.
fn rounds(
    hands:  Hands,
    leader: Side,
    seen:   Set<(List<String>, List<String>)>,
    cards:  Int,
    tricks: Int,
) -> Game
    (collector, pile, hands) = play(hands, turn: leader, pile: [], owed: 0, collector: leader)
    hands = with_hand(hands, collector, [..hand(hands, collector), ..Iter.reverse(pile)])
    cards = cards + Iter.count(pile)
    tricks = tricks + 1
    now = shape(hands)

    case
        Iter.is_empty(hand(hands, other(collector))) -> {status: .Finished, cards:, tricks:}
        now in seen -> {status: .Loop, cards:, tricks:}
        _           -> rounds(hands, collector, Set.insert(seen, now), cards, tricks)
    end
end

/// Plays one trick from `turn` on, onto `pile` (newest card first), and
/// returns who collects the pile, the pile and the hands left. `owed` is
/// how many cards `turn` still has to pay, and `collector` who played the
/// payment card they are paying for.
fn play(
    hands:     Hands,
    turn:      Side,
    pile:      List<String>,
    owed:      Int,
    collector: Side,
) -> (Side, List<String>, Hands)
    case hand(hands, turn)
        [] ->
            (other(turn), pile, hands)

        [card, ..rest] ->
            hands = with_hand(hands, turn, rest)
            pile = [card, ..pile]

            case
                penalty(card) > 0 -> play(hands, other(turn), pile, penalty(card), turn)
                owed == 1         -> (collector, pile, hands)
                owed > 1          -> play(hands, turn, pile, owed - 1, collector)
                _                 -> play(hands, other(turn), pile, 0, collector)
            end
    end
end

/// The cards a payment card makes the other player pay, or 0 for a number
/// card.
fn penalty(card: String) -> Int
    case card
        "J" -> 1
        "Q" -> 2
        "K" -> 3
        "A" -> 4
        _   -> 0
    end
end

/// The hands with every number card alike, which is all that decides how
/// the game goes on.
fn shape(hands: Hands) -> (List<String>, List<String>)
    (alike(hands.a), alike(hands.b))
end

/// `cards` with each number card written `-`.
fn alike(cards: List<String>) -> List<String>
    cards
    |> Iter.map(fn card -> if penalty(card) > 0 then card else "-")
    |> Iter.to_list()
end

fn other(side: Side) -> Side
    case side
        .A -> .B
        .B -> .A
    end
end

fn hand(hands: Hands, side: Side) -> List<String>
    case side
        .A -> hands.a
        .B -> hands.b
    end
end

fn with_hand(hands: Hands, side: Side, cards: List<String>) -> Hands
    case side
        .A -> {..hands, a: cards}
        .B -> {..hands, b: cards}
    end
end

// FILE: camicia_test.nomi
import
    camicia
    camicia.Game
end

/// The cards written in `cards`, top first, separated by spaces or lines.
fn deck(cards: String) -> List<String>
    String.words(cards)
end

test "simulate game"
    [
        (
            "two cards, one trick",
            deck("2"),
            deck("3"),
            Game{status: .Finished, cards: 2, tricks: 1},
        ),
        (
            "three cards, one trick",
            deck("2 4"),
            deck("3"),
            {status: .Finished, cards: 3, tricks: 1},
        ),
        (
            "four cards, one trick",
            deck("2 4"),
            deck("3 5 6"),
            {status: .Finished, cards: 4, tricks: 1},
        ),
        (
            "the ace reigns supreme",
            deck("2 A"),
            deck("3 4 5 6 7"),
            {status: .Finished, cards: 7, tricks: 1},
        ),
        (
            "the king beats ace",
            deck("2 A"),
            deck("3 4 5 6 K"),
            {status: .Finished, cards: 7, tricks: 1},
        ),
        (
            "the queen seduces the king",
            deck("2 A 7 8 Q"),
            deck("3 4 5 6 K"),
            {status: .Finished, cards: 10, tricks: 1},
        ),
        (
            "the jack betrays the queen",
            deck("2 A 7 8 Q"),
            deck("3 4 5 6 K 9 J"),
            {status: .Finished, cards: 12, tricks: 1},
        ),
        (
            "the 10 just wants to put on a show",
            deck("2 A 7 8 Q 10"),
            deck("3 4 5 6 K 9 J"),
            {status: .Finished, cards: 13, tricks: 1},
        ),
        (
            "simple loop with decks of 3 cards",
            deck("J 2 3"),
            deck("4 J 5"),
            {status: .Loop, cards: 8, tricks: 3},
        ),
        (
            "the story is starting to get a bit complicated",
            deck(
                """
                2 6 6 J 4 K Q 10 K J Q 2 3 K 5 6 Q Q A A 6 9 K A 8 K 2 A 9 A
                Q 4 K K K 3 5 K 8 Q 3 Q 7 J K J 9 J 3 3 K K Q A K 7 10 A Q 7
                10 J 4 5 J 9 10 Q J J K 6 10 J 6 Q J 5 J Q Q 8 3 8 A 2 6 9 K 7
                J K K 8 K Q 6 10 J 10 J Q J 10 3 8 K A 6 9 K 2 A A 10 J 6 A 4 J
                A J J 6 2 J 3 K 2 5 9 J 9 6 K A 5 Q J 2 Q K A 3 K J K 2 5 6 Q
                J Q Q J 2 J 9 Q 7 7 A Q 7 Q J K J A 7 7 8 Q 10 J 10 J J 9 2 A 2
                """
            ),
            deck(
                """
                7 2 10 K 8 2 J 9 A 5 6 J Q 6 K 6 5 A 4 Q 7 J 7 10 2 Q 8 2 2 K
                J A 5 5 A 4 Q 6 Q K 10 8 Q 2 10 J A Q 8 Q Q J J A A 9 10 J K 4
                Q 10 10 J K 10 2 J 7 A K K J A J 10 8 K A 7 Q Q J 3 Q 4 A 3 A Q
                Q Q 5 4 K J 10 A Q J 6 J A 10 A 5 8 3 K 5 9 Q 8 7 7 J 7 Q Q Q
                A 7 8 9 A Q A K 8 A A J 8 4 8 K J A 10 Q 8 J 8 6 10 Q J J A A J
                5 Q 6 J K Q 8 K 4 Q Q 6 J K 4 7 J J 9 9 A Q Q K A 6 5 K
                """
            ),
            {status: .Finished, cards: 361, tricks: 1},
        ),
        ("two tricks",  deck("J"),     deck("3 J"),   {status: .Finished, cards: 5, tricks: 2}),
        ("more tricks", deck("J 2 4"), deck("3 J A"), {status: .Finished, cards: 12, tricks: 4}),
        (
            "simple loop with decks of 4 cards",
            deck("2 3 J 6"),
            deck("K 5 J 7"),
            {status: .Loop, cards: 16, tricks: 4},
        ),
        (
            "easy card combination",
            deck("4 8 7 5 4 10 3 9 7 3 10 10 6 8 2 8 5 4 5 9 6 5 2 8 10 9"),
            deck("6 9 4 7 2 2 3 6 7 3 A A A A K K K K Q Q Q Q J J J J"),
            {status: .Finished, cards: 40, tricks: 4},
        ),
        (
            "easy card combination, inverted decks",
            deck("3 3 5 7 3 2 10 7 6 7 A A A A K K K K Q Q Q Q J J J J"),
            deck("5 10 8 2 6 7 2 4 9 2 6 10 10 5 4 8 4 8 6 9 8 5 9 3 4 9"),
            {status: .Finished, cards: 40, tricks: 4},
        ),
        (
            "mirrored decks",
            deck("2 A 3 A 3 K 4 K 2 Q 2 Q 10 J 5 J 6 10 2 9 10 7 3 9 6 9"),
            deck("6 A 4 A 7 K 4 K 7 Q 7 Q 5 J 8 J 4 5 8 9 10 6 8 3 8 5"),
            {status: .Finished, cards: 59, tricks: 4},
        ),
        (
            "opposite decks",
            deck("4 A 9 A 4 K 9 K 6 Q 8 Q 8 J 10 J 9 8 4 6 3 6 5 2 4 3"),
            deck("10 7 3 2 9 2 7 8 7 5 J 7 J 10 Q 10 Q 3 K 5 K 6 A 2 A 5"),
            {status: .Finished, cards: 151, tricks: 21},
        ),
        (
            "random decks #1",
            deck("K 10 9 8 J 8 6 9 7 A K 5 4 4 J 5 J 4 3 5 8 6 7 7 4 9"),
            deck("6 3 K A Q 10 A 2 Q 8 2 10 10 2 Q 3 K 9 7 A 3 Q 5 J 2 6"),
            {status: .Finished, cards: 542, tricks: 76},
        ),
        (
            "random decks #2",
            deck("8 A 4 8 5 Q J 2 6 2 9 7 K A 8 10 K 8 10 9 K 6 7 3 K 9"),
            deck("10 5 2 6 Q J A 9 5 5 3 7 3 J A 2 Q 3 J Q 4 10 4 7 4 6"),
            {status: .Finished, cards: 327, tricks: 42},
        ),
        (
            "Kleber 1999",
            deck("4 8 9 J Q 8 5 5 K 2 A 9 8 5 10 A 4 J 3 K 6 9 2 Q K 7"),
            deck("10 J 3 2 4 10 4 7 5 3 6 6 7 A J Q A 7 2 10 3 K 9 6 8 Q"),
            {status: .Finished, cards: 5790, tricks: 805},
        ),
        (
            "Collins 2006",
            deck("A 8 Q K 9 10 3 7 4 2 Q 3 2 10 9 K A 8 7 7 4 5 J 9 2 10"),
            deck("4 J A K 8 5 6 6 A 6 5 Q 4 6 10 8 J 2 5 7 Q J 3 3 K 9"),
            {status: .Finished, cards: 6913, tricks: 960},
        ),
        (
            "Mann and Wu 2007",
            deck("K 2 K K 3 3 6 10 K 6 A 2 5 5 7 9 J A A 3 4 Q 4 8 J 6"),
            deck("4 5 2 Q 7 9 9 Q 7 J 9 8 10 3 10 J 4 10 8 6 8 7 A Q 5 2"),
            {status: .Finished, cards: 7157, tricks: 1007},
        ),
        (
            "Nessler 2012",
            deck("10 3 6 7 Q 2 9 8 2 8 4 A 10 6 K 2 10 A 5 A 2 4 Q J K 4"),
            deck("10 Q 4 6 J 9 3 J 9 3 3 Q K 5 9 5 K 6 5 7 8 J A 7 8 7"),
            {status: .Finished, cards: 7207, tricks: 1015},
        ),
        (
            "Anderson 2013",
            deck("6 7 A 3 Q 3 5 J 3 2 J 7 4 5 Q 10 5 A J 2 K 8 9 9 K 3"),
            deck("4 J 6 9 8 5 10 7 9 Q 2 7 10 8 4 10 A 6 4 A 6 8 Q K K 2"),
            {status: .Finished, cards: 7225, tricks: 1016},
        ),
        (
            "Rucklidge 2014",
            deck("8 J 2 9 4 4 5 8 Q 3 9 3 6 2 8 A A A 9 4 7 2 5 Q Q 3"),
            deck("K 7 10 6 3 J A 7 6 5 5 8 10 9 10 4 2 7 K Q 10 K 6 J J K"),
            {status: .Finished, cards: 7959, tricks: 1122},
        ),
        (
            "Nessler 2021",
            deck("7 2 3 4 K 9 6 10 A 8 9 Q 7 A 4 8 J J A 4 3 2 5 6 6 J"),
            deck("3 10 8 9 8 K K 2 5 5 7 6 4 3 5 7 A 9 J K 2 Q 10 Q 10 Q"),
            {status: .Finished, cards: 7972, tricks: 1106},
        ),
        (
            "Nessler 2022",
            deck("2 10 10 A J 3 8 Q 2 5 5 5 9 2 4 3 10 Q A K Q J J 9 Q K"),
            deck("10 7 6 3 6 A 8 9 4 3 K J 6 K 4 9 7 8 5 7 8 2 A 7 4 6"),
            {status: .Finished, cards: 8344, tricks: 1164},
        ),
        (
            "Casella 2024, first infinite game found",
            deck("2 8 4 K 5 2 3 Q 6 K Q A J 3 5 9 8 3 A A J 4 4 J 7 5"),
            deck("7 7 8 6 10 10 6 10 7 2 Q 6 3 2 4 K Q 10 J 5 9 8 9 9 K A"),
            {status: .Loop, cards: 474, tricks: 66},
        ),
    ]
    |> subtests (description, player_a, player_b, expected), description
        assert camicia.simulate_game(player_a, player_b) == expected
    end
end
  • simulate_game returns a Game, a struct of a Status enum (Finished or Loop) and the two counts, where the canonical data writes "finished" and "loop".
  • Cards stay the canonical strings. penalty is the one place that knows a card: J, Q, K and A make the other player pay 1 to 4 cards, and every other card is a number card worth 0.
  • A trick is play, a tail-recursive function over whose turn it is, the pile so far (newest card first), how many cards the player on turn still owes, and who played the payment card they owe for. A payment card hands the debt to the other player; the last card of a debt ends the trick for that card’s player; a player with no card to play ends it for the other.
  • The hands are a Hands struct of the two decks, with a private Side enum and hand and with_hand to read and replace one side. The collector puts the pile under their deck in the order it was played, which is Iter.reverse of the pile as play built it.
  • rounds plays tricks until the player who did not collect has no cards, or the hands take a shape they had before. The shape is both decks with every number card written -, since the rules decide nothing by a number card’s value; the shapes seen so far, the starting one included, are a Set of tuples.
  • The 28 canonical cases are one subtests table named by the description column. A deck is written as its cards separated by spaces and read with String.words (the test file’s deck), so a 26-card deck fits on a line, and the two decks of “the story is starting to get a bit complicated” are """ strings over six lines each. As a list of strings, nomi fmt puts each card on its own line, about 360 lines for that case alone.
  • The long games, Kleber 1999 to Nessler 2022, play up to 8,344 cards each. Putting a pile under a deck is a list literal with two spreads, [..hand, ..Iter.reverse(pile)], linear in the deck, which is at most 52 cards, so lists serve and no queue is needed.