D : Line World

04Dec12

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 (D; hard difficulty):

Line World

Santa visits a one-dimensional consisting only of the following persons as its elements:

M male adult
F female adult
m male kid
f female kid
P parent (male or female)
O senior (male or female)

The following picture shows an example population.

Advent Programming Contest – D

Each person can only interact with its direct neighbour. The world is circular, so the person at the last position is a direct neighbor of the first position. The size of the world adjusts perfectly to the number of persons alife. The world implements the follwing transition rules:

  • f grows up to become F
  • m grows up to become M
  • MF, mf, mF or Mf bond and change to a family with kids and parents: fPPm
  • FM, fm, fM or Fm as long as neither of them is already bond change to a family with kids and parents: mPPf
  • single F ages to an O
  • single M ages to an O
  • P ages to O
  • O dies (gets removed)

For one iteration, each person can only once be part of one transistion. Newly created persons do not interact in the same round. If multiple transition rules can be applied to the same persons, mind the following priorities:

  • bonding rules have priority over single position transistions
  • in case multiple bondings are possible, prefer that one where the left neighbor has the lower position number
  • If a transistion with bonding takes place across the first and last element, say mXXXXf, the first element is replaced by offspring and parent and the last element by the other offspring and parent -> PfXXXXmP

Example: fPPmM -> PmOOMfP -> OMfPPmO -> fPPmOOM -> PmOOMfP -> OMfPPmO -> fPPmOOM -> PmOOMfP -> OMfPPmO …

Problem

Write a program that reads the current state (maximum 80 persons) from standard input. The next line contains a number identifying the current day in December. Simulate the world according to the rules above with a pace of one step per day until December 24. Write out the number of kids on December 24 as the result. Santa needs that number to arrange the correct amount of presents.

Sample Input 1

mfmfmf
20

Sample Output 1

6

Sample Input 2

MFm
1

Sample Output 2

2

Solution (D.cpp):

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

typedef struct t_Person_struct
{
  struct t_Person_struct *m_p, *m_n;
  bool m_spawnedThisIteration;
  char m_c;
}
t_Person;

class Population
{
  private:
    t_Person *m_first;

  public:
    Population( FILE *p )
    {
      m_first = NULL;
      char c;
      int i = 0;
      t_Person *pe, *last = NULL;
      do
      {
        fscanf( p, "%c", &c );
        if( c != '\n' )
        {
          if( i == 80 )
            throw "Population::<constructor> - too many characters in input";
          switch( c )
          {
            case 'M':
            case 'F':
            case 'm':
            case 'f':
            case 'P':
            case 'O':
              break;
            default:
              throw "Population::<constructor> - illegal character in input";
          }
          pe = ( t_Person* )malloc( sizeof( t_Person ));
          pe->m_p = last;
          pe->m_n = NULL;
          pe->m_spawnedThisIteration = false;
          pe->m_c = c;
          if( m_first == NULL )
            m_first = pe;
          else
            last->m_n = pe;
          last = pe;
          i ++;
        }
      }
      while( c != '\n' );
    }
  private:
    void p_Delete( t_Person *p )
    {
      if( p != NULL )
      {
        p_Delete( p->m_n );
        free( p );
      }
    }
  public:
    ~Population( void )
    {
      p_Delete( m_first );
    }
    void p_Iterate( int p /* Day of December */ )
    {
      if(( p < 1 ) || ( p > 24 ))
        throw "Population::p_Iterate() - illegal input value";
      for( ; p < 24; p ++ )
      {
        p_ClearSpawnedThisIterationFlag();
        p_KillO();
        p_AgePToO();
        p_Breed();
        p_AgeFAndMToO();
        p_Age_fToFAnd_mToM();
      }
    }
    int f_NumberOfChildren( void )
    {
      int i = 0;
      t_Person *p = m_first;
      while( p != NULL )
      {
        if(( p->m_c == 'f' ) || ( p->m_c == 'm' ))
          i ++;
        p = p->m_n;
      }
      return i;
    }
  private:
    void p_ClearSpawnedThisIterationFlag( void )
    {
      t_Person *p = m_first;
      while( p != NULL )
      {
        p->m_spawnedThisIteration = false;
        p = p->m_n;
      }
    }
    void p_KillO( void )
    {
      t_Person *p = m_first, *pr, *ne, *d = NULL;
      while( p != NULL )
      {
        if( p->m_c == 'O' )
        {
          pr = p->m_p;
          ne = p->m_n;
          if( pr != NULL )
            pr->m_n = ne;
          else
            m_first = ne;
          if( ne != NULL )
            ne->m_p = pr;
          d = p;
        }
        p = p->m_n;
        if( d != NULL )
        {
          free( d );
          d = NULL;
        }
      }
    }
    void p_AgePToO( void )
    {
      t_Person *p = m_first;
      while( p != NULL )
      {
        if( p->m_c == 'P' )
          p->m_c = 'O';
        p = p->m_n;
      }
    }
    void p_Breed( void )
    {
      t_Person *last = f_Last();
      if( m_first != NULL )
        if(( f_Female( m_first ) && f_Male( last ))
          || ( f_Male( m_first ) && f_Female( last )))
        {
          t_Person *Fc = f_SpawnChild( f_Female( m_first )?'m':'f' ), *Lc = f_SpawnChild( f_Male( last )?'f':'m' );
          Fc->m_p = m_first;
          Fc->m_n = m_first->m_n;
          m_first->m_n->m_p = Fc;
          m_first->m_n = Fc;

          Lc->m_p = last->m_p;
          Lc->m_n = last;
          last->m_p->m_n = Lc;
          last->m_p = Lc;
          m_first->m_c = 'P';
          last->m_c = 'P';
        }

      t_Person *p = NULL;
      if( m_first != NULL )
        p = m_first->m_n;
      while( p != NULL )
      {
        t_Person *L = p->m_p, *R = p;
        if(( !L->m_spawnedThisIteration ) && ( !R->m_spawnedThisIteration ))
          if(( f_Female( L ) && f_Male( R ))
            || ( f_Male( L ) && f_Female( R )))
          {
            t_Person *Lc = f_SpawnChild( f_Female( L )?'m':'f' ), *Rc = f_SpawnChild( f_Male( R )?'f':'m' );
            Lc->m_p = L->m_p;
            Lc->m_n = L;
            if( L->m_p == NULL )
              m_first = Lc;
            else
              L->m_p->m_n = Lc;
            L->m_p = Lc;

            Rc->m_p = R;
            Rc->m_n = R->m_n;
            if( R->m_n != NULL )
              R->m_n->m_p = Rc;
            R->m_n = Rc;
            L->m_c = 'P';
            R->m_c = 'P';
          }
        p = p->m_n;
      }
    }
    void p_AgeFAndMToO( void )
    {
      t_Person *p = m_first;
      while( p != NULL )
      {
        if(( p->m_c == 'F' ) || ( p->m_c == 'M' ))
          p->m_c = 'O';
        p = p->m_n;
      }
    }
    void p_Age_fToFAnd_mToM( void )
    {
      t_Person *p = m_first;
      while( p != NULL )
      {
        if( !p->m_spawnedThisIteration )
        {
          if( p->m_c == 'f' )
            p->m_c = 'F';
          else
            if( p->m_c == 'm' )
              p->m_c = 'M';
        }
        p = p->m_n;
      }
    }
    bool f_Female( const t_Person * const p )
    {
      return (( p->m_c == 'f' ) || ( p->m_c == 'F' ));
    }
    bool f_Male( const t_Person * const p )
    {
      return (( p->m_c == 'm' ) || ( p->m_c == 'M' ));
    }
    t_Person *f_SpawnChild( const char p )
    {
      t_Person *pe = ( t_Person* )malloc( sizeof( t_Person ));
      pe->m_p = NULL;
      pe->m_n = NULL;
      pe->m_spawnedThisIteration = true;
      pe->m_c = p;
      return pe;
    }
    t_Person *f_Last( void )
    {
      t_Person *p = m_first;
      if( p == NULL )
        return NULL;
      l_LOOP:
        if( p->m_n != NULL )
        {
          p = p->m_n;
          goto l_LOOP;
        }
        else
          return p;
    }
};

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;

  public:
    CharStack( void )
    {
      m_top = NULL;
      m_int = 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 )
    {
      char c;
      t_CharStackNode *n;
      p_Delete( m_top );
      m_top = NULL;
      m_int = 0;
      do
      {
        fscanf( p, "%c", &c );
        if( c != '\n' )
        {
          n = ( t_CharStackNode* )malloc( sizeof( t_CharStackNode ));
          n->m_down = m_top;
          m_top = n;
          n->m_char = c;
        }
      }
      while( c != '\n' );
    }
    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;
    }
};

int main( void )
{
  Population p( stdin );
  CharStack cS;
  cS.p_Input( stdin );
  cS.p_ConvertContentToInt();
  p.p_Iterate( cS.f_Int());
  printf( "%d\n", p.f_NumberOfChildren());
  return 0;
}

Testing:

g++ -Wall D.cpp
mv a.out D
./D
mfmfmf
20
6
./D
MFm
1
2
Advertisements


No Responses Yet to “D : Line 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: