HW7 confirmations

.gitignore

/venv/
/*.txt
/.idea/
__pycache__/

README.md

Some programs to help me confirm my answers to HW7.

mystery.py

#!/usr/bin/env python3

import argparse
import random
from collections import defaultdict
from typing import Sequence, List, NamedTuple, Tuple, Any, Union


class Result(NamedTuple):

    seq: Tuple[int, ...]
    num_outer_loops: int
    num_i_assignments: int
    num_j_assignments: int
    num_swaps: int

    def num_assignments(self):
        return self.num_i_assignments + self.num_j_assignments

    def num_operations(self):
        return self.num_assignments() + self.num_swaps

    def __str__(self):
        k = self.num_j_assignments + self.num_i_assignments + self.num_swaps
        return f"Result<n={len(self.seq)},k={k},i+j={self.num_i_assignments + self.num_j_assignments},outer={self.num_outer_loops},i={self.num_i_assignments},j={self.num_j_assignments},swaps={self.num_swaps}>"


def swap(a: List[Any], i: int, j: int):
    tmp = a[i]
    a[i] = a[j]
    a[j] = tmp


def algo(seq: Sequence[int], p: int) -> Result:
    a = list(seq)
    num_swaps, num_i_assignments, num_j_assignments, num_outer_loops = 0, 0, 0, 0
    n = len(a)
    i = 0
    j = n - 1
    while i < j:
        while i < j and a[i] < p:
            i += 1
            num_i_assignments += 1
        while i < j and a[j] >= p:
            j -= 1
            num_j_assignments += 1
        if i < j:
            swap(a, i, j)
            num_swaps += 1
        num_outer_loops += 1
    return Result(tuple(a), num_outer_loops, num_i_assignments, num_j_assignments, num_swaps)


_DEFAULT_MIN = -50
_DEFAULT_MAX = 49
_DEFAULT_LEN = (_DEFAULT_MAX - _DEFAULT_MIN) + 1


class Capture(NamedTuple):

    min: Union[float, int]
    max: Union[float, int]
    mean: Union[float, int]
    n: int


class Tracker(object):

    def __init__(self):
        self.min = None
        self.max = None
        self.n = 0
        self.sum = 0

    def __call__(self, value: Union[float, int]):
        self.n += 1
        if self.min is None or value < self.min:
            self.min = value
        if self.max is None or value > self.max:
            self.max = value
        self.sum += value

    def capture(self) -> Capture:
        return Capture(self.min, self.max, self.sum / self.n, self.n)



def trial(sequence, p) -> Result:
    return algo(sequence, p)


def fixed_generator(sequence, trials):
    sequence = tuple(sequence)
    for i in range(trials):
        yield sequence


def rand_generator(rng: random.Random, length: int, trials: int, minval: int, maxval: int):
    for i in range(trials):
        sequence = [None] * length
        for j in range(len(sequence)):
            sequence[j] = rng.randrange(minval, maxval)
        yield sequence


def main():
    parser = argparse.ArgumentParser()
    parser.add_argument("sequence", nargs='*', type=int)
    parser.add_argument("--min", type=int, default=_DEFAULT_MIN)
    parser.add_argument("--max", type=int, default=_DEFAULT_MAX)
    parser.add_argument("-n", "--length", type=int, default=_DEFAULT_LEN)
    parser.add_argument("-t", "--trials", type=int, default=1)
    parser.add_argument("-p", "--threshold", type=int, default=0)
    parser.add_argument("-v", "--verbose", action='store_true', help="print every trial")
    args = parser.parse_args()
    trackers = defaultdict(Tracker)
    if args.sequence:
        sequence_generator = fixed_generator(args.sequence, args.trials)
    else:
        sequence_generator = rand_generator(random.Random(), args.length, args.trials, args.min, args.max)
    for sequence in sequence_generator:
        result = trial(sequence, args.threshold)
        stats = {
            'operations' : result.num_operations(),
            'assignments': result.num_assignments(),
            'swaparoos'  : result.num_swaps,
            'outerloops' : result.num_outer_loops,
        }
        for k, v in stats.items():
            track = trackers[k]
            track(v)
        if args.verbose:
            print(result)
    for category, stats in trackers.items():
        print(f"{category}\t{stats.capture()}")
    return 0


if __name__ == '__main__':
    exit(main())

poker.py

#!/usr/bin/env python3

import itertools
from typing import NamedTuple, FrozenSet, Callable, Sequence, Dict, Tuple
from math import factorial as fact
from collections import defaultdict


_RANKS = frozenset(range(1, 14))
assert len(_RANKS) == 13
_RANK_NAMES = dict([(1, 'A'), (11, 'J'), (12, 'Q'), (13, 'K')] + [(r, str(r)) for r in range(2, 11)])
HEARTS = '♥'
CLUBS = '♣'
DIAMONDS = '♦'
SPADES = '♠'
SUITS = frozenset({SPADES, HEARTS, DIAMONDS, CLUBS})
assert len(SUITS) == 4
_ONE_PAIR = (1, 1, 1, 2)
_TWO_PAIR = (1, 2, 2)
_THREE_OF_A_KIND = (1, 1, 3)
_FOUR_OF_A_KIND = (1, 4)
_FULL_HOUSE = (2, 3)


class Card(NamedTuple):

    rank: int
    suit: str

    @staticmethod
    def deck(suits=None, ranks=None) -> FrozenSet['Card']:
        if suits is None:
            suits = SUITS
        if ranks is None:
            ranks = _RANKS
        cards = set()
        for rank in ranks:
            for suit in suits:
                cards.add(Card(rank, suit))
        assert len(cards) == len(suits) * len(ranks)
        return frozenset(cards)

    def __str__(self):
        rank_name = _RANK_NAMES.get(self.rank, None)
        if rank_name is None:
            rank_name = str(self.rank)
        return f"{rank_name}{self.suit}"

    @staticmethod
    def tally(cards: Sequence['Card'], predicate: Callable[['Card'], bool]) -> int:
        count = 0
        for card in cards:
            if predicate(card):
                count += 1
        return count

    @staticmethod
    def count_by_rank(cards: Sequence['Card']) -> Dict[int, int]:
        d = defaultdict(int)
        for card in cards:
            d[card.rank] += 1
        return d


class Hand(NamedTuple):

    cards: FrozenSet[Card]
    rank_counts_sorted: Tuple[int, ...]

    @staticmethod
    def create(cards: Sequence[Card]) -> 'Hand':
        rank_counts = Card.count_by_rank(cards)
        return Hand(frozenset(cards), tuple(sorted(rank_counts.values())))

    def size(self):
        return len(self.cards)

    def suit_count(self, suit):
        return sum([1 if card.suit == suit else 0 for card in self.cards])

    def has_card(self, card: Card):
        for h in self.cards:
            if card == h:
                return True
        return False

    def rank_count(self, suit):
        return sum([1 if card.suit == suit else 0 for card in self.cards])

    def __str__(self):
        return f"{{{','.join(map(str, self.cards))}}}"

    def full_house(self):
        return self.rank_counts_sorted == _FULL_HOUSE

    def one_pair(self):
        return self.rank_counts_sorted == _ONE_PAIR

    def two_pair(self):
        return self.rank_counts_sorted == _TWO_PAIR

    def three_of_a_kind(self):
        return self.rank_counts_sorted == _THREE_OF_A_KIND

    def four_of_a_kind(self):
        return self.rank_counts_sorted == _FOUR_OF_A_KIND


def main():
    deck = Card.deck()
    hand_size = 5
    n = 0
    n1p, n2p, n3k, n4k, nfh = 0, 0, 0, 0, 0
    nclub = 0
    nhd = 0
    for cards in itertools.combinations(deck, hand_size):
        n += 1
        hand = Hand.create(cards)
        if hand.rank_counts_sorted == _ONE_PAIR:
            n1p += 1
        elif hand.rank_counts_sorted == _TWO_PAIR:
            n2p += 1
        elif hand.rank_counts_sorted == _THREE_OF_A_KIND:
            n3k += 1
        elif hand.rank_counts_sorted == _FOUR_OF_A_KIND:
            n4k += 1
        elif hand.rank_counts_sorted == _FULL_HOUSE:
            nfh += 1
        if hand.suit_count(HEARTS) + hand.suit_count(DIAMONDS) == hand.size():
            nhd += 1
        if hand.suit_count(CLUBS) > 0:
            nclub += 1
    assert 52 == len(deck)
    assert C(52, hand_size) == n
    print(f"{n} hands")
    print(f"{n1p} one-pair hands")
    print(f"{n2p} two-pair hands")
    print(f"{n3k} three-of-a-kind hands")
    print(f"{nfh} full house hands; {C(13,1) * C(4,3) * C(12,1) * C(4,2)}")
    print(f"{n4k} four-of-a-kind hands; 13 * 48 = {13 * 48}")
    print(f"{n - n1p - n2p - n3k - nfh - n4k} hands with unique cards; C(13,5)*4**5 = {C(13,5) * 4**5}")
    print(f"{n1p + n2p + n3k + nfh + n4k} with at least 2 of same rank; expect {C(52,5) - C(13,5) * 4**5}")
    print(f"{nclub} hands have at least one {CLUBS}; expect 2023203")
    print(f"{nhd} hands are all {HEARTS} or {DIAMONDS}; C(26, 5) = {C(26, 5)}")
    return 0


# noinspection PyPep8Naming
def C(n, r):
    """Returns the number of subsets or r elements from a set of size n."""
    return fact(n) // fact(r) // fact(n - r)


if __name__ == '__main__':
    exit(main())

reps.py

#!/usr/bin/env python3

import itertools

def main():
    chars = {'a', 'b', 'c'}
    t10 = [''.join(x) for x in itertools.product(*([sorted(chars)] * 10))]
    n = 0
    for t in t10:
        hasreps = False
        for i in range(1, len(t)):
            if t[i - 1] == t[i]:
                hasreps = True
                break
        if not hasreps:
            n += 1
    print(n)
    return 0


if __name__ == '__main__':
    exit(main())

test_poker.py

#!/usr/bin/env python3


from unittest import TestCase
from poker import Card, Hand, C
import poker

class HandTest(TestCase):

    def test_one_pair(self):
        hand = Hand.create([Card(1, 'H'), Card(1, 'S'), Card(2, 'C'), Card(3, 'S'), Card(4, 'D')])
        assert 5 == hand.size()
        self.assertTrue(hand.one_pair(), f"one pair in {hand}")
        self.assertFalse(hand.two_pair())
        self.assertFalse(hand.full_house())
        self.assertFalse(hand.three_of_a_kind())
        self.assertFalse(hand.four_of_a_kind())

    def test_fourofakind(self):
        hand = Hand.create([Card(1, 'H'), Card(1, 'S'), Card(1, 'D'), Card(1, 'C'), Card(4, 'D')])
        assert 5 == hand.size()
        self.assertTrue(hand.four_of_a_kind(), f"four of a kind in {hand}")
        self.assertFalse(hand.one_pair(), f"one pair in {hand}")
        self.assertFalse(hand.two_pair())
        self.assertFalse(hand.full_house())
        self.assertFalse(hand.three_of_a_kind())


class MainTest(TestCase):

    def test_x(self):
        poker.main()