/*
	 * usage: tur <quintuples> <inputs>
	 * Quintuples are in the form
	 * 
	 * qi a b M qj  .........
	 * 
	 * i and j are zero-suppressed integers; can't have
	 * q1 and q01.  M is 'L' or 'R'.  Blank is 'B' in quintuples.
	 * It is expected that every state begins with the letter q.
	 *
	 * One quintuple per line.  Comments after the quintuple are
	 *				ignored.
	 * Lines which are empty or begin with a space are ignored.
	 * Hence more comments are possible.
	 * For example the text between the hyphens defines a machine
----------------------------------

q0 0 B R q0     move right on 0
q0 1 B R q0     move right on 1
q0 B B L q0     move left on blank

	Implicitly the input alphabet is binary, and
	the machine always loops

----------------------------------
	 */

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

#define ORIGIN 1000
#define SIZE 2000

void decr ( char s[] )
{
  int i;

  for (i=0; s[i]!= '\0'; ++i)
    if ( s[i] == '\n' )
    {
      s[i] = '\0';
      return;
    }
}


int getnumber ( char ** buff )
{
  char *buffer = *buff;
  int i, a;

  while( *buffer != '\0' && ! isdigit ( * buffer ) )
    ++buffer;

  if ( *buffer == '\0' )
  {
    *buff = buffer;
    return -1;
  }

  a = 0;
  while ( isdigit ( * buffer ) )
  {
    a = 10*a + *buffer - '0';
    ++ buffer;
  }

  *buff = buffer;
  return a;
}

int dontuse ( char buf[] )
{
  if (( ! isspace ( buf[0] )) && buf[0] != '\0' )
    return 0;
  else
    return 1;
}

int lookup ( int thestate, char symbol, int state[], char scanned[], int count )
{
  int i;
  for (i=0; i<count; ++i)
    if ( thestate == state[i] && symbol == scanned[i] )
      return i;

  return -1;
}

void show_config ( int state, char tape[], int place, int minplace,
		int maxplace)
{
  int i;

  printf("Configuration: state q%d\n", state);
  for (i=minplace; i<=maxplace; ++i)
    printf("%c", tape[ORIGIN+i]);
  printf("\n");
  for (i=minplace; i<=maxplace; ++i)
    if ( i<place )
      printf (" ");
    else if ( i == place )
      printf ("^");
  
  printf("\n");
}
  
main(int argc, char * argv[])
{
  char oldstatechar[1000];
  int oldstate[1000];
  char scanned[1000];
  char overwrite[1000];
  char move[1000];
  int newstate[1000];
  char newstatechar[1000];
  int count,i;
  int final_state,state, square;
  int minplace, maxplace;
  int trace;

  char tape[SIZE];

  int timeout;

  char buffer[200];
  FILE * inputs, * machine;
  int ok;

  ok = 1;

  if (argc < 3 )
    ok = 0;

  if ( ok && strcmp ( argv[1], "-trace" ) == 0 )
  {
    trace = 1;
    if ( argc < 4 )
      ok = 0;
     else
     {
	machine = fopen ( argv[2], "r" );
	inputs = fopen ( argv[3], "r" );
     }
  }
  else
  {
    trace = 0;
    machine = fopen ( argv[1], "r" );
    inputs = fopen ( argv[2], "r" );
  }

  if ( !ok )
  {
    fprintf(stderr,"usage: %s [-trace] <machine> <inputs>\n", argv[0]);
    exit(-1);
  }

  count = 0;
  while ( fgets ( buffer, 1000, machine ) != NULL )
  {
    char * buf = buffer;

    if ( dontuse ( buffer ) )
	continue;

    oldstatechar[count] = *buf;
    ++buf;
    oldstate[count] = getnumber ( & buf );
    ++buf;
    scanned[count] = *buf;
    buf += 2;
    overwrite[count] = *buf;
    buf += 2;
    move[count] = *buf;
    buf += 2;
    newstatechar[count] = *buf;
    ++buf;
    newstate[count] = getnumber ( & buf );
    ++count;
  }

  fclose ( machine );

  for (i=0; i<count; ++i)
    printf("%c%d %c %c %c %c%d\n", oldstatechar[i],
	oldstate[i], scanned[i], overwrite[i], move[i], newstatechar[i],
	newstate[i]);

  while ( fgets (  buffer, 200, inputs ) != NULL  )
  {
    decr ( buffer );
    if ( dontuse ( buffer )  )
      continue;

    for (i=0; i<SIZE; ++i)
      tape[i] = 'B';
  
    timeout = 1000;
  
    printf("\ninput: %s\n", buffer);
    minplace = 0;
  
    for (i=0; buffer[i] != '\0' && ! isspace ( buffer[i] ); ++i)
      tape[ORIGIN + i] = buffer[i];
  
    maxplace = i-1;
  
    state = 0;
    square = 0;
  
  
    while ( timeout-- > 0 && state >= 0 && -1000 < square && 1000 > square )
    {
      if ( trace )
        show_config ( state, tape, square, minplace, maxplace );
      final_state = state;
      int ndex =
	lookup ( state, tape[square + ORIGIN], oldstate, scanned, count );
      if ( square < minplace )
  	minplace = square;
      if ( square > maxplace )
  	maxplace = square;
      if ( ndex >= 0 )
      {
        tape[square + ORIGIN] = overwrite[ndex];
        if ( move[ndex] == 'L' )
  	--square;
        else
  	++square;
        state = newstate[ndex];
      }
      else
        state = -1;
    }
  
    if ( timeout <= 0 )
      printf( "output: loops\n");
    else
    {
      printf("output:");
      for (i=minplace; i<=maxplace; ++i)
        if ( tape[ORIGIN+i] == 'B' )
  	printf(" ");
        else
          printf("%c", tape[ORIGIN+i]);
      //printf(" in state q%d\n", final_state);
      printf("\n");
    }     
  }
}