What is the coin in a line problem?
In the coin in a line problem, two players are given an even number of coins in a single row. The players take turns alternatively. For each turn, a player selects a coin from either the beginning or the end of the row. The player with the maximum total value wins. ​
So, the goal is to provide a strategy in which the player with the first move gets the maximum value coins in the end.
There is an even amount of coins (i.e., 1 to n ) and the two players take their turns alternatively.
If player1 picks the coin at position 1, then player2 (who is equally clever) will pick up a coin and leave player1 with the less valuable coin.
If player1 picks the coin at position n, then player2 (who is equally clever) will pick up a coin, and leave player1​ with the less valuable coin.
Combined Form
Max_Value(1,n) = Maximum {coin[1] + Minimum{Max_Value(3,n),
Max_Value(2,n-1)} , coin[n] +
Minimum{Max_Value(2,n-1),Max_Value(1,n-2)}};
Code
# Python Implementationdef Coin_in_a_line(arr, n):# Creating a table to store max value.Max_Value = [[0 for i in range(n)]for i in range(n)]# Fill the table using the above method.for k in range(n):for j in range(k, n):i = j - kx = 0if((i + 2) <= j):x = Max_Value[i + 2][j]y = 0if((i + 1) <= (j - 1)):y = Max_Value[i + 1][j - 1]z = 0if(i <= (j - 2)):z = Max_Value[i][j - 2]Max_Value[i][j] = max(arr[i] + min(x, y),arr[j] + min(y, z))return Max_Value[0][n - 1]# Sample codearr = [ 5, 16, 3, 7 ]print(Coin_in_a_line(arr, 4))
This problem can be solved most efficiently by dynamic programming. The main logic behind the code is explained best by the Max_Value array:
The row number specifies the starting position and the column number specifies the ending position within the coin line. We must pick a coin at either end of this range. So, Max_Value[i][j] would mean the range from i to j.
In the code, k is the interval or window. The base case is when k is 0 or i = j. This means that there is only one coin to choose. Hence, the diagonal of the array will be filled first:
Next, the interval is 1, meaning there are 2 choices to pick from, namely arr[i] or arr[j]. We must pick the maximum between these two. These values are filled out in the array:
Now, the interval is 2 or larger. There are a few possible scenarios we need to cover. At the start, we can pick either arr[i] (first) or arr[j] (last).
If we pick the first value, our opponent can choose either arr[i+1] or arr[j].
- If they pick
arr[i+1], our next choice will bearr[i+2]orarr[j]. But since we built up from the base case, we already have the max value for this inMax_Value[i+2][j]! We will store this inx. - If they pick
arr[j], our next choice will bearr[i+1]orarr[j-1]. This can be found inMax_Value[i+1][j-1]. We will store this iny.
So, for this scenario, what we have as our choice of moves is:
arr[i] + min(x, y)
If we pick the last value, our opponent can choose either arr[i] or arr[j-1].
- If they pick
arr[i], our next choice will bearr[i+1]orarr[j-1]. This can be found inMax_Value[i+1][j-1]. Like before, we will store this iny. - If they pick
arr[j-1], our next choice will bearr[i]orarr[j-2]. This can be found inMax_Value[i][j-2]. We will store this inz.
So, for this scenario, what we have as our choice of moves is:
arr[j] + min(y, z)
Lastly, we must take the maximum out of these two scenarios:
max(arr[i] + min(x, y), arr[j] + min(y, z))
This will help us find Max_Value[0][3], which is the answer!
Free Resources