Q : Hello Satan!

17Dec12

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

Hello Satan!

Santa gets a lot of wish lists these days, but they often contain lots of spelling errors, which is irritating the elves, since they produce goods only if the name matches exactly.

Problem

Your task is to implement a program that reads the contents of a wish list, and writes a list with correct spelling. You program should read from standard input until an empty line. The output should consist of the corrected wish list without the extra line (but there should be a newline after each item).

Wish list items can contain the following toy names:

action figure
airplane model kit
bucket of wooden blocks
child tricyle
doll
marble run set
plastic toy dinosaur
puzzle
railway train set
teddybear
toy racing car
tubs of modeling clay
wooden chalk drawing board

Each toy will appear in a separate line. Lines not containing any (possible misspelled) toys should be copied as-is. Each word of a toy name may contain at most one error, which is either a swap of two characters or a wrong character.

Example

Input

Dear Santa,
this year I was really good!
I wish for:
chlid trycyle
toy racyng car
bucket of wodden blocks
airplaen model kid
Love you!
Maggie
(empty line)

Output

Dear Santa,
this year I was really good!
I wish for:
child tricyle
toy racing car
bucket of wooden blocks
airplane model kit
Love you!
Maggie

Solution (Q.cpp):

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

typedef struct t_IntListNode_struct
{
  struct t_IntListNode_struct *m_next;
  int m_int;
}
t_IntListNode;

class IntList
{
  private:
    t_IntListNode *m_first, *m_last, *m_current;

  public:
    IntList( void )
    {
      m_first = NULL;
      m_current = NULL;
    }
  private:
    void p_Delete( t_IntListNode *p )
    {
      if( p != NULL )
      {
        p_Delete( p->m_next );
        free( p );
      }
    }
  public:
    ~IntList( void )
    {
      p_Delete( m_first );
    }
    void p_Add( const int p )
    {
      t_IntListNode *n = ( t_IntListNode* )malloc( sizeof( t_IntListNode ));
      n->m_next = NULL;
      n->m_int = p;
      if( m_first == NULL )
      {
        m_first = n;
        m_current = n;
      }
      else
      {
        m_last->m_next = n;
        if( m_current == NULL )
          m_current = n;
      }
      m_last = n;
    }
    void p_Next( void )
    {
      if( m_current != NULL )
        m_current = m_current->m_next;
    }
    bool f_EndOfList( void )
    {
      return ( m_current == NULL );
    }
    int f_Int( void )
    {
      if( m_current == NULL )
        throw "IntList::f_Int() - m_current == NULL";
      return m_current->m_int;
    }
};

typedef struct t_CharListNode_struct
{
  struct t_CharListNode_struct *m_next;
  char m_char;
}
t_CharListNode;

class CharList
{
  private:
    t_CharListNode *m_first, *m_last;
    size_t m_length;

  public:
    CharList( void )
    {
      m_first = NULL;
      m_length = 0;
    }
  private:
    void p_Delete( t_CharListNode *p )
    {
      if( p != NULL )
      {
        p_Delete( p->m_next );
        free( p );
      }
    }
  public:
    ~CharList( void )
    {
      p_Delete( m_first );
    }
    void p_Reset( void )
    {
      p_Delete( m_first );
      m_first = NULL;
      m_length = 0;
    }
    void p_Input( FILE *p )
    {
      p_Reset();
      char c;
      do
      {
        fscanf( p, "%c", &c );
        if( c != '\n' )
          p_Add( c );
      }
      while( c != '\n' );
    }
    void p_Add( const char p )
    {
      t_CharListNode *n = ( t_CharListNode* )malloc( sizeof( t_CharListNode ));
      n->m_next = NULL;
      n->m_char = p;
      if( m_first == NULL )
        m_first = n;
      else
        m_last->m_next = n;
      m_last = n;
      if( m_length < ( size_t )-2 )
        m_length ++;
    }
    size_t f_Length( void )
    {
      return m_length;
    }
    bool f_ContainsOnlyLowercaseLettersOrSpaces( void )
    {
      t_CharListNode *n = m_first;
      if( n == NULL )
        return false;
      do
      {
        if((( n->m_char >= 'a' ) && ( n->m_char <= 'z' )) || ( n->m_char == ' ' ))
          ;
        else
          return false;
        n = n->m_next;
      }
      while( n != NULL );
      return true;
    }
    char *f_String( void )
    {
      size_t i = 0;
      t_CharListNode *n = m_first;
      char *s = ( char* )malloc( sizeof( char ) * ( m_length + 1 ));
      for( ; i < m_length; i ++, n = n->m_next )
        s[ i ] = n->m_char;
      s[ i ] = '\0';
      return s;
    }
};

typedef struct t_StringListNode_struct
{
  struct t_StringListNode_struct *m_next;
  char *m_string;
}
t_StringListNode;

class StringList
{
  private:
    t_StringListNode *m_first, *m_last, *m_current;

  public:
    StringList( void )
    {
      m_first = NULL;
      m_current = NULL;
    }
  private:
    void p_Delete( t_StringListNode *p )
    {
      if( p != NULL )
      {
        p_Delete( p->m_next );
        free( p->m_string );
        free( p );
      }
    }
  public:
    ~StringList( void )
    {
      p_Delete( m_first );
    }
    void p_Add( const char * const p )
    {
      t_StringListNode *n = ( t_StringListNode* )malloc( sizeof( t_StringListNode ));
      n->m_next = NULL;
      n->m_string = ( char* )malloc( sizeof( char ) * ( strlen( p ) + 1 ));
      strcpy( n->m_string, p );
      if( m_first == NULL )
      {
        m_first = n;
        m_current = n;
      }
      else
      {
        m_last->m_next = n;
        if( m_current == NULL )
          m_current = n;
      }
      m_last = n;
    }
    void p_Next( void )
    {
      if( m_current != NULL )
        m_current = m_current->m_next;
    }
    char *f_String( void )
    {
      if( m_current == NULL )
        throw "StringList::f_String() - m_current == NULL";
      char *s = ( char* )malloc( sizeof( char ) * ( strlen( m_current->m_string ) + 1 ));
      strcpy( s, m_current->m_string );
      return s;
    }
};

class Word
{
  private:
    size_t m_stringLength;
    char *m_string;

  public:
    Word( const char * const p )
    {
      m_stringLength = strlen( p );
      m_string = ( char* )malloc( sizeof( char ) * ( m_stringLength + 1 ));
      strcpy( m_string, p );
    }
    ~Word( void )
    {
      free( m_string );
    }
    void p_Print( void )
    {
      printf( "%s", m_string );
    }
    bool f_ProbableMatch( const Word * const p )
    {
      if( m_stringLength != p->m_stringLength )
        return false;
      size_t i = 0, correctLetters = 0;
      for( ; i < m_stringLength; i ++ )
        if( m_string[ i ] == p->m_string[ i ] )
          correctLetters ++;
      if(( correctLetters + 2 ) < m_stringLength )
        return false;
      size_t a[ 26 ], b[ 26 ];
      for( i = 0; i < 26; i ++ )
      {
        a[ i ] = 0;
        b[ i ] = 0;
      }
      for( i = 0; i < m_stringLength; i ++ )
      {
        a[ m_string[ i ] - 'a' ] ++;
        b[ p->m_string[ i ] - 'a' ] ++;
      }
      size_t d = 0;
      for( i = 0; i < 26; i ++ )
        d += abs( a[ i ] - b[ i ] );
      if( d > 2 )
        return false;
      return true;
    }
};

class ToyName
{
  private:
    size_t m_numberOfWords;
    Word **m_word;

  public:
    ToyName( const char * const p )
    {
      m_numberOfWords = 0;
      size_t i = 0;
      CharList cL;
      StringList sL;
      for( ; i <= strlen( p ); i ++ )
        if(( p[ i ] != ' ' ) && ( p[ i ] != '\0' ))
          cL.p_Add( p[ i ] );
        else
        {
          m_numberOfWords ++;
          char *s = cL.f_String();
          cL.p_Reset();
          sL.p_Add( s );
          free( s );
        }
      m_word = ( Word** )malloc( sizeof( Word* ) * m_numberOfWords );
      for( i = 0; i < m_numberOfWords; i ++ )
      {
        char *s = sL.f_String();
        sL.p_Next();
        m_word[ i ] = new Word( s );
        free( s );
      }
    }
    ~ToyName( void )
    {
      size_t i = 0;
      for( ; i < m_numberOfWords; i ++ )
        delete m_word[ i ];
      free( m_word );
    }
    void p_Print( void )
    {
      size_t i = 0;
      for( ; i < m_numberOfWords; i ++ )
      {
        m_word[ i ]->p_Print();
        if(( i + 1 ) < m_numberOfWords )
          printf( " " );
      }
    }
    bool f_ProbableMatch( const ToyName * const p )
    {
      if( m_numberOfWords != p->m_numberOfWords )
        return false;
      size_t i = 0;
      for( ; i < m_numberOfWords; i ++ )
        if( !m_word[ i ]->f_ProbableMatch( p->m_word[ i ] ))
          return false;
      return true;
    }
};

int main( void )
{
  const size_t k_NUMBER_OF_TOY_NAMES = 13;
  ToyName *k_ToyName[ k_NUMBER_OF_TOY_NAMES ];
  k_ToyName[ 0 ] = new ToyName( "action figure" );
  k_ToyName[ 1 ] = new ToyName( "airplane model kit" );
  k_ToyName[ 2 ] = new ToyName( "bucket of wooden blocks" );
  k_ToyName[ 3 ] = new ToyName( "child tricyle" );
  k_ToyName[ 4 ] = new ToyName( "doll" );
  k_ToyName[ 5 ] = new ToyName( "marble run set" );
  k_ToyName[ 6 ] = new ToyName( "plastic toy dinosaur" );
  k_ToyName[ 7 ] = new ToyName( "puzzle" );
  k_ToyName[ 8 ] = new ToyName( "railway train set" );
  k_ToyName[ 9 ] = new ToyName( "teddybear" );
  k_ToyName[ 10 ] = new ToyName( "toy racing car" );
  k_ToyName[ 11 ] = new ToyName( "tubs of modeling clay" );
  k_ToyName[ 12 ] = new ToyName( "wooden chalk drawing board" );

  CharList cL;
  IntList toyNameIndices;
  StringList lines;
  do
  {
    cL.p_Input( stdin );
    if( cL.f_Length() > 0 )
    {
      if( cL.f_ContainsOnlyLowercaseLettersOrSpaces())
      {
        char *s = cL.f_String();
        ToyName *tN = new ToyName( s );
        size_t i = 0;
        bool b = false;
        for( ; i < k_NUMBER_OF_TOY_NAMES; i ++ )
          if( k_ToyName[ i ]->f_ProbableMatch( tN ))
          {
            toyNameIndices.p_Add( i );
            b = true;
            break;
          }
        if( !b )
        {
          toyNameIndices.p_Add( -1 );
          lines.p_Add( s );
        }
        free( s );
        delete tN;
      }
      else
      {
        char *s = cL.f_String();
        toyNameIndices.p_Add( -1 );
        lines.p_Add( s );
        free( s );
      }
    }
  }
  while( cL.f_Length() > 0 );

  while( !toyNameIndices.f_EndOfList())
  {
    int i = toyNameIndices.f_Int();
    toyNameIndices.p_Next();
    if( i >= 0 )
      k_ToyName[ i ]->p_Print();
    else
    {
      char *s = lines.f_String();
      lines.p_Next();
      printf( "%s", s );
      free( s );
    }
    printf( "\n" );
  }
  return 0;
}

Testing:

g++ -Wall Q.cpp
mv a.out Q
./Q
Dear Santa,
this year I was really good!
I wish for:
chlid trycyle
toy racyng car
bucket of wodden blocks
airplaen model kid
Love you!
Maggie

Dear Santa,
this year I was really good!
I wish for:
child tricyle
toy racing car
bucket of wooden blocks
airplane model kit
Love you!
Maggie
Advertisements


No Responses Yet to “Q : Hello Satan!”

  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: