You are given an array x of n positive numbers. You start at point (0,0) and moves x[0] metres to the north, then x[1] metres to the west, x[2] metres to the south, x[3] metres to the east and so on. In other words, after each move your direction changes counter-clockwise.
Write a one-pass algorithm with O(1) extra space to determine, if your path crosses itself, or not.
┌───┐
│ │
└───┼──>
. │
| 2 | 1 | 1 | 2 |
Expected Output: true
┌──────┐
│ │
│
│
└────────────>
| 1 | 2 | 3 | 4 |
Expected Output: false
┌────┐
│ │
│ │
└─> │
| 2 | 2 | 2 | 1 |
Expected Output: true
. +--+
. | |
. +---+ |
. | |
. x------+
| 2 | 0 | 0 | 4 | 2 | 0 | 0 | 3 | 0 | 0 | 4 | 0 | 0 | 7 |
Expected Output: true
If we can generate the list of points then at each point we can check if we crossed one of the lines that came before. Because I prefer to work with generators and its idiomatic Racket to make functions as flexible as possible, I want to stream back a sequence of points defining the lines and whether each line crosses any of the predecessors.
A helpful utility function here would be one that can work as a fold but return a stream that yields back intermediate steps. That exists within transducers but I haven’t found a way to make that works with streams. Regardless, its easy enough to implement
(require racket/generator)
(define (folding-sequence initial fn seq)
(define-values (has-more? next) (sequence-generate seq))
(sequence->stream
(in-generator
(let recur ([acc initial])
(cond [(has-more?) (let ([next-val (fn acc (next))])
(yield next-val)
(recur next-val))])))))<<requires>>
<<folding-sequence>>
(sequence->list (folding-sequence 0 + '(1 2 3 4 5)))'(1 3 6 10 15)
Oh, I just found data/collections:foldl/steps the only differences are argument order and whether the seed is also emitted
<<requires>>
(sequence->list (foldl/steps + 0 '(1 2 3 4 5)))'(0 1 3 6 10 15)
Looks like we won’t have to move this after all.
Since when we move 0 spaces we end up at the same point as before, we will want the ability to de-dupe consecutive points. Lets write a helper for that too. Deduping 1 1 2 3 2 2 1 should generate 1 2 3 2 1
(define (dedupe-consequitive seq #:eq? [eq? eq?])
(sequence->stream
(in-generator
(let recur ([prev 'dedupe-consequitive-a-value-that-never-matches]
[remaining seq])
(match remaining
[(sequence) (void)]
[(sequence next next-rest ...)
(cond [(not (eq? prev next))
(yield next)])
(recur next next-rest)])))))Note that we also accept an optional keyword arg that we will use later to supply a custom comparison function
<<requires>>
<<dedupe-consequitive>>
(~> '(1 1 2 3 3 4 4 4 5 6 7 7 9 9 7) dedupe-consequitive sequence->list)'(1 2 3 4 5 6 7 9 7)
Moving past that, we start by simply generating the points that define the lines. The interesting thing is that every four cells in a row indicate a different direction to move. We could define the directions a cell in each position would move as a vector that we’re multipling by and then adding.
So each new point is found as follows
| Move | Direction Vector | Move Vector (A*B) | New Point (C+PrevPoint) |
|---|---|---|---|
| 2 | (0 1) | (0 2) | (0 2) |
| 1 | (-1 0) | (-1 0) | (-1 2) |
| 3 | (0 -1) | (0 -3) | (-1 -1) |
| 0 | (1 0) | (0 0) | (-1 -1) |
| 1 | (0 1) | (0 1) | (-1 0) |
First we define the directions sequence. In code this is as simple as defining the direction vector and cycling all the options forever.
(define directions (in-cycle (map list->vec '((0 1) (-1 0) (0 -1) (1 0)))))With the above helper functions, we have just about everything necessary to get our points. We simply zip up our directions and our moves, multiplying each through to get the amount of steps along the x and y axis that happen at each point. We then just sum these up from the starting point streaming back each point.
<<directions>>
<<dedupe-consequitive>>
(define (vec-eq? vec1 . other-vecs)
(and (vec? vec1)
(andmap (lambda (v) (and (vec? v) (vec= v vec1))) other-vecs)))
(define starting-point (make-parameter (vec 0 0)))
(define (get-points moves)
(define direction-moves (for/stream ([d directions]
[m moves])
(vec* d m)))
(~> (starting-point)
(foldl/steps vec+ _ direction-moves)
(dedupe-consequitive #:eq? vec-eq?)))Lets check this against example 4 above
<<requires>>
<<get-points>>
(~> (first data)
get-points
sequence->list)(list (vec 0 0) (vec 0 2) (vec 4 2) (vec 4 4) (vec 7 4) (vec 7 0) (vec 0 0))
Now we get the line segments simply by zipping this sequence of ordered points with itself offset by one
(define (line-segments-from-points points)
(for/stream ([p1 points]
[p2 (rest points)])
(cons p1 p2)))<<requires>>
<<get-points>>
<<line-segments-from-points>>
(~> (first data)
get-points
line-segments-from-points
sequence->list
pretty-print)(list (cons (vec 0 0) (vec 0 2)) (cons (vec 0 2) (vec 4 2)) (cons (vec 4 2) (vec 4 4)) (cons (vec 4 4) (vec 7 4)) (cons (vec 7 4) (vec 7 0)) (cons (vec 7 0) (vec 0 0)))
We want to be able to pair each line segment with each line segment that follows it forming a sort of combinations triangle.
(define (generate-sequence fn-sequence-generate*)
(sequence->stream
(in-generator
(define (keep-going front continue)
(when front
(yield (first front))
(call-with-values continue keep-going)))
(call-with-values fn-sequence-generate* keep-going))))
(define (combination-triangle seq)
(sequence->stream
(in-generator
(define (keep-going front continue)
(when front
(yield (list (first front)
(generate-sequence continue)))
(call-with-values continue keep-going)))
(call-with-values (thunk (sequence-generate* seq)) keep-going))))To test this I’d like for the input 0 1 2 3 4 to get back
(0 (1 2 3 4))(1 (2 3 4))(2 (3 4))(3 (4))(4 ())
<<requires>>
<<combination-triangle>>
(~>> (naturals)
(take 5)
combination-triangle
sequence->list
(map (lambda (x) (list (first x) (sequence->list (second x)))))
sequence->list)'((0 (1 2 3 4)) (1 (2 3 4)) (2 (3 4)) (3 (4)) (4 ()))
Looks like this works
With the combinations triangle we can match up each line segment against the “others” to verify if there is an intersection.
We need just one more helper function here and thats one that can take a pair of (line-segment remaing-line-segments) and tell us if there are any intersections.
Fortunately actually checking if two lines intersect - which is surprisingly not that easy - is already implemented for us in the racket geometry module.
(require sfont/geometry)
(segment-intersection (vec 0 0) (vec 0 2) (vec -1 1) (vec 0 1))
(segment-intersection (vec 0 0) (vec 0 2) (vec -1 1) (vec -1 2))(vec 0 1) #f
Getting all intersections is just a matter of running this against each combination. We’ll just go ahead and stream back any intersections and if you want to see if there are any you can check if the resulting sequence is empty.
(define/match (intersections this-segment-and-segments-to-check)
[((list _ (? empty?))) '()]
[((list (cons b1 e1) segments))
(~>> (rest segments)
(map (match-lambda [(cons b2 e2)
(segment-intersection b1 e1 b2 e2)]))
(filter identity))])Now we can put together all the above to check if the are any crossings.
<<requires>>
<<get-points>>
<<line-segments-from-points>>
<<combination-triangle>>
<<intersections>>
(define has-crossing (lambda~>> get-points
line-segments-from-points
combination-triangle
(filter (compose not empty? intersections))))And to verify this against our inputs above, remember that we expect our examples to cross, not cross, not cross, then cross again.
<<has-crossing>>
(~>> (list data1 data2 data3 data4)
(map first)
(map (compose not empty? has-crossing))
sequence->list)'(#t #f #f #t)
(require racket/generator)
(require racket/match)
(require racket/pretty)
(require threading)
(require (except-in data/collection sequence->list)) ;;https://stackoverflow.com/a/62505165/5056
(require sfont/geometry)