Python Your goal is to complete the following: In this assignment\'s programming

Question

Python

Your goal is to complete the following:

In this assignment's programming component, you will determine the winners of two variations of the game NIM. Specifically, we will be playing n-Pile, a version of NIM where stones are removed from n piles. See the background materials above for reference The two variations of n-Pile we will be examining are: 1. Classic n-Pile : there are n piles and a player may remove any number of stones from any pile during their turn; Restricted n-Pile: a player may only remove a pre-specified num- ber of stones during their turn. You may have seen this represented as m1, m2,., mn)-NIM (and this can also be played on n piles) 4.1 Game Data Structures Your solutions must adhere to the following definitions for the data structures that you will use: 1. a board is a list of natural numbers where the number at index i represents the number of stones in pile. For example, if board = [0, 4, 3, 7] then board [O] would return 0 and show that pile zero is empty. Likewise board [1] would show that pile one has four stones in it. len (board) would show that there are four total piles: 2. moves is a tuple of natural numbers that represent legal amounts of stones that a player may take per turn. For example if moves was equal to (1, 3, 4), then each player may only take one stone, three stones, or four stones out of any pile. (Note that this is only applicable for restrictedPileWinner);

Explanation / Answer

#functions convert a binary array to a decimal number (big-endian form)
def binToDec(binary):
    output = 0
    for i in range(len(binary)):
        output += pow(2, i) * binary[i]
    return output

#XOR logic between two binary arrays (big-endian form)
def XOR(bin1, bin2):

    binOut = []

    for i in range(max(len(bin1), len(bin2))):

        if i == len(bin1):
            binOut.extend(bin2[i:])
            break

        elif i == len(bin2):
            binOut.extend(bin1[i:])
            break

        elif bin1[i] == bin2[i]:
            binOut.append(0)

        else:
            binOut.append(1)

    return binOut

#CODE HERE

import numpy as np

def nPileWinner(board):
    #Holds XOR binary list
    binX = []
    #tuple of moves
    final = ()
    for num in range(len(board)):
        #XOR between all of the piles in the board
        binX = XOR(binX, decToBin(board[num]))
    #If this is 0 then player two wins
    if binToDec(binX) == 0:
        return (2,())
    else:
        #Check for valid moves
        for num in range(len(board)):
            #Check to see XOR between the binX and what the current pile is
            current = XOR(binX, decToBin(board[num]))
            #Make current to be decimal number this is the number after stones are removed
            stones = binToDec(current)
            #If we are not adding stones to the pile
            if board[num] >= stones:
                #add the pile number and how many stones to remove to the final tuple
                final += ((num, (board[num] - stones)),)
            else:
                pass

        return (1, (final))

#Holds dictionary for grundy numbers
#0 will always be 0
D = {0:0}
def restrictedPileWinner(board, moves):
    #Holds what moves are in binary
    moveBin = []
    #Tuple to return
    final = ()
    #populate moveBin
    for move in moves:
        moveBin.append(decToBin(move))
    #Determines the XOR between all of the piles in the board
    binX = []
    #Create binX
    for num in range(len(board)):
        grun = decToBin(grundy(board[num], moves))
        binX = XOR(binX, grun)
    #If this is 0 then player two wins
    if binToDec(binX) == 0:
        return (2,())
    else:
        #Check for valid moves
        for num in range(len(board)):
            grun = decToBin(grundy(board[num], moves))
            decGrun = (grundy(board[num], moves))
            #Check to see XOR between the binX and what the current pile is
            current = XOR(binX, grun)
            #Make current to be decimal number
            stones = binToDec(current)
            #If we are not adding stones
            if decGrun >= stones:
                #Add the move to be returned
                final += ((num, decGrun - stones),)
            else:
                pass
        if final == ():
            return (2,())
        else:
            return (1, (final))
  

#Convert decimal to a binary array (big-endian)
def decToBin(decimal):
    output = []
    while (decimal > 0):
        if decimal % 2 == 1:
            output.append(1)
        else:
            output.append(0)
        if decimal == 1:
            break
        decimal = decimal//2
    return output

#Produces grundy number for game with pile amount and moves
def grundy(pile, moves):
    for i in range(1, pile + 1):
        #Hold the possibilities of numbers to be reached in this game
        poss = []
        #List all the possible numbers to be reached
        for m in moves:
            poss.append(i - m)
        #Holds the grundy numbers that the current number's descendants have
        desc = []
        #Check if any possibiliities are already in the dictionary, if not, add them
        for p in poss:
            if p in D.keys():
                desc.append(D[p])
            #Don't put negatives in the dictionary
            elif p < 0:
                pass
        #Set the current number in the dictionary to have min grundy number not appearing in its possibilities
        D[i] = mex(desc)
    return D.get(pile)

#Returns the minimum natural number not in the list
def mex(grundy):
    small = 0
    while small in grundy:
        small = small + 1
    return small

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.