Skip to content

Instantly share code, notes, and snippets.

@ijkilchenko
Last active May 11, 2018 04:56
Show Gist options
  • Save ijkilchenko/f7fb015fa1d6e3f1af82f5c12089b6db to your computer and use it in GitHub Desktop.
Save ijkilchenko/f7fb015fa1d6e3f1af82f5c12089b6db to your computer and use it in GitHub Desktop.
import random
from math import sqrt, floor
"""
Guessing game. When playing, the game picks a random value from i to j
and each time a guess g is made, g is added to the previous running cost
of playing this game.
"""
cache = {}
class Game:
def __init__(self, i, j):
self.i = i
self.j = j
"""
The expected cost of playing this game, calculated using a simulation.
"""
def sim_cost(self, max_games=5000):
return sum([self._play(strat=Game._random_guess) for _ in range(0, max_games)])/max_games
"""
The expected cost of playing this game when each new guess is based on
guessing the value between i and j such that the sum of values to the left
of the guess is the same as the sum of values to the right of the guess.
"""
def best_cost(self, max_games=5000):
return sum([self._play(strat=Game._best_guess) for _ in range(0, max_games)])/max_games
"""
The expected cost of playing the game, calculated using dynamic programming.
"""
def true_guess(self, max_games=5000):
return sum([self._play(strat=Game._true_guess) for _ in range(0, max_games)])/max_games
def _true_guess(i, j):
if (i, j) in cache:
return cache[(i, j)]
elif i == j:
return i
elif i > j:
return 0
min_cost = j
min_s = j
n = j - (i - 1)
for s in range(i, j):
cost = s/n + (s-1-(i-1))/n*Game._true_guess(i, s-1) + (j-s)/n*Game._true_guess(s+1, j)
if cost < min_cost:
min_s = s
min_cost = cost
cache[(i, j)] = min_s
return cache[(i, j)]
def _random_guess(i, j):
return random.randint(i, j)
def _best_guess(i, j):
return floor(sqrt((j**2+j+(i**2-i))/2))
def _play(self, strat):
k = random.randint(self.i, self.j)
low = self.i
high = self.j
guess = strat(low, high)
cost = guess
while guess != k:
if guess < k:
low = guess + 1
else:
high = guess - 1
guess = strat(low, high)
cost += guess
return cost
if __name__ == '__main__':
game = Game(1, 100)
print(game.sim_cost())
print(game.best_cost())
print(game.true_guess())
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment