IT6 - Editorial

alexmathew · November 17, 2016, 5:55am

PROBLEM LINK:

Practise

Contest

Author: Alisha M Baji

Tester: Alex Mathew

Editorialist: Alex Mathew

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

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.

EXAMPLE

Input:

EACBD EABCD

Output:

Move Down

Move Right

Press OK

Move Up

Move Right

Press OK

Move Left

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.