The End of the World

(Solution to Practice Problem E2)

/****************************************************************
 *
 *  ACS Programming Competition 1995
 *
 *  Solution to Practice problem E2
 *
 *  The end of the World.
 *
 *  Brendan Humphreys
 *  brendan@cssa.anu.edu.au
 *
 *
 *
 */

#define NUM  256
#define CH   257
#define DONE 258


int hint[6][5];
int digit[5];
int l,i,r;
int pos = 0, rules = 0;
int tokenval = 0;
int negvar = 0;

int lexan()
{ 
    int t;
    while(1)
    {
	t = getchar();
	if (t == '\n') 
	    return DONE;
	else if (isdigit(t))
	{ 
	    tokenval = t - '0';
	    return NUM;
	}
	else if (isalpha(t))
	{ 
	    tokenval = t;
	    return CH;
	}
	else if (t == '#')
	{
	    exit(0);
	    return;
	}
	else
	{
	    tokenval = -1;
	    return t;
	}
    }
}

parse()   /* parses and translates expression list */
{
    l = lexan();
    while (l != DONE)
    {
	rules++;
	pos = 0;
	for (i = 0; i < 5; i++)
	    hint[rules][i] = 0;
	var(); match('='); expr(); match(';');
    }
}

var()
{ 
    if (l == CH)
    {
	hint[rules][pos] = 'e'- tokenval + 1;
	pos++;
	match(CH);
	return;
    }
    pos++;
    return;
}

expr()
{
    int t;
    stmt();
    switch (l)
    {
      case '-':
	negvar =  1;
	match(l);
	stmt();
	break; 
      case '+':
	match(l);
	stmt();
	break;
      default:
	break;
    }
    return;
}
stmt()
{
    int t;
    switch (l)
    {
      case NUM:
	t = l;
	if (negvar)
	{
	    negvar = 0;
	    tokenval = -1 * tokenval;
	}
        hint[rules][pos] = tokenval;
        pos++;
	match(l);
	var();
	return;
	break;
      case CH:
	if (negvar) 
	{ 
	    hint[rules][pos] = -1;
	    negvar = 0;
	}
	else
	    hint[rules][pos] = 1;
	pos++;
	var();
      default:
	return;
    }
} 
int match(t)
    int t;
{
    if (l == t ) 
	l = lexan();
    else 
    {
	printf("syntax error! expecting %c, got %d\n",t,l);
	exit(1);
    }	
}

void n2d(int n)
{
    int j;
    digit[0] = 1; 
    for (j=5; j > 0; j--)
    {
	digit[j] = n % 10;
        n = n / 10;
    }
}

void main()
{
    int r;
    int i;
    while(1)
    { 
	rules = 0;  
	parse();
	for (i = 1994; i < 100000; i++ )
	{
	    n2d(i); 
	    for (r = 1; r <= rules; r++ )
		if (!(digit[hint[r][0]] == (hint[r][1]*digit[hint[r][2]] 
		      + hint[r][3]*digit[hint[r][4]]) % 10 ))
		    break;
	    if (r > rules)
	    {
		for (i = 1; i <= 5; i++ )
		    printf("%d",digit[i]);  
		printf("\n");
		break;
	    }
	}
	if (i == 100000)
	    printf("We are saved!\n");
    }
}