Process simulation

Process simulation is asking you to simulate a process based on some description. Some problems, you can solve them by straightforwardly simulate the whole process. Some problems need you to find some tricks during the simulation and then improve simulation efficiency. I’d like to summarize some problems in this article.

1503. Last Moment Before All Ants Fall Out of a Plank

class Solution {
public:
    int getLastMoment(int n, vector<int>& left, vector<int>& right) {
        int nl = left.size(), nr=right.size();
        if (nl==0) return n-*min_element(right.begin(), right.end());
        if (nr==0) return  *max_element(left.begin(), left.end());
        return max(n-*min_element(right.begin(), right.end()),  *max_element(left.begin(), left.end()));
    }
};

My original code can be found here. For the commented part, I was trying to simulate the whole process as I found if I each time move by 0.5, by at most 2*10⁴ moving steps, Everything will be clear. Some critical events will be what will happen if two ants meet with each other? We should do is putting the location of left moving ant to the group of the right moving ants and the same for the right moving ants. If you are moving to this step, you will realize you actually don’t need to do anything as if you meet each other, they will have the same location value. There is NO change in terms of the left and right array values before and after the swapping, although ant_left_pos is moved to ant_right_pos, and ant_right_pos is moved to ant_left_pos(Why? because ant_left_pos==ant_right_pos when they meet with each other.).

class Solution {
public:
    int getLastMoment(int n, vector<int>& left, vector<int>& right) {
        int nl = left.size(), nr=right.size();
        //right
        if (nl==0) return n-*min_element(right.begin(), right.end());
        if (nr==0) return  *max_element(left.begin(), left.end());
        return max(n-*min_element(right.begin(), right.end()),  *max_element(left.begin(), left.end()));
        //sort(left.begin(), left.end());
        //sort(right.begin(), right.end());
    /*
        set<int> ll, rr, ll1, rr1;
        for (auto x:left)ll.insert(x<<1);
        for (auto x:right)rr.insert(x<<1);
        float step = 0;
        while (1){
            if (ll.empty()){
                if(rr.empty())return int(step);
                return int(step/2)+(n-*(rr.rbegin()));
            }
            if (rr.empty()){
                return int(step/2)+(n-*(ll.begin()));
            }
            step++;
            ll1.clear();
            rr2.clear();
            for(auto x:ll)ll1.insert(x+1);
            for(auto x:rr)rr1.insert(x+1);
            ll.clear();rr.clear();
            for(auto x:ll1){
                if (rr1.find(x)!=rr1.end())
            }
            
            
        }
            */
        
    }
};

957. Prison Cells After N Days

/**
* jimmy shen
* time complexity O(2^6  *6)
* space complexity O(2^6)
*/
class Solution {
public:
    vector<int> prisonAfterNDays(vector<int>& cells, int N) {
        unordered_map<int, int> m;
        vector<vector<int>> history;
        vector<int> new_cells(cells.size(), 0);
        for (int i=0;i<N;++i){
            
            for (int j=1;j<cells.size()-1;++j){
                new_cells[j] = 1-(cells[j-1]^cells[j+1]);
            }
            cells = new_cells;
            int cells_int = 0;
            for (int k=0;k<cells.size();++k){
                cells_int |= (cells[k]<<(cells.size()-1-k));
            }
            if (m.find(cells_int)!=m.end()){
                int prev = m[cells_int];
                int ret = (N-1-prev)%(i-prev) +prev;
                return history[ret];
            }
            
            m[cells_int] = i;
            history.push_back(cells);
        }
        return cells;
        
    }
};