<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>

class Solution:
    def stoneGameIX(self, stones: List[int]) -> bool:
        # I wish Alice and Bob would get stoned and leave us alone!! Get married already...

        # n stones with assoc values in 1..1e4
        # each player can remove any stone
        #     player who removes a stone loses if the sum of removed stones is divis by 3
        #     Bob wins if there are no stones left, even if Alice wins

        # brute force: try all plays and see what happens

        # smarter: divis by three just means we need to know the sum mod 3 after removal and thus we only need the counts
        # of stones with each residue

        # top-down DFS can be done where we track the count of stones with each residue
        
        # but this will involve all combinations of r0, r2, r2 which is cubic time, yikes

        # another idea: start with rs = 0
        #   Alice:
        #     > r0: lose
        #     > r1: -> Bob, r0, r1-1, r2, rs=1
        #     > r2: -> Bob, r0, r1, r2-1, rs=2
        
        # don't want to be stuck with just the 3-rs play and nothing else

        # play patterns: can always play a 0, doesn't change sum mod 3
        # other than zeros we have
        # 1 1 2 1 2 1 2 1 2 1 2 1 ...
        #   2 2 1 2 1 2 1 2 ...
        #
        # move chain is fixed by Alice!
        #
        # if Alice picks 1, and there are 1 more r1 than r2, then the sequence plays out, zeroes get taken in some order, and Bob wins
        #                2                       r2      r1,  ....................................................................... same
        #
        # if the pattern doesn't play out then suppose the 11212121... pattern plus zeros can go on for n moves
        #   then the next player loses

        # either way Alice can set in motion via first pick of 1 or 2 residue the forced chain of later moves

        r = [0]*3
        for n in stones: r[n%3] += 1

        N = len(stones)

        print(f"{r=}, {N=}")

        # if Alice plays a 1 first
        if r[1]:
            if r[1] == 1:
                plays = 1 + r[0]
                if plays < N and plays&1: return True
            elif r[1] > r[2]+1:
                # 112121...1
                plays = 2 + r[2]*2 + r[0]
                if plays < N and plays&1: return True
            elif r[1] < r[2]+1:
                # 11 212121 2 --> two plays of r1, then for each r1 thereafter we have two more plays, then a final 2
                plays = 2 + 2*(r[1]-2) + 1 + r[0]
                if plays < N and plays&1: return True
            # else: 1121212... plays all r1 and r2, and then play all r0, plays==n, Bob wins
        
        if r[2]:
            # 11212... -> 22121... is just swapping 1s and 2s, so same logic just replace all 1 with 2 and vice-versa
            if r[2] == 1:
                plays = 1+r[0]
                if plays < N and plays&1: return True
            elif r[2] > r[1]+1:
                plays = 2 + r[1]*2 + r[0]
                if plays < N and plays&1: return True
            elif r[2] < r[1]+1:
                plays = 2 + 2*(r[2]-2) + 1 + r[0]
                if plays < N and plays&1: return True

        # Alice can't force a win so Bob will win: either Alice must play a losing next move, or all stones are taken
        return False
1000