<p>Alice and Bob continue their games with stones. There is a row of n stones, and each stone has an associated value. You are given an integer array <code>stones</code>, where <code>stones[i]</code> is the <strong>value</strong> of the <code>i<sup>th</sup></code> stone.</p>

<p>Alice and Bob take turns, with <strong>Alice</strong> starting first. On each turn, the player may remove any stone from <code>stones</code>. The player who removes a stone <strong>loses</strong> if the <strong>sum</strong> of the values of <strong>all removed stones</strong> is divisible by <code>3</code>. Bob will win automatically if there are no remaining stones (even if it is Alice&#39;s turn).</p>

<p>Assuming both players play <strong>optimally</strong>, return <code>true</code> <em>if Alice wins and</em> <code>false</code> <em>if Bob wins</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> stones = [2,1]
<strong>Output:</strong> true
<strong>Explanation:</strong>&nbsp;The game will be played as follows:
- Turn 1: Alice can remove either stone.
- Turn 2: Bob removes the remaining stone. 
The sum of the removed stones is 1 + 2 = 3 and is divisible by 3. Therefore, Bob loses and Alice wins the game.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> stones = [2]
<strong>Output:</strong> false
<strong>Explanation:</strong>&nbsp;Alice will remove the only stone, and the sum of the values on the removed stones is 2. 
Since all the stones are removed and the sum of values is not divisible by 3, Bob wins the game.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> stones = [5,1,2,4,3]
<strong>Output:</strong> false
<strong>Explanation:</strong> Bob will always win. One possible way for Bob to win is shown below:
- Turn 1: Alice can remove the second stone with value 1. Sum of removed stones = 1.
- Turn 2: Bob removes the fifth stone with value 3. Sum of removed stones = 1 + 3 = 4.
- Turn 3: Alices removes the fourth stone with value 4. Sum of removed stones = 1 + 3 + 4 = 8.
- Turn 4: Bob removes the third stone with value 2. Sum of removed stones = 1 + 3 + 4 + 2 = 10.
- Turn 5: Alice removes the first stone with value 5. Sum of removed stones = 1 + 3 + 4 + 2 + 5 = 15.
Alice loses the game because the sum of the removed stones (15) is divisible by 3. Bob wins the game.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= stones.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= stones[i] &lt;= 10<sup>4</sup></code></li>
</ul>

from collections import defaultdict

from functools import lru_cache

class Solution:
    def stoneGameIX(self, stones: List[int]) -> bool:
      # [0, 1, 1, 2, 2] -> 1, 1, 2, 0, 2
      count = defaultdict(int)
      for stone in stones:
        count[stone % 3] += 1
      print(count)

      count[0] = count[0] % 2
      # count[1] = count[1] % 6 # 3 of 1s makes mod 0, but 2 players
      # count[2] = count[2] % 6 # 3 of 2s makes mod 0, but 2 players
      min_cnt = max(min(count[1] - 1, count[2] - 1), 0)
      count[1] -= min_cnt
      count[2] -= min_cnt

      # print(count)
      # start with 2 -> counter with 2 or counter with 0
      # start with 1 -> counter with 1
      # 2 -> 0 or 2

      @lru_cache
      def play(zeros: int, ones: int, twos: int, total: int, player_alice: bool):
        # print(zeros, ones, twos, total, player_alice)
        if total == 0:
          return True

        if zeros == 0 and ones == 0 and twos == 0:
          return not player_alice  # not player_alice

        output = False
        if zeros > 0:
          output |= not play(zeros - 1, ones, twos, total % 3, not player_alice)
        if ones > 0:
          output |= not play(zeros, ones - 1, twos, (total + 1) % 3, not player_alice)
        if twos > 0:
          output |= not play(zeros, ones, twos - 1, (total + 2) % 3, not player_alice)
        return output

      return play(count[0], count[1], count[2], 3, True)

990