CareerCup

If we observe the 2D matrix[6][5], we have integer values as (intVal) :
a -> 0
b -> 1
e -> 4
f -> 5
.
.
.
z -> 25
=====================
Map these 1D values to 2D index values.

Let [ _i ] [ _j ] be current position of cursor on matrix.

Let i be a row_no and j be col_no.
ROW = 6;
COL = 5;

for any alphabet 'input', find [i][j] like this
i = intVal(input) / COL;
j = intVal(input) % COL;

now first move (i - _i) horizontal steps, then move (j - _j) vertical steps. This can be printed also.
After reaching to [i][j], print '!' (OK button), then update values of [ _i ] [ _j ] equal to [i][j].

In C#
--------

public void FindMovementMatrix(string input)
        {
            //-----------------------------------------
            //Can put this segment out of this function so that it won't be called everytime this function called
            Point[] coordinateList = new Point[26];
            for (int i = 0; i < 26; i++)
                coordinateList[i] = new Point(i % 5, i / 5); //assign coordinate to point 0-25 (a-z)
            //-----------------------------------

            Point p_curr = coordinateList[0];
            int x_dist = 0;
            int y_dist = 0;
            foreach (char c in input)
            {
                if (c < 97 && c > 122) //ASCII representation of a-z is 97-122
                {
                    Console.WriteLine("\nUnsupported charater found! {0}", c);
                    break;
                }

                int idx = c - 97; //idx should start from 0 thus minus with 97 (a character)

                x_dist = coordinateList[idx].X - p_curr.X;
                y_dist = coordinateList[idx].Y - p_curr.Y;

                if (x_dist < 0)
                    for (int j = x_dist; j < 0; j++)
                        Console.Write("L");
                if (y_dist < 0)
                    for (int j = y_dist; j < 0; j++)
                        Console.Write("U");
                if (x_dist > 0)
                    for (int j = 0; j < x_dist; j++)
                        Console.Write("R");
                if (y_dist > 0)
                    for (int j = 0; j < y_dist; j++)
                        Console.Write("D");

                p_curr = coordinateList[idx];
            }

            Console.WriteLine("!");
        }

Where can we assume the initial position of cursor?

16 #include <stdio.h>
 17 #include <strings.h>
 18 void print_path(int src,int dst){
 19   
 20   while(dst!=src) {
 21     if(dst%5 > src%5) {printf("r");src+=1;}
 22     else if(dst%5 < src%5) {printf("l");src-=1;}
 23     else{ 
 24       if(dst>src) {printf("d"); src+=5;}
 25       else {printf("u");src-=5;}
 26     }
 27   } 
 28     printf("!");
 29 }
 30 
 31 //assume lower case
 32 void remote(char *str, int len){
 33   int cur=0;
 34   int src;
 35   int dst;
 36   
 37   while(cur!=len-1){
 38     src=str[cur]-'a'; //convert to 0-25
 39     dst=str[cur+1]-'a';
 40     print_path(src,dst);
 41     cur++;
 42   } 
 43 } 
 44 
 45 int main(int argc, char *argv[]){
 46   char *in;
 47   if(argc<2)
 48     in="balamark";
 49   else
 50     in=argv[1];
 51 
 52   remote(in, strlen(in));
 53   return 0;
 54 }

There can be multiple sequences. Do they want all such path or anyone?

we can map each alphabet to a coordinate.....create a list of coordinates and then apply djikstra to get to the next alphabet.

I think there will also be a special case for letter 'z'. There is only "up" direction possible from that location.

my approach
1. Maintain a hashtable which stores char --> address
2. As there is no diagonal moment possible, the shortest distance from the current point to the target would be moving horizontally till we reach the column containing the target and moving vertically to the row containing the target.(increase/decrease x and increase/decrease y)
3. print out the sequence while moving and print ! once you reach the target.

char *getCommand(char *word)
{

    int index = 0;

    int prevX = -1;
    int prevY = -1;

    std::string result;

    while (word[index] != '\0')
    {
        int offset = word[index] - 'a';

        int x = offset % 5;
        int y = offset / 5;

        if (prevX == -1)
        {
            prevX = x;
            prevY = y;
        }
        else
        {
            if (x - prevX > 0)
            {
                for(int e=prevX; e<x; ++e)
                {
                    result.append("r");
                }
            }
            else
            {
                for(int e = x; e<prevX; ++e)
                {
                    result.append("l");
                }
            }

            if (x - prevY > 0)
            {
                for(int e=prevY; e < y;++e)
                {
                    result.append("d");
                }
            }
            else
            {
                for(int e = y; e<prevY;++e)
                {
                    result.append("u");
                }
            }

            prevX = x;
            prevY = y;
        }

        index++;
    }

    char *command = new char[result.length()+1];
    memcpy(command, result.c_str(), result.length());
    command[result.length()] = '\0';
    return command;
}

class Solution
{
/* return the position of the char c in alphabet. example position a = 0, position b = 1 */
public static int getPosition( char c )
{
	int n = (int)c;
	return n - 96 ;
}
/* from the position of a char, determine it's x coordinate in the keyboard */
public static int getX(int position )
{
	return position / 5 ;
}
/* from the position of a char, determine it's y coordinate in the keyboard */
public static int getY(int position)
{
	return position % 5 ;
}

/* make an print the combination that writes the word */
public static void makeCombination(String word)
{
	int size = word.length();
	int pos = 0;
	char prev = '`';  /*  has acii = 96. make sure we start at (0,0) */
	char next ;
	StringBuilder comb = new StringBuilder();
	while( pos < size )
	{
		
		next = word.charAt(pos++);  
		int prev_pos = getPosition(prev);
		int next_pos = getPosition(next);
		comb.append( genMove( getX(prev_pos), getY(prev_pos),
		 getX(next_pos),  getY(next_pos)));  /* combination for prev -> next in kb */
		prev = next;
	}
	System.out.println(comb);
}


public static String genMove(int i , int j , int m , int n)
{
	/* instead of djikstra or else to find the shortest path */
	/* it's more efficient to just go up and down. pretty simple too */
	/* though i agree if this program is to be use in the long run, moves must be 
	precomputed and stored somewhere so we don't have to do this every time */
	StringBuilder move = new StringBuilder();

	if( i < m )
	{
		/* move down on the keyboard */
		int cnt = 0;
		while(cnt++ < m - i )
		{
			move.append('d');
		}
	}
	if( i > m )
	{
		/* move up on keyboard */
		int cnt = 0;
		while(cnt++ < i - m )
		{
			move.append('u');
		}
	}
	if( j < n )
	{
		/* then move right */
		int cnt = 0;
		while(cnt++ < n - j )
		{
			move.append('r');
		}
	}

	if( j > n )
	{
		/* then move left */
		int cnt = 0;
		while(cnt++ < n - j )
		{
			move.append('l');
		}
	}
	move.append('!'); /* found the letter sought*/
	return move.toString();
}
public static void main(String arg[])
{
	/* run example */
	String string = new String("vaiejoahvuhpae");
	makeCombination(string);
}

}

refer to my earlier reply for the approach

public class AlphabetMatrixMoves {

	public static void main(String args[]) {
		char[][] array = { { 'a', 'b', 'c', 'd', 'e' },
				{ 'f', 'g', 'h', 'i', 'j' }, { 'k', 'l', 'm', 'n', 'o' },
				{ 'p', 'q', 'r', 's', 't' }, { 'v', 'u', 'w', 'x', 'y' },
				{ 'z' } };

		HashMap<Character, int[]> map = fillMap(array);

		String testStr = "zkl";
		
		char[] test = testStr.toCharArray();

		int[] cur = { 0, 0 };
		
		System.out.println("Starting at "+Arrays.toString(cur));

		for (int i = 0; i < test.length; i++) {
			// need to go to
			System.out.println("Need to go to " + test[i]);

			
			int[] target = map.get(test[i]);
			
			System.out.println("Target "+Arrays.toString(target));

			while (cur[0] != target[0] || cur[1] != target[1]) {

				while (cur[0] < target[0]) {
					cur[0]++;
					System.out.print(" DOWN ");
				}

				while (cur[0] > target[0]) {
					cur[0]--;
					System.out.print(" UP ");
				}

				while (cur[1] > target[1]) {
					cur[1]--;
					System.out.print(" LEFT ");
				}

				while (cur[1] < target[1]) {
					cur[1]++;
					System.out.print(" RIGHT ");
				}
			}
			System.out.println(" ! ");
			
		}

	}

	private static HashMap<Character, int[]> fillMap(char[][] array) {
		Map<Character, int[]> map = new HashMap<Character, int[]>();

		for (int i = 0; i < array.length; i++) {
			for (int j = 0; j < array[i].length; j++) {
				map.put(array[i][j], new int[] { i, j });
			}
		}
		System.out.println(map);
		return (HashMap<Character, int[]>) map;

	}

}

First , I will put all alphabets in a two dimensional array , say , alphabets[6][5] , thus , alphabets[0][0] becomes 'a' and so on. Now , I will create a hashmap for all 26 alphabets mapping there location on two dimension array . I can do that by creating a class say ,Coordinates , having two instance variables int row and int column . So , it can be written like this ,
Map<Character,Coordinate> keys = new HashMap<Character, Coordinate>;
Coordinate aobj = new Coordinate(0,0); // create obj for 'a', with row =0 , col =0
keys.put('a',aobj);

Or , we can simply put two digit integer and later retrieve the column and row from unit place and tens place respectively.

Now , lets say we have to write sequence for a word say 'word' ,
By using hashmap we will find location of 'w' is 4,2 and location of o is 2, 4
Travelling from 4,2 to 2,4 can be done in various ways , one way is to first traverse the difference in rows vertically , if difference of first-second is positive then upwards otherwise downwards , in this case ,4- 2=2 so two rows upwards , similarly for the columns can be done.

I think the qns is same as that of finding a word in a given 2-D array. Use recursion and whenever we recurr for up, left. right or down print "up - 'u', down 'd', left 'l', right 'r' and enter '!" accordingly as per the call. This will give the complete sequence of moves.

public List<String> findSteps(String input_) {
    char[] letters = input_.toCharArray();
    List<String> sequence = new ArrayList<String>();
    int currentRow = 0; // start at top left
    int currentCol = 0;
    for (char letter : letters) {
      // find the row/column in the matrix where this letter will be
      int diff = letter - 'a';
      int row = diff / 5;
      int col = diff % 5;

      // find where the new row/column is in relation to our existing position

      // row movement
      if (row < currentRow) {
        // need to move up by this may rows
        for (int i = row; i < currentRow; i++) {
          sequence.add("u");
        }
      } else if (row > currentRow) {
        // need to move down by this may rows
        for (int i = currentRow; i < row; i++) {
          sequence.add("d");
        }
      }

      // column movement
      if (col < currentCol) {
        // need to move left by this many columns
        for (int i = col; i < currentCol; i++) {
          sequence.add("l");
        }
      } else if (col > currentRow) {
        // need to move right by this many columns
        for (int i = currentCol; i < col; i++) {
          sequence.add("r");
        }
      }
      
      // update position
      currentRow = row;
      currentCol = col;
    }
    sequence.add("!"); // enter
    return sequence;
  }

#include <iostream>
#include <string>
#include <map>

using namespace std;

struct Pos {
	Pos ()
	: x(0), y(0)
	{}

	int x;
	int y;
};

Pos getDistance(Pos &a, Pos &b)
{
  Pos distance;
  distance.x = b.x - a.x;
  distance.y = b.y - a.y;

  return distance;
}

enum Moves {
  UP 	= 'u',
  DOWN	= 'd',
  LEFT	= 'l',
  RIGHT	= 'r',
  ENTER = '!'
};

map<char, Pos> positions;
Pos getNextPos(Pos p1, char letter)
{
	Pos absPos = positions[letter];
	return getDistance(p1, absPos);
}

string generateSequence(string word)
{
	Pos curPos;
	string sequence;
	for(unsigned int i = 0; i < word.size(); ++i)
	{
	    Pos next;
	    if (i == 0 && curPos.x == 0 && curPos.y == 0)
	      next = positions[word[i]];
	    else
	      next = getNextPos(curPos, word[i]);

	    curPos = positions[word[i]];
	    if (next.x > 0)
			while(next.x-- > 0)
			  sequence += DOWN;
	    else
			while(next.x++ < 0)
			  sequence += UP;

	    if (next.y != 0)
	    {
			if (next.y > 0)
				while(next.y-- >= 0)
					sequence += RIGHT;
			else
				while(next.y++ <= 0)
					sequence += LEFT;
	    }

	    sequence += '!';
	}

	return sequence;
}

int main()
{
  int count = 97;
  for (int i = 0; i < 6; i++)
  {
    for (int j = 0; j < 5; j++)
    {
      Pos p;
      p.x = i+1;
      p.y = j;
      positions[count++] = p;
    }
  }

  cout << generateSequence("zztop") << endl;

  return 0;
}

#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <map>
using namespace std;

// 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

//helper function that takes a map of coordinates and print out the path of instructions
void print_instructions( vector< pair<int, int> >& );
//print out path
void printout(int, int ,int ,int );



int main(int argc, char* argv[])
{
  if(argc!=2) {
    cout<<"Please provide one input argument!"<<endl;
    return 1;
  }  

  string word = string(argv[1]);
  vector< pair<int, int> > map;
  

  for(string::const_iterator p = word.begin();p!=word.end();p++){
    // position from 1-26
    int position = int(*p)-int('a')+1;
    //convert position to X-Y coordiates
    int X_cor = ceil(double(position)/5.0);
    int Y_cor = position % 5;
    if(Y_cor==0) Y_cor=5;
    
    map.push_back( make_pair(X_cor,Y_cor) );    

  }
  


  print_instructions(map);
  


  return 0;
  
}


//helper function that takes a map of coordinates and print out the path of instructions
void print_instructions( vector< pair<int, int> >& map )
{

  //assume the current cursor is at [1,1] == 'a'
  printout(map[0].first,1,map[0].second,1);


  for(vector< pair<int, int> >::const_iterator p = map.begin();p!=map.end();p++){
    vector< pair<int, int> >::const_iterator next = p+1;
    if(next==map.end()) continue;
    int x_next = next->first;
    int x =p->first;
    int y_next = next->second;
    int y =p->second;

    printout(x_next,x,y_next,y);
    

  }// loop over all coordinate elements in map
  



}

//print out path
void printout(int x_next, int x,int y_next,int y)
{

 //X direction    
    if(x_next >= x){
      for(int i=0;i< (x_next-x);i++){
        cout<<"D";
      }
    }
    
    else{
      for(int i=0;i< (x-x_next);i++){
        cout<<"U";
      }
    }
    

    //Y direction
    if(y_next >= y){
      for(int i=0;i< (y_next-y);i++){
        cout<<"R";
      }
    }
    
    else{
      for(int i=0;i< (y-y_next);i++){
        cout<<"L";
      }
    }    

    cout<<"!";
    

}

#python
# I do not use any array I simply calculate the location
#I I assume we stat in the top left ('a')
def cinst(c,p):
nc=ord(c)-97
np=ord(p)-97
y=(nc/5)-(np/5)
x=(nc%5)-(np%5)
print "c=%s p=%s nc=%d np=%d x=%d y=%d"%(c,p,nc,np,x,y)
if y>0:
for i in range(abs(y)):
print 'D'
else:
for i in range(abs(y)):
print 'U'
if x>0:
for i in range(abs(x)):
print 'R'
else:
for i in range(abs(x)):
print 'L'
print 'Enter'

def get_word_sec(word):
p='a'
for c in word:
cinst(c,p)
p=c

Position of a given letter 'w' in the matrix will be:

int i = (w-'a')/5;
int j = (w-'a')%5;

Get the difference of current 'i' and new 'i' calculated using above formula,

int diff_i = (new_i - old_i);
int diff_j = (new_j - old_j);

From here it's simple,

if(diff_i < 0)
    // append 'U' in the output (diff_i) times
else 
    // append 'D' in the output (diff_i) times

// same with j
if(diff_j < 0)
    // append 'L' in the output (diff_j) times
else 
    // append 'R' in the output (diff_j) times

#include <iostream>
#include <vector>
#include <string>
#include <math.h>
using namespace std;


string wordPressed(string input)
{
string output;
pair<int, int> key_pos(0,0);
for(int i=0;i<input.size();i++)
{
int x = (input[i]-'a')%5;
int y = (input[i]-'a')/5;
int move_x = x-key_pos.first;
if(move_x<0)
output.insert(output.end(), abs(move_x), 'i');
else
if(move_x>0)
output.insert(output.end(), abs(move_x), 'r');

int move_y = y-key_pos.second;
if(move_y<0)
output.insert(output.end(), abs(move_y), 'u');
else
if(move_y>0)
output.insert(output.end(), abs(move_y), 'd');
output.insert(output.end(), 1, '!');
key_pos = pair<int, int>(x,y);
}
return output;
}


int main()
{
string output = wordPressed("kkndkkndk");
cout<<output;
}

string sequence(const string &word, char &cur, int &index) {
	string ret = “”;
	if (word.length() == 0)
		return ret;
	if (index >= word.length())
		return ret;
	if (cur == word[index])
		ret += ‘!’;
	else {
		int curValue = (int)(cur-’a’+1);
		int destValue = (int)(word[index]-’a’+1);
		ret += string((curValue/5-destValue/5)>0 ? ‘u’ : ‘d’, (curValue/5-destValue/5));
		ret += string((curValue%5-destValue%5)>0 ? ‘l’ : ‘r’, (curValue%5-destValue%5));
		ret += ‘!’;
	}
	cur = word[index];
	index ++;
	if (index >= word.length())
		return ret;
	else return ret+sequence(word, cur, index);

}

Another similar version with the C code above

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

void print_path(int src, int dst){
while(src != dst){
if(src%5 < dst%5){
src ++;
putchar('r');
}
else if(src/5 < dst/5){
src +=5;
putchar('d');
}
else if(src%5 > dst%5){
src --;
putchar('l');
}
else if(src/5 > dst/5){
src -=5;
putchar('u');
}
}

putchar('!');
putchar('\n');

}

void main(int argc, char *argv[]){

char *x;
if(argc < 2){
x = "test";
}
else{
x = argv[1];
}
int src = 0;
int dst = 0;
while(*x != '\0'){
putchar(*x);
putchar(':');
dst = *x - 'a';
print_path(src, dst);
src = dst;
x ++;
}

}

Looks like a graph, with each letter being a node. And we need to find the path from one node to the other using breadth first search and the nodes being the subsequent letters. Meaning if have a word "hello", we need to find the following paths:
1. "h" to "e"
2. "e" to "l"
3. "l" to "o"

Each node may have up to 4 children.

public class RemoteLogic {

	private char[][] keyBoard = new char[6][5];

	public RemoteLogic(char[][] keyBoard) {
		this.keyBoard = keyBoard;
	}

//	Function writes a word in form of u,d,l,r,!
	public void writeWord(String wordToDisplay) {
		//last row position of the cursor
		int lastrowpos = 0;
		//last column position of the cursor
		int lastcolpos = 0;
		for (int i = 0; i <= wordToDisplay.length() - 1; i++) {
			// Convert each character in the word to ascii code
			char c = wordToDisplay.charAt(i);
			//Convert to zero based index for easier handling
			int cint = (int) c - 97;
			//Store current row and column position
			int currrowpos = cint / 5;
			int currcolpos = cint % 5;
			
			moveCursor(currrowpos, currcolpos, lastrowpos, lastcolpos);

			lastrowpos = currrowpos;
			lastcolpos = currcolpos;
			System.out.println("!");

		}

	}
	
	//Gets the current and the last position of the cursor and moves the cursor accordingly
	private void moveCursor(int currrowpos, int currcolpos, int lastrowpos,
			int lastcolpos) {
		//If on the same character , just press enter
		if (currcolpos == lastcolpos && currrowpos == lastrowpos) {
			System.out.println("!");
		}
		
		//first move within a column
		if (currcolpos < lastcolpos) {
			printMoves(lastcolpos - currcolpos, "l");
		}
		//then move between rows
		if (currrowpos < lastrowpos) {
			printMoves(lastrowpos - currrowpos, "u");
		}
		
		if (currcolpos > lastcolpos) {
			printMoves(currcolpos - lastcolpos, "r");
		}

		if (currrowpos > lastrowpos) {
			printMoves(currrowpos - lastrowpos, "d");
		}
	}
	
	//Print number of moves 
	private void printMoves(int i, String string) {
		for (int x = 1; x <= i; x++) {
			System.out.print(string);
		}
	}

}

string getSequence(string target){
    int curRow = 0, curCol = 0;
    string ans = "";
    for(int i=0; i<target.size(); i++){
	int chNum = target[i] - 'a';

	int row = chNum / 5;
	int col = chNum % 5;

	while(curRow != row){
	    if(curRow > row){
		curRow--;
		ans += 'u';
	    }else{
		curRow++;
		ans += 'd';
	    }
	}
	while(curCol != col){
	    if(curCol > col){
		curCol--;
		ans += 'l';
	    }else{
		curCol++;
		ans += 'r';
	    }		
	}
	ans += '!';
    }
    return ans;
}

public class Remote
    {
        private StringBuilder sb;

        public string GetPatternForWord(string word)
        {
            sb = new StringBuilder();
            char currentChar = 'a';		// begin here
            foreach (char c in word)
            {
                GetPatternForChar(lineNo(currentChar), currentChar, lineNo(c), c);

                // by this time the cursor should be at the destination
                currentChar = c;
            }

            return sb.ToString();
        }

        private void GetPatternForChar(int currLineNo, char currChar, int destLineNo, char destChar)
        {
            if (currChar == destChar)
            {
                return;
            }

            if (destLineNo == currLineNo)
            {
                if (currChar < destChar)
                {
                    sb.Append('r');
                    GetPatternForChar(currLineNo, next(currChar), destLineNo, destChar);
                }
                else
                {
                    sb.Append('l');
                    GetPatternForChar(currLineNo, prev(currChar), destLineNo, destChar);
                }
            }
            else if (destLineNo > currLineNo)
            {
                sb.Append('d');
                GetPatternForChar(currLineNo + 1, down(currChar), destLineNo, destChar);
            }
            else
            {
                sb.Append('u');
                GetPatternForChar(currLineNo - 1, up(currChar), destLineNo, destChar);
            }
        }

        char prev(char c)
        {
            return (char)(c - 1);
        }

        char next(char c)
        {
            return (char)(c + 1);
        }

        char up(char c)
        {
            return (char)(c - 5);
        }

        char down(char c)
        {
            if (c > 't')
            {
                return 'z';
            }

            return (char)(c + 5);
        }

        int lineNo(char c)
        {
            if (c <= 'e')
                return 1;

            if (c <= 'j')
                return 2;

            if (c <= 'o')
                return 3;

            if (c <= 't')
                return 4;

            if (c <= 'y')
                return 5;

            return 6;
        }
    }

#include<iomanip>
#include<iostream>
#include<map>
#include<string>

using std::cout;
using std::endl;
using std::map;
using std::string;

void getIndex(int n, int& a, int& b) {
	a = n/5;
	b = n - 5*a;
}

string getKeyStrokes(const string& s) {

	if(s.empty())
		return s;
	
	static map<char, int> keyboard;
	keyboard['a'] = 0; keyboard['b'] = 1; keyboard['c'] = 2;
	keyboard['d'] = 3; keyboard['e'] = 4; keyboard['f'] = 5;
	keyboard['g'] = 6; keyboard['h'] = 7; keyboard['i'] = 8;
	keyboard['j'] = 9; keyboard['k'] = 10; keyboard['l'] = 11;
	keyboard['m'] = 12; keyboard['n'] = 13; keyboard['o'] = 14;
	keyboard['p'] = 15; keyboard['q'] = 16; keyboard['r'] = 17;
	keyboard['s'] = 18; keyboard['t'] = 19; keyboard['u'] = 20;
	keyboard['v'] = 21; keyboard['w'] = 22; keyboard['x'] = 23;
	keyboard['y'] = 24; keyboard['z'] = 25;
	
	string ret;
	// go from (a1, b1) to (a2, b2)
	int a1, b1, a2, b2, d1, d2;
	// assume the remote starts at the letter "a"
	getIndex(keyboard['a'], a1, b1);
	for(string::size_type k = 0; k != s.size(); ++k) {
		getIndex(keyboard[s[k]], a2, b2);
		d1 = a2 - a1;
		d2 = b2 - b1;
		if(d2 < 0)
			ret += string(-d2, 'l');
		if(d1 > 0)
			ret += string(d1, 'd');
		if(d1 < 0)
			ret += string(-d1, 'u');
		if(d2 > 0)
			ret += string(d2, 'r');
		ret += '!';	
		a1 = a2; b1 = b2;
	}
	return ret;
}

I thin the question is not very difficult, and here is the code and it is self-explanatory:

#include <iostream>
#include <vector>
#include <string>

std::pair<int,int> pos( char c )
{
	int n = c - 'a';
	return std::make_pair( n / 5, n % 5 );
}

void move( const std::pair<int,int>& cp, const std::pair<int,int>& p )
{
	int y = p.first - cp.first;
	int x = p.second - cp.second;

	if( x > 0 ) while( x > 0 ) { std::cout << 'r'; --x; }
	else while( x < 0 ) { std::cout << 'l'; ++x; }

	if( y > 0 ) while( y > 0 ){ std::cout << 'd'; --y; }
	else while( y < 0 ) { std::cout << 'u'; ++y; }
	std::cout << '!' << std::endl;
}

void key_sequence( const  std::string& word )
{
	std::pair<int,int> cp = std::make_pair( 0, 0 ), p;
	for( int i = 0; i < word.size(); ++i )
	{
		p = pos(word[i]);
		move( cp, p );
		cp = p;
	}
}

int main( int argc, char* argv[] )
{
	int k = 0;
	for( int i = 0; i < 5; ++i )
	{
		for( int j = 0; j < 5; ++j ) 
		{
			std::cout << static_cast<char>( 'a' + k ) << " ";
			++k;
		}
		std::cout << std::endl;
	}
	std::cout << static_cast<char>( 'a' + k ) << std::endl;

	std::cout << std::endl;

	key_sequence("word");

	return 0;
}

Given the map is 6*5 , given any character , you can find out which row/col it resides in, in O(1)

void getrowcol(char ch, int rc[2])   // returns back row and col in r[2].

int prevr=0;prevc=0;  //start point

for(i=0;i<strlen(str);i++)
{
getrowcol(str[i],r);
if(r[0]<prevr)
print("r") , (r[0]-prevr) TIMES;
else
print("l") , (prevr-r[0]) TIMES;
if(r[1]<prevc)
print("d") , (r[1]-prevc) TIMES;
else
print("u") , (prevc-r[1]) TIMES;
print("!");
prevr=r[0];
prevc=r[1];
}

public class Solution(){
public String getAction(String str){
int len = str.length();
str = str.toLowerCase();
StringBuffer buf = new StringBuffer();
int x = 0 , y = 0;
for(int i = 0 ; i < len ; i++){
int t = str.charAt(i) - 'a';
int row = t/5;
int col = t%5;
while(row > y) {
buf.append('u');
y++;
}
while(row < y) {
buf.append('d');
y--;
}
while(col > x) {
buf.append('r');
x++;
}
while(col < x) {
buf.append('l');
x--;
}
buf.append('!');
}
return buf.toString();
}
}

def get_path(ipstr, width):
	prev = None
	for i in ipstr:
		if prev:
			prev_pos = get_postion(prev, width)
			current_pos = get_postion(i, width)
			rows_moved = current_pos[0] - prev_pos[0]
			cols_moved = current_pos[1] - prev_pos[1]
			output_str = ''
			if rows_moved:
				move_str = '%d move(s) up' % abs(rows_moved) if rows_moved < 0 else '%d move(s) down' % (rows_moved)
				output_str = output_str + move_str
			if cols_moved:
				move_str = ', %d move(s) left' % abs(cols_moved) if cols_moved < 0 else ', %d move(s) right' % (cols_moved)
				output_str = output_str + move_str
			print output_str
		prev = i

def get_postion(ch, width):
	lin_pos = 25 - (ord('z') - ord(ch))
	row = lin_pos // width
	col = lin_pos % width
	return (row, col)

Sample Usage:

>>> get_path('papajohns', 5)

3 moves up
3 moves down
3 moves up
1 moves down, 4 moves right
1 moves down
1 moves up, 2 moves left
1 moves down, 1 moves right
1 moves down

from string import ascii_lowercase

def remote(key):
    """ we know that alphabet is mapping in 5 columns, 6 rows 
    a = 0
    b = 1
    f = 5
    k = 10
    """
    out = []
    for c in key:
        index = ascii_lowercase.index(c)
        x = index % 5
        y = index / 5

        out.append((x, y))
    pre = (0, 0)
    result = ''
    for i in out:
        result += keypress(pre[0], pre[1], i[0], i[1])
        result += '!'
        pre = i
    return result

def keypress(x1, y1, x2, y2):
    x = x2 - x1
    y = y2 - y1
    out = ''
    out += abs(x) * 'l' if x < 0 else x * 'r'
    out += abs(y) * 'u' if y < 0 else y * 'd'
    return out

if __name__ == '__main__':
    print remote('pythonisawesome')

from string import ascii_lowercase

def remote(key):
    """ we know that alphabet is mapping in 5 columns, 6 rows 
    a = 0
    b = 1
    f = 5
    k = 10
    """
    out = []
    for c in key:
        index = ascii_lowercase.index(c)
        x = index % 5
        y = index / 5

        out.append((x, y))
    pre = (0, 0)
    result = ''
    for i in out:
        result += keypress(pre[0], pre[1], i[0], i[1])
        result += '!'
        pre = i
    return result

def keypress(x1, y1, x2, y2):
    x = x2 - x1
    y = y2 - y1
    out = ''
    out += abs(x) * 'l' if x < 0 else x * 'r'
    out += abs(y) * 'u' if y < 0 else y * 'd'
    return out

if __name__ == '__main__':
    print remote('pythonisawesome')

def char_to_coords(chr):
  num = -ord('a')+ord(chr)
  return (num/5, num%5)

lx,ly = (0,0)

def goto(chr):
  global lx,ly
  x,y = char_to_coords(chr)
  xDiff, yDiff = x-lx, y-ly
  lx,ly = (x,y)
  xDir = 'u' if xDiff < 0 else 'd'
  yDir = 'l' if yDiff < 0 else 'r'
  xCmd = xDir*abs(xDiff)
  yCmd = yDir*abs(yDiff)
  return yCmd+xCmd+'!' if xDiff < 0 else xCmd+yCmd+'!'


for x in 'hello':
  print goto(x)

order x and y directions so that it always aligns with/gets out of the 'z' column first.

here is my python solution

def type(word):

    alpha = [
                ['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']
            ]

    map = {}

    for i in range(len(alpha)):
        for j in range(len(alpha[i])):
            map[alpha[i][j]] = [i,j]

    alpha_index = [0, 0]
    word_index = 0

    type = ""

    while True:

        if word_index > len(word) -1 :
            break

        letter_index = map[word[word_index]]

        y_axis = alpha_index[0] - letter_index[0]
        x_axis = alpha_index[1] - letter_index[1]

        if y_axis == 0 and x_axis == 0:
            type += '! '
            word_index += 1
        elif y_axis != 0:
            if y_axis < 0:
                type += 'd '
                alpha_index = [alpha_index[0] + 1 , alpha_index[1]]
            else:
                type += 'u '
                alpha_index = [alpha_index[0] - 1 , alpha_index[1]]
        else:
            if x_axis < 0:
                type += 'r '
                alpha_index = [alpha_index[0] , alpha_index[1] + 1]
            else:
                type += 'l '
                alpha_index = [alpha_index[0] , alpha_index[1] - 1]

    return type

print (type("google"))

Output: d r ! d r r r ! ! u l l l ! d ! u u r r r !

{
string s;
char c[6][5]={{a,b,c,d,e}
	      {f,g,h,i,j}
	      {k,l,m,n,o}
	      {p,q,r,s,t}
	      {v,u,w,x,y}
	      {z}}
	s="a";//present at 0,0 position
 char c;
static int i=0,j=0;
	system.out.println("press the keys u d r l /n");
	scanner s=new scanner(syste.in);
	c=s.next();
        while(c!="/n")//press enter loop will terminate
	{
		switch(c)
		{
			case 'u':up();
				 break;
			case 'd':down();
				 break;
			case 'r':right();
				 break;
			case 'l':left();
				 break;
			default:
				break;
		}
	}
//select the upper element of the current position
public void up()
{
	if(i==0)
	{
		i=5;
`		s=s+a[i][j];
	}
	else
	{
		i=i-1;
		s=s+a[i][j];
	}
}
//select the below element of the current position
public void down()
{
	if(i==5)
	{
		i=0;
		s=s+a[i][j];
	}
	else
	{
		i=i+1;
		s=s+a[i][j];
	}
}
//select the right side element of the current position
public void rigth()

{
	if(j==4)
	{
		j=0;
		s=s+a[i][j];
	}
	else
	{
		j=j+1;
		s=s+a[i][j];
	}
}
//select the left side element of the current element
public void left()
{
	if(j==0)
	{
		j=4;
		s=s+a[i][j];
	}
	else
	{
		j=j-1;
		s=s+a[i][j];
	}
}
system.out.println("the selcted string is :%s",s);//it will print total u selected string
}
o/p:
strating position at 'a'
u u l u l d r  enter
string is:"azvytsxy"