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 (y2y1) / (x2x1), 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.

Advertisements

Pages: 1 2

2 Responses to “Ladder Range”

  1. Jussi Piitulainen said

    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.

    module Ladder
    
    export findlower
    
    function findlower(ladder, x, y)
        n = length(ladder)
        # (x, y) is above (or on) rung 1
        # (x, y) is below rung n
        b, e = 1, n
        while b + 1 < e 
            # (x, y) is above (or on) rung b
            # (x, y) is below rung e
            m = b + div(e - b, 2)
            # b < m < e
            # (m is half-way between b and e)
            k, c = ladder[m]
            if y < k * x + c
                # (x, y) is below rung m
                e = m
            else
                # (x, y) is above (or on) rung m
                b = m
            end
        end
        # b + 1 == e
        # (x, y) is above (or on) rung b
        # (x, y) is below rung e
        b
    end
    
    end
    
    using Ladder
    
    # Praxis test slopes and intercepts but as Float64
    ladder = collect(zip((0., 2., 10., 6., 7., -1., -11., 0., -7., 11., 0.),
                         (0., 1., 4., 9., 16., 25., 36., 49., 64., 81., 100.)))
    
    println("Testing Praxis points (but Julia indexing is 1-based):")
    println("expecting 8, observing ", findlower(ladder, 0.5, 50.))
    println("expecting 6, observing ", findlower(ladder, 0.25, 25.))
    println()
    println("Testing a point on the third rung:")
    k, c = ladder[3]
    println("expecting 3, observing ", findlower(ladder, 0.2, k * 0.2 + c))
    
  2. Paul said

    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.

    from bisect import bisect_left as bisect
    class LazyRungs(object):
        'rungs is a list of tuples (left, right)'
        def __init__(self, rungs, x):
            self.rungs = rungs
            self.x = x
        def __len__(self): return len(self.rungs)
        def __getitem__(self, i):
            (left, right), x = rungs[i], self.x
            return left * (1-x) + right * x
    
    def ladder(x, y, rungs):
        'return 2 bracketing rungs (a, b), such that a < y <= b'
        i = bisect(LazyRungs(rungs, x), y)  # i is the index such that rungs[i] >= y
        if not 0 < i < len(rungs):
            raise ValueError("(x,y) outside range")
        return i-1, i
    
    left = map(int, '0 1 4 9 16 25 36 49 64 81 100'.split())
    right = map(int, '0 3 14 15 23 24 25 49 57 92 100'.split())
    rungs = list(zip(left, right))
    print(ladder(0.5, 50, rungs))  # (7, 8)
    print(ladder(0.25, 25, rungs)) # (5, 6)
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: