Another python...


  • 38

    Checking out every six pack.

    Solution 1

    def isSelfCrossing(self, x):
        return any(d >= b > 0 and (a >= c or a >= c-e >= 0 and f >= d-b)
                   for a, b, c, d, e, f in ((x[i:i+6] + [0] * 6)[:6]
                                            for i in xrange(len(x))))
    

    Solution 2

    def isSelfCrossing(self, x):
        b = c = d = e = 0
        for a in x:
            if d >= b > 0 and (a >= c or a >= c-e >= 0 and f >= d-b):
                return True
            b, c, d, e, f = a, b, c, d, e
        return False
    

    Explanation

                b                              b
       +----------------+             +----------------+
       |                |             |                |
       |                |             |                | a
     c |                |           c |                |
       |                | a           |                |    f
       +----------->    |             |                | <----+
                d       |             |                |      | e
                        |             |                       |
                                      +-----------------------+
                                                   d
    

    Draw a line of length a. Then draw further lines of lengths b, c, etc. How does the a-line get crossed? From the left by the d-line or from the right by the f-line, see the above picture. I just encoded the criteria for actually crossing it.

    Two details:

    • In both cases, d needs to be at least b. In the first case to cross the a-line directly, and in the second case to get behind it so that the f-line can cross it. So I factored out d >= b.
    • The "special case" of the e-line stabbing the a-line from below is covered because in that case, the f-line "crosses" it (note that even if there is no actual f-line, my code uses f = 0 and thus still finds that "crossing").

  • 2
    R

    Hi, Could you explain the code if possible


  • 0

    Your code is so sneaky,could you mind explaining your thouhhts?
    Thank you!


  • 0

    Alright, I added some.


  • 0

    Alright, I added some.


  • 0
    C

    Nice! How long did it take for you to write this code?


  • 0

    @chris.zhang.336 Really hard to tell, as I was playing around with various ways for a while and took breaks doing other things. I'm guessing I ended up with these after maybe 1-1.5 hours of working on the problem. Yeah, I spend way too much time on this :-)


  • 0
    C

    Still a decent number considering the result, I don't think it would take you too much time to come up with a less sexy solution anyway :)


  • 0
    C

    This is my C++ version of your code :)

    bool isSelfCrossing(vector<int>& x) {
    	int a = 0, b = 0, c = 0, d = 0, e = 0, f = 0;
    	for (int i : x) {
    		f = e; e = d; d = c; c = b; b = a; a = i;
    		if (d >= b && b > 0 && (a >= c || (c - e) <= a && c >= e && (d - f) <= b))
    			return true;
    	}
    	return false;
    }

  • 0
    Z

    Excellent, I somehow complicated the problem by ignoring the [u,l,d,r, u, l, d, r ... ]. Indeed in such order collision must happen within 6 steps! Thank you for sharing.


  • 0
    V

    Great thinking Stefan. I had a doubt (might sound silly :P) The special case of the e-line stabbing the a-line from below: if that was true, why not a case like [1,0,1]?


  • 0
    V

    Oops.. the question says positive numbers.. sorry. Thanks :)


  • 0
    G

    Excellent. However, I wonder if this code could cover the case of that f-line crosses the c-line but not crosses the a-line in the right graph.


  • 0
    Z

    that will be handled when you run the same algorithm, and start with c line...


  • 0
    G

    Yes, I got it. Thanks


  • 0
    A

    So according to the diagram, I feel that I first travel a, then b, then c, etc. But when I try to understand the code, I see that my most recent travelled path is a, before that b, before that c etc..

    I am finding it quite confusing to relate your diagram with the code :(


  • 0

    @AlkhanZi You're talking about solution 2, I guess? Yeah, that one is "backwards", although of course that works as well. But solution 1 is clearer that way, matching the order in the explanation.


  • 0
    A

    Yes.. I get it now. thanks


  • 0
    L

    Hi Stefan, i slightly modified your code - for first plot, shouldn't it be d >= b > 0 and a >= c? But it is incorrect. Why?

    b = c = d = e = f = 0
    for a in x:
            if (d >= b > 0 and a >= c) and (f >= d-b >=0 and a >= c-e >=0):
                return True
            b, c, d, e, f = a, b, c, d, e
        return False

  • 0

    @Lazysheep.wang Don't know what you mean. I do have exactly that for the first plot.
    Your version is wrong because you changed the or to an and and you're missing the b > 0 (or d > 0) for the second plot.


Log in to reply
 

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