Funky Algorithm Logic, Take a Shot :)

dbo · February 15, 2008

I've inherited some ugly code, yay for me. Like most ugly code this particular chunk has a bug in it that I can't seem to track down, and because it's so ugly I think it's just worth rewriting. So I set out to rewrite it thinking that it would be pretty quick and easy, but the logic gets tricky pretty fast. I thought I'd throw out the problem and see if any of you cared to take a stab at it while I did. I'd really appreciate it.

Please spare me comments about the freelance forum. I know where it is and if that's you're take, I respect that. But please kindly move along rather than posting.

So here's the problem. Basically given an array of dates, sorted in ascending order I would like to return a string representation. The display should look something like this:

February 3, 6, 8-15, 24 March 2, 3, 4-8 2007

So you've got to take into account single dates, date ranges (if the month and year are the same, etc). It gets pretty tricky.

In the case of something like this: February 25-28 March 1-4 should be displayed rather than February 25-4.

I'll be hitting it hard very shortly myself. If anyone who is up for the challenge have any more questions, by all means ask. I can also paste the ugly code if someone wants to see how ugly we're talking

laffin · February 15, 2008

Its not hard as u think. just have to keep track of previous Y-m-d and the one currently being operated on

dbo · February 15, 2008

Yes I know this.

I spent about 2 hours on it last time trying to debug. I think I was close... we put things on hold since it was sort of a special case and the bug seemed to have disappeared. As luck would have it I deleted the source code I was working on about 3 days ago... if no one has any insight, I'm about to start from scratch, which will probably be a good thing. It will let me attack it with a clean mind.

dbo · February 15, 2008

This isn't working, but I thought if I through some of my code up maybe someone would be willing to help work through it.

EDIT: Code slightly modified due to an oversight I discovered. More debugging in order

<?php

function getMonth($intMonth)
{
   return date("M", mktime(0, 0, 0, $intMonth, 1, 2000));
}

function getDateRangeString($arrDates, $strDelimiter)
{
   $strRv = "";
   $blnRange = false;
      
   $intLen = count($arrDates);
   for( $i = 0; $i < $intLen; ++$i )
   {
      //Grab the individual parts of the current date to process
      $arrCurrent = explode($strDelimiter, $arrDates[$i]);
      $intCurrentMonth = $arrCurrent[0];
      $intCurrentDay = $arrCurrent[1];
      $intCurrentYear = $arrCurrent[2];
      
      //Initialize the return string if this is the first date
      if( $i == 0 )
      {
         $strRv = getMonth($intCurrentMonth);
         $strRv .= (" " . $intCurrentDay);
      }
      else
      {
         //Grab the individual parts from the previous date
         $arrPrevious = explode($strDelimiter, $arrDates[$i-1]);
         $intPreviousMonth = $arrPrevious[0];
         $intPreviousDay = $arrPrevious[1];
         $intPreviousYear = $arrPrevious[2];
         
         //If the years are different we need to switch to the next year
         if( $intCurrentYear != $intPreviousYear )
         {
            //If we were in the middle of a date range, we need to close the range before adding the year and starting the next month
            if( $blnRange )
            {
               $strRv .= ("-" . $intPreviousDay);
            }
            
            $strRv .= (" " . $intPreviousYear); 
            $strRv .= (" " . getMonth($intCurrentMonth));
            $blnRange = false;
         }
         
         //If the months are different we need to switch to the next month
         if( $intCurrentMonth != $intPreviousMonth )
         {
            //If we were in the middle of a date range, we need to close the range before adding the year
            if( $blnRange )
            {
               $strRv .= ("-" . $intPreviousDay);
            }
            
            $strRv .= (" " . getMonth($intPreviousMonth));
            $blnRange = false;
         }
         
         //Determine if we have a consecutive range of dates
         if( ($intCurrentDay-1) == $intPreviousDay )
         {
            $blnRange = true;
         }
         else
         {
            $strRv .= (" " . $intCurrentDay . ", ");
         }
      }
      
      //Make sure we add the year if this is our last date
      if( ($i+1) == $intLen )
      {
         $strRv .= (" " . $intCurrentYear);
      }
   }
   
   return $strRv;   
}

$arrDates = Array("02/1/2007", "02/2/2007");
echo getDateRangeString($arrDates, "/");

?>

?>

dbo · February 15, 2008

Here's the latest and greatest code. The first 3 test cases seem to be working. The forth bombs.

<?php

function getMonth($intMonth)
{
   return date("M", mktime(0, 0, 0, $intMonth, 1, 2000));
}

function getDateRangeString($arrDates, $strDelimiter)
{
   $strRv = "";
   $blnRange = false;
      
   $intLen = count($arrDates);
   for( $i = 0; $i < $intLen; ++$i )
   {
      //Grab the individual parts of the current date to process
      $arrCurrent = explode($strDelimiter, $arrDates[$i]);
      $intCurrentMonth = $arrCurrent[0];
      $intCurrentDay = $arrCurrent[1];
      $intCurrentYear = $arrCurrent[2];
      
      //Initialize the return string if this is the first date
      if( $i == 0 )
      {
         $strRv = getMonth($intCurrentMonth);
         $strRv .= (" " . $intCurrentDay);
      }
      else
      {
         //Grab the individual parts from the previous date
         $arrPrevious = explode($strDelimiter, $arrDates[$i-1]);
         $intPreviousMonth = $arrPrevious[0];
         $intPreviousDay = $arrPrevious[1];
         $intPreviousYear = $arrPrevious[2];
         
         //If the years are different we need to switch to the next year
         if( $intCurrentYear != $intPreviousYear )
         {
            //If we were in the middle of a date range, we need to close the range before adding the year and starting the next month
            if( $blnRange )
            {
               $strRv .= ("-" . $intPreviousDay);
            }
            
            $strRv .= (" " . $intPreviousYear); 
            $strRv .= (" " . getMonth($intCurrentMonth));
            $blnRange = false;
         }
         
         //If the months are different we need to switch to the next month
         if( $intCurrentMonth != $intPreviousMonth )
         {
            //If we were in the middle of a date range, we need to close the range before adding the year
            if( $blnRange )
            {
               $strRv .= ("-" . $intPreviousDay);
            }
            
            $strRv .= (" " . getMonth($intPreviousMonth));
            $blnRange = false;
         }
         
         //Determine if we have a consecutive range of dates
         if( ($intCurrentDay-1) == $intPreviousDay )
         {
            $blnRange = true;
         }
         else
         {
            $strRv .= ("-" . $intPreviousDay . ",");
            $strRv .= (" " . $intCurrentDay);
            $blnRange = false;
         }
      }
      
      //Make sure we add the year if this is our last date
      if( ($i+1) == $intLen )
      {
         //Make sure we add in the current day if we were still in a range
         if( $blnRange )
         {
            $strRv .= ("-" . $intCurrentDay . ", ");
         }
      
         //Make sure we add the year if this is our last date
         $strRv .= (" " . $intCurrentYear);
      }
   }
   
   return $strRv;   
}

echo "<b>Test Case 1</b><br />";
$arrDates = Array();
$arrDates = Array("02/1/2007", "02/2/2007");
echo getDateRangeString($arrDates, "/");

echo "<br /><br /><b>Test Case 2</b><br />";
$arrDates = Array();
$arrDates = Array("02/1/2007", "02/2/2007", "02/3/2007");
echo getDateRangeString($arrDates, "/");

echo "<br /><br /><b>Test Case 3</b><br />";
$arrDates = Array();
$arrDates = Array("02/1/2007", "02/2/2007", "02/3/2007", "02/5/2007");
echo getDateRangeString($arrDates, "/");

echo "<br /><br /><b>Test Case 4</b><br />";
$arrDates = Array();
$arrDates = Array("02/1/2007", "02/2/2007", "02/3/2007", "02/5/2007", "03/1/2007");
echo getDateRangeString($arrDates, "/");

?>

aschk · February 15, 2008

Ok so let me get this straight.

You want to input two dates (e.g. 12/02/2007 & 15/02/2007) and return a string range (e.g. 12-15 February 2007) ?

dbo · February 15, 2008

No, because those two dates are not consecutive. Only consecutive dates should appear like that. In your example it should be:

Feb 12, 15 2007

dbo · February 15, 2008

Okay, here is the latest code. This one appears to be working for all of the current test cases. Going to get a little more creative now to see if it breaks. I suspect the new year will break it.

<?php

function getMonth($intMonth)
{
   return date("M", mktime(0, 0, 0, $intMonth, 1, 2000));
}

function getDateRangeString($arrDates, $strDelimiter)
{
   $strRv = "";
   $blnRange = false;
      
   $intLen = count($arrDates);
   for( $i = 0; $i < $intLen; ++$i )
   {
      //Grab the individual parts of the current date to process
      $arrCurrent = explode($strDelimiter, $arrDates[$i]);
      $intCurrentMonth = $arrCurrent[0];
      $intCurrentDay = $arrCurrent[1];
      $intCurrentYear = $arrCurrent[2];
      
      //Initialize the return string if this is the first date
      if( $i == 0 )
      {
         $strRv = getMonth($intCurrentMonth);
         $strRv .= (" " . $intCurrentDay);
      }
      else
      {
         //Grab the individual parts from the previous date
         $arrPrevious = explode($strDelimiter, $arrDates[$i-1]);
         $intPreviousMonth = $arrPrevious[0];
         $intPreviousDay = $arrPrevious[1];
         $intPreviousYear = $arrPrevious[2];
         
         //If the years are different we need to switch to the next year
         if( $intCurrentYear != $intPreviousYear )
         {
            //If we were in the middle of a date range, we need to close the range before adding the year and starting the next month
            if( $blnRange )
            {
               $strRv .= ("-" . $intPreviousDay);
            }
            
            $strRv .= (" " . $intPreviousYear); 
            $strRv .= (" " . getMonth($intCurrentMonth));
            $strRv .= (" " . $intCurrentDay);
            $blnRange = false;
         }
         
         //If the months are different we need to switch to the next month
         if( $intCurrentMonth != $intPreviousMonth )
         {
            //If we were in the middle of a date range, we need to close the range before adding the year
            if( $blnRange )
            {
               $strRv .= ("-" . $intPreviousDay);
            }
            
            $strRv .= (" " . getMonth($intCurrentMonth));
            $strRv .= (" " . $intCurrentDay);
            $blnRange = false;
         }
         
         //Determine if we have a consecutive range of dates
         if( $intCurrentMonth == $intPreviousMonth && ($intCurrentDay-1) == $intPreviousDay )
         {
            $blnRange = true;
         }
         else if( $intCurrentMonth == $intPreviousMonth )
         {
            $strRv .= ("-" . $intPreviousDay . ",");
            $strRv .= (" " . $intCurrentDay);
            $blnRange = false;
         }
      }
      
      //Make sure we add the year if this is our last date
      if( ($i+1) == $intLen )
      {
         //Make sure we add in the current day if we were still in a range
         if( $blnRange )
         {
            $strRv .= ("-" . $intCurrentDay . ", ");
         }
      
         //Make sure we add the year if this is our last date
         $strRv .= (" " . $intCurrentYear);
      }
   }
   
   return $strRv;   
}

echo "<b>Test Case 1</b><br />";
$arrDates = Array();
$arrDates = Array("02/1/2007", "02/2/2007");
echo getDateRangeString($arrDates, "/");

echo "<br /><br /><b>Test Case 2</b><br />";
$arrDates = Array();
$arrDates = Array("02/1/2007", "02/2/2007", "02/3/2007");
echo getDateRangeString($arrDates, "/");

echo "<br /><br /><b>Test Case 3</b><br />";
$arrDates = Array();
$arrDates = Array("02/1/2007", "02/2/2007", "02/3/2007", "02/5/2007");
echo getDateRangeString($arrDates, "/");

echo "<br /><br /><b>Test Case 4</b><br />";
$arrDates = Array();
$arrDates = Array("02/1/2007", "02/2/2007", "02/3/2007", "02/5/2007", "03/1/2007");
echo getDateRangeString($arrDates, "/");

echo "<br /><br /><b>Test Case 5</b><br />";
$arrDates = Array();
$arrDates = Array("02/1/2007", "02/2/2007", "02/3/2007", "02/5/2007", "03/1/2007", "03/2/2007", "03/27/2007");
echo getDateRangeString($arrDates, "/");

?>

aschk · February 15, 2008

Right i think i get it now, if you provide

array("12/02/07","13/02/07","14/02/07","17/02/07","20/02/07","21/02/07");

you want "12-14, 17, 20-21 Feb 2007"

dbo · February 15, 2008

Yes. You got it.

I think things are working as expected now. I should update my comments a bit given some of the changes though. Also note the format I'm using for the dates: (m/d/y) (sorry I'm one of those stupid Americans...).

If anyone would be willing to add in some more test cases (provided at the bottom of the script) to see if anything weird happens I'd appreciate it. Also, I'd still be open to any solutions that are more elegant than this one.

<?php

function getMonth($intMonth)
{
   return date("M", mktime(0, 0, 0, $intMonth, 1, 2000));
}

function getDateRangeString($arrDates, $strDelimiter)
{
   $strRv = "";
   $blnRange = false;
      
   $intLen = count($arrDates);
   for( $i = 0; $i < $intLen; ++$i )
   {
      //Grab the individual parts of the current date to process
      $arrCurrent = explode($strDelimiter, $arrDates[$i]);
      $intCurrentMonth = $arrCurrent[0];
      $intCurrentDay = $arrCurrent[1];
      $intCurrentYear = $arrCurrent[2];
      
      //Initialize the return string if this is the first date
      if( $i == 0 )
      {
         $strRv = getMonth($intCurrentMonth);
         $strRv .= (" " . $intCurrentDay);
      }
      else
      {
         //Grab the individual parts from the previous date
         $arrPrevious = explode($strDelimiter, $arrDates[$i-1]);
         $intPreviousMonth = $arrPrevious[0];
         $intPreviousDay = $arrPrevious[1];
         $intPreviousYear = $arrPrevious[2];
         
         //If the years are different we need to switch to the next year
         if( $intCurrentYear != $intPreviousYear )
         {
            //If we were in the middle of a date range, we need to close the range before adding the year and starting the next month
            if( $blnRange )
            {
               $strRv .= ("-" . $intPreviousDay);
            }
            
            $strRv .= (" " . $intPreviousYear); 
            $strRv .= (" " . getMonth($intCurrentMonth));
            $strRv .= (" " . $intCurrentDay);
            $blnRange = false;
         }
         
         //If the months are different we need to switch to the next month
         if( $intCurrentYear == $intPreviousYear && $intCurrentMonth != $intPreviousMonth )
         {
            //If we were in the middle of a date range, we need to close the range before adding the year
            if( $blnRange )
            {
               $strRv .= ("-" . $intPreviousDay);
            }
            
            $strRv .= (" " . getMonth($intCurrentMonth));
            $strRv .= (" " . $intCurrentDay);
            $blnRange = false;
         }
         
         //Determine if we have a consecutive range of dates
         if( $intCurrentYear == $intPreviousYear && $intCurrentMonth == $intPreviousMonth && ($intCurrentDay-1) == $intPreviousDay )
         {
            $blnRange = true;
         }
         else if( $intCurrentYear == $intPreviousYear && $intCurrentMonth == $intPreviousMonth )
         {
            $strRv .= ("-" . $intPreviousDay . ",");
            $strRv .= (" " . $intCurrentDay);
            $blnRange = false;
         }
      }
      
      //Make sure we add the year if this is our last date
      if( ($i+1) == $intLen )
      {
         //Make sure we add in the current day if we were still in a range
         if( $blnRange )
         {
            $strRv .= ("-" . $intCurrentDay . ", ");
         }
      
         //Make sure we add the year if this is our last date
         $strRv .= (" " . $intCurrentYear);
      }
   }
   
   return $strRv;   
}

echo "<b>Test Case 1</b><br />";
$arrDates = Array();
$arrDates = Array("02/1/2007", "02/2/2007");
echo getDateRangeString($arrDates, "/");

echo "<br /><br /><b>Test Case 2</b><br />";
$arrDates = Array();
$arrDates = Array("02/1/2007", "02/2/2007", "02/3/2007");
echo getDateRangeString($arrDates, "/");

echo "<br /><br /><b>Test Case 3</b><br />";
$arrDates = Array();
$arrDates = Array("02/1/2007", "02/2/2007", "02/3/2007", "02/5/2007");
echo getDateRangeString($arrDates, "/");

echo "<br /><br /><b>Test Case 4</b><br />";
$arrDates = Array();
$arrDates = Array("02/1/2007", "02/2/2007", "02/3/2007", "02/5/2007", "03/1/2007");
echo getDateRangeString($arrDates, "/");

echo "<br /><br /><b>Test Case 5</b><br />";
$arrDates = Array();
$arrDates = Array("02/1/2007", "02/2/2007", "02/3/2007", "02/5/2007", "03/1/2007", "03/2/2007", "03/27/2007");
echo getDateRangeString($arrDates, "/");

echo "<br /><br /><b>Test Case 5</b><br />";
$arrDates = Array();
$arrDates = Array("02/1/2007", "02/2/2007", "02/3/2007", "02/5/2007", "03/1/2007", "03/2/2007", "03/27/2008");
echo getDateRangeString($arrDates, "/");

echo "<br /><br /><b>Test Case 5</b><br />";
$arrDates = Array();
$arrDates = Array("02/1/2007", "02/2/2007", "02/3/2007", "02/27/2007", "02/28/2007", "03/1/2007", "03/2/2007", "03/27/2008");
echo getDateRangeString($arrDates, "/");

echo "<br /><br /><b>Test Case 5</b><br />";
$arrDates = Array();
$arrDates = Array("02/1/2007", "02/2/2007", "02/3/2007", "02/5/2007", "03/1/2007", "03/2/2007", "12/29/2008", "12/30/2008", "12/31/2008", "01/1/2009", "01/2/2009");
echo getDateRangeString($arrDates, "/");

?>

laffin · February 15, 2008

Heh, i like working with timestamps, and standard dates strings, and arrays.

so wrote this code up. note: i use an array to break up the dates into a multidimensional array, by year,month,day.

once that is accomplished, it's much easier to build a logic to create date ranges.

Since all is seperated it's just the day logic that needs work on

<?php
function GetDateRange($da)
{
  if(empty($da)) return NULL;
  foreach($da as $day)
  {
  $ds = gmdate('Y-m-d',$day);
  $dp = explode('-',$ds);
  $dma[$dp[0]][$dp[1]][]=$dp[2];
  }
  $out='';
  foreach($dma as $ky => $years)
  {
  foreach($years as $km => $months)
  {
		  $dr=0;
		  $days=array();
		  $dc=count($months);
		  for($i=1;$i<$dc;$i++)
		  {
			  $yd=$months[$i-1];
			  $td=$months[$i];
			  if(!$dr)
			  {
			  	if($yd==($td-1))
					$dr=$yd;
				else 
					$days[]=$yd;
			  } else {
			  	if ($dr && $yd!=($td-1))
			  	{
				  $days[]="$dr-$yd";
				  $dr=0;
			  	}
			  }
		  }
		  if($dr)
			$days[]="$dr-$td";
		  else
			$days[]="$td";
      $out.=(!empty($out)?' ':'').implode(',',$days);
	  $out.=' '.gmdate('F',strtotime("$ky-$km"));
  }
  $out.=' '. $ky;
  }
  return $out;
}
  header('Content-type: text/plain');

  define('SECS_PER_DAY',(24*60*60));
  $start_date="2007-12-15";
  
  $da[]=$lt=strtotime($start_date);

  mt_srand(time());
  

  for($i=1;$i<15;$i++)
  {
  $days=mt_rand(1,5)*SECS_PER_DAY;
  $da[]=($lt+=$days);
  }
  
  foreach ($da as $key => $day)
  {
  echo sprintf("%02d",$key) .") ". gmdate("Y-m-d",$day) ."\n";
  }
  echo GetDateRange($da);      
  echo "\n\n";
  $da=array();
  $start_date="12/15/2007";
  
  $da[]=$lt=strtotime($start_date);

  mt_srand(time());
  
  for($i=1;$i<15;$i++)
  {
  $days=mt_rand(1,2)*SECS_PER_DAY;
  $da[]=$lt+=$days;
  }
  foreach ($da as $key => $day)
  {
  echo sprintf("%02d",$key) .") ". gmdate("Y-m-d",$day) ."\n";
  }
  echo GetDateRange($da);      
  echo "\n";
  
?>

I got these results

00) 2007-12-14

01) 2007-12-16

02) 2007-12-17

03) 2007-12-22

04) 2007-12-23

05) 2007-12-26

06) 2007-12-28

07) 2008-01-02

08) 2008-01-06

09) 2008-01-08

10) 2008-01-12

11) 2008-01-14

12) 2008-01-17

13) 2008-01-19

14) 2008-01-22

14,16-17,22-23,26,28 December 2007 02,06,08,12,14,17,19,22 January 2008

00) 2007-12-14

01) 2007-12-15

02) 2007-12-16

03) 2007-12-18

04) 2007-12-19

05) 2007-12-21

06) 2007-12-22

07) 2007-12-24

08) 2007-12-26

09) 2007-12-27

10) 2007-12-29

11) 2007-12-30

12) 2007-12-31

13) 2008-01-01

14) 2008-01-02

14-16,18-19,21-22,24,26-27,29-31 December 2007 01-02 January 2008

dbo · February 15, 2008

Thanks for the followup. However, at a glance anyways, I like my implementation better. You seem to have a running time of On^3 with all those nested loops.

That being said, it's a trickier problem than it looks like isn't it?

Barand · February 16, 2008

Couldn't resist a go

<?php
$arrDates = Array("02/1/2007", "02/2/2007", "02/3/2007", "02/5/2007", "03/1/2007", "03/2/2007", "03/27/2007");

$k = count ($arrDates);

$str = '';
$seq = array();
$prevm = '';
$year = '';
for ($i=0; $i<$k; $i++)
{
    $t = strtotime($arrDates[$i]);
    $m = date('F', $t);
    $d = date('j', $t);
    $y = date('Y', $t);
    
    if ($prevm != $m || $year != $y)
    {
        if ($seq)
        {
            $s = $seq[0]==$seq[1] ? $seq[0] : join ('-', $seq);
            echo $str . " $s" . " $year ";
        }
        $str = "$m";
        $seq = array($d);
        $prevm = $m;
        $year = $y;
    }
    if (!isset($seq[1]))
    {
        $seq[1] = $d;
    }
    else 
    {
        if ($d - $seq[1] == 1)
        {
            $seq[1] = $d;
        }
        else
        {
            $s = $seq[0]==$seq[1] ? $seq[0] : join ('-', $seq);
            $str .= " $s";
            $seq = array($d, $d);
        }
    }
}
$s = $seq[0]==$seq[1] ? $seq[0] : join ('-', $seq);
echo $str . " $s" . " $year ";

?>

sasa · February 16, 2008

<?php
$a = array('2007-12-14',
'2007-12-16',
'2007-12-17',
'2007-12-22',
'2007-12-23',
'2007-12-26',
'2007-12-28',
'2008-01-02',
'2008-01-06',
'2008-01-08',
'2008-01-12',
'2008-01-14',
'2008-02-17',
'2008-02-19',
'2008-02-20');
foreach ($a as $date){
list($y,$m,$d) = explode('-',$date);
$ad[$y][$m][] = $d;
}
foreach ($ad as $y => $mounts){
foreach ($mounts as $m => $days){
	for ($i = 0; $i < count($days)-1; $i++){
		if (abs($days[$i]) + 1 == $days[$i + 1]) $days[$i + 1] *= -1;
		if ($days[$i] < 0 and $days[$i+1]<0) unset($days[$i]);
	}
	$out .= date("F", mktime(0, 0, 0, $m, 1, 2000));
	$out1 ='';
	foreach ($days as $d) $out1 .= ($d>0 ? ', ':'').$d;
	$out .= substr($out1,1).' ';
}
$out .= "$y ";
}
echo $out;
?>

dbo · February 16, 2008

These are great, thanks guys.

Sign In

Funky Algorithm Logic, Take a Shot :)

Recommended Posts

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Join the conversation

Important Information