The Truck Driver

05Apr13

In the twelve months from March 2013 to March 2014, I programmed solutions to the problems posted on the Contest Coding blog run by Lewis Cornwall, solving 33 problems (out of 47) and achieving a position of 4th on the leaderboard (out of 23).

As that blog has now been discontinued, I’m posting here the solutions I programmed to those problems.

The Truck Driver

A truck driver lives in Washington DC. He has to deliver goods to Pittsburgh, Richmond and Philadelphia before returning home. The truck’s average speed is 60mph. The distances between the cities are:

  • Washington DC – Pittsburgh = 245 miles
  • Washington DC – Richmond = 108 miles
  • Washington DC – Philadelphia = 142 miles
  • Pittsburgh – Richmond = 345 miles
  • Pittsburgh – Philadelphia = 304 miles
  • Richmond – Philadelphia = 248 miles

Using the optimal route, find how long the truck driver spends driving.

Solution and answer (The Truck Driver.c):

Includes: seal_bool, printDateAndTime.

/*
Solution and answer for problem "The Truck Driver" (5th April 2013) of http://ContestCoding.WordPress.com/

Fri Apr 05 09:00:00 2013

The optimal route is: Washington DC -> Richmond -> Pittsburgh -> Philadelphia -> Washington DC (or its reverse.)
The distance travelled in the optimal route is: 899 miles.
The time taken to travel the optimal route is: ~14.98 hours (~14 hours, 58 minutes.)

Fri Apr 05 09:00:00 2013

Solution programmed in C using Leonardo IDE 3.4.1; solution took ~1s to run on a 80MHz PowerPC 601.
*/

#include "seal_bool.h"
#include "printDateAndTime.h"
#include <stdlib.h>
#include <stdio.h>

void p_Distance_Set( const int p_a, const int p_b, const int p_distance );
int f_Distance_Get( const int p_a, const int p_b );
void p_Distance_Reset( void );

void main( void )
{
  const char *Pittsburgh = "Pittsburgh", 
             *Richmond = "Richmond",
             *Philadelphia = "Philadelphia",
             *Washington_DC = "Washington DC";
  const char *city_names[ 4 ] = { Pittsburgh, Richmond, Philadelphia, Washington_DC };
  const short a[ 3 ] = { 0, 1, 2 },
              b[ 3 ] = { 0, 2, 1 },
              c[ 3 ] = { 1, 0, 2 },
              d[ 3 ] = { 1, 2, 0 },
              e[ 3 ] = { 2, 0, 1 },
              f[ 3 ] = { 2, 1, 0 };
  const short *routes[ 6 ] = { a, b, c, d, e, f };
  const short number_of_routes = 6;
  const short average_speed = 60;

  short i = 0;
  int distance;
  short k;
  bool first_route = true;
  int optimal_distance;
  short optimal_route;
  double optimal_time;

  p_PrintDateAndTime();
  printf( "\n" );

  atexit( p_Distance_Reset );
  p_Distance_Set( 3, 0, 245 );
  p_Distance_Set( 3, 1, 108 );
  p_Distance_Set( 3, 2, 142 );
  p_Distance_Set( 0, 1, 345 );
  p_Distance_Set( 0, 2, 304 );
  p_Distance_Set( 1, 2, 248 );
  for( ; i < number_of_routes; i ++ )
  {
    distance = f_Distance_Get( 3, routes[ i ][ 0 ] );
    for( k = 0; k < 2; k ++ )
      distance += f_Distance_Get( routes[ i ][ k ], routes[ i ][ k + 1 ] );
    distance += f_Distance_Get( routes[ i ][ 2 ], 3 );
    if( first_route || ( distance < optimal_distance ))
    {
      optimal_route = i;
      optimal_distance = distance;
    }
    first_route = false;
  }
  printf( "The optimal route is: %s -> ", Washington_DC );
  for( i = 0; i < 3; i ++ )
    printf( "%s -> ", city_names[ routes[ optimal_route ][ i ]] );
  printf( "%s (or its reverse.)\n", Washington_DC );
  printf( "The distance travelled in the optimal route is: %d miles.\n", optimal_distance );
  optimal_time = ( double )optimal_distance / ( double )average_speed;
  printf( "The time taken to travel the optimal route is: ~%.2f hours (~%d hours, %d minutes.)\n", optimal_time, ( int )optimal_time, ( int )(( optimal_time - ( int )optimal_time ) * 60.0 ));

  printf( "\n" );
  p_PrintDateAndTime();

  exit( EXIT_SUCCESS );
}

typedef struct t_Distance_struct
{
  struct t_Distance_struct *m_n;
  int m_a, m_b, m_distance;
}
t_Distance;

static t_Distance *g_first = NULL, *g_last;

void p_Distance_Set( const int p_a, const int p_b, const int p_distance )
{
  t_Distance *d = ( t_Distance* )malloc( sizeof( t_Distance ));
  d->m_n = NULL;
  d->m_a = p_a;
  d->m_b = p_b;
  d->m_distance = p_distance;
  if( g_first == NULL )
    g_first = d;
  else
    g_last->m_n = d;
  g_last = d;
}

int f_Distance_Get( const int p_a, const int p_b )
{
  t_Distance *d = g_first;
  while( d != NULL )
  {
    if((( d->m_a == p_a ) && ( d->m_b == p_b ))
      || (( d->m_a == p_b ) && ( d->m_b == p_a )))
      return d->m_distance;
    d = d->m_n;
  }
  fprintf( stderr, "Error: no route between %d and %d.\n", p_a, p_b );
  exit( EXIT_FAILURE );
}

static void p_Distance_Delete( t_Distance *p )
{
  if( p != NULL )
  {
    p_Distance_Delete( p->m_n );
    free( p );
  }
}

void p_Distance_Reset( void )
{
  p_Distance_Delete( g_first );
  g_first = NULL;
}
Advertisements


No Responses Yet to “The Truck Driver”

  1. Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: