#!/usr/bin/env python3
"""Deals a game of euchre again from its revealed seed, exactly as the app dealt it.

Usage: python3 verify_deal.py HOUSE_SEED ["YOUR PHRASE"] [--hands N] [--joker] [--dealers n,e,e,s]
                              [--patterns 3232,2323,1234] [--colorful] [--everyone 3232 | --one-at-a-time]
                              [--first-dealer black-jack] [--chooser north] [--drawn north,east,west]
                              [--cuts 9,-,bump] [--players 3 [--dummy]]
       python3 verify_deal.py --record game.json

HOUSE_SEED is the 64 hex digits the app reveals when the game is over. Check that the
fingerprint printed below matches the one the app showed before the first card.

Each dealer deals from the top of the deck in rounds of packets, clockwise from their left.
A pattern such as 3232 is the first round's packets (three, two, three, two); the second
round makes each hand up to five. 11111 is one card at a time, five times round, and 5555
deals each hand whole, as games did before dealers chose a pattern. The app's Check the Deal
screen lists each deal's pattern. The computer opponents, east and west, each deal as the
game's seed draws for them (--colorful when colorful dealers were on), which this script
prints so you can compare. In a tournament's game your partner's way is drawn the same way
(--drawn north,east,west), and at the other table everyone's (--drawn north,east,south,west).
Where the table's rules require one way of every dealer (--everyone 3232, or --one-at-a-time,
the same as --everyone 11111), no one's way is drawn, and every deal should be dealt that way.

The first dealer is the seat the game's seed draws, or where cards were turned up for it
(--first-dealer black-jack, jack, ace, low or high), the player they chose: the cards come from a
shuffle of their own, the deck without the Joker shuffled as for a deal numbered -1, and are dealt
face up from the left of the player who turned them (--chooser), the next to deal after the game
before, or with no game before, the seat the seed draws. They go round one at a time until the
first black jack, jack or ace; or each player takes one, the lowest dealing (ace low) or the
highest (jack highest, then ace), those who tie for it taking another.

Where the rules have a cut (--cuts), the player on the dealer's right cuts the deck before each
deal: the top cards go under. Give each deal's cut in turn: the number of cards lifted, - where
the seed cut (a computer player's cut, and yours unless you cut by hand), or bump where the cutter
declined; deals past the list are cut by the seed. The seed's cut is the SHA-256 of "cut:", the
deal's number from 0, a colon and the game seed's 64 hex digits: its first two bytes as a
number, modulo the deck's size less 7, plus 4, so at least four cards stay each side. With a
kitchen-table shuffle the cutter's cut takes the place of the dealer's.

A game with a kitchen-table shuffle deals each hand from the cards gathered after the one
before, so it needs the game's record: copy it from Check the Deal into a file and pass it
with --record. The record gives the shuffle and how many times the dealer riffled. It also
works for any other game.

Cutthroat, three-handed euchre (--players 3), is played from east, south and west: the seed draws
the first dealer among them (its digest's last byte modulo 3, counting east, south, west), the
choosing cards go round the three, and the deal passes left among them, skipping north. Each
dealer deals five cards to each of the three from their left, in rounds of three packets, then
turns up the next card over a kitty of eight: a pattern is the first round's three packets, such
as 323, and one at a time is written out round by round, 111/111/111/111/111. A way of dealing
four maps to three by its first three packets (3232 deals 323, the opponents' drawn ways too).
With a dummy (--dummy), four hands are dealt as in the partners game, north's the dummy.
"""
import argparse
import hashlib
import json
import unicodedata

MASK = (1 << 64) - 1
SEATS = ["north", "east", "south", "west"]
SUITS = ["♣", "♦", "♥", "♠"]  # clubs, diamonds, hearts, spades
RANKS = ["9", "10", "J", "Q", "K", "A"]
# The usual patterns an opponent's draw picks from, by the first byte of its digest modulo 8.
USUAL = ["3232", "3232", "3232", "3232", "2323", "2323", "3333", "2222"]
# Colorful dealers' ways, by the fifth byte of the digest modulo 7: the cascade and its reverse,
# fours and ones, ones and fours, all fours or all ones first, and one at a time.
COLOURFUL = ["1234", "4321", "4141", "1414", "4444", "1111", "11111"]
# The ways a table's rules may require of every dealer: one at a time, or one of the four standard patterns.
REQUIRABLE = ["11111", "3232", "2323", "3333", "2222"]
# How many riffles each shuffle gives the gathered cards before the cut, for a record that doesn't give the number:
# the standard's two for a kitchen-table shuffle, as the app reads such a game; None shuffles thoroughly.
RIFFLES = {"thorough": None, "kitchenTable": 2}
SHUFFLE_NAMES = {"kitchenTable": "kitchen table"}


def splitmix64(state):
    state = (state + 0x9E3779B97F4A7C15) & MASK
    z = state
    z = ((z ^ (z >> 30)) * 0xBF58476D1CE4E5B9) & MASK
    z = ((z ^ (z >> 27)) * 0x94D049BB133111EB) & MASK
    return state, z ^ (z >> 31)


def rotl(x, k):
    return ((x << k) | (x >> (64 - k))) & MASK


class Xoshiro256StarStar:
    def __init__(self, words):
        self.s = list(words)
        if not any(self.s):
            self.s[0] = 1

    def next(self):
        s = self.s
        result = (rotl((s[1] * 5) & MASK, 7) * 9) & MASK
        t = (s[1] << 17) & MASK
        s[2] ^= s[0]
        s[3] ^= s[1]
        s[1] ^= s[2]
        s[0] ^= s[3]
        s[2] ^= t
        s[3] = rotl(s[3], 45)
        return result

    def below(self, bound):
        """A uniform number in 0..bound-1, by Lemire's multiply-and-reject method."""
        product = self.next() * bound
        if product & MASK < bound:
            threshold = ((1 << 64) - bound) % bound
            while product & MASK < threshold:
                product = self.next() * bound
        return product >> 64


def stream(seed_words, deal_number):
    """Each deal's own random numbers: the seed mixed with SplitMix64 outputs from the deal number."""
    state, mixed = deal_number & MASK, []
    for word in seed_words:
        state, value = splitmix64(state)
        mixed.append(word ^ value)
    return Xoshiro256StarStar(mixed)


def new_deck(joker):
    """The deck in order: clubs, diamonds, hearts, spades, each 9 through ace, then the Joker."""
    return [rank + suit for suit in SUITS for rank in RANKS] + (["Joker"] if joker else [])


def thorough_deck(seed_words, deal_number, joker):
    """A Fisher-Yates shuffle, drawing from the end of the deck toward the front."""
    rng = stream(seed_words, deal_number)
    deck = new_deck(joker)
    for i in range(len(deck) - 1, 0, -1):
        j = rng.below(i + 1)
        deck[i], deck[j] = deck[j], deck[i]
    return deck


def riffle(deck, rng):
    """One riffle: cut the deck in two, the top packet taking as many cards as heads in a coin tossed
    once for each card (the top bit of a draw), then let the cards fall together from the top, each
    from the top packet when a draw below the cards left in both packets is below its count."""
    top = sum(rng.next() >> 63 for _ in deck)
    upper, lower, riffled = deck[:top], deck[top:], []
    while upper or lower:
        if rng.below(len(upper) + len(lower)) < len(upper):
            riffled.append(upper.pop(0))
        else:
            riffled.append(lower.pop(0))
    return riffled


def cut(deck, rng):
    """The top cards go to the bottom: as many as a draw below one less than the deck's size, plus one."""
    point = 1 + rng.below(len(deck) - 1)
    return deck[point:] + deck[:point]


def kitchen_table_deck(seed_words, deal_number, gathered, riffles, cutter_cuts=False):
    """The cards as gathered after the hand before, riffled and cut with the deal's random numbers; where the
    player on the dealer's right cuts, only riffled, for their cut to follow."""
    rng = stream(seed_words, deal_number)
    deck = list(gathered)
    for _ in range(riffles):
        deck = riffle(deck, rng)
    return deck if cutter_cuts else cut(deck, rng)


def seed_cut(seed_hex, deal_number, size):
    """Where the seed cuts the deck for a deal: four cards or more each side."""
    digest = hashlib.sha256(("cut:" + str(deal_number) + ":" + seed_hex).encode("utf-8")).digest()
    return (digest[0] << 8 | digest[1]) % (size - 7) + 4


def parse_cut(code):
    """A cut as --cuts gives it: the cards lifted, None for the seed's, or "bump"."""
    code = code.strip()
    if code in ("-", "seed", ""):
        return None
    if code == "bump":
        return "bump"
    if not code.isdigit():
        raise ValueError(code)
    return int(code)


# Cutthroat's one at a time for three, written round by round, since 11111 is the four-player one.
ONE_AT_A_TIME_FOR_THREE = "111/111/111/111/111"


def rounds(pattern):
    """A pattern's rounds of packets, for the players in turn from the dealer's left."""
    if pattern == "11111":
        return [[1, 1, 1, 1]] * 5
    if pattern == ONE_AT_A_TIME_FOR_THREE:
        return [[1, 1, 1]] * 5
    first = [int(digit) for digit in pattern]
    return [first] if all(size == 5 for size in first) else [first, [5 - size for size in first]]


def for_three(pattern):
    """A way of dealing four as it deals three in cutthroat with the kitty: its first three packets."""
    if pattern == "11111":
        return ONE_AT_A_TIME_FOR_THREE
    return pattern if len(pattern) == 3 or pattern == ONE_AT_A_TIME_FOR_THREE else pattern[:3]


def seats_playing(players):
    """The seats a game is played from: all four, or in cutthroat east, south and west."""
    return SEATS if players == 4 else ["east", "south", "west"]


def seat_after(seat, seats, places):
    """The seat `places` to the left of `seat` among `seats`."""
    return seats[(seats.index(seat) + places) % len(seats)]


def deal(deck, dealer, pattern):
    """Deals the deck from the top in rounds of packets clockwise from the dealer's left, then the
    up-card and the kitty. A three-player pattern deals east, south and west, skipping north."""
    seats = seats_playing(len(rounds(pattern)[0]))
    order = [seat_after(dealer, seats, place) for place in range(1, len(seats) + 1)]
    hands, top = {seat: [] for seat in SEATS}, 0
    for sizes in rounds(pattern):
        for seat, size in zip(order, sizes):
            hands[seat] += deck[top:top + size]
            top += size
    return hands, deck[top], deck[top + 1:]


# How the first dealer may be chosen by cards: dealing round until a card appears, or a draw.
FIRST_DEALER = {"black-jack": "the first black jack", "jack": "the first jack", "ace": "the first ace",
                "low": "the lowest card, the ace low", "high": "the highest card, the jack highest"}
# How ranks stand in a draw, lowest first.
LOW_DRAW = ["A", "9", "10", "J", "Q", "K"]
HIGH_DRAW = ["9", "10", "Q", "K", "A", "J"]


def choose_dealer(seed_words, how, chooser, seats=SEATS):
    """The cards turned up to choose the first dealer, each with the seat it went to, and the dealer
    they chose: from the choosing shuffle, dealt from the chooser's left round `seats`. A chooser
    not among them, north before a cutthroat game, hands the cards to the next seat that is."""
    deck = thorough_deck(seed_words, -1, False)
    while chooser not in seats:
        chooser = SEATS[(SEATS.index(chooser) + 1) % 4]
    order = [seat_after(chooser, seats, place) for place in range(1, len(seats) + 1)]
    turns = []
    if how in ("black-jack", "jack", "ace"):
        for number, card in enumerate(deck):
            seat = order[number % len(order)]
            turns.append((seat, card))
            rank, suit = card[:-1], card[-1]
            if (how == "ace" and rank == "A") or (how == "jack" and rank == "J") \
                    or (how == "black-jack" and rank == "J" and suit in "♣♠"):
                return turns, seat
    standing = LOW_DRAW if how == "low" else HIGH_DRAW
    contenders, top = order, 0
    while len(contenders) > 1 and top + len(contenders) <= len(deck):
        drawn = [(seat, deck[top + place]) for place, seat in enumerate(contenders)]
        top += len(contenders)
        turns += drawn
        ranks = [standing.index(card[:-1]) for _, card in drawn]
        best = min(ranks) if how == "low" else max(ranks)
        contenders = [seat for (seat, _), rank in zip(drawn, ranks) if rank == best]
    return turns, contenders[0]


def drawn_style(seat, seed_hex, colourful):
    """How a computer player deals all game, drawn from the game's seed so the app can't pick it:
    its usual pattern, the deal number (from 0) from which it changes up, or None, and whether it's
    a colorful way."""
    digest = hashlib.sha256(("deal:" + seat + ":" + seed_hex).encode("utf-8")).digest()
    if colourful and digest[3] % 2 == 0:
        return COLOURFUL[digest[4] % len(COLOURFUL)], None, True
    usual = USUAL[digest[0] % 8]
    changes_up = usual in ("3232", "2323") and digest[1] % 4 == 0
    return usual, (4 + digest[2] % 8) if changes_up else None, False


def drawn_pattern(style, deal_number):
    usual, changes_up_at, _ = style
    if changes_up_at is not None and deal_number >= changes_up_at:
        return "2323" if usual == "3232" else "3232"
    return usual


def valid_pattern(code, players=4):
    if players == 3:
        return code in ("555", ONE_AT_A_TIME_FOR_THREE) or (len(code) == 3 and all(c in "1234" for c in code))
    return code in ("5555", "11111") or (len(code) == 4 and all(c in "1234" for c in code))


def main():
    parser = argparse.ArgumentParser(description="Deal a euchre game again from its revealed seed.")
    parser.add_argument("house_seed", nargs="?", help="the 64 hex digits revealed after the game")
    parser.add_argument("phrase", nargs="?", default="", help="the phrase you added, if any")
    parser.add_argument("--hands", type=int, default=3, help="how many deals to show")
    parser.add_argument("--joker", action="store_true", help="the game was played with the Joker")
    parser.add_argument("--dealers", help="each deal's dealer as n, e, s or w, when a misdeal kept a dealer dealing")
    parser.add_argument("--patterns", help="each deal's pattern, such as 3232,2323,1234; the last one given carries on")
    parser.add_argument("--colorful", "--colourful", dest="colourful", action="store_true",
                        help="colorful dealers were on")
    parser.add_argument("--everyone", choices=REQUIRABLE,
                        help="the one way the table's rules required of every dealer, such as 3232 or 11111")
    parser.add_argument("--one-at-a-time", dest="everyone", action="store_const", const="11111",
                        help="everyone dealt one at a time: the same as --everyone 11111")
    parser.add_argument("--first-dealer", choices=["seed"] + list(FIRST_DEALER), default="seed",
                        help="how the first dealer was chosen: drawn by the seed, or by cards turned up")
    parser.add_argument("--chooser", choices=SEATS, help="who turned up the choosing cards, when the seed didn't draw them")
    parser.add_argument("--drawn", default="east,west",
                        help="the seats whose ways of dealing the seed drew: east,west unless it's a tournament's game")
    parser.add_argument("--cuts", help="each deal's cut where the rules have one: cards lifted, - for the seed's, or bump")
    parser.add_argument("--players", type=int, choices=[3, 4], default=4,
                        help="3 for cutthroat, played from east, south and west")
    parser.add_argument("--dummy", action="store_true", help="cutthroat with a dummy dealt at north")
    parser.add_argument("--record", metavar="FILE", help="the game's record, copied from Check the Deal")
    args = parser.parse_args()

    shuffle, riffles, records = "thorough", None, None
    if args.record:
        with open(args.record, encoding="utf-8") as file:
            record = json.load(file)
        args.house_seed, args.phrase, args.joker = record["houseSeed"], record["phrase"], record["joker"]
        args.players, args.dummy = record.get("players", 4), record.get("dummy", False)
        args.colourful = record["colourful"]
        args.everyone = record.get("everyone") or ("11111" if record.get("oneAtATime") else None)
        if args.everyone not in [None] + REQUIRABLE:
            parser.error("the record's required way of dealing isn't one this script knows")
        shuffle, records = record["shuffle"], record["deals"]
        if shuffle not in RIFFLES:
            parser.error("the record's shuffle isn't one this script knows")
        riffles = record.get("riffles", RIFFLES[shuffle])
        dealers = [entry["dealer"] for entry in records]
        patterns = [entry["pattern"] for entry in records]
        draws = record["dealersChose"] and not args.everyone
        args.first_dealer, args.chooser = record.get("firstDealer", "seed"), record.get("chooser")
        drawn = record.get("drawn", ["east", "west"])
        if record.get("cuts") is not None:
            args.cuts = ",".join(str(code) for code in record["cuts"]) or "-"
    else:
        if not args.house_seed:
            parser.error("give the house seed, or --record and a file")
        dealers = [next(seat for seat in SEATS if seat[0] == letter.strip()) for letter in args.dealers.split(",")] \
            if args.dealers else None
        patterns = args.patterns.split(",") if args.patterns else [args.everyone or "5555"]
        # The opponents deal as the seed draws for them, except where the rules require one way of everyone and in
        # games from before dealers chose a pattern.
        draws = bool(args.patterns) and not args.everyone
        drawn = [seat.strip() for seat in args.drawn.split(",")]
    if args.dummy and args.players != 3:
        parser.error("--dummy is for cutthroat: give --players 3 too")
    if args.players == 3 and args.joker:
        parser.error("cutthroat is played without the Joker")
    # In cutthroat with the kitty, three are dealt to: a way of dealing four deals the three-player pattern it maps to.
    three_hands = args.players == 3 and not args.dummy
    dealt_as = for_three if three_hands else (lambda code: code)
    if not args.patterns and not args.record:
        patterns = [dealt_as(code) for code in patterns]
    if not all(valid_pattern(code, 3 if three_hands else 4) for code in patterns):
        if three_hands:
            parser.error("a pattern for three is three digits from 1 to 4, such as 323, or 111/111/111/111/111 or 555")
        parser.error("a pattern is four digits from 1 to 4, such as 3232, or 11111 or 5555")
    if not all(seat in SEATS for seat in drawn):
        parser.error("--drawn names seats: north, east, south or west, separated by commas")
    try:
        cuts = [parse_cut(code) for code in args.cuts.split(",")] if args.cuts is not None else None
    except ValueError:
        parser.error("a cut is the number of cards lifted, - for the seed's, or bump")

    # The app keeps the phrase in Unicode's composed form (NFC), however it was typed.
    phrase = unicodedata.normalize("NFC", args.phrase)
    fingerprint = hashlib.sha256(args.house_seed.encode("utf-8")).hexdigest()
    digest = hashlib.sha256((args.house_seed + ":" + phrase).encode("utf-8")).digest()
    words = [int.from_bytes(digest[i:i + 8], "big") for i in range(0, 32, 8)]
    seats = seats_playing(args.players)
    dealer = seats[digest[31] % len(seats)]
    print("Fingerprint:", fingerprint)
    print("Game seed:  ", digest.hex())
    if args.first_dealer != "seed":
        # With no game before, the seat the seed draws turns up the cards; in cutthroat a chooser at north, the next to
        # deal after a partners game, hands them to east.
        chooser = args.chooser or dealer
        while chooser not in seats:
            chooser = SEATS[(SEATS.index(chooser) + 1) % 4]
        turns, dealer = choose_dealer(words, args.first_dealer, chooser, seats)
        print(f"Choosing by {FIRST_DEALER[args.first_dealer]}, {chooser} turning the cards:")
        for seat, card in turns:
            print(f"  {seat:<6} {card}")
    print("First dealer:", dealer)
    if riffles is not None:
        print(f"Shuffle: {SHUFFLE_NAMES[shuffle]}, {riffles} riffle{'' if riffles == 1 else 's'} and a cut")
    styles = {seat: drawn_style(seat, digest.hex(), args.colourful) for seat in SEATS if seat in drawn} if draws else {}
    for seat, style in styles.items():
        usual, changes_up_at, colourful = style
        change = f", then {dealt_as(drawn_pattern(style, changes_up_at))} from deal {changes_up_at + 1}" \
            if changes_up_at is not None else ""
        print(f"The seed draws {seat} to deal {dealt_as(usual)}{change}{' (colorful)' if colourful else ''}")

    for number in range(len(dealers) if dealers else args.hands):
        if dealers:
            dealer = dealers[number]
        pattern = patterns[min(number, len(patterns) - 1)]
        if riffles is None or number == 0:
            deck = thorough_deck(words, number, args.joker)
        else:
            # The hand before, gathered up: its tricks as played, the cards still held, then the table.
            before = records[number - 1]
            gathered = [card for trick in before["tricks"] for card in trick] + before["held"] + before["onTable"]
            if sorted(gathered) != sorted(new_deck(args.joker)):
                parser.error(f"the cards gathered after deal {number} aren't a whole deck")
            deck = kitchen_table_deck(words, number, gathered, riffles, cutter_cuts=cuts is not None)
        cut_line = None
        if cuts is not None:
            # The player on the dealer's right cuts: the top cards go under.
            cutter = seat_after(dealer, seats, -1)
            how = cuts[number] if number < len(cuts) else None
            if how == "bump":
                cut_line = f"  cut    none: {cutter} bumped"
            else:
                lifted = seed_cut(digest.hex(), number, len(deck)) if how is None else how
                if not 4 <= lifted <= len(deck) - 4:
                    parser.error(f"the cut of deal {number + 1} leaves fewer than four cards one side")
                deck = deck[lifted:] + deck[:lifted]
                cut_line = f"  cut    {lifted} by {cutter}" + (", from the seed" if how is None else "")
        hands, up_card, kitty = deal(deck, dealer, pattern)
        print(f"\nDeal {number + 1}, {dealer} dealing {pattern}")
        if cut_line:
            print(cut_line)
        if dealer in styles and dealt_as(drawn_pattern(styles[dealer], number)) != pattern:
            print(f"  (the seed drew {dealt_as(drawn_pattern(styles[dealer], number))} for {dealer} here)")
        if args.everyone and pattern != dealt_as(args.everyone):
            print(f"  (the table's rules required {dealt_as(args.everyone)} of every dealer)")
        for seat in SEATS:
            # In cutthroat north is dealt nothing under the kitty, and holds the dummy with one.
            if args.players == 3 and seat == "north":
                if args.dummy:
                    print(f"  {'dummy':<6} {' '.join(hands[seat])}")
                continue
            print(f"  {seat:<6} {' '.join(hands[seat])}")
        print(f"  up     {up_card}")
        print(f"  kitty  {' '.join(kitty)}")
        dealer = seat_after(dealer, seats, 1)
    print("\nThe deal passes left after every hand except a misdeal, when the same dealer deals again."
          + (" In cutthroat it passes among east, south and west." if args.players == 3 else ""))


if __name__ == "__main__":
    main()