A standard chess-board has 8 columns denoted by letters from A through H and 8 rows denoted by digits from 1 through 8. The following problems concern the chess king.
Program the following commands for moving the king:
FORWARD n -- to move repeatedly the king through n squares
forward.
TORIGHT n -- to move repeatedly the king through n squares to
the right hand direction.
BACKWARD n -- to move repeatedly the king through n squares backward.
TOLEFT n -- to move repeatedly the king through n squares to the
left hand direction.
REACH <position> -- to place the king on <position>
according to the rules of the chess game, i.e. at the next square in any
direction. The <position> is specified as usual by a combination
of one letter and one digit, e.g. A5, C7, etc..
Given an initial position of the king and a program for moving in the following form
BEGIN
COMMAND_1;
COMMAND_2:
........
COMMAND_N;
END
where the commands are described in the previous problem, you should output the sequence of moves, that the king will make.
An example:
Given initial position A1 and the following program
BEGIN
FORWARD 2;
TORIGHT 3;
REACH E4;
END
the sequence of moves can be look like the following one:
A1 A2 A3 B3 C3 D3 E3 E4.
Let us divide commands FORWARD, TORIGHT, BACKWARD and TOLEFT into two groups. The first one consists of FORWARD and BACKWARD, whereas the second one consists of TORIGH and TOLEFT. Let us consider a program, that contains only commands FORWARD, TORIGHT, BACKWARD and TOLEFT. An allowed substitution is to replace two adjacent commands belonging to different groups by one REACH command. After making such a substitution, the total number of commands will decrease by 1.
Write a program, that transforms a given program by making substitutions of the above type, so that the king will do the minimal number of moves.
Source: Obuchenieto po matematika i informatika, journal published by
Bulgarian Ministry of Education, n. 2, 1991, pp. 39-40.
© The text is translated from Bulgarian by Emil
Kelevedzhiev (keleved@math.bas.bg)
Return to the Home
Page of Bulgarian Mathematics and Informatics Competitions.