>>>Hello! We are writing this program in PYTHON, thank you for your help!<<<

Nim is a game of strategy played between two players. The players take turns in removing one or more counters from a given heap of counters among several distinct heaps. In normal play the player who takes the last counter wins. The more common variation (known as misere play) of Nim where the player who takes the last counter loses.

The best strategy for this game was given by C. L. Bouton in 1901. It is defined in terms of the nim-sum. Supposing there are three heaps - A, B, and C having a, b, and c counters. The nim-sum is given by nim-sum = a b c where is the xor operator.

The first player who starts with a non-zero nim-sum will always win the game, if he knows the strategy. On the other hand, if the player starts with a zero nim-sum, he will lose if his opponent knows the strategy.

Let us assume that you are starting with a non-zero nim-sum X. Then compute the individual nim-sums with each heap as follows. a X = p b X = q c X = r Find the first heap where the individual nim-sum is smaller than the heap size. Let us say that (q < b), then subtract or take from the second heap (b - q) counters, leaving q counters behind. If you now compute the nim-sum of all the heaps it will be zero. In your subsequent moves always remove counters such that the starting nim-sum is zero for your opponent.

Let us say the three heaps A, B, and C have 8, 13 and 5 counters. The nim-sum X is X = 8 13 5 = 0 You will lose this game. In another game, you have three heaps of 9, 7, and 12 counters. The nim-sum X is X = 9 7 12 = 2 Now compute the nim-sum with each individual heap p = 9 2 = 11 q = 7 2 = 5 r = 12 2 = 14 Your winning move is to remove (7 - 5 = ) 2 counters from heap B, leaving 5 counters in that heap.

The end game will depend whether it is normal play or the misere game. In normal play you want to end up with an even number of heaps of size 1. In the misere game you want to end up with an odd number of heaps of size 1.

The program that you will write will be called Nim.py. You will read a file called nim.txt. The first line in nim.txt is the number of data sets n that you will have. This will be followed by n lines of data. Each line of data of will have 2 or more numbers. These numbers represent the number of counters in each heap. The numbers on a given line will be separated by one or more spaces. If the nim-sum of a given line of data is zero your program will output Lose Game Otherwise, your program will output the first heap from which you can remove the number of counters according to the strategy outlined above. Remove 2 counters from Heap 2

If this was the data file (nim.txt) that was given to you:

4 3 4 5 8 13 5 123 675 296 864 917 532 9 7 4 12 

Then your output will be as follows:

Remove 2 counters from Heap 1 Lose Game Remove 239 counters from Heap 3 Remove 6 counters from Heap 2 

The file that you will be turning in will be called Nim.py. You must follow the template of the program given. You may NOT change the names of the functions or the names of the input parameters. This is the way we will test your program. You may write as many helper functions that you need.

# File: Nim.py # Description: # Student's Name: # Student's UT EID: # Partner's Name: # Partner's UT EID: # Course Name: CS 313E # Unique Number: # Date Created: # Date Last Modified: # Input: heaps is a list of integers giving the count in each heap # Output: function returns a single integer which is the nim-sum def nim_sum (heaps): return 0 # placeholder for the actual return statement # Input: heaps is a list of integers giving the count in each heap # nim_sum is an integer # Output: function returns two integers. The first integer is number # of counters that has to be removed. The second integer is # the number of the heap from which the counters are removed. # If the nim_sum is 0, then return 0, 0 def find_heap (heaps, nim_sum): return 0, 0 # placeholder for the actual return statement def main(): # read input from input file nim.txt # call function nim_sum() with inputs as given # call function find_heap() with inputs as given # print the results # The line above main is for grading purposes only. # DO NOT REMOVE THE LINE ABOVE MAIN if __name__ == "__main__": main()