Simulating problems about the game Set, from the Riddler

set.py

import random
from itertools import combinations

# I'm taking a simulation approach to solving these Riddler problems about the game Set
# https://fivethirtyeight.com/features/how-many-sets-of-cards-can-you-find/
# The answers might not be exactly right, since I'm just doing brute force calculations.
# But hell, it's fun!

###############
## CONSTANTS ##
###############

PROP_NUMBER = 2
PROP_SHAPE = 3
PROP_COLOR = 5
PROP_SHADING = 7

PROPERTIES = [PROP_NUMBER, PROP_SHAPE, PROP_COLOR, PROP_SHADING]
RANGE_PROPERTIES = 3  # In set, properties can have three different values 

BOARD_SIZE = 12


#############
## HELPERS ##
#############

def get_property(card, prop):
	for i in range(RANGE_PROPERTIES):
		if card%(prop ** (i+1)) != 0:
			return i
	print('Unexpected value in card {}', card)
	raise

def set_property(card, prop, val):
	return card * prop ** val

def is_match(cards):
	for p in PROPERTIES:
		prop_set = set()
		for c in cards:
			prop_set.add(get_property(c, p))
		if len(prop_set) != 1 and len(prop_set) != RANGE_PROPERTIES:
			return False
	return True

def match_count(board, group_size=RANGE_PROPERTIES):
	counter = 0
	for group in combinations(board, group_size):
		counter += is_match(group)
	return counter

def build_deck(properties, deck={1}):
	if len(properties) == 0:
		return deck

	new_deck = deck.copy()
	properties = properties.copy()
	prop = properties.pop()

	for card in deck:
		for p in range(RANGE_PROPERTIES):
			new_deck.add(set_property(card, prop, p))
	return build_deck(properties, new_deck)


################
## QUESTION 1 ##
################

def question_one():
	deck = build_deck(PROPERTIES)
	board_size = BOARD_SIZE
	simulation_run = 1000  #I had to increase this to about 10k to get the answer

	while True:
		print('Testing board size {}...'.format(board_size))
		always_matches = True

		for i in range(simulation_run):
			board = random.sample(deck, board_size)
			if match_count(board) == 0:
				always_matches = False
				break;

		if always_matches == False:
			board_size += 1
		else:
			print("Minimum value without match count: {}".format(board_size - 1))
			return


################
## QUESTION 2 ##
################

def question_two():
	deck = build_deck(PROPERTIES)
	board_size = BOARD_SIZE
	simulation_run = 50000

	max_matches = 0
	for i in range(simulation_run):
		board = random.sample(deck, board_size)
		max_matches = max(max_matches, match_count(board))
	
	print("Maximum matches found: {}".format(max_matches))


################
## QUESTION 3 ##
################

# Build the deck of 81 cards
def question_three():
	deck = build_deck(PROPERTIES)
	simulation_run = 1000

	contains_set_count = 0
	for i in range(simulation_run):
		# Choose a random 12 of those to be the board
		board = random.sample(deck, BOARD_SIZE)
		contains_set_count += (match_count(board) >= 1)

	print("Probability of at least one set: {}".format(float(contains_set_count)/float(simulation_run)))

# question_one()
# question_two()
# question_three()