Ladder Range

July 25, 2017

Once a year, or thereabouts, I pick up Jon Bentley’s book Programming Pearls and read a random chapter; even though I’ve read it before, re-reading always makes the material seem fresh. Today’s exercise is Exercise 7 from Chapter 4 about binary search:

A colleague faced the following problem in a program to draw lines on a bit-mapped display. An array of n pairs of reals (ai, bi) defined the n lines y = mi x +
bi. The lines were ordered in the x-interval [0, 1] in the sense that yi < yi+1 for all values of i between 0 and n − 2 and all values of x in [0, 1].

[ Here Bentley has a picture of a ladder with rungs at various angles to the horizontal. We won’t reproduce it here; get the book if you want to see it. ]

Less formally, the lines don’t touch in the vertical slab. Given a point (x, y), where 0 ≤ x ≤ 1, he wanted to determine the two lines that bracket the point. How could he solve the problem quickly?

Your task is to write a program to solve Bentley’s exercise. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
2 Comments »

2 Responses to “Ladder Range”

  1. Jussi Piitulainen said
    July 25, 2017 at 2:46 PM

    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
    July 27, 2017 at 7:14 AM

    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 comment