## Ladder Range

### July 25, 2017

We represent the ladder as two vectors, *left* and *right*, both the same length, containing the *y* coordinates of the endpoints, sorted in ascending order. Here’s some sample data, giving the *y* coordinates in ascending order, bounded by 0 at the bottom and 100 at the top:

(define left '(0 1 4 9 16 25 36 49 64 81 100)) (define right '(0 3 14 15 23 24 25 49 57 92 100))

We have 11 rungs on the ladder, including top and bottom, and we need the slope and intercept of each line. Normally the formula for computing the slope of a line given two points on the line is (*y*_{2} − *y*_{1}) / (*x*_{2} − *x*_{1}), but since the *x* coordinates of our ladder are 0 and 1, the slope reduces to the height of the right end of the rung minus the height of the left end of the rung. The *y*-intercept of the rung is even easier to compute: since the left side of the ladder is the *y* axis, the intercept is just the height of the left end of the rung:

(define slopes (map (lambda (left right) (- right left)) left right))

(define intercepts left)

> slopes (0 2 10 6 7 -1 -11 0 -7 11 0) > intercepts (0 1 4 9 16 25 36 49 64 81 100)

To determine if a target point (*x*, *y*) is above or below a line, we compute the *y*-value of the line at the target *x*, then compare to the target *y*:

(define (lt? idx x y) (let ((slope (list-ref slopes idx)) (intercept (list-ref intercepts idx))) (positive? (- (+ (* slope x) intercept) y))))

For instance, target point (0.5, 50) is between lines 7 and 8 (the rung from 49 to 49 and the rung from 64 to 57):

> (lt? 7 0.5 50) #f > (lt? 8 0.5 50) #t

Now we can find the desired interval by binary search:

(define (ladder x y) (when (or (lt? 0 x y) (not (lt? 10 x y))) (error 'ladder "out of bounds")) (let loop ((lo 0) (hi (- (length left) 1))) (let ((mid (quotient (+ lo hi) 2))) (cond ((= (- hi lo) 1) (values lo hi)) ((lt? mid x y) (loop lo mid)) (else (loop mid hi))))))

Here are some examples:

> (ladder 0.5 50) 7 8 > (ladder 0.25 25) 5 6

You can run the program at http://ideone.com/QP8BGS.

Pages: 1 2

Binary search is where I tend to make the relevant assumptions explicit as comments, as below (in Julia). Otherwise I keep getting something off by one or some condition accidentally reversed.

I had two typos in my test code on the first run. I had also written the test invocations to expect zero-based indexes, so the correct one-based indexes were reported as off-by one on that first run :)

My function returns only the lower-rung index. The corresponding upper-rung index is the next integer.

In Python using the bisect module for the search. As bisect needs a list, the class LazyRungs is used, that behaves like a list and only calculates the y-value when needed.