# ------------------------------------------------------------------------------ # Part 1 - Valid table VALUE = 0 VALUES = {'A': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9, '0': 10, 'J': 11, 'Q': 12, 'K': 13} SUIT = COLOUR = 1 COLOURS = {'D': True, 'H': True, 'C': False, 'S': False} N_SUITS = 4 def comp10001huxxy_valid_table(groups): """ Returns a boolean indicating whether list of groups `groups` (containing card strings) represents a valid table. """ # Checks each group for validity conditions for group in groups: if not valid_group(group): return False return True def valid_group(group): """ Returns a boolean indicating whether list of card strings `group` represents a valid group: either a run or n-of-a-kind. """ # Groups must be either empty or of length three or greater if len(group) == 0: return True elif len(group) < 3: return False else: return valid_run(group) or valid_n_of_a_kind(group) def valid_run(group): """ Returns a boolean indicating whether list of card strings `group` (which is of a valid length) represents a valid run. """ # Generates list of cards in format (value: int, is_red: bool) so that it # can be sorted by card value cards = [] for card in group: curr_value = VALUES[card[VALUE]] curr_colour = COLOURS[card[SUIT]] cards.append((curr_value, curr_colour)) cards.sort() # Processes cards one-by-one, checking for violation of run group rules prev_card = cards[0] for card in cards[1:]: # Value increases by 1 for adjacent cards in the run if card[VALUE] != prev_card[VALUE] + 1 or \ card[COLOUR] == prev_card[COLOUR]: return False prev_card = card return True def valid_n_of_a_kind(group): """ Returns a boolean indicating whether list of card strings `group` (which is of a valid length) represents a valid n-of-a-kind group. """ # Checks that each card has the same value, while adding suits to set value = group[0][VALUE] suits = {group[0][SUIT]} for card in group[1:]: if card[VALUE] != value: return False suits.add(card[SUIT]) # Checks that a group of four or less cards contains no duplicate suits if len(group) <= N_SUITS: return len(suits) == len(group) # Checks that a group of more than four contains one of each suit else: return len(suits) == N_SUITS # ------------------------------------------------------------------------------ # Part 2 - Group validation # Sample solution 1 from math import factorial # index of value of a card VALUE = 0 # index of suit of a card SUIT = 1 # value of Ace ACE = 'A' # dictionary of scores of individual cards card_score = { '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9, '0': 10, 'J': 11, 'Q': 12, 'K': 13, ACE: 20, } # suits which are red RED_SUITS = 'HD' # suits which are black BLACK_SUITS = 'SC' # card colours RED = 1 BLACK = 2 # minimum no. of cards in an n-of-a-kind set MIN_CARDS_NKIND = 2 # minimum no. of non-Ace cards in a run MIN_NONACE_RUN = 2 # minimum no. cards in a run MIN_RUN = 3 def is_ace(card): """Boolean evaluation of whether `card` is an Ace""" return card[VALUE] == ACE def get_score(card): """return the score of `card`, based on its value""" return card_score[card[VALUE]] def get_colour(card): """Return the colour of `card` (`RED` or `BLACK`)""" if card[SUIT] in RED_SUITS: return RED else: return BLACK def comp10001go_score_group(cards): """Validate/score a group of cards (order unimportant), supplied as a list of cards (each a string); return the positive score of the group if valid, and negative score otherwise. Note, assumes that all cards are valid, and unique.""" # construct sorted list of values of cards (ignore suit for now) values = sorted([get_score(card) for card in cards]) # CASE 1: N-of-a-kind if all cards of same value, at least # `MIN_CARDS_NKIND` cards in total, and not Aces if (len(set(values)) == 1 and len(cards) >= MIN_CARDS_NKIND and not is_ace(cards[0])): return factorial(len(cards)) * card_score[cards[0][VALUE]] # construct sorted list of non-Ace cards nonace_cards = sorted([card for card in cards if not is_ace(card)], key=lambda x: get_score(x)) # construct list of Ace cards ace_cards = list(set(cards) - set(nonace_cards)) # run must have at least `MIN_NONACE_RUN` non-Ace cards in it if len(nonace_cards) >= MIN_NONACE_RUN: is_run = True prev_val = prev_colour = None score = 0 # iterate through cards to make sure they form a run for card in nonace_cards: # CASE 1: for the first card in `nonace_cards`, nothing to # check for if prev_val is None: score = prev_val = get_score(card) prev_colour = get_colour(card) # CASE 2: adjacent to previous card in value elif get_score(card) - prev_val == 1: # CASE 2.1: alternating colour, meaning continuation of run if get_colour(card) != prev_colour: prev_val = get_score(card) prev_colour = get_colour(card) score += prev_val # CASE 2.2: not alternating colour, meaning invalid run else: is_run = False break # CASE 3: repeat value, meaning no possibility of valid run elif get_score(card) == prev_val: is_run = False break # CASE 4: gap in values, in which case check to see if can be # filled with Ace(s) else: gap = get_score(card) - prev_val - 1 gap_filled = False # continue until gap filled while is_run and gap and len(ace_cards) >= gap: gap_filled = False # search for an Ace of appropriate colour, and remove # from list of Aces if found (note that it doesn't matter # which Ace is used if multiple Aces of same colour) for i, ace in enumerate(ace_cards): if get_colour(ace) != prev_colour: ace_cards.pop(i) prev_val += 1 prev_colour = get_colour(ace) score += prev_val gap -= 1 gap_filled = True break if not gap_filled: is_run = False if is_run and gap_filled and get_colour(card) != prev_colour: prev_val = get_score(card) prev_colour = get_colour(card) score += prev_val else: is_run = False if is_run and len(cards) >= MIN_RUN and not ace_cards: return score return -sum(values) def comp10001go_valid_groups(groups): for cards in groups: if not cards or (len(cards) > 1 and comp10001go_score_group(cards) < 0): return False return True # Sample solution 2 import math SUIT_TO_COLOUR = dict(zip('HDCS', 'RRBB')) VALUE_STRING_TO_VALUE = dict(zip('A234567890JQK', range(1, 14))) VALUE_TO_VALUE_STRING = {v: k for k, v in VALUE_STRING_TO_VALUE.items()} class Card: def __init__(self, card_string): if isinstance(card_string, tuple): card_string = VALUE_TO_VALUE_STRING[card_string[0]] + card_string[1] self.value_str = card_string[0] self.value = VALUE_STRING_TO_VALUE[self.value_str] self.suit = card_string[1] self.colour = SUIT_TO_COLOUR[self.suit] self.inv_colour = 'R' if self.colour == 'B' else 'B' self.orphan_value = -20 if self.is_ace() else -self.value def __eq__(self, other): return self.value_str == other.value_str and self.suit == other.suit def __repr__(self): return f'Card(\'{self.value_str}{self.suit}\')' def __str__(self): return f'{self.value_str}{self.suit}' def is_ace(self): return self.value_str == 'A' def is_black(self): return self.colour == 'B' def is_king(self): return self.value_str == 'K' def is_red(self): return self.colour == 'R' def construct_n_of_a_kind(cards): # Early bail if we don't have enough cards. if len(cards) < 2: return None # Ensure that all of the cards have the same value and are not an Ace. value = None for card in cards: if card.is_ace(): return None elif value is None: value = card.value elif card.value != value: return None # Return the cards as is. return list(cards) def construct_run(cards): # Early bail if we don't have enough cards. if len(cards) < 3: return None # Partition the cards into Aces and non-Aces. non_aces = [] aces_by_colour = {'B': [], 'R': []} for card in cards: if card.is_ace(): aces_by_colour[card.colour].append(card) else: non_aces.append(card) # Ensure we have enough non-Aces. if len(non_aces) < 2: return None # Sort the non-Aces by value. non_aces.sort(key=lambda card: card.value) # Attempt to construct a valid run from the avaialble cards. prev = non_aces.pop(0) run = [prev] while non_aces: top = non_aces[0] # Check for a normal valid transition. if prev.value + 1 == top.value and prev.colour == top.inv_colour: run.append(non_aces.pop(0)) # Consume the current card in the run. prev = top else: # Check if we can do an Ace insertion. aces = aces_by_colour[prev.inv_colour] if aces and not prev.is_king(): # Can't go higher than a King for Ace insertion. ace = aces.pop(0) # Consume the next Ace. run.append(ace) prev = Card((prev.value + 1, ace.suit)) else: # We did not find a valid transition. return None # If we have any aces left over, we do not have a valid run. if aces_by_colour['B'] or aces_by_colour['R']: return None return run def score_n_of_a_kind(cards): return cards[0].value * math.factorial(len(cards)) def score_orphans(cards): return sum(map(lambda card: card.orphan_value, cards)) def score_run(cards): return sum(range(cards[0].value, cards[-1].value + 1)) def comp10001go_valid_groups(group_strings): # Convert the card strings to Card objects. card_groups = [list(map(Card, card_strings)) for card_strings in group_strings] # Attempt to shape each of the groups of cards into the three allowed shapes. for cards in card_groups: if construct_n_of_a_kind(cards) is not None: pass elif construct_run(cards) is not None: pass elif len(cards) == 1: pass else: return False # If all groups of cards were one of the three allowed shapes, we're good. return True # ------------------------------------------------------------------------------ # Part 3 - Play and Group! # Sample solution 1 from math import factorial # index of value of a card VALUE = 0 # index of suit of a card SUIT = 1 # value of Ace ACE = 'A' # dictionary of scores of individual cards card_score = { '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9, '0': 10, 'J': 11, 'Q': 12, 'K': 13, ACE: 20, } # suits which are red RED_SUITS = 'HD' # suits which are black BLACK_SUITS = 'SC' # card colours RED = 1 BLACK = 2 # minimum no. of cards in an n-of-a-kind set MIN_CARDS_NKIND = 2 # minimum no. of non-Ace cards in a run MIN_NONACE_RUN = 2 # minimum no. cards in a run MIN_RUN = 3 def is_ace(card): """Boolean evaluation of whether `card` is an Ace""" return card[VALUE] == ACE def get_score(card): """return the score of `card`, based on its value""" return card_score[card[VALUE]] def get_colour(card): """Return the colour of `card` (`RED` or `BLACK`)""" if card[SUIT] in RED_SUITS: return RED else: return BLACK def comp10001go_score_group(cards): """Validate/score a group of cards (order unimportant), supplied as a list of cards (each a string); return the positive score of the group if valid, and negative score otherwise. Note, assumes that all cards are valid, and unique.""" # construct sorted list of values of cards (ignore suit for now) values = sorted([get_score(card) for card in cards]) # CASE 1: N-of-a-kind if all cards of same value, at least # `MIN_CARDS_NKIND` cards in total, and not Aces if (len(set(values)) == 1 and len(cards) >= MIN_CARDS_NKIND and not is_ace(cards[0])): return factorial(len(cards)) * card_score[cards[0][VALUE]] # construct sorted list of non-Ace cards nonace_cards = sorted([card for card in cards if not is_ace(card)], key=lambda x: get_score(x)) # construct list of Ace cards ace_cards = list(set(cards) - set(nonace_cards)) # run must have at least `MIN_NONACE_RUN` non-Ace cards in it if len(nonace_cards) >= MIN_NONACE_RUN: is_run = True prev_val = prev_colour = None score = 0 # iterate through cards to make sure they form a run for card in nonace_cards: # CASE 1: for the first card in `nonace_cards`, nothing to # check for if prev_val is None: score = prev_val = get_score(card) prev_colour = get_colour(card) # CASE 2: adjacent to previous card in value elif get_score(card) - prev_val == 1: # CASE 2.1: alternating colour, meaning continuation of run if get_colour(card) != prev_colour: prev_val = get_score(card) prev_colour = get_colour(card) score += prev_val # CASE 2.2: not alternating colour, meaning invalid run else: is_run = False break # CASE 3: repeat value, meaning no possibility of valid run elif get_score(card) == prev_val: is_run = False break # CASE 4: gap in values, in which case check to see if can be # filled with Ace(s) else: gap = get_score(card) - prev_val - 1 gap_filled = False # continue until gap filled while is_run and gap and len(ace_cards) >= gap: gap_filled = False # search for an Ace of appropriate colour, and remove # from list of Aces if found (note that it doesn't matter # which Ace is used if multiple Aces of same colour) for i, ace in enumerate(ace_cards): if get_colour(ace) != prev_colour: ace_cards.pop(i) prev_val += 1 prev_colour = get_colour(ace) score += prev_val gap -= 1 gap_filled = True break if not gap_filled: is_run = False if is_run and gap_filled and get_colour(card) != prev_colour: prev_val = get_score(card) prev_colour = get_colour(card) score += prev_val else: is_run = False if is_run and len(cards) >= MIN_RUN and not ace_cards: return score return -sum(values) def comp10001go_valid_groups(groups): for cards in groups: if not cards or (len(cards) > 1 and comp10001go_score_group(cards) < 0): return False return True def comp10001go_score_groups(groups): score = 0 for group in groups: score += comp10001go_score_group(group) return score def comp10001go_randplay(discard_history, player_no, hand): from random import shuffle shuffle(hand) # for first turn, select lowest card return hand[0] def comp10001go_play(discard_history, player_no, hand): # for first turn, select lowest card if not discard_history: return sorted(hand, key=lambda x: get_score(x))[0] # for subseuquent rounds, select card which maximises optimal score else: return sorted(hand, key=lambda x: get_score(x))[0] def comp10001go_group(discard_history, player_no): # construct list of discards from `discard_history` discards = [] for turn in discard_history: discards.append(turn[player_no]) return [[card] for card in discards] # Sample solution 2 SUIT_TO_COLOUR = dict(zip('HDCS', 'RRBB')) VALUE_STRING_TO_VALUE = dict(zip('A234567890JQK', range(1, 14))) VALUE_TO_VALUE_STRING = {v: k for k, v in VALUE_STRING_TO_VALUE.items()} class Card: def __init__(self, card_string): if isinstance(card_string, tuple): card_string = VALUE_TO_VALUE_STRING[card_string[0]] + card_string[1] self.value_str = card_string[0] self.value = VALUE_STRING_TO_VALUE[self.value_str] self.suit = card_string[1] self.colour = SUIT_TO_COLOUR[self.suit] self.inv_colour = 'R' if self.colour == 'B' else 'B' self.orphan_value = -20 if self.is_ace() else -self.value def __eq__(self, other): return self.value_str == other.value_str and self.suit == other.suit def __repr__(self): return f'Card(\'{self.value_str}{self.suit}\')' def __str__(self): return f'{self.value_str}{self.suit}' def is_ace(self): return self.value_str == 'A' def is_black(self): return self.colour == 'B' def is_king(self): return self.value_str == 'K' def is_red(self): return self.colour == 'R' def comp10001go_play(discard_history, player_no, hand): # Convert the card strings to Card objects. discard_history = [list(map(Card, card_strings)) for card_strings in discard_history] hand = list(map(Card, hand)) # Greedily discard the smallest valued card in my hand. hand.sort(key=lambda card: card.orphan_value) return str(hand[0]) def comp10001go_group(discard_history, player_no): return [[discards[player_no]] for discards in discard_history] # ------------------------------------------------------------------------------ # Part 4 - Optimal grouping # Sample solution 1 from math import factorial # index of value of a card VALUE = 0 # index of suit of a card SUIT = 1 # value of Ace ACE = 'A' # dictionary of scores of individual cards card_score = { '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9, '0': 10, 'J': 11, 'Q': 12, 'K': 13, ACE: 20, } # suits which are red RED_SUITS = 'HD' # suits which are black BLACK_SUITS = 'SC' # card colours RED = 1 BLACK = 2 # minimum no. of cards in an n-of-a-kind set MIN_CARDS_NKIND = 2 # minimum no. of non-Ace cards in a run MIN_NONACE_RUN = 2 # minimum no. cards in a run MIN_RUN = 3 def is_ace(card): """Boolean evaluation of whether `card` is an Ace""" return card[VALUE] == ACE def get_score(card): """return the score of `card`, based on its value""" return card_score[card[VALUE]] def get_colour(card): """Return the colour of `card` (`RED` or `BLACK`)""" if card[SUIT] in RED_SUITS: return RED else: return BLACK def comp10001go_score_group(cards): """Validate/score a group of cards (order unimportant), supplied as a list of cards (each a string); return the positive score of the group if valid, and negative score otherwise. Note, assumes that all cards are valid, and unique.""" # construct sorted list of values of cards (ignore suit for now) values = sorted([get_score(card) for card in cards]) # CASE 1: N-of-a-kind if all cards of same value, at least # `MIN_CARDS_NKIND` cards in total, and not Aces if (len(set(values)) == 1 and len(cards) >= MIN_CARDS_NKIND and not is_ace(cards[0])): return factorial(len(cards)) * card_score[cards[0][VALUE]] # construct sorted list of non-Ace cards nonace_cards = sorted([card for card in cards if not is_ace(card)], key=lambda x: get_score(x)) # construct list of Ace cards ace_cards = list(set(cards) - set(nonace_cards)) # run must have at least `MIN_NONACE_RUN` non-Ace cards in it if len(nonace_cards) >= MIN_NONACE_RUN: is_run = True prev_val = prev_colour = None score = 0 # iterate through cards to make sure they form a run for card in nonace_cards: # CASE 1: for the first card in `nonace_cards`, nothing to # check for if prev_val is None: score = prev_val = get_score(card) prev_colour = get_colour(card) # CASE 2: adjacent to previous card in value elif get_score(card) - prev_val == 1: # CASE 2.1: alternating colour, meaning continuation of run if get_colour(card) != prev_colour: prev_val = get_score(card) prev_colour = get_colour(card) score += prev_val # CASE 2.2: not alternating colour, meaning invalid run else: is_run = False break # CASE 3: repeat value, meaning no possibility of valid run elif get_score(card) == prev_val: is_run = False break # CASE 4: gap in values, in which case check to see if can be # filled with Ace(s) else: gap = get_score(card) - prev_val - 1 gap_filled = False # continue until gap filled while is_run and gap and len(ace_cards) >= gap: gap_filled = False # search for an Ace of appropriate colour, and remove # from list of Aces if found (note that it doesn't matter # which Ace is used if multiple Aces of same colour) for i, ace in enumerate(ace_cards): if get_colour(ace) != prev_colour: ace_cards.pop(i) prev_val += 1 prev_colour = get_colour(ace) score += prev_val gap -= 1 gap_filled = True break if not gap_filled: is_run = False if is_run and gap_filled and get_colour(card) != prev_colour: prev_val = get_score(card) prev_colour = get_colour(card) score += prev_val else: is_run = False if is_run and len(cards) >= MIN_RUN and not ace_cards: return score return -sum(values) def comp10001go_valid_groups(groups): for cards in groups: if not cards or (len(cards) > 1 and comp10001go_score_group(cards) < 0): return False return True def comp10001go_score_groups(groups): score = 0 for group in groups: score += comp10001go_score_group(group) return score def comp10001go_randplay(discard_history, player_no, hand): from random import shuffle shuffle(hand) # for first turn, select lowest card return hand[0] def comp10001go_partition(cards): # BASE CASE 1: no cards, so no grouping to make if len(cards) == 0: return [] # BASE CASE 2: single card, so make a singleton group if len(cards) == 1: return [[cards]] # RECURSIVE CASE out = [] first = cards[0] for sub_partition in comp10001go_partition(cards[1:]): # insert `first` in each of the subpartition's groups for n, subpart in enumerate(sub_partition): out.append(sub_partition[:n] + [[first] + subpart] + sub_partition[n+1:]) # put `first` in its own subpart out.append([[first]] + sub_partition) return out def comp10001go_best_partitions(cards): # generate and score all valid card groups from `cards` valid_groups = [(part, comp10001go_score_groups(part)) for part in comp10001go_partition(cards) if comp10001go_valid_groups(part)] if valid_groups: first_group, best_score = valid_groups[0] best_groups = [first_group] for group, score in valid_groups[1:]: if score > best_score: best_groups = [group] best_score = score elif score == best_score: best_groups.append(group) return best_groups # Sample solution 2 import itertools import math SUIT_TO_COLOUR = dict(zip('HDCS', 'RRBB')) VALUE_STRING_TO_VALUE = dict(zip('A234567890JQK', range(1, 14))) VALUE_TO_VALUE_STRING = {v: k for k, v in VALUE_STRING_TO_VALUE.items()} class Card: def __init__(self, card_string): if isinstance(card_string, Card): card_string = str(card_string) elif isinstance(card_string, tuple): card_string = VALUE_TO_VALUE_STRING[card_string[0]] + card_string[1] self.value_str = card_string[0] self.value = VALUE_STRING_TO_VALUE[self.value_str] self.suit = card_string[1] self.colour = SUIT_TO_COLOUR[self.suit] self.inv_colour = 'R' if self.colour == 'B' else 'B' self.orphan_value = -20 if self.is_ace() else -self.value def __hash__(self): return hash(str(self)) def __eq__(self, other): return self.value_str == other.value_str and self.suit == other.suit def __repr__(self): return f'Card(\'{self.value_str}{self.suit}\')' def __str__(self): return f'{self.value_str}{self.suit}' def is_ace(self): return self.value_str == 'A' def is_black(self): return self.colour == 'B' def is_king(self): return self.value_str == 'K' def is_red(self): return self.colour == 'R' def construct_n_of_a_kind(cards): # Early bail if we don't have enough cards. if len(cards) < 2: return None # Ensure that all of the cards have the same value and are not an Ace. value = None for card in cards: if card.is_ace(): return None elif value is None: value = card.value elif card.value != value: return None # Return the cards as is. return list(cards) def construct_run(cards): # Early bail if we don't have enough cards. if len(cards) < 3: return None # Partition the cards into Aces and non-Aces. non_aces = [] aces_by_colour = {'B': [], 'R': []} for card in cards: if card.is_ace(): aces_by_colour[card.colour].append(card) else: non_aces.append(card) # Ensure we have enough non-Aces. if len(non_aces) < 2: return None # Sort the non-Aces by value. non_aces.sort(key=lambda card: card.value, reverse=True) # Attempt to construct a valid run from the avaialble cards. prev = non_aces.pop() run = [prev] while non_aces: top = non_aces[-1] # Check for a normal valid transition. if prev.value + 1 == top.value and prev.colour == top.inv_colour: run.append(non_aces.pop()) # Consume the current card in the run. prev = top else: # Check if we can do an Ace insertion. aces = aces_by_colour[prev.inv_colour] if aces and not prev.is_king(): # Can't go higher than a King for Ace insertion. ace = aces.pop() # Consume the next ace. run.append(ace) prev = Card((prev.value + 1, ace.suit)) else: # We did not find a valid transition. return None # If we have any aces left over, we do not have a valid run. if aces_by_colour['B'] or aces_by_colour['R']: return None return run def score_n_of_a_kind(cards): return cards[0].value * math.factorial(len(cards)) def score_orphans(cards): return sum(map(lambda card: card.orphan_value, cards)) def score_run(cards): return sum(range(cards[0].value, cards[-1].value + 1)) def score_group(cards): if len(cards) == 1: return score_orphans(cards) grouped_cards = construct_n_of_a_kind(cards) if grouped_cards is not None: return score_n_of_a_kind(grouped_cards) grouped_cards = construct_run(cards) if grouped_cards is not None: return score_run(grouped_cards) assert False, 'Should not be possible' def is_valid_group(cards): if len(cards) == 1: return True elif construct_n_of_a_kind(cards) is not None: return True elif construct_run(cards) is not None: return True else: return False def _generate_partitions(cards, groups): if len(cards) == 0: yield frozenset(groups) return for k in range(1, len(cards) + 1): for combination in map(frozenset, itertools.combinations(cards, k)): if not is_valid_group(combination): continue remaining_cards = cards - combination groups.append(combination) yield from _generate_partitions(remaining_cards, groups) groups.pop() def generate_partitions(cards): seen = set() for partition in _generate_partitions(frozenset(cards), []): if partition in seen: continue seen.add(partition) yield list(map(list, partition)) def comp10001go_best_partitions(card_strings): cards = set(map(Card, card_strings)) max_score = float('-inf') max_partitions = [] for partition in generate_partitions(cards): score = sum(map(score_group, partition)) if score > max_score: max_score = score max_partitions = [partition] elif score == max_score: max_partitions.append(partition) return [[list(map(str, cards)) for cards in partition] for partition in max_partitions]