# Another python...

• 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").

• Hi, Could you explain the code if possible

Thank you!

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

• @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 :-)

• 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 :)

• 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;
}``````

• 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.

• 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]?

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

• 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.

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

• Yes, I got it. Thanks

• 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 :(

• @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.

• Yes.. I get it now. thanks

• 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``````

• @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.

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