B : Johnny’s Dice

02Dec12

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 (B; easy difficulty):

Johnny’s Dice

John von Neumann suggested a simple method for generating random numbers, which scaled well on the computers of his time. The method, called the middle-square method works as follows: Start with a seed number, square it, cut out the middle digits of the resulting number as the random number, then use that number as the seed for the next iteration. Von Neumann used 10 digit numbers but for our purpose, 2 digits will do:

Implement the following algorithm: Start with a given seed, which is an integer between 1 and 99. The number is then squared, if necessary padded with zeros to 4 digits, and the second and third digit form the random number, which is also used as the new seed.

Problem

Your task is to implement this random number generator. Your program should read from standard input. If a line contains an integer number between 1 and 99, take this as the seed, calculate the next number and print it (without leading zeroes) to standard output followed by a newline character. If the input is 0, the program should terminate.

Sample Input

12
99
7
0

Sample Output

14
80
4

Solution (B.c):

#include <stdio.h>
#include <stdlib.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 );
bool f_CharStack_Empty( void );
void p_CharStack_ConvertContentToInt( void );
bool f_CharStack_ErrorOccurredConvertingContentToInt( void );
int f_CharStack_Int( void );

int main( void )
{
  int i;
  l_LOOP:
    p_CharStack_Input( stdin );
    p_CharStack_ConvertContentToInt();
    if( f_CharStack_ErrorOccurredConvertingContentToInt())
      return -1;
    i = f_CharStack_Int();
    if(( i >= 1 ) && ( i <= 99 ))
    {
      i *= i;
      char s[ 5 ];
      sprintf( s, "%s%s%s%d", ( i < 1000 )?"0":"", ( i < 100 )?"0":"", ( i < 10 )?"0":"", i );
      if( s[ 1 ] != '0' )
        printf( "%c", s[ 1 ] );
      printf( "%c\n", s[ 2 ] );
      goto l_LOOP;
    }
    else
      if( i != 0 )
        return -2;
  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 )
{
  char c;
  t_CharStackNode *n;
  p_CharStack_Reset();
  do
  {
    fscanf( p, "%c", &c );
    if( 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 != '\n' );
}

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 B.c
mv a.out B
./B
12
14
99
80
7
4
0
Advertisements


No Responses Yet to “B : Johnny’s Dice”

  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: