/***********************************************
** ProjectB: Robot Control Program            **
** Subject : 433-142 Computing Fundamentals B **
** Date	   : 19th September, 2001             **
** Name	   : Huang Jian                       **
** Enrolment number: 126432                   **
***********************************************/

/**********************************************/
/*Included Files and Symbolic Constants       */

#include <stdio.h>

#define ROW     40
#define COL     80
#define FACE    4

#define FACE1	'^'
#define FACE2	'<'
#define FACE3	'v'
#define FACE4	'>'

#define DOT     '.'
#define SPACE   ' '
#define WALL    '*'

#define TRUE	1
#define FALSE	0

/**********************************************/
/*Function Prototypes                         */

void init_map (char [][COL]);
void get_map (char [][COL]);
void print_map (char [][COL], char *[]);
void execute (char [][COL]);
void left_turn (char [], char *);
void right_turn (char [], char *);
char *go_forward (char [][COL], char *);
char *locate_robot (char [][COL]);
void add_rec (char *, char *[]);
void add_id (char, char[]);
void boxes_to_move (char [][COL], char [], char *, char);
void what_in_front(char [][COL], char [], char *, char);
int is_robot (char);
int is_box (char *);
int is_element(char, char []);
int is_one_movable (char *, char);
int is_all_movable (char [][COL], char, char);
int is_all_boxes_movable (char [][COL], char [], char);
void move_box (char [][COL], char [], char);
void move_line_box (char *, char[], char);
void forward_box (char *, char);
void forward_robot (char *);

/**********************************************/
/*Main Function                               */
int main (void)
{
  char map [ROW][COL];
  
  init_map (map);
  get_map (map);
  execute (map);

  return 0;
}

/**********************************************/
/*Initial Map Array                           */
void init_map (char map[][COL])
{
  int i, j;

  for (i=0;i<ROW;i++)
    for (j=0;j<COL;j++)
      map[i][j] = NULL;

  return;
}

/**********************************************/
/*Inport Map from Standard Input              */
void get_map (char map[][COL])
{
  int i=0;

  while (gets (map[i++]) != NULL)
    if (map[i-1][0] == NULL)  return;

  return;
}

/**********************************************/
/*Command Execution Function                  */
void execute (char map[][COL])
{
  char c,
       *robot,
       face [FACE] = {FACE1,FACE2,FACE3,FACE4},
       *trail_rec [ROW*COL] = {NULL};         //map-sized array to 
	                                      //record robot trails
  robot = locate_robot (map);

  while ((c = getchar()) == '(')
  {
    while ((c = getchar()) != ')')
	{
      add_rec (robot, trail_rec);
			
      if (c == 'l' || c == 'L') 
        left_turn (face, robot);
      if (c == 'r' || c == 'R') 
        right_turn (face, robot);
      if (c == 'f' || c == 'F') 
        robot = go_forward (map, robot);
      if (c == 'p' || c == 'P') 
        print_map (map, trail_rec);
	}
  }

  return;
}

/**********************************************/
/*Print Map to Standard Output                */
void print_map (char map[][COL], char *trail_rec[])
{
  int i;

  for (i=0;trail_rec[i] != NULL;i++)          //adding trails to map
    if (*trail_rec[i] == SPACE)
        *trail_rec[i] = DOT;

  for (i=0; map[i][0] != NULL; puts (map[i++]));
  
  printf ("\n");

  return;
}

/**********************************************/
/*'L' Responce--Turn Left                     */
void left_turn (char face[], char *robot)
{
  int n;

  for (n=0; *robot != face[n]; n++);
  
  if (*robot != face[3])
      *robot = face[n+1];
  else
      *robot = face[0];

  return;
}

/**********************************************/
/*'R' Responce--Turn Right                    */
void right_turn (char face[], char *robot)
{
  int n;

  for (n=3; *robot != face[n]; n--);
  
  if (*robot != face[0])
      *robot = face[n-1];
  else
      *robot = face[3];

  return;
}

/*********************************************/
/*'F' Responce--Push Box                     */
char *go_forward (char map[][COL], char *robot)
{
  char id[27] = {0};                         //reserve array to record
                                             //boxes need to move  
  if (*robot == FACE1)                       //including robot
  {	
    if (*(robot-COL) == DOT || *(robot-COL) == SPACE)
        forward_robot (robot);
		
    else if (is_box (robot-COL))
	{	
       boxes_to_move (map, id, robot-COL, FACE1);
			
       if (is_all_boxes_movable (map, id, FACE1))
           move_box (map, id, FACE1);
	}
  }
  
  if (*robot == FACE2)
  {	
    if (*(robot-1) == DOT || *(robot-1) == SPACE)
        forward_robot (robot);
		
    else if (is_box (robot-1))
	{	
       boxes_to_move (map, id, robot-1, FACE2);
			
       if (is_all_boxes_movable (map, id, FACE2))
           move_box (map, id, FACE2);
	}
  }
  
  if (*robot == FACE3)
  {	
    if (*(robot+COL) == DOT || *(robot+COL) == SPACE)
        forward_robot (robot);
		
    else if (is_box (robot+COL))
	{	
       boxes_to_move (map, id, robot+COL, FACE3);
			
       if (is_all_boxes_movable (map, id, FACE3))
           move_box (map, id, FACE3);
	}
  }
  
  if (*robot == FACE4)
  {	
    if (*(robot+1) == DOT || *(robot+1) == SPACE)
        forward_robot (robot);
		
    else if (is_box (robot+1))
	{	
       boxes_to_move (map, id, robot+1, FACE4);
			
       if (is_all_boxes_movable (map, id, FACE4))
           move_box (map, id, FACE4);
	}
  }
  
  robot = locate_robot (map);

  return robot;
}


/**********************************************/
/*Locate Position of the Robot                */
char *locate_robot (char map[][COL])
{
  int i, j;

  for (i=0; i<ROW; i++)
    for (j=0;j<COL;j++)
      if (is_robot (map[i][j]))
        return &map[i][j];

  return NULL;
}

/**********************************************/
/*Record Trail of Robot                       */
void add_rec (char *robot, char *trail_rec[])
{
  int i;

  for (i=0;trail_rec[i] != NULL;i++)
    if (trail_rec[i] == robot)	return;

  trail_rec[i] = robot;

  return;
}

/**********************************************/
/*Adding Box's ID to List                     */
void add_id (char box, char id[])
{
  if (is_robot(box))  id[26] = box;           //put robot to last cell
  else                id[box-'A'] = box;      //boxes in alphabet. order

  return;
}

/**********************************************/
/*Checking Which Box(es) Need to Move         */
void boxes_to_move (char map[][COL], char id[], char *box, char direct)
{
  add_id (*box, id);                          //box advanced need move
  add_id (direct, id);                        //robot need move
  what_in_front (map, id, box, direct);       //anything in front need move

  return;
}

/**********************************************/
/*Finding All Boxes in Front                  */
void what_in_front(char map[][COL], char id[], char *box, char direct)
{
  int i, j;

  if (direct == FACE1)                       //start from present box
  {                                          //checking all boxes in
    for (i=1;i<ROW;i++)                      //front recursively
      for (j=0;j<COL;j++)
        if (map[i][j] == *box &&
            map[i-1][j] != *box &&
            is_box (&map[i-1][j]) &&
            !(is_element (map[i-1][j], id)))
	{                                    //if box id not recorded
            add_id (map[i-1][j], id);        //add it to id list
            what_in_front (map, id, &map[i-1][j], FACE1);
	}
  }
	
  if (direct == FACE2)
  {
    for (i=0;i<ROW;i++)
      for (j=1;j<COL;j++)
        if (map[i][j] == *box &&
            map[i][j-1] != *box &&
            is_box (&map[i][j-1]) &&
            !(is_element (map[i][j-1], id)))
	{
            add_id (map[i][j-1], id);
            what_in_front (map, id, &map[i][j-1], FACE2);
	}
  }
	
  if (direct == FACE3)
  {
    for (i=0;i<ROW-1;i++)
      for (j=0;j<COL;j++)
        if (map[i][j] == *box &&
            map[i+1][j] != *box &&
            is_box (&map[i+1][j]) &&
            !(is_element (map[i+1][j], id)))
	{
            add_id (map[i+1][j], id);
            what_in_front (map, id, &map[i+1][j], FACE3);
	}
  }
	
  if (direct == FACE4)
  {
    for (i=0;i<ROW;i++)
      for (j=0;j<COL-1;j++)
        if (map[i][j] == *box &&
            map[i][j+1] != *box &&
            is_box (&map[i][j+1]) &&
            !(is_element (map[i][j+1], id)))
	{
            add_id (map[i][j+1], id);
            what_in_front (map, id, &map[i][j+1], FACE4);
	}
  }

  return;
}

/**********************************************/
/*Robot Existence Check                       */
int is_robot (char r)
{
  if (r == FACE1 || r == FACE2 ||
      r == FACE3 || r == FACE4   )	
      return TRUE;

  return FALSE;
}

/**********************************************/
/*Box Existence Check                         */
int is_box (char *box)
{
  if (*box == SPACE ||
      *box == DOT   ||
      *box == WALL  ||
      is_robot (*box) )  return FALSE;
  else                   return TRUE;
}

/**********************************************/
/*Box ID Existence Checking                   */
int is_element(char c, char box_id[])
{
  int i;

  for (i=0;i<27;i++) 
    if (box_id[i] != 0 && c == box_id[i]) return TRUE;

  return FALSE;
}

/**********************************************/
/*Multi-Package Movability Check              */
int is_all_boxes_movable (char map[][COL], char id[], char direct)
{
  int i;

  for (i=0;i<26;i++)
    if (id[i] != 0)
      if (!(is_all_movable (map, id[i], direct)))
        return FALSE;

  return TRUE;
}

/**********************************************/
/*Package Movability Check                    */
int is_all_movable (char map[][COL], char box_id, char direct)
{
  int i, j;

  for (i=0;i<ROW;i++)
    for (j=0;j<COL;j++)
      if (map[i][j] == box_id)
        if (!(is_one_movable (&map[i][j], direct))) 
          return FALSE;

  return TRUE;
}

/**********************************************/
/*single-Box Movability Check                 */
int is_one_movable (char *box, char direct)
{
  if (direct == FACE1 && *(box-COL) != WALL)	return TRUE; 
  if (direct == FACE2 && *(box-1)   != WALL)	return TRUE;
  if (direct == FACE3 && *(box+COL) != WALL)	return TRUE;
  if (direct == FACE4 && *(box+1)   != WALL)	return TRUE;

  return FALSE;
}

/**********************************************/
/*Multi-Box Movement Control                  */
void move_box (char map[][COL], char id[], char direct)
{
  int i;
	                                      //start from the line
  if (direct == FACE1)                        //furthest to robot
    for (i=0;i<COL;i++)                       //move line by line
        move_line_box (&map[0][i],id,FACE1);
  
  if (direct == FACE2)
    for (i=0;i<ROW;i++)
        move_line_box (&map[i][0],id,FACE2);
  
  if (direct == FACE3)
    for (i=0;i<COL;i++)
        move_line_box (&map[ROW-1][i],id,FACE3);
  
  if (direct == FACE4)
    for (i=0;i<ROW;i++)
        move_line_box (&map[i][COL-1],id,FACE4);

  return;
}

/**********************************************/
/*Line-By-Line Box Movement Control           */
void move_line_box (char *line, char box_id[], char direct)
{
  int i;
                                              //start from furthest 
  if (direct == FACE1)                        //point in a line
  {	                                      //move box one by one
	for (i=0;i<ROW;i++)                   
      if (is_element(*(line+i*COL), box_id))
         forward_box (line+i*COL,FACE1);
  }
	
  if (direct == FACE2)
  {	
	for (i=0;i<COL;i++)
      if (is_element(*(line+i), box_id))
         forward_box (line+i,FACE2);
  }
	
  if (direct == FACE3)
  {	
	for (i=0;i<ROW;i++)
      if (is_element(*(line-i*COL), box_id))
         forward_box (line-i*COL,FACE3);
  }
	
  if (direct == FACE4)
  {	
	for (i=0;i<COL;i++)
      if (is_element(*(line-i), box_id))
         forward_box (line-i,FACE4);
  }

  return;
}

/**********************************************/
/*sigle-Box Movement Control                  */
void forward_box (char *box, char direct)
{
  if (direct == FACE1)
  {	*(box-COL) = *box;
    *box = SPACE;
  }
	
  if (direct == FACE2) 
  {	*(box-1) = *box;
    *box = SPACE;
  }
 
  if (direct == FACE3) 
  {	*(box+COL) = *box;
    *box = SPACE;
  }
	
  if (direct == FACE4)
  {	*(box+1) = *box;
    *box = SPACE;
  }	

  return;
}

/**********************************************/
/*Robot Movement Control--Go Forward          */
void forward_robot (char *robot)
{
  if (*robot == FACE1 && *(robot-COL) != WALL)
  {
    *(robot-COL) = FACE1;
    *robot = DOT;
  }

  if (*robot == FACE2 && *(robot-1) != WALL)
  {	
	*(robot-1) = FACE2;
    *robot = DOT;
  }

  if (*robot == FACE3 && *(robot+COL) != WALL)
  {	
	*(robot+COL) = FACE3;
    *robot = DOT;
  }

  if (*robot == FACE4 && *(robot+1) != WALL)
  {	
	*(robot+1) = FACE4;
    *robot = DOT;
  }

  return;
}