# IT6 - Editorial

Practise

Contest

Author: Alisha M Baji

Tester: Alex Mathew

Editorialist: Alex Mathew

EASY-MEDIUM

OBSERVATION

### PROBLEM:

Kiran got a very ancient TV set from his grandfather’s attic. When she switched it on, she learnt that the remote controls were very different from the modern TV remotes. To switch to another channel, she needs to bring up virtual keyboard console and press direction keys to write the channel name to go to that channel.
The virtual console looks like this :

A B C D E

F G H I J

K L M N O

P Q R S T

U V W X Y

Z

Help her write a code to find the shortest path to print a channel name on the virtual screen. Given a screen containing alphabets from A-Z, we can go from one character to another characters using a remote. The remote contains left, right, top and bottom keys.

Find shortest possible path to type all characters of given string using the remote. Initial position is top left and all characters of input string should be printed in order.

Input:

EACBD EABCD

Output:

Move Down

Move Right

Press OK

Move Up

Move Right

Move Right

Move Right

Press OK

Press OK

Move Left

Move Left

Move Left

Move Left

Move Down

Move Down

Press OK

### EXPLANATION:

Consider the virtual keyboard as a 2D matrix and each character of the name to be printed. Calculate the distance of x and y positions of the current and the next character. Depending on the row and column difference either move up or down or left or right of the matrix.
For example,

If row difference is negative, move up the matrix, otherwise move down.
If column difference is negative move left, otherwise move right.
Once the next character is reached, print ‘Press okay’ and repeat for the current and next character.

### BASIC FUNCTION

void printPath(string str)

{
int i = 0;
// start from charcater ‘A’ present at position (0, 0)

``````int curX = 0, curY = 0;

while (i < str.length())
{
// find cordinates of next character
int nextX = (str[i] - 'A') / 5;
int nextY = (str[i] - 'B' + 1) % 5;

// Move Up if destination is above
while (curX > nextX)
{
cout << "Move Up" << endl;
curX--;
}

// Move Left if destination is to the left
while (curY > nextY)
{
cout << "Move Left" << endl;
curY--;
}

// Move down if destination is below
while (curX < nextX)
{
cout << "Move Down" << endl;
curX++;
}

// Move Right if destination is to the right
while (curY < nextY)
{
cout << "Move Right" << endl;
curY++;
}

// At this point, destination is reached
cout << "Press OK" << endl;
i++;
}
``````

}

This code runs with a complexity of O(n)

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.