Straight-forward Dumb Simulation Solution 0ms O(1) Space


  • 0
    R

    Test cases are too small, so I did a pure simulation implementation and still got 0 ms result. Not as brilliant as the pattern finding solution but still it works.

    Let's consider each movement, since the movements always happen in counter-clockwise sequence, so we can only look at one direction and apply accordingly to other directions.

    If we want to move upwards (NORTH), we will be able to cross either the previous "SOUTH" line drawn by the last eastward movement or the previous "NORTH" border line drawn by the last westward movement. All we need to do is to determine the potential crossing line before each move. In order words, we can expand the following pseudo code into the final solution.

    for x in X[1 .. n]
    move point
    if point hit potential line: return true
    update potential line for the next move

    Implementation in C++ (quite long):

    enum dir_t
    {
        NORTH = 0,
        WEST = 1,
        SOUTH = 2,
        EAST = 3
    };
    
    dir_t next_dir(dir_t d)
    {
        switch(d)
        {
            case NORTH: return WEST;
            case WEST : return SOUTH;
            case SOUTH: return EAST;
            case EAST : return NORTH;
        }
        
        return NORTH;
    }
    
    struct point_t
    {
        int x;
        int y;
        
        point_t() : x(0), y(0) {}
        point_t(int a, int b) : x(a), y(b) {}
        
        bool operator <= (const point_t& p) const
        {
            return this->x < p.x || (this->x == p.x && this->y <= p.y);
        }
        
    };
    
    ostream& operator << (ostream& os, const point_t& p)
    {
        return os << "[" << p.x << "," << p.y << "]";
    }
    
    typedef pair<point_t, point_t> line_t;
    
    ostream& operator << (ostream& os, const line_t& l)
    {
        if(l.first <= l.second)
            return os << "{" << l.first << "," << l.second << "}";
        else
            return os << "{INV}";
    }
    
    bool is_line_valid(line_t& l)
    {
        return l.first <= l.second;
    }
    
    void make_line_invalid(line_t& l)
    {
        l.first.x = 0; l.first.y = 0;
        l.second.x = -1; l.second.y = -1;
    }
    
    typedef vector<line_t> border_t;
    
    point_t move_point(point_t& s, dir_t d, int l)
    {
        point_t p(s);
        switch(d)
        {
            case NORTH: p.y += l; return p;
            case WEST : p.x -= l; return p;
            case SOUTH: p.y -= l; return p;
            case EAST : p.x += l; return p;
        }
        
        return p;
    }
    
    bool can_hit(point_t& e, dir_t d, border_t& border)
    {
        if(is_line_valid(border[d]))
        {
            switch(d)
            {
                case NORTH: return e.x >= border[NORTH].first.x && e.x <= border[NORTH].second.x && e.y >= border[NORTH].first.y;
                case WEST : return e.y >= border[WEST ].first.y && e.y <= border[WEST ].second.y && e.x <= border[WEST ].first.x;
                case SOUTH: return e.x >= border[SOUTH].first.x && e.x <= border[SOUTH].second.x && e.y <= border[SOUTH].first.y;
                case EAST : return e.y >= border[EAST ].first.y && e.y <= border[EAST ].second.y && e.x >= border[EAST ].first.x;
            }
        }
        
        return false;
    }
    
    void update_border(point_t& s, point_t& e, dir_t d, border_t& border)
    {
        dir_t nd = next_dir(d);
        
        switch(nd)
        {
            case NORTH:
            {
                if(is_line_valid(border[SOUTH]) && e.y < border[SOUTH].first.y)
                {
                    if(e.x >= border[SOUTH].first.x && e.x <= border[SOUTH].second.x)
                        border[NORTH] = border[SOUTH];
                }
                
                border[SOUTH].first = s;
                border[SOUTH].second = e;
                break;
            }
            case WEST:
            {
                if(is_line_valid(border[EAST]) && e.x > border[EAST].first.x)
                {
                    if(e.y >= border[EAST].first.y && e.y <= border[EAST].second.y)
                        border[WEST] = border[EAST];
                }
                
                border[EAST].first = s;
                border[EAST].second = e;
                break;
            }
            case SOUTH:
            {
                if(is_line_valid(border[NORTH]) && e.y > border[NORTH].first.y)
                {
                    if(e.x >= border[NORTH].first.x && e.x <= border[NORTH].second.x)
                        border[SOUTH] = border[NORTH];
                }
                
                border[NORTH].first = e;
                border[NORTH].second = s;
                break;
            }
            case EAST:
            {
                if(is_line_valid(border[WEST]) && e.x < border[WEST].first.x)
                {
                    if(e.y >= border[WEST].first.y && e.y <= border[WEST].second.y)
                        border[EAST] = border[WEST];
                }
                
                border[WEST].first = e;
                border[WEST].second = s;
                break;
            }
        }
    }
    
    class Solution {
    public:
        bool isSelfCrossing(vector<int>& x) {
            int i, N = x.size();
            
            dir_t d = NORTH;
            point_t s(0,0);
            border_t border(4);
            
            for(i = 0; i < 4; ++i) make_line_invalid(border[i]);
            
            border[SOUTH].first = s;
            border[SOUTH].second = s;
            
            for(i = 0; i < N; ++i)
            {
                point_t e = move_point(s, d, x[i]);
                
                if(can_hit(e, d, border)) return true;
                
                update_border(s, e, d, border);
                
                // cout << "e: " << e << endl;
                
                // cout << "N: " << border[NORTH] << endl;
                // cout << "W: " << border[WEST ] << endl;
                // cout << "S: " << border[SOUTH] << endl;
                // cout << "E: " << border[EAST ] << endl;
                // cout << endl;
                
                s = e;
                d = next_dir(d);
            }
            return false;
        }
    };
    

Log in to reply
 

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