0ms with aggressive state space reduction


  • 2
    0

    Sharing my 0ms solution with detailed explanation:

    First, let's apply standard backtracking/dfs with memoization, but keeping the game state abstract:

    class Solution { 
        unordered_map<GameState, bool, GameStateHash> cache; 
        bool canWin(const GameState& s) { 
            auto it = cache.find(s); 
            if (it != cache.end()) return it->second; 
            vector<GameState> next = s.generatePossibleNextMoves(); 
            for (const GameState & n : next) 
                if (!canWin(n)) return cache[s] = true; 
            return cache[s] = false; 
        } 
    public: 
       bool canWin(const string& s) { return canWin(GameState(s)); } 
    };
    

    The naive implementation of a GameState can be a string with +/- and generatePossibleNextMoves() from the easy version of the problem.

    Now, let's see how we can define the GameState to have 0ms runtime. In a nutshell, we can compress/reduce state space, by merging similar game states with the same outcomes (e.g. beginner-wins or beginner-loses).
    Example: following game states are actually the same:

    +++-++++-+++++
    +++++-++++-+++
    ++++-+++++-+++
    ---+++--++++---+++++--
    

    Thus, we can encode these states as (3,4,5): an ordered list of integers, where each integer is a length of a chains of consequtive +-es.

    It's also easy to see that singe + can be ignored. ++ and +++ same, so we can encode both ++ and +++ as 3 (for consistency), and skip 1-s.

    This is already pretty great state space reduction, isn't it? But we can do much better:

    Consider “symmetric” states, where each number repeats even number of times (example: 3,3,4,4,9,9,9,9). It is easy to show that every symmetric state is a beginner-loses state. It is easy to show that winning strategy exists for the 2nd player, since 2nd-player can always mirror the move of the opponent at each step. Thus, those “symmetric” states, being “beginner-loses” are equivalent to the empty state (). Similarly, it is also easy to show that removing a symmetric sub-state from the game-state doesn't change the outcome. E.g. (5,5,6,6,6,7,7,7,7,8,8,8,8,8) after removing a symmetric sub-state (5,5,6,6,8,8,8,8) becomes (6,8).

    Thus, each game state can be represented as a set of unique integers: set < int >

    Note, that we need to implement generatePossibleNextMoves(), so we need to actively add and remove numbers to the set.

    Addition a number to the set and removal of the number to the game state in our reduced state space becomes one operation: toggle(), which adds the number if it was absent and removes if it was present.

    struct GameState { 
        set<int> chains; 
        int hash = 0; 
        GameState() {} 
        GameState(const string& s) { 
            int l = 0; 
            for (int i=0; i<=(int)s.size(); i++) 
                if (s[i]=='+') l++; else toggle(l), l = 0; 
        } 
            
        void toggle(int len) { 
            if (len<=1) return; 
            if (len==2) len = 3; 
            auto it = chains.find(len); 
            if (it == chains.end()) chains.insert(len); else chains.erase(it); 
            hash ^= len * len * len; 
        } 
    };
    

    Generating possible moves is trivial:

    struct GameState { // continued
        vector<GameState> generatePossibleNextMoves() const { 
            vector<GameState> result; 
            for (int len : chains) { 
                GameState s = *this; 
                s.toggle(len); 
                if (len <= 3) result.push_back(s); 
                else { 
                    for (int j=0; j<len-2 && j<len/2; j++) { 
                        GameState t = s; 
                        t.toggle(j); 
                        t.toggle(len-2-j); 
                        result.push_back(t); 
                    } 
                } 
            } 
            return result; 
        } 
    };
    

    We also need a hashcode and equality comparer for the GameState, so we can use it as a key in unordered_map. For efficiency, the hash code is stored directly as a field, and updated incrementally on each toggle() operation.

    struct GameStateHash { size_t operator() (const GameState& s) const { return s.hash; } }; 
    
    bool operator == (const GameState& a, const GameState& b) 
    { return a.hash == b.hash && a.chains == b.chains; } 
    

    Further optimization is possible:

    • instead of set<int>, you can also use bitset<> class.

    • instead of generating new set of possible moves you can incrementally change the state


  • 0
    M

    The part "removing a symmetric sub-state doesn't change the outcome" is indeed inspiring.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.