Python 3: TC O(n) SC O(1): Tricky Logic, "Forced Move Chains"
Intuition\n\nThis is just a tricky problem, it\'s not like a sliding window problem or something where it fits into a neat pattern and you just crank through th
# Intuition\n\nThis is just a tricky problem, it\'s not like a sliding window problem or something where it fits into a neat pattern and you just crank through the code.\n\nThis is a Nim-like game where the first person forced into an illegal move (taking a value that makes the sum divis by three) loses. As an added twist, if there are no stones left, the Bob always wins.\n\n# Simplifying the Game\n\nUsually the trick to getting `O(n)` time solutions from a game with many possible moves is to simplify as much as possible.\n\nHere we want to avoid making the sum of taken elements divisible by three. That means the residue of the sum mod 3 must be 1 or 2.\n\nTherefore **we only need to know the number of elements of each residue mod 3.**\n\nThis lets us consider taking an arbitrary stone among the array in `O(1)` and lets us use `O(1)` memory potentially.\n\n## Game Solution Patterns\n\n\n### Top-Down DFS\n\nThe classic pattern is to write a `dfs(...)` function that\n* takes the current game state as parameters\n* and returns the winner\n\nIf *any* of the current player\'s plays results in `dfs(resultingState...) == currentPlayer` then the current player can "force a win" by making that play. The idea is that the function returns the optimal strategy. So if the other player loses after this play, then the current player will win.\n\nUnfortunately this will give TLE here. Each player has three moves in general: take an element with reach residue mod 3. One of those will result in an instant loss. The others will branch out. Even with caching we\'d visit most combinations of the number of remaining stones with reach residue.\n\nTherefore we need something faster.\n\n### Trick 1: Maintain an Invariant\n\nThe classic solution to a Nim game, e.g. each player can take `1..k` items and whoever is forced to take the `n`th element loses is based on invariants.\n\nThe idea is that if the first player can always make the second player draw stone `(k+1)*m+1`, then no matter what the second player plays, the first player can play `k+1-otherPlay`. This leaves `(k+1)*(m-1)+1` stones remaining. Then the second player will be forced to take the last stone; after `m` rounds there will be `(k+1)*0 + 1 == 1` stones remaining.\n\nHere, however, that doesn\'t work:\n* if the current sum residue is 1 for example, then the next player can pick a stone with the same residue, or a stone with residue 0\n* AND there are a finite number of stones with each residue\n\n### Trick 2: Forced Move Chain\n\nThis is the one that solves this problem: **Alice\'s first play dictates the total number of legal moves, and thus we can calculate who will win.**\n\nFirst we note that taking a stone with residue zero doesn\'t change the sum. Therefore taking a stone of residue zero after any first move taking 1 or 2 won\'t mean losing (except for taking the very last stone if you\'re Alice).\n\nTherefore if Alice starts with a `1`, then the pattern is\n* `11212121....`, with all the residue zero stones mixed in\n* if there is one more 1 than 2 the Bob wins\n  * the sequence will play out all the 1 and 2 residues\n  * then the zeros will get played as well at some point\n  * and thus the stones pile will be empty at the end and Bob wins\n* if there\'s an excess of 1s then the sequence will look like `112121....1`, we calculate the number of non-losing plays (i.e. those that don\'t set the sum residue to zero) and see who wins\n* if there\'s an excess of `2` then same idea, we play `1121212....12`, calculate legal plays, and return\n\nIf Alice starts with a `2` then the pattern is `2212121...`; it\'s the same logic as `11212..` except 1 and 2 are flipped.\n\n# Edge Cases and Play Parity\n\nAlice makes the first, third, etc. plays. Therefore if there are an odd number of legal plays then Alice wins. If there are an even number then Bob wins, because there\'s no subsequent odd play.\n\nTherefore the parity is mostly what determines if Alice or Bob wins, hence `plays&1` in the code.\n\n**Edge case one: all stones played.** If the sequence ends with playing all stones then Bob wins no matter whose turn is next. Therefore I have all the `plays < N` checks.\n\n**Edge case 2: only one of residue `1` and/or `2`.** If there\'s only one with residue `1` for example then we don\'t have `1121212...`, we just have `1000...0` as the legal plays. Same with `221212...` being impossible if we just have a single residue of `2`.\n\nMy early solutions didn\'t have this edge case and hence I kept getting wrong answers.\n\n**Edge case 3: make sure you compare against `N`.** You might be tempted to think that e.g. `r[1] > r[2]+1` means you can\'t run out of stones. But you can! If `r[1] == r[2]+2`, e.g. `r[1] == 4` and `r[2]==2` then you can clearly have `112121` as the move sequence, and that sequence plays out all of the tiles.\n\nOne way to handle this is to have `r[1]==r[2]+2` checks. But I prefer instead to just compare `plays < N` in all cases just to be sure.\n\nI might still have some unnecessary `plays < N` checks, but it\'s a bit safer and not really any less performant to make the checks anyway. In an interview I\'d do the checks just to hurry up and solve the problem ASAP without bugs so that\'s what I practice on LC when writing solutions. Slower and correct is vastly better than fast and wrong.\n\n# Complexity\n- Time complexity: linear, we count up the number of stones with each residue mod 3\n\n- Space complexity: constant because mod 3 is hard-coded\n\n# For Larger Mods\n\nIf the question asked for mod 4 or higher then I think we\'re doomed because the move chain wouldn\'t be forced.\n\nFor any modulus `m`, then\n* the requirement that we not have `sum == 0 mod m` means we can\'t play one of the `m` residues\n* we can always play residue `0` after the first play, this is a "trivial residue"\n* therefore for each game state in general there are `m-2` nontrivial residues we can play\n\nThe `m==3` case is easy because `m-2 == 1`, and thus there\'s only one nontrivial play in each round: hence the forced move chain.\n\nFor `m > 3` then our DFS exploration of all possible nontrivial plays will branch exponentially. With caching we\'d wind up with something like a `O(n**(m-2))` solution or something similar. Yikes.\n\n# Code\n```python3 []\nclass Solution:\n    def stoneGameIX(self, stones: List[int]) -> bool:\n        # I wish Alice and Bob would get stoned and leave us alone!! Get married already...\n\n        # n stones with assoc values in 1..1e4\n        # each player can remove any stone\n        #     player who removes a stone loses if the sum of removed stones is divis by 3\n        #     Bob wins if there are no stones left, even if Alice wins\n\n        # brute force: try all plays and see what happens\n\n        # smarter: divis by three just means we need to know the sum mod 3 after removal and thus we only need the counts\n        # of stones with each residue\n\n        # top-down DFS can be done where we track the count of stones with each residue\n        \n        # but this will involve all combinations of r0, r2, r2 which is cubic time, yikes\n\n        # another idea: start with rs = 0\n        #   Alice:\n        #     > r0: lose\n        #     > r1: -> Bob, r0, r1-1, r2, rs=1\n        #     > r2: -> Bob, r0, r1, r2-1, rs=2\n        \n        # don\'t want to be stuck with just the 3-rs play and nothing else\n\n        # play patterns: can always play a 0, doesn\'t change sum mod 3\n        # other than zeros we have\n        # 1 1 2 1 2 1 2 1 2 1 2 1 ...\n        #   2 2 1 2 1 2 1 2 ...\n        #\n        # move chain is fixed by Alice!\n        #\n        # 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\n        #                2                       r2      r1,  ....................................................................... same\n        #\n        # if the pattern doesn\'t play out then suppose the 11212121... pattern plus zeros can go on for n moves\n        #   then the next player loses\n\n        # either way Alice can set in motion via first pick of 1 or 2 residue the forced chain of later moves\n\n        r = [0]*3\n        for n in stones: r[n%3] += 1\n\n        N = len(stones)\n\n        # if Alice plays a 1 first\n        if r[1]:\n            if r[1] == 1:\n                plays = 1 + r[0]\n                if plays < N and plays&1: return True\n            elif r[1] > r[2]+1:\n                # 112121...1\n                plays = 2 + r[2]*2 + r[0]\n                if plays < N and plays&1: return True\n            elif r[1] < r[2]+1:\n                # 11 212121 2 --> two plays of r1, then for each r1 thereafter we have two more plays, then a final 2\n                plays = 2 + 2*(r[1]-2) + 1 + r[0]\n                if plays < N and plays&1: return True\n            # else: 1121212... plays all r1 and r2, and then play all r0, plays==n, Bob wins\n        \n        if r[2]:\n            # 11212... -> 22121... is just swapping 1s and 2s, so same logic just replace all 1 with 2 and vice-versa\n            if r[2] == 1:\n                plays = 1+r[0]\n                if plays < N and plays&1: return True\n            elif r[2] > r[1]+1:\n                plays = 2 + r[1]*2 + r[0]\n                if plays < N and plays&1: return True\n            elif r[2] < r[1]+1:\n                plays = 2 + 2*(r[2]-2) + 1 + r[0]\n                if plays < N and plays&1: return True\n\n        # Alice can\'t force a win so Bob will win: either Alice must play a losing next move, or all stones are taken\n        return False\n```
['Python3']