Solutions and Discussion for Perl Quiz of the Week #2
Mark Jason Dominus <[email protected]> Mon, 28 Oct 2002 13:25:59 -0500
| Newsgroups | gmane.comp.lang.perl.qotw.quiz-of-the-week |
|---|---|
| Organization | Plover Systems |
| Message-ID | <[email protected]> |
Sample solutions and discussion
Perl Quiz of The Week #2 (20021023)
Write a function, days_diff, to compute the time difference, in days,
between two dates. The dates will be strings in the format
Wed Oct 16 2002
For example:
days_diff("Wed Oct 16 2002", "Wed Oct 23 2002")
should return 7.
days_diff("Wed Oct 16 2002", "Tue Oct 16 2001")
should return -365.
I thought this would be an easy problem. But as I should have
remembered, almost nothing to do with date calculations is easy or
simple. Some of the varied complications are discussed below.
I had originally imagined two types of solution. One might use one of
the heavy-duty CPAN date calculation modules, such as Date::Calc or
Date::Manip; the other other use the standard Time::Local module.
The Time::Local solution I produced looked like this:
use Time::Local 'timegm';
my @mon = qw(Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec);
my %m2n = map {$mon[$_] => $_} 0 .. 11;
sub days_diff {
my @times;
for (0 .. 1) {
my ($dw, $mn, $dm, $yr) = split /\s+/, $_[$_];
push @times, timegm(0, 0, 0, $dm, $m2n{$mn}, $yr-1900);
}
($times[1] - $times[0])/86400;
}
Here I used the 'timegm' function to turn each date into a Unix epoch
time (number of seconds since the start of 1970), subtract the two
epoch times to find the difference in seconds, and then divide the
result by 86400 to get the number of days difference.
1. It might seem as though this could produce a fractional result.
The question is: Is the interval between consecutive midnights in
GM time (Greenwich Mean) time always exactly 86400 seconds?
The answer is no, not exactly, because GMT days are occasionally
86401 seconds long. Astronomers throw in an extra 'leap second' at
the end of June or December to keep the actual solar noon
synchronized with chronological noon; the extra second is
occasionally necessary because the Earth's rotation is gradually
slowing. (They might in principle subtract a second sometimes
because of random rotational changes called 'nutations', but it's
never happened.) In particular, there were extra seconds at the
end of June 1997 and December 1998.
However, as far as I know, no Unix system actually uses GMT, and no
'gmtime()' function actually calculates Greenwich mean time!
Instead, they all use UTC (Coordinated Universal Time) which is
just like GM time, except without the leap seconds; UTC days are
always exactly 86400 seconds long. My system even documents this:
The ctime(), gmtime() and localtime() functions all take an
argument of data type time_t which represents calendar time.
When interpreted as an absolute time value, it represents the
number of seconds elapsed since 00:00:00 on January 1, 1970,
Coordinated Universal Time (UTC).
So the function above works even across intervals where the GM
calendar contains leap seconds, supposing that the 'timegm'
function is actually producing UTC times. If not, the final
difference should simply be rounded off to the nearest integer.
2. A second issue is that in many localities, mostly in Europe and
North America, there's a practice called 'Daylight Saving Time'
where the clock is set forward in the spring and backward in the
autumn. For example, in Philadelphia, there was no local time
02:30 Sunday April 7 2002:
plover% perl -le 'print scalar localtime(1018160911)'
Sun Apr 7 01:28:31 2002
But an hour later it was:
plover% perl -le 'print scalar localtime(1018160911 + 3600)'
Sun Apr 7 03:28:31 2002
April 7 was only 23 hours long, because 2:00-2:59 was missing;
similarly, yesterday (Sunday, October 27) was 25 hours long. GM
time does not have any such adjustments, so they don't affect the
sample function above. However, several people used the
'timelocal' function instead of 'timegm' in similar solutions,
leading to incorrect results. For example, when called like this
days_diff("Mon Oct 21 2002", "Mon Oct 28 2002"); # Daylight saving
their functions would return 7.04166666666606 instead of 7, because
of the extra hour. Again, rounding off would have solved the
problem, but the solutions I saw that used timelocal() didn't round
off either.
3. Here's a related issue. One poster on the -discuss list presented
a solution that would check the day of the week for validity, a
reasonable addition:
my $sttime = timelocal(0,0,1,$stdayno,$months{$stmonth},$styear);
my @sttime = gmtime($sttime);
if($stday ne $days[ $sttime[6] ]) { # (gmtime)[6] is the dayname
return "start date was invalid\n";
}
But there's an inconsistency in the implementation. See it? He
uses timelocal() to convert the argument to epoch time, but then
gmtime() to convert it back and get the day of the week. That
works OK where I live, because 1AM local time is either 5AM or 6AM
UTC the same day, so the day of the week is the same. But had this
poster run his test program in Tokyo, where 1AM local time is 6PM
UTC the previous day, he would never have had a success!
4. Here's a puzzling issue. For various reasons, none of the
'timelocal()' solutions posted to the -discuss list actually
works. The one I excerpted above assumes that the dates are in the
format
Wednesday 16 October 2002
but the problem specification calls for
Wed Oct 16 2002
Two others assume that the dates will be in the format
Wed 9 16 2002
which seems rather unlikely.
I'm curious about why the authors of these functions didn't get
this right. Was it carelessness, or a deliberate modification of
the spec?
5. The major defect of the sample solution above is that the timegm()
function has a limited range. It returns its result as an integer
number of seconds since 1970; on machine with 32-bit integers, this
covers a range of about 136 years, from Fri Dec 13 20:45:52 1901
through Tue Jan 19 03:14:07 2038. Outside this range, it throws an
exception. This may be acceptable to the accounting department,
but the limitation should be noted.
6. Solutions using one of the heavyweight CPAN date calculation
modules don't have this range limitation. These modules also do
all the difficult work. Here's a solution I produced that uses the
'Date::Calc' module:
use Date::Calc 'Delta_Days', 'Decode_Date_US';
sub days_diff {
my @d = @_;
s/^\w+// for @d; # Remove day of the week
Delta_Days(map Decode_Date_US($_), @d);
}
'Decode_Date_US' attempts to parse and translate a Date in US
format, where the month precedes the day number. Unfortunately,
the days of the week confuse this function, so I have to strip them
out first. The function returns a year number, month number (1-12)
and day number. The 'Delta_Days' function takes two dates in year,
month, day format and computes the number of days difference
between them.
Steve Smoot produced essentially the same solution:
sub days_diff {
return Delta_Days(Decode_Date_US(substr($_[0],4)),Decode_Date_US(substr($_[1],4)));
}
7. Shawn Carroll benchmarked a Date::Calc solution against a
Date::Manip solution and found that Date::Calc was about 80 times
faster. This is probably because Date::Calc is written in C, while
Date::Manip is in pure Perl. The Date::Manip manual contains an
extensive discussion of this point, and the tradeoffs between
Date::Calc and Date::Manip.
8. Some people coded the date calculations by hand. This is tricky to
get right, but has the benefit that if you get do it right, it
doesn't have the range limitations of Time::Local. Date
calculations are really complicated, and tend to end up looking
like a big stew, so I didn't bother to debug the ones that didn't
work. Here's one of the less stewish examples, provided by G. Rommel:
sub days_diff {
my ($start, $end) = @_;
my ($wd1, $mo1, $day1, $yr1) = split ' ',$start;
my ($wd2, $mo2, $day2, $yr2) = split ' ',$end;
# Convert the month.
my %mnum = ('Jan'=>0, 'Feb'=>1, 'Mar'=>2,
'Apr'=>3, 'May'=>4, 'Jun'=>5,
'Jul'=>6, 'Aug'=>7, 'Sep'=>8,
'Oct'=>9, 'Nov'=>10, 'Dec'=>11);
# Days before this month this year.
my @db = qw(0 31 59 90 120 151 181 212 243 273 304 334);
$mn1 = $mnum{$mo1};
$startday = int(($yr1 - 1601) * 365.2425) + $db[$mn1] + $day1;
$startday++ if $mn1 > 1 && ($yr1%4==0) && (($yr1%400==0) || ($yr1%100!=0));
$mn2 = $mnum{$mo2};
$endday = int(($yr2 - 1601) * 365.2425) + $db[$mn2] + $day2;
$endday++ if $mn2 > 1 && ($yr2%4==0) && (($yr2%400==0) || ($yr2%100!=0));
return $endday - $startday;
}
Rommel transforms each input date into a count of the number of
days since the beginning of 1601. (The 365.2425 is the average
number of days in the Gregorian calendar year.) He then subtracts
the counts to get the difference. Rommel notes that this approach
fails to detect invalid dates ("Sep 37 2002" is interpreted as the
same as "Oct 7 2002", for example) and that the function won't work
after the year 5881210 because the number of days will no longer
fit into an integer variable.
9. There was a long discussion on the -discuss list about Julian
vs. Gregorian dates. The calendar presently in use in most of the
world is the Gregorian calendar, first introduced by Pope Gregory
XIII in 1582. Prior to this, most European countries used the
Julian calendar, almost the same but with a different leap day
schedule. When you see a date like "Tuesday July 2 1776" there is
a question about what it means; the same label may be applied by
the Julian and Gregorian calendars to different days.
There some complications on top of this:
* Not every country switched to the Gregorian calendar at the
same time. Most Catholic countries switched immediately;
other countries held out. Great Britain and its colonies
(including what would eventually become the USA) switched
calendars in 1752. Russia switched in 1918; this is why the
October Revolution is now celebrated in November.
* The switch was accompanied by a one-time modification of the
calendar, to bring the dates back into line with the
seasons. In Spain, for example, October 1582 had only 21
days. In Great Britain, September 1752 had only 19 days.
In Sweden there was a big mix-up too complicated to explain
here.
http://www.geocities.com/CapeCanaveral/Lab/7671/gregory.htm
contains some interesting details about these issues.
So one might ask: What is days_diff("Fri Sep 1 1752", "Sun Oct 1
1752")? In Spain, it's 30, as one would expect. In England or the
USA, one might like the answer to be 19---except that in England,
Sep 1 1752 was a Tuesday, not a Friday.
Several people tried to take this into account. All of the
solutions were locality-specific. For example, one gentleman wrote
a version that was accurate in France, taking into account that
fact that in France, Dec 10 1582 was followed immediately by Dec 20
1582.
I feel that this is misguided. It's interesting, but it's a lot of
work and the payoff seems small. The gentleman I mentioned before
who included the correct adjustment for France had his function
deliver an error if you asked for Dec 15 1582, which didn't exist
in France (or, more precisely, there was no date with that name):
if ($jd[$i] > 15821210 and $jd[$i] < 15821220) {
print "Not a valid date:\nFrance switched to the Gregorian calendar in 1582\n";
print "and 10 Dec 1582 was followed immediately by 20 Dec\n";
exit;
}
This person would have had a much easier time if he had lived in
Israel rather than in France. The entire function could have been
replaced with:
sub days_diff {
my $date = shift;
print "There is no date called '$date'\n";
exit;
}
(In the Hebrew calendar, "Mon Oct 28 2002" is called "Heshvan 22, 5763".)
If one is going to historically inaccurate date names, then why not
also throw an error for 10 Dec 1793? There was no date with that
name either, in France, because the Gregorian calendar was
abolished for 13 years after the Revolution and was replaced by a
new calendar, in which 10 Dec 1793 was known instead as
Decade II, Decadi de Frimaire, de l'Annee 2 de la Revolution
or more succinctly, "20 Frimaire II", perhaps.
And this says nothing about the question of whether France will
still be using the Gregorian calendar 7,000 years from now.
It's my feeling that if you're really trying to convert historic
dates, the interface presented by days_diff() is hopelessly
inadequate. The sample solutions pretend that the Gregorian
calendar was in use everywhere at all times; which isn't
historically accurate, but it's probably the best you can do
without expending an enormous amount of effort; see the GNU Emacs
'calendar' package, for example.
It didn't occur to me when I posed the question that people would
get worried about this. But the issue could turn out to be
important for some applications. For example, if you're trying to
compute interest payments for money borrowed before the calendar
change, it would be unfair to charge a full month's interest for
September 1752 or October 1582 or whatever, when those months were
ten or eleven days short. But I think in such a case, you would
really have to go back to the people requesting the function and
ask what they wanted it to do.
10. Last week I observed with some surprise that when some code failed
in some circumstances, people tended to come up with very
complicated examples rather than simple ones. I observed this
again this week. To illustrate the potential difficulty in
handling Julian vs. Gregorian dates, folks brought up the
September 1752 oddity in the Great Britain calendar. A simpler
example would be that
days_diff("Xxx Feb 28 1700", "Xxx Mar 1 1700")
should return 1 if the dates are interpreted as Gregorian dates,
but 2 if they are interpreted as Julian dates, since the Julian
calendar has Feb 29 1700 and the Gregorian calendar omits it.
11. Astronomers use their own modification of the Julian calendar;
they label the dates with numbers, with day 0 being a certain day
about 6700 years ago, and increasing by 1 each day afterwards. If
you could convert a (presumably Gregorian) date like "Wed Oct 16
2002" to astronomical form, you could then subtract the day
numbers of two dates to get the number of days in between.
Unfortunately, nobody implemented this right. One programmer who
chose this path did this:
sub days_diff {
my($day,$month,$mday,$year) = split(/\s+/,$_[0]);
my($day2,$month2,$mday2,$year2) = split(/\s+/,$_[1]);
my $monthToNum = {
Jan => 1,
Feb => 2,
Mar => 3,
Apr => 4,
May => 5,
Jun => 6,
Jul => 7,
Aug => 8,
Sep => 9,
Oct => 10,
Nov => 11,
Dec => 12,
};
my $jd_1 = _jday($year,$monthToNum->{$month},$mday);
my $jd_2 = _jday($year2,$monthToNum->{$month2},$mday2);
return $jd_2 - $jd_1;
}
sub _jday {
my($y,$m,$d) = @_;
my $jd = ( 1461 * ( $y + 4800 + ( $m - 14 ) / 12 ) ) / 4 +
( 367 * ( $m - 2 - 12 * ( ( $m - 14 ) / 12 ) ) ) / 12 -
( 3 * ( ( $y + 4900 + ( $m - 14 ) / 12 ) / 100 ) ) / 4 +
$d - 32075;
return $jd;
}
The '_jday' function here is supposed to convert a year, month, and
day to an astronomical Julian day number. This programmer said:
What I did do was Google for 'julian day' and I found
http://hermetic.magnet.ch/cal_stud/jdn.htm
That's a good approach in general, but unfortunately, he cribbed
the code without reading the accompanying discussion on that page:
Days are integer values in the range 1-31, months are integers
in the range 1-12, and years are positive or negative
integers. Division is to be understood as in integer
arithmetic, with remainders discarded.
This programmer's '_jday' function doesn't discard remainders, so
it produces mostly wrong answers. A correct version:
sub _jday {
my($y,$m,$d) = @_;
my $a = int(($m-14)/12);
my $b = int(( 1461 * ( $y + 4800 + $a ) ) / 4);
my $c = int(( 367 * ( $m - 2 - 12 * $a ) ) / 12);
my $e = int(( $y + 4900 + $a ) / 100 );
my $f = int(( 3 * $e ) / 4);
my $jd = $b + $c - $f + $d - 32075;
return $jd;
}
One other person posted an astronomical Julian day solution to the
-discuss list, and made the same mistake. I think the moral here is
something about how you can't just paste code into your program and
expect it to work.
12. Here's a small test suite:
use Test;
BEGIN {plan tests => 7 }
END {
ok(days_diff("Wed Oct 16 2002", "Wed Oct 23 2002"), 7);
ok(days_diff("Wed Oct 16 2002", "Tue Oct 16 2001"), -365);
ok(days_diff("Mon Oct 21 2002", "Mon Oct 28 2002"), 7); # Daylight saving
ok(days_diff("Thu Oct 31 2002", "Fri Nov 1 2002"), 1);
ok(days_diff("Sun Jun 29 1997", "Tue Jul 1 1997"), 2); # Leap second
ok(days_diff("Wed Dec 30 1998", "Fri Jan 1 1999"), 2); # Last leap second
ok(days_diff('Wed Jul 4 1776','Tue Jul 4 1976'), 73048);
}
1;
To use this, put it in a file called 'DiffTest.pm'; then add the
line
use DiffTest;
to the top of the file that contains your days_diff() function.
Thanks again to all the subscribers, and to those who participated in
the discussion. I will send another quiz on Wednesday.
Sample solutions for this week's 'expert' quiz may be slightly delayed,
since I have some other things to attend to this afternoon.