Stone Game VII — Algorithms&Visualizations

Introduction
In this article, we are going to study and solve the medium difficulty LeetCode challenge Stone Game VII. It’s a sort of extension of the previous Stone Game VI, already analyzed and solved in this previous article. Let’s get started with the problem description, the examples, the analysis of the problem, and eventually the code.

The Problem
First off, let me ctrl-c ctrl-v the problem description:

Alice and Bob take turns playing a game, with Alice starting first.

There are n stones arranged in a row. On each player's turn, they can remove either the leftmost stone or the rightmost stone from the row and receive points equal to the sum of the remaining stones' values in the row. The winner is the one with the higher score when there are no stones left to remove.

Bob found that he will always lose this game (poor Bob, he always loses), so he decided to minimize the score’s difference. Alice’s goal is to maximize the difference in the score.

Given an array of integers stones where stones[i] represents the value of the ith stone from the left, return the difference in Alice and Bob's score if they both play optimally.

Constraints:
n == stones.length
2 <= n <= 1000
1 <= stones[i] <= 1000

Example:
Input: stones = [5,3,1,4,2]
Output: 6
Explanation:
- Alice removes 2 and gets 5 + 3 + 1 + 4 = 13 points. Alice = 13, Bob = 0, stones = [5,3,1,4].
- Bob removes 5 and gets 3 + 1 + 4 = 8 points. Alice = 13, Bob = 8, stones = [3,1,4].
- Alice removes 3 and gets 1 + 4 = 5 points. Alice = 18, Bob = 8, stones = [1,4].
- Bob removes 1 and gets 4 points. Alice = 18, Bob = 12, stones = [4].
- Alice removes 4 and gets 0 points. Alice = 18, Bob = 12, stones = [].
The score difference is 18–12 = 6.

The First Approach
The game is rather straightforward, at each step Alice and Bob have to pick a stone (the leftmost or the rightmost), collecting as many points as the sum of the remaining ones. Alice’s objective is to maximize the difference in the scores, while Bob wants to minimize it.

At first, thinking of picking the least valuable stone between the leftmost and rightmost one might seem a sensible strategy, because it would make each player gain the biggest possible score they can get at each turn. Before explaining the reasons why this approach is wrong, let’s see what would happen if, given the example input: stones=[5,3,1,4,2], the players applied this game strategy:

Picking the least valuable stones strategy

Input: stones = [5,3,1,4,2]

If Alice and Bob stuck to the strategy of choosing the least valuable stone at each turn, the game would conclude with:

Alice’s Score:21
Bob’s Score:14

The image shows the whole game and the choices that each player makes during her/his turn.

The difference between Alice and Bob’s scores would be 7, but we expected it to be 6. The problem here is that each player has focused on maximizing the score, but this is not the goal of the challenge, because Alice wants to maximize the difference in her and Bob’s score, while Bob’s objective is to minimize it!
In this specific case, Bob didn’t play optimally! As a matter of fact, Bob might have achieved a better final result just by picking stone [5] in his first turn, and then following the least valuable stone strategy! Let’s check this out:

As portrayed by the picture, if Bob picks stone [5] during his first turn, and then picks only the least valuable stone throughout the rest of the game, the final difference in the scores will be smaller than the previous scenario difference.
In other words, we have found a better strategy for Bob.
What about Alice? Is there a better strategy she can follow? For this specific input, this is the best strategy for Alice. How can I claim it? Well, just because this is exactly the strategy in the example solution description. Nevertheless, it’s easy to demonstrate that picking the least valuable stone is not the way to go for Alice either! (Try with other inputs)

By now, it should be clear that the least valuable stone strategy doesn’t work out.
What can we do then? Perhaps we want to check all the possibilities and pick the best one. Let’s see.

The Second Approach
We have seen in the previous section that finding the optimal strategies for Alice and Bob is not a piece of cake. Thus, we will be trying to search in the whole solution space. Let me explain what I mean:
At each turn, the players have to decide between two options, leftmost or rightmost stone. What we want to do is examining both the possibilities, and see where they lead to.
Before jumping into the visualization, I want to point out that when we analyze all the possibilities we can either keep track of Bob and Alice’s scores, and eventually compute the difference, or directly keep track of the difference itself at each step. It’s not a big optimization, but still, I’ll be going with the second. Once again, on one hand, Bob’s objective is to minimize the difference in the scores, on the other hand, Alice targets the maximization of it.

Ok, let’s take some time to analyze the above tree. The leaves represent almost all the possible conclusions of the game. Bob will always try to minimize the number in the red circle (which represents the difference in the scores), while Alice will try to maximize it.
Before moving on, just a quick note about the last turn. It’s a bit different from the other ones because, even though Bob still has two choices, it’s obvious that he will always go with the least valuable remaining stone. As a matter of fact, when there are only two left stones, picking the least valuable one always makes sense to any player.
(By the way, I might have ‘normally’ expanded the tree in the last turn as well, however, I preferred to include this small optimization here to reduce the image size)

How can we read the above tree then? We will get started from the bottom, working our way up to the root. At each step, (once again) Alice will maximize the difference, while Bob will try to minimize it. Let’s bubble up the red circle containing the differences in the final scores to have a different view of the same image, which might be useful for a better understanding of the tree:

Here you go! Bubbling up the results, we will end up with the solution to the problem. I want it to be crystal clear to everyone:
Alice will kick off the game by picking stone [2] because she knows that her choice will limit Bob to minimize the score’s difference by choosing between ending up with a difference of 6 or 7 points. Consequently, the turn after, Bob will pick stone [5], because that choice will make Alice win by 6, instead of 7. Second last turn Alice can pick both stone [4] or stone [3], it doesn’t really matter, because both the choices will lead to the same final solution.

This approach seems legit, so I guess it’s time to translate all of this into code.

The Code

Conclusions
I hope you enjoyed this article and learned something new. I can’t wait to read your feedback.
For other coding challenges, don’t hesitate to visit my profile. Have a great day!

“Tell me and I forget, teach me and I may remember, involve me and I learn.”
― Benjamin Franklin