jhwaters/riddler_classic_2018_04_13.py Secret

## riddler_classic_2018_04_13.py
from fractions import Fraction

class ShutTheBox:
    # possible moves for each sum
    moves = {i: tuple() for i in range(1,13)}
    for a in range(1,10):
        moves[a] += ((a,),)
        if a < 9:
            for b in range(a+1,10):
                if a+b <= 12:
                    moves[a+b] += ((a,b),)
                if b < 9:
                    for c in range(b+1,10):
                        if a+b+c <= 12:
                            moves[a+b+c] += ((a,b,c),)
                        if c < 9:
                            for d in range(c+1,10):
                                if a+b+c+d <= 12:
                                    moves[a+b+c+d] += ((a,b,c,d),)

    # count number of ways each sum can be obtained
    roll2 = {i: 0 for i in range(2,13)}
    for a in range(1,7):
        for b in range(1,7):
            roll2[a+b] += 1

    known_states = {}  # stores known win probabilities

    def __init__(self, state=None):
        # state: dict with keys 1-9; value is True if the tile is shut, False if not
        self.state = {i: False for i in range(1,10)} if state is None else state

    def __str__(self):
        return ''.join(['_' if self.state[i] else str(i) for i in range(1,10)])

    def evaluate_move(self, move):
        newstate = {}
        for i in range(1,10):
            if self.state[i]:
                if i in move:  # not a valid move (loss)
                    return 0
                else:
                    newstate[i] = True
            else:
                newstate[i] = bool(i in move)
        if False in newstate.values():  # game is unfinished
            return ShutTheBox(state=newstate).win_chance()
        else:  # win
            return 1

    def best_move(self, roll):
        return max([self.evaluate_move(m) for m in self.moves[roll]])

    def win_chance_1d(self):  # rolling 1 dice
        return Fraction(sum([self.best_move(roll) for roll in range(1,7)]), 6)

    def win_chance_2d(self):  # rolling 2 die
        return Fraction(sum([self.best_move(roll) * self.roll2[roll] for roll in range(2,13)]), 36)

    def win_chance(self):
        s = str(self)
        if s in ShutTheBox.known_states:  # use already-calculated win probability
            return ShutTheBox.known_states[s]
        else:  # calculate win probability and store
            can_roll_1 = self.state[7] and self.state[8] and self.state[9]
            w = max(self.win_chance_1d(), self.win_chance_2d()) if can_roll_1 else self.win_chance_2d()
            ShutTheBox.known_states[s] = w
            return w

if __name__ == '__main__':
    game = ShutTheBox()
    w = game.win_chance()
    print("odds of winning: {}/{} = {}".format(w.numerator, w.denominator, float(w)))
    if input("display odds for all game states? (yes/no) ").lower() in ['yes', 'y']:
        pairs = [(ShutTheBox.known_states[state], state) for state in ShutTheBox.known_states]
        for win_prob, state in sorted(pairs, reverse=True):
            print("{}: {}".format(state, float(win_prob)))
	from fractions import Fraction

	class ShutTheBox:
	# possible moves for each sum
	moves = {i: tuple() for i in range(1,13)}
	for a in range(1,10):
	moves[a] += ((a,),)
	if a < 9:
	for b in range(a+1,10):
	if a+b <= 12:
	moves[a+b] += ((a,b),)
	if b < 9:
	for c in range(b+1,10):
	if a+b+c <= 12:
	moves[a+b+c] += ((a,b,c),)
	if c < 9:
	for d in range(c+1,10):
	if a+b+c+d <= 12:
	moves[a+b+c+d] += ((a,b,c,d),)

	# count number of ways each sum can be obtained
	roll2 = {i: 0 for i in range(2,13)}
	for a in range(1,7):
	for b in range(1,7):
	roll2[a+b] += 1

	known_states = {} # stores known win probabilities

	def __init__(self, state=None):
	# state: dict with keys 1-9; value is True if the tile is shut, False if not
	self.state = {i: False for i in range(1,10)} if state is None else state

	def __str__(self):
	return ''.join(['_' if self.state[i] else str(i) for i in range(1,10)])

	def evaluate_move(self, move):
	newstate = {}
	for i in range(1,10):
	if self.state[i]:
	if i in move: # not a valid move (loss)
	return 0
	else:
	newstate[i] = True
	else:
	newstate[i] = bool(i in move)
	if False in newstate.values(): # game is unfinished
	return ShutTheBox(state=newstate).win_chance()
	else: # win
	return 1

	def best_move(self, roll):
	return max([self.evaluate_move(m) for m in self.moves[roll]])

	def win_chance_1d(self): # rolling 1 dice
	return Fraction(sum([self.best_move(roll) for roll in range(1,7)]), 6)

	def win_chance_2d(self): # rolling 2 die
	return Fraction(sum([self.best_move(roll) * self.roll2[roll] for roll in range(2,13)]), 36)

	def win_chance(self):
	s = str(self)
	if s in ShutTheBox.known_states: # use already-calculated win probability
	return ShutTheBox.known_states[s]
	else: # calculate win probability and store
	can_roll_1 = self.state[7] and self.state[8] and self.state[9]
	w = max(self.win_chance_1d(), self.win_chance_2d()) if can_roll_1 else self.win_chance_2d()
	ShutTheBox.known_states[s] = w
	return w

	if __name__ == '__main__':
	game = ShutTheBox()
	w = game.win_chance()
	print("odds of winning: {}/{} = {}".format(w.numerator, w.denominator, float(w)))
	if input("display odds for all game states? (yes/no) ").lower() in ['yes', 'y']:
	pairs = [(ShutTheBox.known_states[state], state) for state in ShutTheBox.known_states]
	for win_prob, state in sorted(pairs, reverse=True):
	print("{}: {}".format(state, float(win_prob)))