Perl Advent Calendar 2007-12-16

Timely Flight Planning for a Sleigh

by Bill Ricker

Please don't mind the gap here - your editors and our regular contributors all had outbreaks of real life. More contributors welcome!

Santa's Sr Elf Flight Planner must arrange to visit every chimney in the time available, so the sequence is carefully optimized. (The computer that solves this Traveling Salesman Problem instance is leased from NSA for the night of their annual holiday party.)

The Flight Planners use "divide and conquer" to create a simplifying assumption: Santa will do each timezone as a unit. This breaks the worldwide into a nearly trivial ordering of TZ's and a Traveling Salesman problem within each timezone. There are many more than 24 timezones, what with some being offset by 0:30 or even 0:15, and being fragmented by local government DST options.

It is little appreciated that Santa actually has more than 24 hours to do his deliveries, even if he's restricted to say midnight to 5am local. The TZs are spanning UTC+14 1 to UTC-12 2

Using the DateTime::TimeZone module, the Elf Flight Planner can see how each timezone meshes with World Time (aka UTC, GMT, Z):

        Pacific/Kiritimati:(UTC+14)
                     2007-12-24T10:00:00Z  00loc
                  to 2007-12-24T15:00:00Z   5am 
                (end 2007-12-25T10:00:00Z +24)
        Europe/London:(UTC+0)
                     2007-12-25T00:00:00Z  00loc
                  to 2007-12-25T05:00:00Z   5am 
                (end 2007-12-26T00:00:00Z +24)
        America/New_York:(UTC-5)
                     2007-12-25T05:00:00Z  00loc
                  to 2007-12-25T10:00:00Z   5am 
                (end 2007-12-26T05:00:00Z +24)
        US/Samoa:(UTC-11)
                     2007-12-25T11:00:00Z  00loc
                  to 2007-12-25T16:00:00Z   5am 
                (end 2007-12-26T11:00:00Z +24)
        
        Deliveries      from 2007-12-24T10:00:00Z
                          to 2007-12-25T16:00:00Z; 
                        which is  1D06:00
        Xmas somewhere populated 
                        from 2007-12-24T10:00:00Z 
                          to 2007-12-26T11:00:00Z; 
                        which is 2D01:00

He can start deliveries at least as soon as the 25th starts at 12-24T1000Z on Christmas Island in UTC+14 Kiritimati.cx timezone and should end before sunrise, say 5am local to be safe, 12-25T1600Z in UTC-11 with Samoa (.ws and .as), .nu, .tk, and Midway Island; from there, there are only ships at sea in UTC-12, and maybe a few lightkeepers at (unpopulated) Baker Is and Howland Is which we can ignore as they're on the way back north up the International Date Line.

That's 30 hours not counting flying time from North Pole to South Pacific and back, but since first and last time zones are sparsely populated, he can probably include the on-station legs in the first and last hour. If kids in UTC+14 bed down early or in UTC-11 sleep in well, he gets even longer. (And likewise anywhere populous timezones at one offset are adjacent to a group far less so.)

Note that this means a given Date lasts 50 hours 3 - it's 12-25 somewhere from 12-24T1000Z (12-25T0000 in UTC+14 Christmas Island) to 12-26T1200Z (12-26T0000 in UTC-12 Howard & Baker Islands).

mod16.pl

   1 #! perl -wl
   2 use strict;
   3 use warnings;
   4 use DateTime;
   5 use DateTime::TimeZone;
   6 
   7 
   8 my $hour=3600;
   9 
  10 
  11 my %Options=(year=>2007,
  12              month=>12,
  13 	     day=>25,
  14 	     hour=>00,
  15 	     minute=>00,
  16 	     second=>00,
  17 	     # time_zone => 'Asia/Tapei',
  18 	     );
  19 my @TZNames=(
  20 	'Pacific/Kiritimati', # GMT+14 start
  21 	'Europe/London', # GMT+0 in winter
  22 	'America/New_York',
  23 	# GMT-11 ends the day 
  24 	'US/Samoa',  # aka 'Pacific/Apia', 
  25 	# as only uninhabited islands and ships in GMT-12 lately	
  26 	# 'GMT-12' 
  27 	);
  28 
  29 my ($first,$lastD,$lastX);
  30 
  31 foreach my $tzn (@TZNames) 
  32 {
  33 	my $xmas= DateTime->new(%Options,  time_zone => $tzn ,);
  34 	my $offset=DateTime::TimeZone->new(name=>$tzn)
  35 			->offset_for_datetime($xmas)
  36 				/ $hour;
  37 	$xmas->set_time_zone('GMT');
  38 	$first ||= $xmas;
  39 	my $dawn= DateTime->new(%Options,  time_zone => $tzn ,
  40 			hour=>05)->set_time_zone('GMT');
  41 	my $stst= DateTime->new(%Options,  time_zone => $tzn ,
  42 			day=>26)->set_time_zone('GMT');  # begins St.Stephens or Boxing day
  43 	$lastD= $dawn;
  44 	$lastX= $stst;
  45 	
  46 	printf "\t%s:(UTC%+02d)\n\t\t     %sZ  00loc\n\t\t  to %sZ   5am \n\t\t(end %sZ +24)\n",
  47 		$tzn, $offset, $xmas, $dawn, $stst;
  48 }
  49 
  50 printf "\n\tDeliveries \tfrom %sZ\n\t\t\t  to %sZ; \n\t\t\twhich is  %dD%02d:%02d\n",
  51 	$first , $lastD,
  52 	($lastD-$first)->in_units(qw(days hours minutes	));
  53 
  54 printf "\tXmas somewhere populated \n\t\t\tfrom %sZ \n\t\t\t  to %sZ; \n\t\t\twhich is %dD%02d:%02d\n", 
  55 	$first , $lastX,
  56 	($lastX-$first)->in_units(qw(days hours minutes	));

1. UTC+13,+14 are the bulge of the International Dateline in the South Pacific, where islands in UTC-11,-12 switched sides to be in the same day as other South Pacific islands rather than Hawaii and Alaska.

2. UTC-12 currently has no population thus no DST definitions or named TZ, but is a nautical TZ.

3. No wonder the Millenium New Years TV special coverage lasted so long!

Normally we wouldn't review a Phalanx 100 module, but

If you need to support Timezone redefinition in quasi-realtime faster than your Sysadmins can patch your OS, DateTime::TimeZone will give you control, as it has its own copy of the Olson/ZoneInfo TZ database, which follows latest ZoneInfo patches at least as quickly as OS vendors. (This would be useful if say a Web2.0 application knows about user home or destination TZs and has to track future changes when legislated for planning.) Otherwise, Perl follows the OS's TZ/DST definitions, and was unlikely to have Perl-specific DST bugs this last spring forward and fall back. For most purposes, the other TimeZone modules are fine.

For a different view of how Santa's Elves can deliver everything in 30 hours, see Wired-- Bill