> Solutions for tree coins in a line problem

This is a post for game theory problems. All solutions are written in Python.

I didn’t have to put a lot of details here. Comment below if you have any issue.

Keep in mind: the current state is generated by its sub states (further states).

> Coins in a line I

Problem: http://www.lintcode.com/en/problem/coins-in-a-line/

This problem start taking coins from the right side.

Solution:

class Solution:
    """
    @param n: an integer
    @return: a boolean which equals to True if the first player will win
    """
    def firstWillWin(self, n):
        dp = [False] * (n+1)

        for i in range(1, n+1):
            if not (dp[i-1] and dp[i-2]):
                dp[i] = True
        return dp[n]

dp[i] represents if the current player can win when i~n coins have been selected.

For not (dp[i-1] and dp[i-2]), dp[i] is True when and only when there is a False in dp[i]'s sub states dp[i-1] and dp[i-2]. Which means, there is a possible lose for his opponent. dp[i]'s sub states represent the coins his opponent can gain. We want this value smaller so that we can gain more.

class Solution:
  def firstWillWin(self, n):
      def search(i, dp, visited):
          if visited[i]:
              return dp[i]
          if i == 0:
              dp[i] = False
          elif i == 1:
              dp[i] = True
          elif i == 2:
              dp[i] = True
          else:
              dp[i] = not (search(i-1, dp, visited) and search(i-2, dp, visited))

          visited[i] = True
          return dp[i]

      dp = [False] * (n+1)
      visited = [False] * (n+1)
      return search(n, dp, visited)

> Coins in a line II

Problem: http://www.lintcode.com/en/problem/coins-in-a-line-ii/

This problem starts taking coins from the left side.

Solution:

class Solution:
    """
    @param: values: a vector of integers
    @return: a boolean which equals to true if the first player will win
    """
    def firstWillWin(self, values):
        n = len(values)
        if n <= 2:
            return True
        dp = [0] * (n + 1)
        dp[n] = 0; dp[n-1] = values[n-1]; dp[n-2] = values[n-1] + values[n-2]

        sum = [0] * (n + 1)
        for i in range(n-1, -1, -1):
            sum[i] = sum[i+1] + values[i]

        for i in range(n-3, -1, -1):
            dp[i] = sum[i] - min(dp[i+1], dp[i+2])
        return dp[0] > sum[0] / 2

dp[i] means the max coins can gain from i to end

sum[i] means the sum from i to end

dp[i] = max(values[i] + sum[i+1] - dp[i+1], values[i] + values[i+1] + sum[i+2] - dp[i+2]) => dp[i] = sum[i] - min(dp[i+1], dp[i+2])

class Solution:
  """
  @param: values: a vector of integers
  @return: a boolean which equals to true if the first player will win
  """

  def firstWillWin(self, values):
      def search(i, dp, visited):
          if visited[i]:
              return dp[i]
          if i == n:
              dp[i] = 0
          elif i == n - 1:
              dp[i] = values[n - 1]
          elif i == n - 2:
              dp[i] = values[n - 1] + values[n - 2]
          else:
              dp[i] = self.sum[i] - min(search(i + 1, dp, visited), search(i + 2, dp, visited))

          visited[i] = True
          return dp[i]

      n = len(values)
      dp = [0] * (n + 1)
      visited = [False] * (n + 1)
      self.sum = [0] * (n + 1)
      for i in range(n - 1, -1, -1):
          self.sum[i] = self.sum[i + 1] + values[i]
      return search(0, dp, visited) > self.sum[0] / 2

> Coins in a line III

Problem:

There are n coins in a line. Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins.

Could you please decide the first player will win or lose?
Example

Given array A = [3,2,2], return true.

Given array A = [1,2,4], return true.

Given array A = [1,20,4], return false.

Solution:

class Solution:
    """
    @param: values: a vector of integers
    @return: a boolean which equals to true if the first player will win
    """
    def firstWillWin(self, values):
        n = len(values)
        dp = [[0] * (n+1) for _ in range(n+1)]

        ''' sum for array [i, j), i includes, j excludes '''
        sum = [0]
        for i in range(n):
            sum.append(sum[-1] + values[i])

        for i in range(n, -1, -1):
            for j in range(i+1, n+1):
                ''' initialization '''
                if i+1 == j:
                    dp[i][j] = values[i]
                else:
                    dp[i][j] = sum[j] - sum[i] - min(dp[i+1][j], dp[i][j-1])

        return dp[0][n] > sum[n] / 2

dp[i][j]=max(values[i]+sum[i+1][j]-dp[i+1][j], values[j]+sum[i][j-1]-dp[i][j-1])

values[i]+sum[i+1][j] and values[j]+sum[i][j-1] are equal to sum[i][j]

So dp[i][j]=sum[i][j]-min(dp[i+1][j],dp[i][j-1])

class Solution:
  """
  @param: values: a vector of integers
  @return: a boolean which equals to true if the first player will win
  """

  def firstWillWin(self, values):
      def search(start, end, sum, dp, visited):
          if visited[start][end]:
              return dp[start][end]
          elif start == end:
              dp[start][end] = sum[end] - sum[start-1]
          else:
              dp[start][end] = sum[end] - sum[start-1]\
                   - min(search(start+1, end, sum, dp, visited), search(start, end-1, sum, dp, visited))

          visited[start][end] = True
          return dp[start][end]

      if not values:
          return False
      n = len(values)

      sum = [0] * (n+1)
      ''' sum for array [i, j], i includes, j includes '''
      for i in range(1, n+1):
          sum[i] = sum[i-1] + values[i-1]

      dp = [[0] * (n+1) for _ in range(n+1)]
      visited = [[False] * (n+1) for _ in range(n+1)]

      return search(1, n, sum, dp, visited) > sum[n] / 2