I : Logo Turtle Graphics

09Dec12

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 (I; medium difficulty):

Logo Turtle Graphics

When Santa’s elves enjoy some free time, they like to play with logo turtle graphics.

Problem

Implement a turtle simulator (without graphics). The turtle’s starting position is 0,0 and it is heading north. Your program should read commands from standard input and simulate the turtle’s movements. Each line contains exactly one command. The command arguments are positive integers, including 0. Commands and arguments are seperated by a space.

Instruction set

FDn advance turtle n units in forward direction
BKn move turtle n units back
RTdeg turn right deg degrees
LTdeg turn left deg degrees
CS clear everything and start over at position 0,0 facing north

When reading a single line with the command “END”, your program should print the turtle’s current position rounded to two digits (C/C++ programmers: add newline) and terminate. The X-axis runs towards east, the Y axis towards north. Print always two digits behind the decimal point. Separate values for X and Y by a comma, no spaces.

Example 1

Input

FD 10
END

Output

0.00,10.00

Example 2

Input

RT 30
FD 10
LT 90
BK 5
END

Output

9.33,6.16

Solution (I.c):

#include <stdio.h>
#include <stdlib.h>
#include <string.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, char *p_inputTerminatedBy );
bool f_CharStack_Empty( void );
void p_CharStack_ConvertContentToInt( void );
bool f_CharStack_ErrorOccurredConvertingContentToInt( void );
int f_CharStack_Int( void );
bool f_CharStack_CompareContentTo( const char * const p );

double f_Correct( double p )
{
  while( p < 0.0 )
    p += 360.0;
  while( p >= 360.0 )
    p -= 360.0;
  return p;
}

double f_Add( const double p_angle1, const double p_angle2 )
{
  return f_Correct( p_angle1 + p_angle2 );
}

double f_Subtract( const double p_angle1, const double p_angle2 )
{
  return f_Correct( p_angle1 - p_angle2 );
}

double f_Angle2Radian( const double p )
{
  return p * ( M_PI / 180.0 );
}

double f_XComponentOfVector( const double p_direction, const double p_magnitude )
{
  return sin( f_Angle2Radian( p_direction )) * p_magnitude;
}

double f_YComponentOfVector( const double p_direction, const double p_magnitude )
{
  return cos( f_Angle2Radian( p_direction )) * p_magnitude;
}

typedef enum
{
  k_COMMAND__FD,
  k_COMMAND__BK,
  k_COMMAND__RT,
  k_COMMAND__LT,
  k_COMMAND__CS,
  k_COMMAND__END,

  k_COMMAND__UNKNOWN,

  k_COMMAND__ERROR__SHOULD_NOT_HAVE_AN_ARGUMENT,
  k_COMMAND__ERROR__SHOULD_HAVE_AN_ARGUMENT,
  k_COMMAND__ERROR__SHOULD_HAVE_ONLY_ONE_ARGUMENT,
  k_COMMAND__ERROR__ARGUMENT_IS_NOT_A_POSITIVE_INTEGER
}
t_COMMAND;

t_COMMAND f_InputCommand( FILE *p_file, int *p_argument )
{
  char c;
  p_CharStack_Input( p_file, &c );
  if( f_CharStack_CompareContentTo( "END" ))
  {
    if( c != '\n' )
      return k_COMMAND__ERROR__SHOULD_NOT_HAVE_AN_ARGUMENT;
    return k_COMMAND__END;
  }
  if( f_CharStack_CompareContentTo( "CS" ))
  {
    if( c != '\n' )
      return k_COMMAND__ERROR__SHOULD_NOT_HAVE_AN_ARGUMENT;
    return k_COMMAND__CS;
  }
  t_COMMAND command = k_COMMAND__UNKNOWN;
  if( f_CharStack_CompareContentTo( "LT" ))
    command = k_COMMAND__LT;
  else
    if( f_CharStack_CompareContentTo( "RT" ))
      command = k_COMMAND__RT;
    else
      if( f_CharStack_CompareContentTo( "BK" ))
        command = k_COMMAND__BK;
      else
        if( f_CharStack_CompareContentTo( "FD" ))
          command = k_COMMAND__FD;
  if( command == k_COMMAND__UNKNOWN )
    return k_COMMAND__UNKNOWN;
  if( c != ' ' )
    return k_COMMAND__ERROR__SHOULD_HAVE_AN_ARGUMENT;
  p_CharStack_Input( p_file, &c );
  if( c != '\n' )
    return k_COMMAND__ERROR__SHOULD_HAVE_ONLY_ONE_ARGUMENT;
  p_CharStack_ConvertContentToInt();
  if( f_CharStack_ErrorOccurredConvertingContentToInt())
    return k_COMMAND__ERROR__ARGUMENT_IS_NOT_A_POSITIVE_INTEGER;
  *p_argument = f_CharStack_Int();
  return command;
}

int main( void )
{
  double x = 0, y = 0, r = 0;
  int argument;
  l_LOOP:
    switch( f_InputCommand( stdin, &argument ))
    {
      case k_COMMAND__END:
        printf( "%.2f,%.2f\n", x, y );
        return 0;
      case k_COMMAND__CS:
        x = 0;
        y = 0;
        r = 0;
        break;
      case k_COMMAND__LT:
        r = f_Subtract( r, argument );
        break;
      case k_COMMAND__RT:
        r = f_Add( r, argument );
        break;
      case k_COMMAND__BK:
        x += f_XComponentOfVector( r, -argument );
        y += f_YComponentOfVector( r, -argument );
        break;
      case k_COMMAND__FD:
        x += f_XComponentOfVector( r, argument );
        y += f_YComponentOfVector( r, argument );
        break;
      default:
        return -1;
    }
    goto l_LOOP;
}

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, char *p_inputTerminatedBy )
{
  char c;
  t_CharStackNode *n;
  p_CharStack_Reset();
  do
  {
    fscanf( p_file, "%c", &c );
    if(( c != ' ' ) && ( c != '\n' ))
    {
      n = ( t_CharStackNode* )malloc( sizeof( t_CharStackNode ));
      n->m_down = g_charStack_top;
      g_charStack_top = n;
      n->m_char = c;
    }
  }
  while(( c != ' ' ) && ( c != '\n' ));
  *p_inputTerminatedBy = c;
}

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;
}

bool f_CharStack_CompareContentTo( const char * const p )
{
  size_t i = 0, k = strlen( p ) - 1;
  t_CharStackNode *n = g_charStack_top;
  for( ; i < strlen( p ); i ++, k --, n = n->m_down )
  {
    if( n == NULL )
      return false;
    if( p[ k ] != n->m_char )
      return false;
  }
  if( n != NULL )
    return false;
  return true;
}

Testing:

gcc -std=c99 -Wall -lm I.c
mv a.out I
./I
FD 10
END
0.00,10.00
./I
RT 30
FD 10
LT 90
BK 5
END
9.33,6.16
Advertisements


No Responses Yet to “I : Logo Turtle Graphics”

  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: