O : Cocktails

15Dec12

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

Cocktails

When Santa and the elves enjoy some free time after work, they like to enjoy a cocktail every now and then. They have a book with several cocktail recipes listing the ingredients for each cocktail. However, usually they have only a subset of ingredients in stock. Help Santa and the elves to determine which cocktails they can make for some given ingredients.

Problem

Write a program that first reads a list of cocktails from standard input. The first line contains the number of cocktails. The following lines contain the cocktails and their ingredients in the following format:

Cocktail Name: ingredient1, ingredient2, ..., last ingredient

After reading the cocktails, there is a line with the available ingredients, seperated by comma.

Your program shall output a list of alphabetically sorted cocktails that can be made with this ingredients. Each line should end with a newline. If it is not possible to mix any cocktail with the given input, the output should be a single empty line (with newline).

Example

Input

11
Brazilian Sunrise:cachaca,grenadine,lemon juice,orange juice
Tequila Sunrise:tequila,grenadine,lemon juice,orange juice
Latin Lover:cachaca,tequila,lime juice,ananas juice,lemon juice
Caipirinha:cachaca,lime juice
Caipifragola:cachaca,strawberry liqueur,strawberry sirup,lime juice
Strawberry Daiquiri:rum,strawberry liqueur,lime juice
Margarita:tequila,cointreau,lime juice
Carribean Dream:rum,grenadine,orange juice,lemon juice,ananas juice,passion fruit nectar
Malibu Barbados:carribean rum with coconut,orange juice,ananas juice
Malibu Margarita:carribean rum with coconut,cointreau,tequila,ananas juice,lemon juice,lime juice
Malibu Sunrise:carribean rum with coconut,grenadine,orange juice
cachaca,lime juice,grenadine,lemon juice,orange juice,carribean rum with coconut

Output

Brazilian Sunrise
Caipirinha
Malibu Sunrise

Solution (O.cpp):

#include <stdio.h>
#include <stdlib.h>
#include <string.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;

  public:
    IntList( void )
    {
      m_first = 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;
      else
        m_last->m_next = n;
      m_last = n;
    }
    bool f_IntIsInList( const int p )
    {
      t_IntListNode *n = m_first;
      while( n != NULL )
      {
        if( p == n->m_int )
          return true;
        n = n->m_next;
      }
      return false;
    }
    bool f_ObjectListIsInParameterList( IntList *p )
    {
      t_IntListNode *n = m_first;
      while( n != NULL )
      {
        if( !p->f_IntIsInList( n->m_int ))
          return false;
        n = n->m_next;
      }
      return true;
    }
};

class Cocktail
{
  private:
    char *m_name;
    IntList m_ingredients;

  public:
    Cocktail( const char * const p )
    {
      m_name = ( char* )malloc( sizeof( char ) * ( strlen( p ) + 1 ));
      strcpy( m_name, p );
    }
    ~Cocktail( void )
    {
      free( m_name );
    }
    char *f_Name( void )
    {
      char *s = ( char* )malloc( sizeof( char ) * ( strlen( m_name ) + 1 ));
      strcpy( s, m_name );
      return s;
    }
    void p_AddIngredientId( const int p )
    {
      m_ingredients.p_Add( p );
    }
    bool f_MayMixWithIngredients( IntList *p )
    {
      return m_ingredients.f_ObjectListIsInParameterList( p );
    }
};

typedef struct t_StringTreeNode_struct
{
  struct t_StringTreeNode_struct *m_left, *m_right;
  char *m_string;
  int m_id;
}
t_StringTreeNode;

class StringTree
{
  private:
    t_StringTreeNode *m_root;
    int m_nextId;

  public:
    StringTree( void )
    {
      m_root = NULL;
      m_nextId = 0;
    }
  private:
    void p_Delete( t_StringTreeNode *p )
    {
      if( p != NULL )
      {
        p_Delete( p->m_left );
        p_Delete( p->m_right );
        free( p->m_string );
        free( p );
      }
    }
  public:
    ~StringTree( void )
    {
      p_Delete( m_root );
    }
    void p_Add( const char * const p )
    {
      if( m_root == NULL )
        m_root = p_Add_private( p );
      else
        p_Add_private( m_root, p );
    }
  private:
    t_StringTreeNode *p_Add_private( const char * const p )
    {
      t_StringTreeNode *n = ( t_StringTreeNode* )malloc( sizeof( t_StringTreeNode ));
      n->m_left = NULL;
      n->m_right = NULL;
      n->m_string = ( char* )malloc( sizeof( char ) * ( strlen( p ) + 1 ));
      strcpy( n->m_string, p );
      n->m_id = m_nextId ++;
      return n;
    }
    void p_Add_private( t_StringTreeNode *p_node, const char * const p_string )
    {
      const int i = strcmp( p_string, p_node->m_string );
      if( i == 0 )
        ;
      else
        if( i < 0 )
        {
          if( p_node->m_left == NULL )
            p_node->m_left = p_Add_private( p_string );
          else
            p_Add_private( p_node->m_left, p_string );
        }
        else
        {
          if( p_node->m_right == NULL )
            p_node->m_right = p_Add_private( p_string );
          else
            p_Add_private( p_node->m_right, p_string );
        }
    }
  public:
    int f_Id( const char * const p )
    {
      return f_Id_private( m_root, p );
    }
  private:
    int f_Id_private( const t_StringTreeNode * const p_node, const char * const p_string )
    {
      if( p_node == NULL )
        throw "StringTree::f_Id() - the string is not in the tree";
      const int i = strcmp( p_string, p_node->m_string );
      if( i == 0 )
        return p_node->m_id;
      else
        if( i < 0 )
          return f_Id_private( p_node->m_left, p_string );
        else
          return f_Id_private( p_node->m_right, p_string );
    }
  public:
    bool f_Empty( void )
    {
      return ( m_root == NULL );
    }
    void p_Print_InOrder( void )
    {
      p_Print_InOrder_private( m_root );
    }
  private:
    void p_Print_InOrder_private( const t_StringTreeNode * const p )
    {
      if( p != NULL )
      {
        p_Print_InOrder_private( p->m_left );
        printf( "%s\n", p->m_string );
        p_Print_InOrder_private( p->m_right );
      }
    }
};

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

class CharStack
{
  private:
    t_CharStackNode *m_top;
    int m_int;
    size_t m_length;

  public:
    CharStack( void )
    {
      m_top = NULL;
      m_int = 0;
      m_length = 0;
    }
  private:
    void p_Delete( t_CharStackNode *p )
    {
      if( p != NULL )
      {
        p_Delete( p->m_down );
        free( p );
      }
    }
  public:
    ~CharStack( void )
    {
      p_Delete( m_top );
    }
    void p_Input( FILE *p_file, const char * const p_terminatorCharacters, char *p_terminatedByCharacter )
    {
      char c;
      t_CharStackNode *n;
      p_Delete( m_top );
      m_top = NULL;
      m_int = 0;
      m_length = 0;
      bool b = false;
      do
      {
        fscanf( p_file, "%c", &c );
        size_t i = 0;
        for( ; (( i < strlen( p_terminatorCharacters )) && ( !b )); i ++ )
          if( c == p_terminatorCharacters[ i ] )
            b = true;
        if( !b )
        {
          n = ( t_CharStackNode* )malloc( sizeof( t_CharStackNode ));
          n->m_down = m_top;
          m_top = n;
          n->m_char = c;
          if( m_length < ( size_t )-2 )
            m_length ++;
        }
      }
      while( !b );
      *p_terminatedByCharacter = c;
    }
    bool f_Empty( void )
    {
      return ( m_top == NULL );
    }
    void p_ConvertContentToInt( void )
    {
      if( f_Empty())
        throw "CharStack::p_ConvertContentToInt() - f_Empty() == true";
      else
      {
        t_CharStackNode *n = m_top;
        int multiplier = 1;
        m_int = 0;
        do
        {
          if(( n->m_char >= '0' ) && ( n->m_char <= '9' ))
          {
            m_int += (( n->m_char - '0' ) * multiplier );
            n = n->m_down;
            multiplier *= 10;
          }
          else
            throw "CharStack::p_ConvertContentToInt() - non-numerical character on stack";
        }
        while( n != NULL );
      }
    }
    int f_Int( void )
    {
      return m_int;
    }
    char *f_String( void )
    {
      char *s = ( char* )malloc( sizeof( char ) * ( m_length + 1 ));
      size_t i = 0, k = m_length - 1;
      t_CharStackNode *n = m_top;
      for( ; i < m_length; i ++, k --, n = n->m_down )
        s[ k ] = n->m_char;
      s[ i ] = '\0';
      return s;
    }
};

int main( void )
{
  CharStack cS;
  char c;
  cS.p_Input( stdin, "\n", &c );
  cS.p_ConvertContentToInt();
  const int numberOfCocktails = cS.f_Int();

  Cocktail **cocktail = ( Cocktail** )malloc( sizeof( Cocktail* ) * numberOfCocktails );
  int i = 0;
  char *s;
  StringTree ingredients;
  for( ; i < numberOfCocktails; i ++ )
  {
    cS.p_Input( stdin, ":", &c );
    s = cS.f_String();
    cocktail[ i ] = new Cocktail( s );
    free( s );
    do
    {
      cS.p_Input( stdin, ",\n", &c );
      s = cS.f_String();
      ingredients.p_Add( s );
      const int id = ingredients.f_Id( s );
      free( s );
      cocktail[ i ]->p_AddIngredientId( id );
    }
    while( c == ',' );
  }

  IntList ingredientsAvailable;
  do
  {
    cS.p_Input( stdin, ",\n", &c );
    s = cS.f_String();
    ingredients.p_Add( s );
    const int id = ingredients.f_Id( s );
    free( s );
    ingredientsAvailable.p_Add( id );
  }
  while( c == ',' );

  StringTree cocktailsCanMix;
  for( i = 0; i < numberOfCocktails; i ++ )
    if( cocktail[ i ]->f_MayMixWithIngredients( &ingredientsAvailable ))
    {
      s = cocktail[ i ]->f_Name();
      cocktailsCanMix.p_Add( s );
      free( s );
    }
  cocktailsCanMix.p_Print_InOrder();
  if( cocktailsCanMix.f_Empty())
    printf( "\n" );
  return 0;
}

Testing:

g++ -Wall O.cpp
mv a.out O
./O
11
Brazilian Sunrise:cachaca,grenadine,lemon juice,orange juice
Tequila Sunrise:tequila,grenadine,lemon juice,orange juice
Latin Lover:cachaca,tequila,lime juice,ananas juice,lemon juice
Caipirinha:cachaca,lime juice
Caipifragola:cachaca,strawberry liqueur,strawberry sirup,lime juice
Strawberry Daiquiri:rum,strawberry liqueur,lime juice
Margarita:tequila,cointreau,lime juice
Carribean Dream:rum,grenadine,orange juice,lemon juice,ananas juice,passion fruit nectar
Malibu Barbados:carribean rum with coconut,orange juice,ananas juice
Malibu Margarita:carribean rum with coconut,cointreau,tequila,ananas juice,lemon juice,lime juice
Malibu Sunrise:carribean rum with coconut,grenadine,orange juice
cachaca,lime juice,grenadine,lemon juice,orange juice,carribean rum with coconut
Brazilian Sunrise
Caipirinha
Malibu Sunrise
Advertisements


No Responses Yet to “O : Cocktails”

  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: