Nerd Fortress

Posted in Hacker Challenge | Tagged challenge, coding, conversion, programming, time | 2 Comments

2 Responses to “Programming Challenge: Time Parser”

1. on February 22, 2008 at 10:23 am Mr. ANSI Pants

   Here’s my whack at it in PHP.

   <?php
   function array_swap(&$array, $key1, $key2)
   {
   	if ($key1 == $key2) return;
   
   	$array[$key1] += $array[$key2];
   	$array[$key2] = $array[$key1] - $array[$key2];
   	$array[$key1] -= $array[$key2];
   }
   
   function convert_time($original)
   {
   	$pieces = explode(':', $original);
   	array_swap($pieces, 0, count($pieces) - 1);
   
   	if (count($pieces) == 1 && !is_numeric($pieces[0]))
   	{
   		return $original;
   	}
   
   	$result = 0;
   	$multiplier = 1;
   	foreach ($pieces as $piece)
   	{
   		$result += $piece * $multiplier;
   		$multiplier *= 60;
   	}
   
   	return $result;
   }
   
   function convert_expression($expression)
   {
   	$pieces = preg_split('/[\s]+/', $expression);
   	$pieces = array_map('convert_time', $pieces);
   	return implode(' ', $pieces);
   }
   
   echo convert_expression('1:45.2 + 83 - 2:34');
   ?>
   

   -Mr. ANSI Pants

   P.S. I just timed this sucker on my 2.66 GHz Core2 Duo (running Windows XP Pro) and averaged 0.04 milliseconds on the example problem.

   
   
2. on February 25, 2008 at 9:22 am Random Boy

   Back in college I discovered the D programming language. Just for kicks, I used it for a project in my machine learning class. I really liked D’s blance of elegance and speed. Now, several years later, the language has grown up quite a bit and seems to be a valid contender for game and systems programming. I thought this excercise would be a good way to get back into the language.

   Here is my solution to this month’s challenge using the D language. I could have used regular expressions, but wanted to see how fast a hand-coded algorithm would be.

   import tango.io.Console;
   import tango.io.Stdout;
   import Float = tango.text.convert.Float;
   import tango.stdc.ctype;
   import tango.time.StopWatch;
   
   const int MAX_PARTS = 3;
   const int BUFFER_SIZE = 1024;
   char[BUFFER_SIZE] numberBuffer;
   
   void waitEnter()
   {
     Cout("\nPress Enter to continue").flush;
     Cin.get();
   }
   
   // We will build the result in a single pass. This should be rather fast.
   // For each time we encounter, grab the components, then calculate the total seconds.
   char[] parse(char[] timeString)
   {
     // Add a space at the end to trigger the close of the final token
     timeString = timeString.dup ~ ' ';
   
     // Look into putting these on the stack to make even faster
     char[] result;
     int numberBufferIndex;
   
     bool insideTime;
     bool insideNumber;
     double[MAX_PARTS] parts;
     int partIndex = 0;
     char[100] conversionBuffer = void;
   
     foreach(char c; timeString)
     {
       if (isdigit(c) || (insideTime && c == '.'))
       {
         if (!insideTime)
         {
           insideTime = true;
         }
   
         numberBuffer[numberBufferIndex++] = c;
       }
       else if (insideTime)
       {
         parts[partIndex++] = Float.parse(numberBuffer[0..numberBufferIndex]);
         numberBufferIndex = 0;
   
         // See if we just left a time token
         if (c == ' ')
         {
           double totalSeconds = 0;
           for (int i = partIndex-1, m = 1; i >=0; i--, m *= 60)
           {
             totalSeconds += parts[i] * m;
           }
   
           result ~= Float.format(conversionBuffer, totalSeconds);
           result ~= ' ';
   
           insideTime = false;
           partIndex = 0;
           parts[] = 0;
         }
       }
       else
       {
           // Not part of a time token
           result = result ~ c;
       }
     }
   
     return result;
   }
   
   int main(char[][] args)
   {
     char[] input = args[0];
     //input = "1:45.2 + 83 - 2:34";
   
     StopWatch elapsed;
     elapsed.start;
   
     int loopTimes = 10000;
     for (int i = 0; i < loopTimes; i++)
     {
       parse(input);
     }
   
     double timePerLoop = elapsed.stop / loopTimes;
   
     Cout("Parsing: " ~ input).newline;
     Cout("Result: " ~ parse(input)).newline;
   
     Stdout.formatln("Time to parse: {0:f4} ms", timePerLoop * 1000);
   
     waitEnter();
     return 0;
   }
   

   This bad boy runs the example problem in under .0027 ms on my 2.4 GHz Core2 Duo running Vista x64.