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. ]]> http://nerdfortress.com/index.php/2008/02/14/programming-challenge-time-parser/#comment-3 Mr. ANSI Pants Fri, 22 Feb 2008 17:23:52 +0000 http://nerdfortress.com/?p=5#comment-3 Here's my whack at it in PHP. <pre> <?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'); ?> </pre> -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. 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.