How to reduce lists of ranges ?

Question

Given a list of ranges ie: 1-3,5,6-4,31,9,19,10,25-20 how can i reduce it to 1-6,9-10,19-25,31 ?

Here is what i've done so far, it seems a little bit complicated, so is there any simpler/clever method to do this.

$in = '1-3,5,6-4,31,9,19,10,25-20';
// Explode the list in ranges
$rs = explode(',', $in);
$tmp = array();
// for each range of the list
foreach($rs as $r) {
    // find the start and end date of the range
    if (preg_match('/(\d+)-(\d+)/', $r, $m)) {
        $start = $m[1];
        $end = $m[2];
    } else {
        // If only one date
        $start = $end = $r;
    }
    // flag each date in an array
    foreach(range($start,$end) as $i) {
        $tmp[$i] = 1;
    }
}
$str = '';
$prev = 999;
// for each date of a month (1-31)
for($i=1; $i<32; $i++) {
    // is this date flaged ?
    if (isset($tmp[$i])) {
        // is output string empty ?
        if ($str == '') {
            $str = $i;
        } else {
            // if the previous date is less than the current minus 1
            if ($i-1 > $prev) {
                // build the new range
                $str .= '-'.$prev.','.$i;
            }
        }
        $prev = $i;
    }
}
// build the last range
if ($i-1 > $prev) {
    $str .= '-'.$prev;
}
echo "str=$str\n";

NB: it must run under php 5.1.6 (i can't upgrade).

FYI : the numbers represent days of month so they are limited to 1-31.

Edit:

From a given range of dates (1-3,6,7-8), i'd like obtain another list (1-3,6-8) where all the ranges are recalculated and ordered.

Answer 1

You just have to search your data to get what you want. Split the input on the delimiter, in your case ','. Then sort it somehow, this safes you searching left from the current position. Take you first element, check whether it's a range and use the highest number in this range (3 out of 1-3 range or 3 if 3 is a single element) for further comparisions. Then take the 2nd element in your list and check if it's a direct successor of the last element. If yes combine the 1st and 2nd elements/range to a new range. Repeat.

Edit: I'm not sure about PHP but a regular expression is a bit overkill for this problem. Just look for a '-' in your exploded array, then you know it's a range. Sorting the exp. array safes you the backtracking, the stuff you are doing with $prev. You could also explode every element in the exploded array on '-' and check if the resulting array has a size > 1 to learn whether an element is a range or not.

Answer 2

Perhaps not the most efficient, but shouldn't be too bad with the limited range of values you're working with:

$in = '1-3,5,6-4,31,9,19,10,25-20';

$inSets = explode(',',$in);
$outSets = array();
foreach($inSets as $inSet) {
    list($start,$end) = explode('-',$inSet.'-'.$inSet);
    $outSets = array_merge($outSets,range($start,$end));
}
$outSets = array_unique($outSets);
sort($outSets);

$newSets = array();
$start = $outSets[0];
$end = -1;
foreach($outSets as $outSet) {
    if ($outSet == $end+1) {
        $end = $outSet;
    } else {
        if ($start == $end) {
            $newSets[] = $start;
        } elseif($end > 0) {
            $newSets[] = $start.'-'.$end;
        }
        $start = $end = $outSet;
    }
}
if ($start == $end) {
    $newSets[] = $start;
} else {
    $newSets[] = $start.'-'.$end;
}
var_dump($newSets);
echo '<br />';

Answer 3

Looking at the problem from an algorithmic stand-point, let's consider the limitations that you've put on the problem. All numbers will be from 1-31. The list is a collection of "ranges", each of which is defined by two numbers (start and end). There is no rule for whether start will be more, less than, or equal to end.

Since we have an arbitrarily large list of ranges but a definite means of sorting/organizing these, a divide and conquer strategy may yield the best complexity.

At first I typed out a very long and careful explanation of how I created each step in this algorithm (the dividing portion, the conquering potion, optimizations, etc.) however the explanation got extremely long. To shorten it, here's the final answer:

<?php
   $ranges = "1-3,5,6-4,31,9,19,10,25-20";
   $range_array = explode(',', $ranges);
   $include = array();
   foreach($range_array as $range){
       list($start, $end) = explode('-', $range.'-'.$range); //"1-3-1-3" or "5-5"
       $include = array_merge($include, range($start, $end));
   }
   $include = array_unique($include);
   sort($include);
   $new_ranges = array();
   $start = $include[0];
   $count = $start;
   // And begin the simple conquer algorithm
   for( $i = 1; $i < count($include); $i++ ){
       if( $include[$i] != ($count++) ){
           if($start == $count-1){
               $new_ranges[] = $start;
           } else {
               $new_ranges[] = $start."-".$count-1;
           }
           $start = $include[$i];
           $count = $start;
       }
   }
   $new_ranges = implode(',', $new_ranges);
?>

This should (theoretically) work on arrays of arbitrary length for any positive integers. Negative integers would get tripped up since - is our delimiter for the range.