LeetCode July Challenge - Day 3

Problem: LeetCode July Challenge - Day 3

Ideas

  1. From the second turn on, cells[0]=cells[7]=0. After that, there are only 64 states possible for the prison, and therefore the states must me cyclic.
  2. I’ll be playing with a bitmap representation of the cell to save up memory and make the operation simpler and faster.

Solution:

class Solution {
    public:
        vector<int> prisonAfterNDays(vector<int>& cells, int N) {
            auto next = [](bitset<8> x){
                return (~((x>>1)^(x<<1))).set(0,0).set(7,0);
            };
            bitset<8> aux;
            for(int i=0; i<8; ++i)
                aux[i] = (cells[i] == 1);

            if(aux[0] || aux[7])
                N--, aux = next(aux);
            vector<bitset<8>> suc;
            suc.push_back(aux);
            while(true){
                aux = next(aux);
                if(aux == suc[0]) break;
                suc.push_back(aux);
            }

            bitset<8> ans = suc[N % suc.size()];
            for(int i=0; i<8; ++i)
                cells[i] = ans[i];
            return cells;
        }
};