Question

Coin taking game

This game is played between 2 players, player 1 and player 2. There are two piles of coins. The values of a coin can be any integer. Both players know the values of all coins in both piles. Player 1 makes the first move, and play alternates between the players. A move consists of taking a coin from the top of either of the piles (either player can take from either pile). The game ends when both piles are empty. A player’s score is the sum of the values of all the coins they took during the game. The player with the higher score wins.

1 Winning the coin taking game

In this task you will write a function best_score(pile1, pile2) in python to determine optimal play for the coin taking game. It will determine the highest score which can be achieved by player 1, assuming that both players play optimally.

1.1 Input

Two lists, pile1 and pile2. These lists contain integers which represent the values of the coins in the game. The numbers in pile1 are the values of coins in the first pile, where pile1[I] is the value of the coin with i coins beneath it in the pile. pile2 represents the coins in the second pile in the same way. The piles may be empty.

1.2 Output

A tuple with two elements. The first is a single number which represents the highest score which player 1 can achieve. The second represents the choices made by both players during the game (assuming optimal play). The choices are represented by a list containing only the numbers 1 and 2, where a 1 indicates that the player took the top coin from pile1 on their turn, and 2 indicates that the player took the top coin from pile2 on their turn.

If multiple sequences of choices are optimal, any of these sequences is acceptable.

Answer 1

Screenshots of the code:

Output:

Code to copy:

def best_scoreHelper(pile1, pile2, turn=1):
if len(pile1) == 0 and len(pile2) == 0:
return (0, 0)
  
if len(pile1) == 0:
# when one pile is empty, we have no option but
# to take the card.
if turn == 1:
b = best_scoreHelper(pile1, pile2[1:], 2)
return (pile2[0] + b[0], b[1])
if turn == 2:
b = best_scoreHelper(pile1, pile2[1:], 1)
return (b[0], pile2[0] + b[1])
if len(pile2) == 0:
if turn == 1:
b = best_scoreHelper(pile1[1:], pile2, 2)
return (pile1[0] + b[0], b[1])
if turn == 2:
b = best_scoreHelper(pile1[1:], pile2, 1)
return (b[0], pile1[0] + b[1])
# else, We have both piles available now.
if turn == 1:
x1 = best_scoreHelper(pile1[1:], pile2, 2)
x1 = (x1[0] + pile1[0], x1[1])
x2 = best_scoreHelper(pile1, pile2[1:], 2)
x2 = (x2[0] + pile2[0], x2[1])
  
if x1[0] > x2[0]:
return x1
else:
return x2
else:
x1 = best_scoreHelper(pile1[1:], pile2, 1)
x1 = (x1[0], x1[1] + pile1[0])
x2 = best_scoreHelper(pile1, pile2[1:], 1)
x2 = (x2[0], x2[1] + pile2[0])
  
if x1[1] > x2[1]:
return x1
else:
return x2
def best_score(pile1, pile2):
return best_scoreHelper(pile1, pile2, 1)[0] # take score for first player
print(best_score([5, 8, 2, 4, 1, 10, 2], [6, 2, 4, 5, 6, 9, 8]))