Python: how to compute date ranges from a list of dates?

I have a list of dates, for example:

['2011-02-27', '2011-02-28', '2011-03-01', '2011-04-12', '2011-04-13', '2011-06-08']

How do I find the contiguous date ranges contained within those dates? In the above exam开发者_StackOverflow中文版ple, the ranges should be:

[{"start_date": '2011-02-27', "end_date": '2011-03-01'},
 {"start_date": '2011-04-12', "end_date": '2011-04-13'},
 {"start_date": '2011-06-08', "end_date": '2011-06-08'}
]

Thanks.

---

This works, but I'm not happy with it, will work on a cleaner solution an edit the answer. Done, here is a clean, working solution:

import datetime
import pprint

def parse(date):
    return datetime.date(*[int(i) for i in date.split('-')])

def get_ranges(dates):
    while dates:
        end = 1
        try:
            while dates[end] - dates[end - 1] == datetime.timedelta(days=1):
                end += 1
        except IndexError:
            pass

        yield {
            'start-date': dates[0],
            'end-date': dates[end-1]
        }
        dates = dates[end:]

dates = [
    '2011-02-27', '2011-02-28', '2011-03-01',
    '2011-04-12', '2011-04-13',
    '2011-06-08'
]

# Parse each date and convert it to a date object. Also ensure the dates
# are sorted, you can remove 'sorted' if you don't need it
dates = sorted([parse(d) for d in dates]) 

pprint.pprint(list(get_ranges(dates)))

And the relative output:

[{'end-date': datetime.date(2011, 3, 1),
  'start-date': datetime.date(2011, 2, 27)},
 {'end-date': datetime.date(2011, 4, 13),
  'start-date': datetime.date(2011, 4, 12)},
 {'end-date': datetime.date(2011, 6, 8),
  'start-date': datetime.date(2011, 6, 8)}]

---

Attempting to ninja GaretJax's edit: ;)

def date_to_number(date):
  return datetime.date(*[int(i) for i in date.split('-')]).toordinal()

def number_to_date(number):
  return datetime.date.fromordinal(number).strftime('%Y-%m-%d')

def day_ranges(dates):
  day_numbers = set(date_to_number(d) for d in dates)
  start = None
  # We loop including one element guaranteed not to be in the set, to force the
  # closing of any range that's currently open.
  for n in xrange(min(day_numbers), max(day_numbers) + 2):
    if start == None:
      if n in day_numbers: start = n
    else:
      if n not in day_numbers: 
        yield {
          'start_date': number_to_date(start),
          'end_date': number_to_date(n - 1)
        }
        start = None

list(
  day_ranges([
    '2011-02-27', '2011-02-28', '2011-03-01',
    '2011-04-12', '2011-04-13', '2011-06-08'
  ])
)

---

from datetime import datetime, timedelta

dates = ['2011-02-27', '2011-02-28', '2011-03-01', '2011-04-12', '2011-04-13', '2011-06-08']
d = [datetime.strptime(date, '%Y-%m-%d') for date in dates]
test = lambda x: x[1] - x[0] != timedelta(1)
slices = [0] + [i+1 for i, x in enumerate(zip(d, d[1:])) if test(x)] + [len(dates)]
ranges = [{"start_date": dates[s], "end_date": dates[e-1]} for s, e in zip(slices, slices[1:])]

Results in the following:

>>> pprint.pprint(ranges)
[{'end_date': '2011-03-01', 'start_date': '2011-02-27'},
 {'end_date': '2011-04-13', 'start_date': '2011-04-12'},
 {'end_date': '2011-06-08', 'start_date': '2011-06-08'}]

The slices list comprehension gets all indices at which the previous date is not one day before the current date. Add 0 to the front and len(dates) to the end and each range of dates can be described as dates[slices[i]:slices[i+1]-1].

---

My slight variation on the theme (I originally built start/end lists and zipped them to return tuples, but I preferred @Karl Knechtel's generator approach):

from datetime import date, timedelta

ONE_DAY = timedelta(days=1)

def find_date_windows(dates):
    # guard against getting empty list
    if not dates:
        return

    # convert strings to sorted list of datetime.dates
    dates = sorted(date(*map(int,d.split('-'))) for d in dates)

    # build list of window starts and matching ends
    lastStart = lastEnd = dates[0]
    for d in dates[1:]:
        if d-lastEnd > ONE_DAY:
            yield {'start_date':lastStart, 'end_date':lastEnd}
            lastStart = d
        lastEnd = d
    yield {'start_date':lastStart, 'end_date':lastEnd}

Here are the test cases:

tests = [
    ['2011-02-27', '2011-02-28', '2011-03-01', '2011-04-12', '2011-04-13', '2011-06-08'],
    ['2011-06-08'],
    [],
    ['2011-02-27', '2011-02-28', '2011-03-01', '2011-04-12', '2011-04-13', '2011-06-08', '2011-06-10'],
]
for dates in tests:
    print dates
    for window in find_date_windows(dates):
        print window
    print

Prints:

['2011-02-27', '2011-02-28', '2011-03-01', '2011-04-12', '2011-04-13', '2011-06-08']
{'start_date': datetime.date(2011, 2, 27), 'end_date': datetime.date(2011, 3, 1)}
{'start_date': datetime.date(2011, 4, 12), 'end_date': datetime.date(2011, 4, 13)}
{'start_date': datetime.date(2011, 6, 8), 'end_date': datetime.date(2011, 6, 8)}

['2011-06-08']
{'start_date': datetime.date(2011, 6, 8), 'end_date': datetime.date(2011, 6, 8)}

[]

['2011-02-27', '2011-02-28', '2011-03-01', '2011-04-12', '2011-04-13', '2011-06-08', '2011-06-10']
{'start_date': datetime.date(2011, 2, 27), 'end_date': datetime.date(2011, 3, 1)}
{'start_date': datetime.date(2011, 4, 12), 'end_date': datetime.date(2011, 4, 13)}
{'start_date': datetime.date(2011, 6, 8), 'end_date': datetime.date(2011, 6, 8)}
{'start_date': datetime.date(2011, 6, 10), 'end_date': datetime.date(2011, 6, 10)}

---

Here is an alternative solution: It returns a list tuples of (start,finish), as that's what I needed ;).

This mutates the list, so I needed to make a copy. Obviously, that increases the memory usage. I suspect that list.pop() is not super-efficient, but that probably depends on the implementation of list in python.

def collapse_dates(date_list):
    if not date_list:
        return date_list
    result = []
    # We are going to alter the list, so create a (sorted) copy.
    date_list = sorted(date_list)
    while len(date_list):
        # Grab the first item: this is both the start and end of the range.
        start = current = date_list.pop(0)
        # While the first item in the list is the next day, pop that and
        # set it to the end of the range.
        while len(date_list) and date_list[0] == current + datetime.timedelta(1):
            current = date_list.pop(0)
        # That's a completed range.
        result.append((start,current))

    return result

You could easily change the append line to append a dict, or yield instead of appending to a list.

Oh, and mine assumes they are already dates.