7
\$\begingroup\$

This is a question that I encountered in one of the competitive coding tests. The question goes as follows:

A 2-player game is being played. There is a single pile of stones. Every stone has an amount (positive) written on top of it. At every turn, a player can take the top 1 or 2 or 3 stones and add to his kitty. Both players want to maximize their winnings. Assuming both players play the game optimally and Player 1 starts the game, what is the maximum amount that Player 1 can win?

I have devised the following recursive approach:

class Main {
  public static void main(String[] args) {
    int a[] = {1,2,3,7,4,8,1,8,1,9,10,2,5,2,3};
    int sum = 0;
    for (int i=0;i<a.length; i++) {
      sum += a[i];
    }
    System.out.println(maxPlayer1(a, 0, sum, 0, a.length));
  }
  public static int maxPlayer1(int[] a, int currSum, int sum, int start, int len) {
    if (len-start <=3) {
      int val = 0;
      for (int i=start; i<len; i++) {
        val += a[i];
      }
      return val;
    }

    int v1 = a[start] + (sum - currSum - a[start]) - 
    maxPlayer1(a, currSum + a[start], sum, start + 1, a.length);

    int v2 = a[start] + a[start+1] + (sum - currSum - a[start] - a[start+1]) - 
    maxPlayer1(a, currSum + a[start] + a[start+1], sum, start + 2, a.length);

    int v3 = a[start] + a[start+1] + a[start+2] + (sum - currSum - a[start] - a[start+1] - a[start+2]) - 
    maxPlayer1(a, currSum + a[start] + a[start+1] + a[start+2], sum, start + 3, a.length);

    return Math.max(v1, Math.max(v2, v3));
  }
}

I have checked my solution on a few inputs. Is my algorithm correct?

\$\endgroup\$
  • 5
    \$\begingroup\$ A few inputs? Nope. You need a lot of inputs. One thing to do is to test your solution against more inputs. This way, you won't need to ask whether your algorithm is correct or not; you know your algorithm is right. Therefore, test some more inputs, so that you know your algorithm works correctly. \$\endgroup\$ – Justin Jun 16 at 16:25
  • 8
    \$\begingroup\$ There is nothing wrong with posting the unit tests you already implemented as an appendix in your question. This makes our task helping you easier. When asking whether your algorithm is correct, this rings bells here. I suggest to read the policy: codereview.stackexchange.com/help/on-topic \$\endgroup\$ – dfhwze Jun 16 at 16:34
  • 2
    \$\begingroup\$ A "pile of stones" together with "written on top" sounds a lot like the players would only be able to look at the top stone, with the scores of all other stones being a secret until the top stone is removed. This should be clarified before the algorithm can be analyzed. \$\endgroup\$ – Roland Illig Jun 16 at 22:53
  • 2
    \$\begingroup\$ @RolandIllig There are very few scenarios where you gain by not taking all 3 stones - I don't think that can be the intention. I can see just the few options where you know you will end up with the same number of stones and tactically not take one with low number in hope you can get a higher one instead… but this is subject to luck. So, strategy would be fairly simple - take the maximum number of stones, except don't take stones with 1 in case you still end up with the same number of stones in the end. (anything else depends on luck). \$\endgroup\$ – Zizy Archer Jun 17 at 8:58
  • 2
    \$\begingroup\$ Why do you need to pass a.length as a separate argument? \$\endgroup\$ – Federico Poloni Jun 17 at 10:05
18
\$\begingroup\$

Usability

I have a remark about defining recursive functions. You don't want consumers of your API to think about the intermediate variables and their initial value. The consumer does not care you are using recursion internally.

Make your recursive function private.

private static int maxPlayer1(int[] a, int currSum, int sum, int start, int len) 

And create a public API entrypoint.

public static int maxPlayer1(int[] a) {
     final int sum = IntStream.of(a).sum();
     return maxPlayer1(a, 0, sum, 0, a.length);
}

The consumer can now call your API without getting a headache:

public static void main(String[] args) {
     final int a[] = {1,2,3,7,4,8,1,8,1,9,10,2,5,2,3};
     System.out.println(maxPlayer1(a));
}

As compared to the original code the consumer had to write.

public static void main(String[] args) {
    int a[] = {1,2,3,7,4,8,1,8,1,9,10,2,5,2,3};
    int sum = 0;
    for (int i=0;i<a.length; i++) {
      sum += a[i];
    }
    System.out.println(maxPlayer1(a, 0, sum, 0, a.length));
  }
\$\endgroup\$
8
\$\begingroup\$

A note on efficiency. Currently the code exhibit an exponential time complexity. It can be reduced significantly.

Notice that the same position is inspected more than once. For example, the opening sequences 3, 1, 2, 2 and 1, 3 all lead to the same position. Further down the game the situation aggravates.

Keep track of the positions already inspected, and before diving into the recursion check whether it is still unknown. Since the position is just an integer (an amount of stones remaining), the cost of tracking is \$O(n)\$ space.

Further improvement is of course alpha-beta pruning.

\$\endgroup\$
7
\$\begingroup\$

The natural way to tackle this problem (as in many similar games) is starting from the final position.

Let B[k] be the maximum score that Player 1 can get if the game starts with only the last k stones left. B[1], B[2], B[3] are initial values that can be computed directly (just take all remaining stones), and then you can fill in B[4], B[5], B[6], ... in this order, since B[k] only depends on B[k-1], B[k-2], B[k-3]; so you can write your code as a loop for k=4,5,6,..., a.length. The resulting algorithm is linear, without no recursion, branching, or approximations required.

Instead, it looks like you are trying to compute the entries B[i] starting from B[a.length]. This leads to a more complicated structure where you make recursive calls, and re-compute the same values B[i] multiple times, as pointed out also by @vnp's answer.

Once you have figured out how to fill the B array in this way, a further improvement is realizing that you only need to keep the last three values B[k], B[k-1], B[k-2] at each step (and possibly also the partial sum a[k-2] + ... + a[a.length]). This gives a solution in O(1) space.

If you want to compare with another famous function in which f(n) depends on its previous values, what you wrote is like computing Fibonacci numbers recursively via return fibonacci(n-1) + fibonacci(n-2). What I suggest above is computing iteratively f[0], f[1], f[2], ... starting from f[0].

\$\endgroup\$
  • \$\begingroup\$ fantastic answer and explanation. +1 \$\endgroup\$ – hLk Jun 17 at 16:47
3
\$\begingroup\$

I am not too happy about the variable name currSum, it is hard to see the meaning of this variable from the name alone.

Consider takenValue or something similar as a variable name.

Note that

a[start] + (sum - currSum - a[start])

Simplifies to

sum - currSum

And similarily for the other cases so;

    int v1 = a[start] + (sum - currSum - a[start]) - 
    maxPlayer1(a, currSum + a[start], sum, start + 1, a.length);

    int v2 = a[start] + a[start+1] + (sum - currSum - a[start] - a[start+1]) - 
    maxPlayer1(a, currSum + a[start] + a[start+1], sum, start + 2, a.length);

    int v3 = a[start] + a[start+1] + a[start+2] + (sum - currSum - a[start] - a[start+1] - a[start+2]) - 
    maxPlayer1(a, currSum + a[start] + a[start+1] + a[start+2], sum, start + 3, a.length);

simplifies to

    int v1 = sum - currSum - 
    maxPlayer1(a, currSum + a[start], sum, start + 1, a.length);

    int v2 = sum - currSum - 
    maxPlayer1(a, currSum + a[start] + a[start+1], sum, start + 2, a.length);

    int v3 = sum - currSum -  
    maxPlayer1(a, currSum + a[start] + a[start+1] + a[start+2], sum, start + 3, a.length);

We should also try to capture the meaning of a[start]+...a[start+n], we can do this by introducing a new variable takenInCurrentStep

Also

  int val = 0;
  for (int i=start; i<len; i++) {
    val += a[i];
  }
  return val;

Is needlessly complicated. We can write this as :

  return sum-currSum;

Bringing this all together :

  public static int maxPlayer1(int[] a, int takenValue, int sum, int start, int len) {
    if (len-start <=3) {
      return sum-takenValue;
    }

    int valueTakenInCurrentStep = 0;
    int lasttokensTakenInCurrentStep = start;
    int valueTakenInCurrentStep = a[lasttokensTakenInCurrentStep];

    int v1 = sum - takenValue -
    maxPlayer1(a, takenValue+ valueTakenInCurrentStep, sum, lasttokensTakenInCurrentStep+1  , a.length);

    int lasttokensTakenInCurrentStep ++;
    int valueTakenInCurrentStep = valueTakenInCurrentStep + a[lasttokensTakenInCurrentStep ];

    int v2 = sum - takenValue -
    maxPlayer1(a, takenValue+ valueTakenInCurrentStep, sum, lasttokensTakenInCurrentStep+1  , a.length);

    int lasttokensTakenInCurrentStep ++;
    int valueTakenInCurrentStep = valueTakenInCurrentStep + a[lasttokensTakenInCurrentStep ];
    int v3 = sum - takenValue - 
    maxPlayer1(a, takenValue+ valueTakenInCurrentStep, sum, lasttokensTakenInCurrentStep+1  , a.length);

    return Math.max(v1, Math.max(v2, v3));
  }
}

The algorithm can be described as;

We have a method that calculates the maximum that the current player can get from the remaining of the game. The method takes the value of all the tokens, the value of the tokens that are no longer available, the value of all tokens, the index of the first currently available token, and the total number of tokens.

It works by if there are 3 or less tokens left return the value of the remaining tokens, which is equal to the value of all tokens minus the value of the tokens already taken. If there are more than 3 tokens return the maximum of the value of remaining tokens minus the amount that the other player gets if current player takes 1,2 or 3 tokens.

This is a correct algorithm, and we can prove this by incursion.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.