« | » Main « | »

Range overlap in two compares

Saturday 12 October 2013

I was helping a co-worker with a quick hackathon project (patch-juggler, which will hopefully grow into an interactive rebase GUI), and he had a function to determine whether two ranges overlap.

His code used eight comparisons to check whether the endpoint of one of the ranges was contained within the other range. In Python it would look like this:

def overlap(start1, end1, start2, end2):
    """Does the range (start1, end1) overlap with (start2, end2)?"""
    return (
        start1 <= start2 <= end1 or
        start1 <= end2 <= end1 or
        start2 <= start1 <= end2 or
        start2 <= end1 <= end2

I said you could do it in two comparisons rather than eight, but could never remember the trick.

Looking online, I found this great explanation on Stack Overflow. I'll restate it in my own words:

Instead of thinking about how overlapping ranges might relate, consider what conditions have to be true for the ranges not to overlap. It's much simpler: either range1 is entirely less than range2, or range1 is entirely greater than range2.

Since the ranges are ordered (start <= end), range1 less than range2 is true if end1 < start2. Similarly range1 greater than range2 can be determined with end2 < start1.

So we can check for non-overlapping ranges with two compares. Inverting the result tells us whether they overlap:

def overlap(start1, end1, start2, end2):
    """Does the range (start1, end1) overlap with (start2, end2)?"""
    return not (end1 < start2 or end2 < start1)

De Morgan's laws mean that we can change it to this:

def overlap(start1, end1, start2, end2):
    """Does the range (start1, end1) overlap with (start2, end2)?"""
    return end1 >= start2 and end2 >= start1

Just looking at this final code, it's hard to see the logic. It's even harder to think about it without holding out two fingers on each hand and waving them around to picture overlapping ranges! But with the reasoning about non-overlapping ranges, it makes perfect sense.

This is one of those programming nuggets that makes me happy, I can't explain why.

What's in which Python 3?

Tuesday 8 October 2013

Two years ago I wrote a post called What's in which Python? which summarized the changes in the Python 2.x releases. Today when I showed it to someone, they asked, "Do you have one for 3.x?"

Here it is. Some things to remember about Python 3:

  • 3.0 came out about the same time as 2.6, so they share a number of features. 2.7 came out between 3.1 and 3.2, so there's overlap there as well.
  • A language moratorium prevented significant changes in 3.2.

3.0: December 3rd, 2008

  • strings are now unicode, no u"" literals
  • print as a function
  • iterators instead of lists: range, .keys, .items, .values, zip, map, filter
  • nonlocal
  • function annotations
  • lots of things moved in the standard library

Full list of 3.0 changes.

3.1: June 27th, 2009

  • OrderedDict and Counter classes
  • __main__.py

Full list of 3.1 changes.

3.2: February 20th, 2011

  • argparse
  • concurrent.futures
  • __pycache__ directories
  • hasattr doesn't swallow all exceptions

Full list of 3.2 changes.

3.3: September 29th, 2012

  • yield from
  • u"" literals are back
  • unittest.mock
  • hash randomization
  • New flexible string representation
  • venv module
  • more of import implemented in Python

Full list of 3.3 changes.

Coverage.py 3.7

Sunday 6 October 2013

The latest version of coverage.py has just hit PyPI: coverage.py v3.7. This is mostly a bug fix release, but I also added a few new minor behavior changes.

Details of the changes are in the change log.

This will be the last version numbered 3.x. The next version will be 4.0, and will drop support for older Pythons (<2.6), old interfaces that aren't used any more, etc.

Finding stale pyc files

Thursday 3 October 2013

Recently I was debugging one of those "it can't happen" kinds of problems, and wanted to make sure I didn't have any stale .pyc files lying around. I figured the "find" command could find pairs of files whose dates compared incorrectly, but I didn't know how to do it.

I asked in the #bash IRC channel, and they gave me this:

find . -name '*.pyc' -exec bash -c 'test "$1" -ot "${1%c}"' -- {} \; -print  #stalepyc

It's one of those Unix-isms I wont be able to remember (yet?), so I'll leave it here to find again when I need it later.

Notice I've added a bashtag to it so I can search for it in my command history. (I wish I had come up that name!).

I'm sure there are other ways to find stale files, maybe even better ones?

« | » Main « | »