ISourceCode

Make the frequent cases fast and the rare case correct

The Game of Euclid – Python way to find out who wins !

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):

25 7

11 7

4 7

4 3

1 3

1 0
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"

OUTPUT:

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 !

4 responses to “The Game of Euclid – Python way to find out who wins !

  1. Rohit Saxena June 15, 2011 at 9:05 pm

    Hey I guess you can write your code a little like this

    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"

    Please note that "Enter number of stones for player A : " is misleading.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: