- 489,783 hits
Make the frequent cases fast and the rare case correct
The Game of Euclid – Python way to find out who wins !
June 11, 2011Posted by on
In 1969, Cole and Davie developed a two-player game based on the Euclidean algorithm, called The Game of Euclid,which has an optimal strategy.The players begin with two piles of a and b stones. The players take turns removing m multiples of the smaller pile from the larger. Thus, if the two piles consist of x and y stones, where x is larger than y, the next player can reduce the larger pile from x stones to x − my stones, as long as the latter is a non negative integer. The winner is the first player to reduce one pile to zero stones.Wikipedia
Two players,A and B play, starting with two natural numbers(stones), the first player A, subtracts any positive multiple of the lesser of the two numbers from the greater of the two numbers, provided that the resulting number must be non negative. Then the second player B, does the same with the two resulting numbers, then A, etc., alternately, until one player is able to subtract a multiple of the lesser number from the greater to reach 0, and thereby wins. For example, the players may start with (25,7):
One of the readers has rectified an issue with my previous code. I am displaying the code given by him
#Author : Rohit Saxena def egame(x,y): if x < y: return egame(y,x) elif x % y == 0: return True elif x - y < y: return not egame(y,x-y) else: return True x = int(raw_input("Enter number of stones for pile 1 : ")) y = int(raw_input("Enter number of stones for pile 2 : ")) print "Player %s wins" % "A" if egame(x,y) else "B"
devgru@ubuntu:~$ python egame.py
Enter number of stones for pile 1 : 25
Enter number of stones for pile 2 : 7
Player A wins
Thanks for Reading !