Instantly share code, notes, and snippets.

boyter/puzzle.py Last active Apr 9, 2017

Friday Quiz Solution
 # Three people are playing the following betting game. # Every five minutes, a turn takes place in which a random player rests and the other two bet # against one another with all of their money. # The player with the smaller amount of money always wins, # doubling his money by taking it from the loser. # For example, if the initial amounts of money are 1, 4, and 6, # then the result of the first turn can be either # 2,3,6 (1 wins against 4); # 1,8,2 (4 wins against 6); or # 2,4,5 (1 wins against 6). # If two players with the same amount of money play against one another, # the game immediately ends for all three players. # Find initial amounts of money for the three players, where none of the three has more than 255, # and in such a way that the game cannot end in less than one hour. (So at least 12 turns) # In the example above (1,4,6), there is no way to end the game in less than 15 minutes. # All numbers must be positive integers. DESIRED_TURNS = 11 MAX_MONEY = 256 # Calculate all the possible sequences for who misses out for each turn def calc_events(current=[], turn=0): if turn == DESIRED_TURNS: return [current] one = list(current) one.append(0) two = list(current) two.append(1) three = list(current) three.append(2) turn += 1 path1 = calc_events(current=one, turn=turn) path2 = calc_events(current=two, turn=turn) path3 = calc_events(current=three, turn=turn) return path1 + path2 + path3 def play_games(p1, p2, p3, events): for event in events: c1 = p1 c2 = p2 c3 = p3 for x in event: if x == 0: if c2 == c3: return [False, p1, p2, p3] if c2 > c3: c2 = c2 - c3 c3 = c3 + c3 else: c3 = c3 - c2 c2 = c2 + c2 if x == 1: if c1 == c3: return [False, p1, p2, p3] if c1 > c3: c1 = c1 - c3 c3 = c3 + c3 else: c3 = c3 - c1 c1 = c1 + c1 if x == 2: if c1 == c2: return [False, p1, p2, p3] if c1 > c2: c1 = c1 - c2 c2 = c2 + c2 else: c2 = c2 - c1 c1 = c1 + c1 return [True, p1, p2, p3] if __name__ == '__main__': possible_events = calc_events() combinations = [] for x in xrange(1, MAX_MONEY): for y in xrange(x, MAX_MONEY): for z in [b for b in xrange(y, MAX_MONEY) if b != x and b != y]: combinations.append([x, y, z]) results = [play_games(x[0], x[1], x[2], possible_events) for x in combinations] print [x for x in results if x[0]]
Owner Author

boyter commented Mar 27, 2017

 Using PyPy ``````[[175, 199, 223], [197, 205, 213], [209, 217, 225]] real 10m2.554s user 9m13.108s sys 0m7.010s ``````
Owner Author

boyter commented Mar 28, 2017

 Made more pythonic and improved performance to boot ``````[[True, 175, 199, 223], [True, 197, 205, 213], [True, 209, 217, 225]] real 7m42.951s user 7m36.011s sys 0m1.465s ``````