M : Santa at cuboid world

13Dec12

I recently participated in the Advent Programming Contest organised by the IEEE Student Branch Klagenfurt (with support from Alpen-Adria-Universität Klagenfurt and Universität Passau), achieving a rank of 11th (out of 118 participants); as submissions of solutions to that contest are now closed, I’m posting here the solutions I submitted to that contest.

Problem (M; easy difficulty):

Santa at cuboid world

As we have seen in a previous task, Santa is visiting quite strange worlds sometimes. This time, the world has three dimensions, but the planet is not spheroid-shaped but a perfect cuboid. Santa wants to meet some friend at a particular corner. Unfortunately he held the map upside down, so he landed at the corner which is in exact opposition to the intended one. Help Santa to get to his friend by traveling the surface of the cuboid on the shortest possible way (hint: the shortest way might not necessarily go along the edges).

Advent Programming Contest - M

Problem

Your task is to implement a program that calculates the shortes way with an accuracy of 2 decimal digits:

  • the first line of input is an integer depicting the number of inputs
  • each further line contains three integers seperated by space depicting the dimensions of the cuboid

The program should print the shortest possible distance on the surface between two opposite corners of the respective cuboid. Outputs should be printed always with two digits after the decimal point followed by a newline.

Example

Input

3
1 2 3
3 3 3
2 2 3

Output

4.24
6.71
5.00

Solution (M.c):

(Thanks go to Kristian Edlund for writing regarding their insight into a similar problem, without which I wouldn’t have solved this problem as easily.)

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct t_CharStackNode_struct
{
  struct t_CharStackNode_struct *m_down;
  char m_char;
}
t_CharStackNode;

typedef enum
{
  false = 0,
  true
}
bool;

static t_CharStackNode *g_charStack_top = NULL;
static int g_charStack_int = 0;
static bool g_charStack_errorOccurredConvertingContentToInt = true;

void p_CharStack_Reset( void );
void p_CharStack_Input( FILE *p_file, const char p_terminator );
bool f_CharStack_Empty( void );
void p_CharStack_ConvertContentToInt( void );
bool f_CharStack_ErrorOccurredConvertingContentToInt( void );
int f_CharStack_Int( void );

#define M_INPUT( p_terminator, p_variable )              \
  p_CharStack_Input( stdin, p_terminator );              \
  p_CharStack_ConvertContentToInt();                     \
  if( f_CharStack_ErrorOccurredConvertingContentToInt()) \
    return -1;                                           \
  p_variable = f_CharStack_Int();                        \
  if( p_variable <= 0 )                                  \
    return -1;                                           \

int main( void )
{
  p_CharStack_Input( stdin, '\n' );
  p_CharStack_ConvertContentToInt();
  if( f_CharStack_ErrorOccurredConvertingContentToInt())
    return -1;
  const int n = f_CharStack_Int();
  int i = 0;
  for( ; i < n; i ++ )
  {
    int a, b, c;
    M_INPUT( ' ', a )
    M_INPUT( ' ', b )
    M_INPUT( '\n', c )

    double t1 = pow( a, 2 ) + pow( b + c, 2 );
    t1 = sqrt( t1 );

    double t2 = pow( b, 2 ) + pow( a + c, 2 );
    t2 = sqrt( t2 );

    double t3 = pow( c, 2 ) + pow( a + b, 2 );
    t3 = sqrt( t3 );

    double s = t1;
    if( t2 < s )
      s = t2;
    if( t3 < s )
      s = t3;
    printf( "%.2f\n", s );
  }
  return 0;
}

static void p_CharStack_Delete( t_CharStackNode *p )
{
  if( p != NULL )
  {
    p_CharStack_Delete( p->m_down );
    free( p );
  }
}

void p_CharStack_Reset( void )
{
  p_CharStack_Delete( g_charStack_top );
  g_charStack_top = NULL;
  g_charStack_int = 0;
  g_charStack_errorOccurredConvertingContentToInt = true;
}

void p_CharStack_Input( FILE *p_file, const char p_terminator )
{
  char c;
  t_CharStackNode *n;
  p_CharStack_Reset();
  do
  {
    fscanf( p_file, "%c", &c );
    if( c != p_terminator )
    {
      n = ( t_CharStackNode* )malloc( sizeof( t_CharStackNode ));
      n->m_down = g_charStack_top;
      g_charStack_top = n;
      n->m_char = c;
    }
  }
  while( c != p_terminator );
}

bool f_CharStack_Empty( void )
{
  return ( g_charStack_top == NULL );
}

void p_CharStack_ConvertContentToInt( void )
{
  if( f_CharStack_Empty())
    g_charStack_errorOccurredConvertingContentToInt = true;
  else
  {
    t_CharStackNode *n = g_charStack_top;
    int multiplier = 1;
    g_charStack_int = 0;
    g_charStack_errorOccurredConvertingContentToInt = false;
    do
    {
      if(( n->m_char >= '0' ) && ( n->m_char <= '9' ))
      {
        g_charStack_int += (( n->m_char - '0' ) * multiplier );
        n = n->m_down;
        multiplier *= 10;
      }
      else
        g_charStack_errorOccurredConvertingContentToInt = true;
    }
    while(( n != NULL ) && ( !g_charStack_errorOccurredConvertingContentToInt ));
  }
}

bool f_CharStack_ErrorOccurredConvertingContentToInt( void )
{
  return g_charStack_errorOccurredConvertingContentToInt;
}

int f_CharStack_Int( void )
{
  return g_charStack_int;
}

Testing:

gcc -std=c99 -Wall -lm M.c
mv a.out M
./M
3
1 2 3
4.24
3 3 3
6.71
2 2 3
5.00

Link: Project Euler 86: Exploring the shortest path from one corner of a cuboid to another. [MathBlog, 3rd March 2012]

Advertisements


No Responses Yet to “M : Santa at cuboid world”

  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: