BBQ and range finding code

The other day we had a very nice oriental-style BBQ at my place. Susi made a Couscous salad, while I made some hummus, a bell pepper salad, a salsa with Habanero chilis, and some marinated olives. On the meaty side, we had lamb chops and chicken wings. Very nice food indeed!

The evening ended with us all sitting still in the semi-dark of my terrace watching out for shooting stars. And we even saw some. Even one, which we will remember forever 😉

In the other life (work), I’ve written an algorithm for finding the bordering elements of contiguous ranges in a given array of ordered values. I’ve used rapid prototyping in Python before transferring the solution to C++. The Python code goes like this:

n = [1, 2, 3, 4, 5, 6, 7,    9, 10, 11, 12,      14, 15, 16]
end = len(n) - 1

ranges = []

def get_right(left, step):
    if left == end:
        return left
    leftmost_r = None
    i = last_i = end
    while True:
        match = n[i] - n[left] == i - left
        if (i == end and match) or i == leftmost_r:
            return last_i
        last_i = i 
        if match:
            i += step
            leftmost_r = i
            i -= step
        if step != 1:
            step /= 2

left = 0
while True:
    right = get_right(left, (len(n) - left) / 2)
    ranges.append((n[left], n[right]))
    if right == end:
        left = right + 1

The basic assumption for the algorithm to work is that n contains sorted values. This allows us to do a kind of binary search, if the currently looked at range (from left to i) does not fit the criterion for a match (namely that n[i] - n[left] != i - left). Maybe this is useful for someone!


NP: Agnostic Front – Gotta go