Google Interview Question
Software Engineer / Developers Site Reliability EngineersCountry: United States
Interview Type: In-Person
Number of loops is irrelevant considering that it's run time is good. Some times the simplest answer is the most correct.
LOL.
Number of loops is a factor in what is simple and what is not and it does not affect the (asymptotic) runtime here.
The comment was more about simplicity rather than runtime...
int _tmain(int argc, _TCHAR* argv[])
{
char myArray[6][5];
char findMovie[] = {"UP"};
char findch;
int ipos[10][2];
int iChar = 65;
int iCurRow = 0;
bool bDone = false;
char AddMoves[10] = "";
char MoVedirection;
bool bver = false;
bool bhor = false;
for (int i =0; i<6;i++)
{
for ( int j =0;j <5;j++)
{
myArray[i][j] = (char)iChar;
iChar++;
}
}
for ( int l=0; l <strlen(findMovie); l++)
{
findch = findMovie[l];
for ( int i = 0; i<6 && !bDone; i++)
{
for (int j = 0; j<5;j++)
{
if ( myArray[i][j] == findch)
{
ipos[iCurRow][0] = i;
ipos[iCurRow][1] = j;
iCurRow++;
l++;
findch = findMovie[l];
if ( findch != NULL)
{
i = 0;
break;
}
else
bDone = true;
}
}
}
}
int curR = 0;
int curC = 0;
for ( int i = 0 ; i< iCurRow ; i++)
{
int destR = ipos[i][0] ;
int destC = ipos[i][1] ;
while (curC > destC)
{
strcat_s(AddMoves,"L");
curC--;
}
while (curR > destR) {
strcat_s(AddMoves,"U");
curR--;
}
while (curC < destC) {
strcat_s(AddMoves,"R");
curC++;
}
while (curR < destR) {
strcat_s(AddMoves,"D");
curR++;
}
strcat_s(AddMoves,"!");
}
return 0;
}
void printSteps(int a, int b, char key)
{
while(a < b) {
cout << key;
a++;
}
}
void printMoves(const char *movie, int w)
{
int x = 0, y = 0;
while(*movie) {
int tx = (tolower(*movie) - 'a') % w;
int ty = (tolower(*movie) - 'a') / w;
printSteps(tx, x, 'l');
printSteps(ty, y, 'u');
printSteps(x, tx, 'r');
printSteps(y, ty, 'd');
cout << '!'; // select
x = tx; y = ty;
movie++;
}
cout << endl;
}
def str2moves(cs):
"""Convet string to moves in matrix
+-----------x
| 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
y
Returns string of moves encoded as follows:
R - right
L - left
D - down
U - up
O - ok
Example:
>>> str2moves('con')
'RRODDRROLO'
>>> str2moves('conz')
'RRODDRROLODDLLLDO'
>>> str2moves('conza')
'RRODDRROLODDLLLDOUUUUUO'
"""
def i2xy(i):
y, x = divmod(i, 5)
return x, y
char2xy = {chr(ord('a') + i): i2xy(i)
for i in range(ord('z') - ord('a') + 1)}
def move(cx, cy, x, y):
"""Moves required to get from (cx, cy) to (x, y)
"""
if y - cy > 0:
moves.extend('D' * (y - cy))
elif y - cy < 0:
moves.extend('U' * (cy - y))
if x - cx > 0:
moves.extend('R' * (x - cx))
elif x - cx < 0:
moves.extend('L' * (cx - x))
return x, y
moves = []
cs = cs.lower()
cx, cy, z = 0, 0, False
for c in cs:
x, y = char2xy.get(c, (None, None))
if x is None:
raise ValueError('invalid char: {}'.format(c))
if z == True:
moves.append('U')
if y == 5: # 'z'
cx, cy = move(cx, cy, x, y - 1)
moves.append('D')
z = True
else:
cx, cy = move(cx, cy, x, y)
moves.append('O')
return ''.join(moves)
if __name__ == '__main__':
import doctest
doctest.testmod()
I think there's actually a bug in your implementation here. The string ``zyz`` does something weird:
DDDDDOURRRROULLLLDO
By my reckoning this works out to "zyu"
Also the string ``azyaz`` turns out strange:
ODDDDDOURRRROUUUUULLLLOUDDDDDO
That last "U" takes the "cursor" off the grid.
I think what it is is that you've got the "z" node's coordinates wrong or something.
Nice question
My solution (Scala)
import scala.annotation.tailrec
object Tests2 {
def main(args: Array[String]) {
solution("up")
}
def solution(word: String) = {
word.foldLeft('a')((current, target) => {
pathToChar(current, target)
target
})
}
@tailrec
def pathToChar(start: Char, target: Char): Unit = {
val move = nextMove(start, target)
val dir = move._1
print(dir)
val nextChar = move._2
if (dir != '!') pathToChar(nextChar, target)
}
private def nextMove(current: Char, target: Char): (Char, Char) = {
def row(c: Char) = (c - 'a') / 5
def col(c: Char) = (c - 'a') % 5
val cr: Int = row(current)
val cc: Int = col(current)
val tr: Int = row(target)
val tc: Int = col(target)
val rowDist: Int = tr - cr
val colDist: Int = tc - cc
if (rowDist > 0) {
('d', (current + 5).toChar)
} else if (rowDist < 0) {
('u', (current - 5).toChar)
} else if (colDist > 0) {
('r', (current + 1).toChar)
} else if (colDist < 0) {
('l', (current - 1).toChar)
} else {
('!', current)
}
}
}
Apparently all I had to do is change the priorities / precedence (left before down, up before right) to solve the last row edge case
import scala.annotation.tailrec
object Tests2 {
def main(args: Array[String]) {
solution("up")
println()
solution("yzy")
}
def solution(word: String) = {
word.foldLeft('a')((current, target) => {
pathToChar(current, target)
target
})
}
@tailrec
def pathToChar(start: Char, target: Char): Unit = {
val move = nextMove(start, target)
val dir = move._1
print(dir)
val nextChar = move._2
if (dir != '!') pathToChar(nextChar, target)
}
private def nextMove(current: Char, target: Char): (Char, Char) = {
def row(c: Char) = (c - 'a') / 5
def col(c: Char) = (c - 'a') % 5
val cr: Int = row(current)
val cc: Int = col(current)
val tr: Int = row(target)
val tc: Int = col(target)
val rowDist: Int = tr - cr
val colDist: Int = tc - cc
if (colDist < 0) {
('l', (current - 1).toChar)
} else if (rowDist < 0) {
('u', (current - 5).toChar)
} else if (colDist > 0) {
('r', (current + 1).toChar)
} else if (rowDist > 0) {
('d', (current + 5).toChar)
} else {
('!', current)
}
}
}
#include<stdio.h>
#include<stdlib.h>
int strlen(char *str)
{
int i=0;
while(str[i++] != '\0');
return i-1;
}
void print_path(int new_x, int new_y, int prev_x, int prev_y)
{
while(new_x != prev_x)
{
if(new_x < prev_x)
{
printf("u");
prev_x--;
}
else
{
printf("d");
prev_x++;
}
}
while(new_y != prev_y)
{
if(new_y < prev_y)
{
printf("l");
prev_y--;
}
else
{
printf("r");
prev_y++;
}
}
printf("!");
}
void lookup_movie(char *movie, int width)
{
int len = strlen(movie);
int new_x, new_y;
int prev_x, prev_y;
int loop=0;
prev_x = prev_y = 0;
while(loop < len)
{
new_x = ( movie[loop] - 'a' ) / width;
new_y = ( movie[loop] - 'a' ) % width;
print_path(new_x, new_y, prev_x, prev_y);
prev_x = new_x;
prev_y = new_y;
loop++;
}
}
#include<stdio.h>
#include<stdlib.h>
int strlen(char *str)
{
int i=0;
while(str[i++] != '\0');
return i-1;
}
void print_path(int new_x, int new_y, int prev_x, int prev_y)
{
while(new_x != prev_x)
{
if(new_x < prev_x)
{
printf("u");
prev_x--;
}
else
{
printf("d");
prev_x++;
}
}
while(new_y != prev_y)
{
if(new_y < prev_y)
{
printf("l");
prev_y--;
}
else
{
printf("r");
prev_y++;
}
}
printf("!");
}
void lookup_movie(char *movie, int width)
{
int len = strlen(movie);
int new_x, new_y;
int prev_x, prev_y;
int loop=0;
prev_x = prev_y = 0;
while(loop < len)
{
new_x = ( movie[loop] - 'a' ) / width;
new_y = ( movie[loop] - 'a' ) % width;
print_path(new_x, new_y, prev_x, prev_y);
prev_x = new_x;
prev_y = new_y;
loop++;
}
}
In Java:
public class MovieTest {
public static void main(String[] args) {
System.out.println(new MovieTest().lookupMovie("up"));
}
public String lookupMovie(String movieName){
String returnString = "";
int[] currentPosition = new int[]{0,0};
for(char c: movieName.toCharArray()){
int v = normalizeCharVal(c);
int y = v/5;
int x = v % 5;
int xdiff = x - currentPosition[0];
int ydiff = y - currentPosition[1];
char moveY = (ydiff > 0? 'D': 'U');
char moveX = (xdiff > 0? 'R': 'L');
for(int i=0; i< Math.abs(ydiff); i++){
returnString += moveY;
}
for(int i=0; i< Math.abs(xdiff); i++){
returnString += moveX;
}
returnString += '!';
currentPosition[0] = x;
currentPosition[1] = y;
}
return returnString;
}
//returns -1 if invalid
//returns 0 to 25 if valid alphabet
private int normalizeCharVal(char c){
int i = c;
if(i > 96){
i -= 97;
} else {
i -= 65;
}
if(i < 0 || i > 25){
return -1;
}
return i;
}
}
class DVRAI
{
public static void Do()
{
char[,] matrix =
{
{'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'}
};
SimpleDo(matrix, "hello");
}
public static void SimpleDo(char[,] matrix, string name)
{
int xStart = 0, yStart = 0, xNext = 0, yNext = 0;
StringBuilder sb = new StringBuilder();
foreach (char ch in name)
{
GetPosition(ch, ref xNext, ref yNext);
if (xNext > xStart)
{
for (int i = xStart; i < xNext; i++)
{
sb.Append("D");
}
}
if (xNext < xStart)
{
for (int i = xNext; i < xStart; i++)
{
sb.Append("U");
}
}
if (yNext > yStart)
{
for(int i = yStart; i < yNext; i++)
{
sb.Append("R");
}
}
if (yNext < yStart)
{
for (int i = yNext; i < yStart; i++)
{
sb.Append("L");
}
}
sb.Append("!");
xStart = xNext;
yStart = yNext;
}
Console.WriteLine(sb.ToString());
}
private static void GetPosition(char ch, ref int x, ref int y)
{
int i = ch - 'a';
x = i / 5;
y = i % 5;
}
}
If we observe grid carefully, they are in sorted order (rows an columns individually). So, I guess, interviewer is expecting binary search on row wise and/or column wise.
Forgive me, if somebody is already noticed this point and above programs are already have this logic (little lazy to read all programs :))
My solution would be to give each letter an index like a[0,0] b[0,1] and so on..then for the text entered find the difference between the character indexes and based on that define
up = if row difference is negative
down = if row difference is positive
left = if column difference is negative
right = if column difference is positive
public String lookUp(String str)
{
char currentChar = 'a';
int rowDiff, colDiff;
String result;
for(int i=0;i<str.length;i++)
{
if(str.charAt(i) >= 'a' && str.charAt(i) <= 'z')
rowDiff = (int) (str.charAt(i) - currentChar)/5;
colDiff = (int) (str.charAt(i) - currentChar)%5 - 1;
for(int j=0;j<rowDiff;j++)
{
if(rowDiff < 0)
result += "l";
else{
result += "r";
}
result += "!";
for(int j=0;j<colDiff;j++)
{
if(colDiff < 0)
result += "u";
else{
result += "d";
}
result += "!";
currentChar = str.charAt(i);
}
return result;
}
package ir.ListAlgorithms.com;
public class LetterGrid {
char movieName[];
int maxLetterPerRow = 5;
int currDIV=0;
int currMOD=0;
String allMoves = "";
LetterGrid(String movieName){
movieName = movieName.toUpperCase();
this.movieName = movieName.toCharArray();
for(int i=0;i<movieName.length();i++){
allMoves += getMove((int)this.movieName[i]-65);
}
System.out.println(allMoves);
}
public String getMove(int x){
int newDIV = x/maxLetterPerRow;
int newMOD = x%maxLetterPerRow;
int dirUD = newDIV - currDIV;
int dirLR = newMOD - currMOD;
char up_down = 'd';
char left_right = 'r';
int mult = 1;
String move ="";
if(dirUD <0) { mult = -1;up_down = 'u'; }
for(int i=0;i<(dirUD*mult);i++) move+=up_down;
if(dirLR <0) {mult = -1;left_right='l'; }
for(int i=0;i<(dirLR*mult);i++) move+=left_right;
currDIV = newDIV;
currMOD = newMOD;
return move+"!";
}
public static void main(String [] args){
new LetterGrid("MEGAMIND");
}
}
C#
private static string ComputePath(int width, string name)
{
var moves = new StringBuilder();
if (!String.IsNullOrEmpty(name))
{
string aName = 'a' + name; // start on a
for (int i = 1; i < aName.Length; i++)
{
int colMoves = (aName[i - 1] - 'a') % width - (aName[i] - 'a') % width;
int rowMoves = (aName[i - 1] - 'a') / width - (aName[i] - 'a') / width;
moves.Append(new string((colMoves < 0 ? 'r' : 'l'), Math.Abs(colMoves)));
moves.Append(new string((rowMoves < 0 ? 'd' : 'u'), Math.Abs(rowMoves)));
moves.Append("!");
}
}
return moves.ToString();
}
Java Code,
Logic first try to move vertically up or down then horizontally towards left or right.
public class GridPrint {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int current = 0;
Scanner sc = new Scanner(System.in);
String text = sc.nextLine();
int n = sc.nextInt();
// check it's only contains a-z.
for(int i = 0; i < text.length() ; i++)
{
int goal = text.charAt(i) - 'a';
int r = goal / n - current / n;
if(r > 0)
print(r, 'D');
else if( r < 0)
print(Math.abs(r), 'U');
current = current + r * n;
r = current - goal;
if( r < 0)
print(Math.abs(r), 'R');
else
print(r,'L');
current = goal;
}
sc.close();
}
public static void print(int n , char c)
{
for(int i = 0; i < n; i++ )
{
System.out.print(c);
}
if(c == 'L' || c == 'R')
{
System.out.print('!');
}
}
}
I don't think this will work. We are not supposed to move to spot where there is no alphabet. Try
mz
5
DDRR!DDDLL!
here is my code. Please let me know if there are any errors.
#include <iostream>
using namespace std;
int getRow(char a, int w){
return (a-97)/w;
}
int getCol(char a, int w){
return (a-97)%w;
}
void printPathFromStartEnd(char s, char e, int w){
if(s == 'a' && e == 'a') {
cout << "!";
return;
}
int start_row = getRow(s, w);
int start_col = getCol(s, w);
int end_row = getRow(e, w);
int end_col = getCol(e, w);
/*
8 total configuration is possible
*/
/*
e 0 0
0 s 0
0 0 0
*/
if(end_row<start_row && end_col<start_col){
int up = abs(start_row-end_row);
int left = abs(start_col - end_col);
while(up--) cout << "u";
while(left--) cout << "l";
cout << "!";
}
/*
0 0 0
0 s 0
e 0 0
*/
else if(end_row>start_row && end_col<start_col){
int left = abs(end_col-start_col);
int down = abs(end_row - start_row);
while(left--) cout << "l";
while(down--) cout << "d";
cout << "!";
}
/*
0 0 e
0 s 0
0 0 0
*/
else if(end_row<start_row && end_col>start_col){
int up = abs(end_row - start_row);
int right = abs(start_col-end_col);
while(up--) cout << "u";
while(right--) cout << "r";
cout << "!";
}
/*
0 0 0
0 s 0
0 0 e
*/
else if(end_row>start_row && end_col>start_col){
int down = abs(start_row-end_row);
int right = abs(start_col - end_col);
while(down--) cout << "d";
while(right--) cout << "r";
cout << "!";
}
/*
0 0 0
e s 0
0 0 0
*/
else if(end_row==start_row && end_col<start_col){
int left = abs(end_col - start_col);
while(left--) cout << "l";
cout << "!";
}
/*
0 0 0
0 s e
0 0 0
*/
else if(end_row==start_row && end_col>start_col){
int right = abs(end_col-start_col);
while(right--) cout << "r";
cout << "!";
}
/*
0 e 0
0 s 0
0 0 0
*/
else if(end_row<start_row && end_col== start_col){
int up = abs(end_row-start_row);
while(up--) cout << "u";
cout << "!";
}
/*
0 0 0
0 s 0
0 e 0
*/
else if(end_row>start_row && end_col == start_col)
{
int down = abs(end_row-start_row);
while(down--) cout << "d";
cout << "!";
}
}
void printPath(string s, int w){
//first we print from a to the first char in the string
printPathFromStartEnd('a', s[0], w);
//then we print the rest
for(int i=0;i<(s.length()-1);i++){
printPathFromStartEnd(s[i], s[i+1], w);
}
}
There was a slight problem. Here is the updated code.
#include <iostream>
using namespace std;
int getRow(char a, int w){
return (a-97)/w;
}
int getCol(char a, int w){
return (a-97)%w;
}
void printPathFromStartEnd(char s, char e, int w){
/*
9 total configuration is possible
*/
/*
if both start and end is the same char
0 0 0
0 s/e 0
0 0 0
*/
if(s == e) {
cout << "!";
return;
}
int start_row = getRow(s, w);
int start_col = getCol(s, w);
int end_row = getRow(e, w);
int end_col = getCol(e, w);
/*
e 0 0
0 s 0
0 0 0
*/
if(end_row<start_row && end_col<start_col){
int up = abs(start_row-end_row);
int left = abs(start_col - end_col);
while(up--) cout << "u";
while(left--) cout << "l";
cout << "!";
}
/*
0 0 0
0 s 0
e 0 0
*/
else if(end_row>start_row && end_col<start_col){
int left = abs(end_col-start_col);
int down = abs(end_row - start_row);
while(left--) cout << "l";
while(down--) cout << "d";
cout << "!";
}
/*
0 0 e
0 s 0
0 0 0
*/
else if(end_row<start_row && end_col>start_col){
int up = abs(end_row - start_row);
int right = abs(start_col-end_col);
while(up--) cout << "u";
while(right--) cout << "r";
cout << "!";
}
/*
0 0 0
0 s 0
0 0 e
*/
else if(end_row>start_row && end_col>start_col){
int down = abs(start_row-end_row);
int right = abs(start_col - end_col);
while(down--) cout << "d";
while(right--) cout << "r";
cout << "!";
}
/*
0 0 0
e s 0
0 0 0
*/
else if(end_row==start_row && end_col<start_col){
int left = abs(end_col - start_col);
while(left--) cout << "l";
cout << "!";
}
/*
0 0 0
0 s e
0 0 0
*/
else if(end_row==start_row && end_col>start_col){
int right = abs(end_col-start_col);
while(right--) cout << "r";
cout << "!";
}
/*
0 e 0
0 s 0
0 0 0
*/
else if(end_row<start_row && end_col== start_col){
int up = abs(end_row-start_row);
while(up--) cout << "u";
cout << "!";
}
/*
0 0 0
0 s 0
0 e 0
*/
else if(end_row>start_row && end_col == start_col)
{
int down = abs(end_row-start_row);
while(down--) cout << "d";
cout << "!";
}
}
void printPath(string s, int w){
//first we print from a to the first char in the string
printPathFromStartEnd('a', s[0], w);
//then we print the rest
for(int i=0;i<(s.length()-1);i++){
printPathFromStartEnd(s[i], s[i+1], w);
}
}
int main(){
cout << "aaaddd ";
printPath("aaaddd", 5);
cout << endl;
cin.get();
cin.get();
}
First, note that we need to hit each character in order.
If the "graph" is just a 2D matrix the shortest path to any character is just trivially moving to the row the character is on, and then the column. Think about it for a second.
So everyone in this thread is in fact finding the shortest path on the graph, it's just not with a "shortest path algorithm" as you'd expect.
{package nb;
import java.sql.Array;
import java.sql.ResultSet;
import java.sql.SQLException;
import java.util.ArrayList;
import java.util.Map;
public class bit
{
public static int i = 0;
public static StringBuilder sb = new StringBuilder();
public static int curR = 0;
public static int curC = 0;
public static int destR=0;
public static int destC=0;
public static void main(String[] args) {
char a[]={'a','b','c','d','e'};
getPath(5, a,0);
}
public static void getPath(int w, char[] str,int i) {
if(i<str.length){
destR = (str[i] - 'a') / w;
destC = (str[i] - 'a') % w;
if (curC > destC) {
sb.append('l');
curC--;
getPath(w, str,i);
}
else if(curR > destR) {
sb.append('u');
curR--;
getPath(w, str, i);
}
else if(curC < destC) {
sb.append('r');
curC++;
getPath(w, str, i);
}
else if(curR < destR) {
sb.append('d');
curR++;
getPath(w, str, i);
}
else{
sb.append('!');
getPath(w, str, i+1);
}
}
if(i==str.length)
System.out.println(sb.toString());
}
}
}
Solution using BFS. Running time - length of string * O(V+E)
#include <iostream>
#include <algorithm>
#include <stack>
#include <list>
#include <queue>
#define G 5
using namespace std;
list<int> *nei;
list <char> *out;
void addEdge(){
for(int v=1; v<=26; v++) {
if(v-1 >= 1 && (v-1)%G !=0) nei[v].push_back(v-1);
if(v+1 <= 26 && v%G != 0) nei[v].push_back(v+1);
if(v+G >=1 && v+G <= 26) nei[v].push_back(v+G);
if(v-G >=1 && v-G <= 26) nei[v].push_back(v-G);
}
}
void print(int l){
list<char>::iterator it;
for(int i=0; i<l; i++) {
for( it=out[i].begin(); it!=out[i].end(); it++)
cout<<*it;
}
}
void find(int s, int end, int pos){
bool visited[27] = {false};
int parent[27] = {-1};
queue<int> q;
list<int>::iterator it;
q.push(s);
visited[s] = true;
parent[s] = 0;
while(!q.empty()) {
int cur = q.front();
q.pop();
for(it = nei[cur].begin(); it!=nei[cur].end(); it++){
if(visited[*it] == false) {
visited[*it] = true;
parent[*it] = cur;
if(*it == end) {
out[pos].push_front('!');
while(parent[end] !=0) {
if(parent[end]+1 == end) out[pos].push_front('r');
if(parent[end]-1 == end) out[pos].push_front('l');
if(parent[end]+G == end) out[pos].push_front('d');
if(parent[end]-G == end) out[pos].push_front('u');
end = parent[end];
} return;
}
q.push(*it);
}
}
}
return;
}
int main() {
string s = "up";
nei = new list<int>[27];
out = new list<char>[s.length()];
addEdge();
find(1, s[0]-96, 0);
for(int i =1; i<s.length(); i++){
if(s[i-1]-96 != s[i]-96)
find(s[i-1]-96, s[i]-96, i);
else out[i].push_front('!');
}
print(s.length());
return 0;
}
Fully functioning Java-code with correct boundary analysis. Let me know your comments :)
import java.io.*;
import java.util.Scanner;
class grid_layout
{
public String movie_name;
public int grid_size;
public int rows = 0, cols = 0;
public int rows_count, cols_count;
public static void main(String args[])
{
grid_layout obj = new grid_layout();
System.out.println("Input the movie name");
obj.input_movie();
System.out.println("Input the grid size");
obj.input_grid_size();
obj.display_grid();
}
public void display_grid()
{
int count=0;
char i = 'a';
int j,flag = 0;
cols_count = grid_size;
rows_count = 26/grid_size +1;
char [][] alpha = new char[rows_count][cols_count];
System.out.println("The grid size is : "+ grid_size);
System.out.println("The grid is :\n");
for(rows = 0; rows < rows_count; rows ++)
{
for(cols = 0; cols < cols_count; cols++)
{
alpha[rows][cols] = i;
i++;
count ++;
if(count == 26)
break;
}
}
for(rows = 0; rows < rows_count; rows ++)
{
for(cols = 0; cols < cols_count; cols++)
{
System.out.print(" " + alpha[rows][cols] + " ");
}
System.out.print("\n");
}
// --------------Computation starts---------------------------
rows = 0;
cols = 0;
j = 0;
System.out.print("\n" + movie_name.charAt(j) + " " + rows_count + cols_count );
for(; rows < rows_count; )
{
for(; cols < cols_count; )
{
if( movie_name.charAt(j) == alpha[rows][cols])
{
System.out.print("!");
flag = 1;
break;
}
else if(movie_name.charAt(j) > alpha[rows][cols_count-1] && (rows+1 != rows_count) )
{
if( alpha[rows+1][cols] != '\0')
{
System.out.print("d");
rows ++;
break;
}
else
{
System.out.print("l");
cols --;
}
}
else if(movie_name.charAt(j) < alpha[rows][0])
{
System.out.print("u");
rows --;
break;
}
else if(movie_name.charAt(j) < alpha[rows][cols] )
{
System.out.print("l");
cols --;
break;
}
else if(movie_name.charAt(j) > alpha[rows][cols])
{
System.out.print("r");
cols ++;
}
}
if(flag == 1)
{
flag=0;
j+=1;
if (j == movie_name.length())
break;
}
}
//------------Computation Ends----------------
}
public void input_movie()
{
Scanner input = new Scanner(System.in);
movie_name = input.nextLine();
System.out.println("The movie name : " + movie_name);
}
public void input_grid_size()
{
Scanner input = new Scanner(System.in);
String answer = input.nextLine();
grid_size = Integer.parseInt(answer);
}
}
Simple modular version. Little bit longer then others but very clear.
public static String multLetters(int amount, char letter)
{
String s = "";
for (int i = 0; i < amount; i++)
s += letter;
return s;
}
public static String getMoves(int i1, int j1, int i2, int j2)
{
String s = "";
if (i1 > i2)
{
s += multLetters(i1 - i2, 'l');
}
else if (i1 < i2)
{
s += multLetters(i2 - i1, 'r');
}
if (j1 > j2)
{
s += multLetters(j1 - j2, 'u');
}
else if (j1 < j2)
{
s += multLetters(j2 - j1, 'd');
}
s += '!';
return s;
}
public static String movieGrid(String movie, int width)
{
int curri = 0;
int currj = 0;
String s = "";
String lowerCaseMovie = movie.toLowerCase();
for (char c : lowerCaseMovie.toCharArray())
{
if (c >= 'a' && c <= 'z')
{
int charVal = c - 'a';
int nexti = charVal % width;
int nextj = charVal / width;
s += getMoves(curri, currj, nexti, nextj);
curri = nexti;
currj = nextj;
}
else
{
return null;
}
}
return s;
}
public static void main(String [] args)
{
System.out.println(movieGrid("up", 5));
}
output:
dddd!u!
In Java:
private static String buildPath(String name, int width)
{
String path = "";
char c;
int x = 0, y = 0, xChar = 0, yChar = 0, xLastChar = 0, yLastChar = 0;
name = name.toLowerCase();
char lastChar = 'a';
for (int i = 0; i < name.length(); i++)
{
c = name.charAt(i);
xChar = (c - 'a') / width;
yChar = (c - 'a') % width;
xLastChar = (lastChar - 'a') / width;
yLastChar = (lastChar - 'a') % width;
x = xChar - xLastChar;
y = yChar - yLastChar;
if (x > 0)
{
for (; x > 0; x--)
{
path += "d";
}
}
else
{
for (; x < 0; x++)
{
path += "u";
}
}
if (y > 0)
{
for (; y > 0; y--)
{
path += "r";
}
}
else
{
for (; y < 0; y++)
{
path += "l";
}
}
path += "!";
lastChar = c;
}
return path;
}
In Java,,,
public class MovieName {
final static int gridWidth = 5;
public static void main(String[] args) {
String[] movie = { "up", "hello", "movie" };
for(String name : movie) {
System.out.println("Input : " + name);
String str = moveGrid(name);
System.out.println("Command : " + str);
str = nameGrid(str);
System.out.println("Output : " + str);
}
}
public static boolean isInRange(int col, int row) {
int ch = 'a' + (row * gridWidth) + col;
return (ch >= 'a' && ch <= 'z');
}
public static String moveGrid(String name) {
StringBuffer sbuf = new StringBuffer();
int curRow = 0;
int curCol = 0;
for(int i = 0; i < name.length(); i++) {
char ch = name.charAt(i);
if(ch < 'a' || ch > 'z')
continue;
ch -= 'a';
int destRow = ch / gridWidth;
int destCol = ch % gridWidth;
while(curRow != destRow || curCol != destCol) {
while(curCol < destCol && isInRange(curCol + 1, curRow)) {
sbuf.append('r');
curCol++;
}
while(curCol > destCol && isInRange(curCol - 1, curRow)) {
sbuf.append('l');
curCol--;
}
while(curRow > destRow && isInRange(curCol, curRow - 1)) {
sbuf.append('u');
curRow--;
}
while(curRow < destRow && isInRange(curCol, curRow + 1)) {
sbuf.append('d');
curRow++;
}
}
sbuf.append('!');
}
return sbuf.toString();
}
public static String nameGrid(String move) {
StringBuffer sbuf = new StringBuffer();
char charIndex = 0;
for(int i = 0; i < move.length(); i++) {
switch(move.charAt(i)) {
case 'l':
charIndex--;
break;
case 'r':
charIndex++;
break;
case 'u':
charIndex -= gridWidth;
break;
case 'd':
charIndex += gridWidth;
break;
case '!':
char ch = (char)('a' + charIndex);
if(ch >= 'a' && ch <= 'z') {
sbuf.append(ch);
}
break;
}
}
return sbuf.toString();
}
}
Input : up
Command : dddd!u!
Output : up
Input : hello
Command : rrd!rru!llldd!!rrr!
Output : hello
Input : movie
Command : rrdd!rr!llldd!rruuu!ru!
Output : movie
In Java with results according to the instruction.
public class CharacterSequence {
final static int gridWidth = 5;
public static void main(String[] args) {
String[] givenWords = { "CON", "OzOfZo", "xyZoo" };
for(String word : givenWords) {
System.out.println("\nGiven Word : " + word);
findGridSequence(word);
}
}
public static void findGridSequence(String word) {
int curX = 0;
int curY = 0;
for(int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
if(ch >= 'a' && ch <= 'z')
ch -= 'a';
else if(ch >= 'A' && ch <= 'Z')
ch -= 'A';
else
continue;
int destX = ch % gridWidth;
int destY = ch / gridWidth;
while(curY != destY || curX != destX) {
while(curX < destX && inRange(findChar(curX+1, curY))) {
curX++;
System.out.println("Right//now at " + findChar(curX, curY));
}
while(curX > destX && inRange(findChar(curX-1, curY))) {
curX--;
System.out.println("Left//now at " + findChar(curX, curY));
}
while(curY < destY && inRange(findChar(curX, curY+1))) {
curY++;
System.out.println("Down//now at " + findChar(curX, curY));
}
while(curY > destY && inRange(findChar(curX, curY-1))) {
curY--;
System.out.println("Up//now at " + findChar(curX, curY));
}
}
System.out.println("OK//to select ---> '" + word.charAt(i) + "'");
}
}
private static boolean inRange(char ch) {
return (ch >= 'A' && ch <= 'Z');
}
private static char findChar(int col, int row) {
return (char)('A' + (row * gridWidth) + col);
}
}
Given Word : CON
Right//now at B
Right//now at C
OK//to select ---> 'C'
Right//now at D
Right//now at E
Down//now at J
Down//now at O
OK//to select ---> 'O'
Left//now at N
OK//to select ---> 'N'
Given Word : OzOfZo
Right//now at B
Right//now at C
Right//now at D
Right//now at E
Down//now at J
Down//now at O
OK//to select ---> 'O'
Left//now at N
Left//now at M
Left//now at L
Left//now at K
Down//now at P
Down//now at U
Down//now at Z
OK//to select ---> 'z'
Up//now at U
Up//now at P
Up//now at K
Right//now at L
Right//now at M
Right//now at N
Right//now at O
OK//to select ---> 'O'
Left//now at N
Left//now at M
Left//now at L
Left//now at K
Up//now at F
OK//to select ---> 'f'
Down//now at K
Down//now at P
Down//now at U
Down//now at Z
OK//to select ---> 'Z'
Up//now at U
Up//now at P
Up//now at K
Right//now at L
Right//now at M
Right//now at N
Right//now at O
OK//to select ---> 'o'
Given Word : xyZoo
Right//now at B
Right//now at C
Right//now at D
Down//now at I
Down//now at N
Down//now at S
Down//now at X
OK//to select ---> 'x'
Right//now at Y
OK//to select ---> 'y'
Left//now at X
Left//now at W
Left//now at V
Left//now at U
Down//now at Z
OK//to select ---> 'Z'
Up//now at U
Up//now at P
Up//now at K
Right//now at L
Right//now at M
Right//now at N
Right//now at O
OK//to select ---> 'o'
OK//to select ---> 'o'
public static void getCode(int m, String str) {
int index = 0;
int i;
int n = str.length();
for(i = 0; i < n; i++) {
int dest = str.charAt(i) - 'a';
while(index != dest) {
if(index + m <= dest) {
index += m;
System.out.print("d");
} else if(index - m >= dest) {
index -= m;
System.out.print("u");
} else if(index > dest) {
index -= 1;
System.out.print("l");
} else {
index += 1;
System.out.print("r");
}
}
System.out.print("!");
}
}
Algorithm:
1.store abcde...in a 2-D array
2.Search for row
3.If row is greater than the previous row value,move down otherwise move up.In case of no changing in row donot move up or down.
4.Now look for column and move right or left correspondingly....
Remember initial position to be (0,0)
I have implemented in C using turbo C++ compiler
#include<conio.h>
#include<stdio.h>
#include<string.h>
void main()
{
char a[6][6]={"abcde","fghij","klmno","pqrst","uvwxy","z"};
char b[10],*p;
static int i,j,k,l,s,r,t;
clrscr();
while(i<6)
puts(a[i++]);
printf("Enter the word to be accesed:");
gets(b);
for(i=0;b[i]!='\0';i++)
{
for(j=0;j<6;j++)
{
p=strchr(a[j],b[i]);
if(p!=NULL)
{
if(j-l>0)
for(k=0;k<j-l;k++)
printf("Down\t");
if(l-j>0)
for(k=0;k<l-j;k++)
printf("Up\t");
for(s=0;s<5;s++)
{
//if(s==r)
//printf("Ok");
if(a[j][s]==b[i])
{
t=s;
if(s>r)
for(k=0;k<s-r;k++)
printf("Right\t");
if(r>s)
for(k=0;k<r-s;k++)
printf("Left\t");
printf("Ok\n");
}
}
r=t;
l=j;
}
}
}
getch();
}
import java.lang.Math;
class DVRtext{
public static void main(String[] args){
String movieName = "ipz";
int gridSize = 5, numCol = gridSize, numRow = (int) Math.ceil(26.0/numCol);
char thisChar;
int m,n,mL,mR,mU,mD,k;
int a_ascii = (int) 'a';
for(int i=0; i< movieName.length(); i++){
thisChar = movieName.charAt(i);
m = ((int) thisChar - a_ascii )/numCol;
n = ((int) thisChar - a_ascii )%numCol;
// System.out.println(thisChar + " m:" + m + " n:" + n + " numRow:" + numRow);
if(m >numRow/2){ mU = numRow-m;mD =-1;} else {mU=-1; mD = m;}
if(n >numCol/2){ mL = numCol-n;mR =-1;} else {mL=-1; mR = n;}
//System.out.println(mL + " " + mR + " " + mU + " " + mD);
for(k=0;k<mL;k++){System.out.printf("%c",'L');}
for(k=0;k<mR;k++){System.out.printf("%c",'R');}
for(k=0;k<mU;k++){System.out.printf("%c",'U');}
for(k=0;k<mD;k++){System.out.printf("%c",'D');}
System.out.printf("%c",'!');
}
}
}
Solution A:
Construct graph. Then do the BFS for each word.
Solution B:
But there is no need to BFS, if we see z is the special case of u.
if the word is z , search path for u and we can add DOWN + OK
if the previous word is z , add UP then use u as start point.
Let's work on B
import java.util.ArrayList;
import java.util.List;
public class CharSeq {
public static String map = "abcdefghijklmnopqrstuvwxy";
public static int cols = 5;
public static void addNTimes(List<String> list, String word, int times) {
for (int i = 0; i < times; i++) {
list.add(word);
}
}
public static List<String> charSeq(String word) {
int x = 0;
int y = 0;
List<String> answer = new ArrayList<String>();
word = word.toLowerCase();
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (c == 'z') {
c = 'u';
}
int index = map.indexOf(c);
int cx = index % cols;
int cy = index / cols;
if (cy < y) {
addNTimes(answer, "Up", y - cy);
} else if (y < cy) {
addNTimes(answer, "Down", cy - y);
}
if (cx < x) {
addNTimes(answer, "Left", x - cx);
} else if (x < cx) {
addNTimes(answer, "Right", cx - x);
}
if (word.charAt(i) == 'z') {
answer.add("Down");
answer.add("Ok");
if (i + 1 < word.length()) {
answer.add("Up");
}
} else {
answer.add("Ok");
}
x = cx;
y = cy;
}
return answer;
}
public static void main(String[] argv) {
System.out.println(charSeq("CON"));
}
}
I can seemany people propose a table/map while that's just an alphabet and is already part of the language, just calculate the offset.
To avoid "z" trap (z to right) and down to "z" empty string you need to rotate clockwise - you'll always have max 2 directions out of 4, and never get stuck if doing that clockwise.
void printPath(std::string &word) {
assert(word.size() != 0);
std::transform(word.begin(), word.end(), word.begin(), ::tolower);
char position = 'a';
for(const char &c : word) {
assert(c >= 'a' && c <= 'z');
char diffX = ((c - 'a') % 5) - ((position - 'a') % 5);
char diffY = ((c - 'a') / 5) - ((position - 'a') / 5);
for(int i = diffX; i < 0; ++i) std::cout << "LEFT" << std::endl;
for(int i = diffY; i < 0; ++i) std::cout << "UP" << std::endl;
for(int i = 0; i < diffX; ++i) std::cout << "RIGHT" << std::endl;
for(int i = 0; i < diffY; ++i) std::cout << "DOWN" << std::endl;
std::cout << "OK" << std::endl;
position = c;
}
}
public static void getCode(int m, String str) {
int index = 0;
int i;
int n = str.length();
for(i = 0; i < n; i++) {
int dest = str.charAt(i) - 'a';
while(index != dest) {
if(index + m <= dest) {
index += m;
System.out.print("d");
} else if(index - m >= dest) {
index -= m;
System.out.print("u");
} else if(index > dest) {
if(index % m < dest % m) {
index -= m;
System.out.print("u");
} else {
index -= 1;
System.out.print("l");
}
} else {
if(index % m > dest % m) {
index += m;
System.out.print("d");
} else {
index += 1;
System.out.print("r");
}
}
}
System.out.print("!");
}
}
Another Python implementation. I've focused on clarity & explicitness (in other words, this won't win code golf). Docstrings, PEP 8 & 257, etc.
#!/usr/bin/env python
import string
from collections import namedtuple
from itertools import izip_longest, tee
VALUES = string.lowercase
NUM_ROWS = 5
# Using a namedtuple for readability & ease of debugging.
Coords = namedtuple("Coordinates", "x y")
def rows(iterable, n, fillvalue=None):
"""Generator function that yields a single row of the matrix."""
args = [iter(iterable)] * n
results = izip_longest(fillvalue=fillvalue, *args)
for row in results:
yield [i for i in row if i]
def positions_dict():
"""Returns a dictionary mapping characters to coordinates."""
lookup = {}
for i, row in enumerate(rows(VALUES, NUM_ROWS)):
for j, elem in enumerate(row):
lookup[elem] = Coords(j, i)
return lookup
def node_cmp(start, next_move):
"""Returns a list of 'instructions' for moving around the graph.
Precedence is given to 'Up' and 'Left' moves since there is a
constraint on the x-axis. 'z' being on a row by itself will create
weirdness with strings like 'zxz' or 'xzx'.
"""
instrs = []
if start.y > next_move.y:
instrs += ["Up"] * (start.y - next_move.y)
if start.x > next_move.x:
instrs += ["Left"] * (start.x - next_move.x)
if start.y < next_move.y:
instrs += ["Down"] * (next_move.y - start.y)
if start.x < next_move.x:
instrs += ["Right"] * (next_move.x - start.x)
return instrs
def pairwise(iterable):
"""Returns a list of coordinate pairs. This enables windowing over
the set of coordinates to consider them two at a time.
Example:
>> pairwise('dogs')
[('d', 'o'), ('o', 'g'), ('g', 's')]
"""
a, b = tee(iterable)
next(b, None)
return zip(a, b)
def main(target):
target = target.lower()
positions = positions_dict()
coords = [positions[i] for i in target]
instrs = []
# If our first letter isn't 'a', we need to inject the coordinates for that
# letter at the head of the list. Otherwise, we need to make sure our first
# instruction is 'OK'.
if target[0] != 'a':
coords.insert(0, positions['a'])
else:
instrs += ['OK']
for pair in pairwise(coords):
instrs += node_cmp(*pair)
instrs.append('OK')
return instrs
if __name__ == "__main__":
import sys
from pprint import pprint
try:
word = sys.argv[1]
except IndexError:
raise IndexError("You need to provide a word to build.")
[pprint(i) for i in main(word)]
using System.Collections.Generic;
using System.Diagnostics;
namespace SimplePlays
{
public class PathFinder
{
private readonly char[][] m_Board = new char[][]
{
new char[] {'a', 'b', 'c', 'd', 'e'},
new char[] {'f', 'g', 'h', 'i', 'j'},
new char[] {'k', 'l', 'm', 'n', 'o'},
new char[] {'p', 'q', 'r', 's', 't'},
new char[] {'u', 'v', 'w', 'x', 'y'},
new char[] {'z', ' '}
};
Dictionary<char, Position> m_NavigationBoard = new Dictionary<char, Position>();
public PathFinder()
{
initNavigationBoard();
}
private void initNavigationBoard()
{
for (int i = 0; i < m_Board.Length; i++)
{
for (int j = 0; j < m_Board[i].Length; j++)
{
m_NavigationBoard.Add(m_Board[i][j], new Position(i, j, m_Board[i].Length - 1));
}
}
}
public void PrintPath(string input)
{
if (string.IsNullOrEmpty(input))
{
return;
}
Position lastKnownPosition = new Position(0,0, 0);
foreach (char chr in input)
{
Position newPosition = m_NavigationBoard[chr];
PrintDirections(lastKnownPosition, newPosition);
lastKnownPosition = newPosition;
}
}
private void PrintDirections(Position from, Position to)
{
// for example, from Z to N
if (from.ColumnIndex < to.ColumnIndex && (to.ColumnIndex > from.MaxColumnIndex))
{
PrintRowsDirections(from, to);
PrintColumnDirections(from, to);
}
else
{
PrintColumnDirections(from, to);
PrintRowsDirections(from, to);
}
PrintStep(Directions.Ok);
}
private void PrintRowsDirections(Position from, Position to)
{
int tempIndex = from.RowIndex;
int tempDirection = from.GetRowDirection(to);
while (tempIndex != to.RowIndex)
{
// Do step
tempIndex += tempDirection;
//Print
PrintStep((tempDirection > 0) ? Directions.Down : Directions.Up);
}
}
private void PrintColumnDirections(Position from, Position to)
{
int tempColumnIndex = from.ColumnIndex;
int tempColumnDirection = from.GetColumnDirection(to);
while (tempColumnIndex != to.ColumnIndex)
{
// Do step
tempColumnIndex += tempColumnDirection;
//Print
PrintStep((tempColumnDirection > 0) ? Directions.Right : Directions.Left);
}
}
private void PrintStep(Directions step)
{
Debug.WriteLine(step);
}
enum Directions
{
Ok,
Up,
Down,
Left,
Right
}
[DebuggerDisplay("RI: {RowIndex}, CI: {ColumnIndex}")]
class Position
{
public Position(int rowIndex, int columnIndex, int maxColumnIndex)
{
RowIndex = rowIndex;
ColumnIndex = columnIndex;
MaxColumnIndex = maxColumnIndex;
}
public int RowIndex { get; set; }
public int ColumnIndex { get; set; }
public int MaxColumnIndex { get; set; }
public int GetRowDirection(Position newPosition)
{
if (newPosition.RowIndex >= this.RowIndex)
{
return 1;
}
return -1;
}
public int GetColumnDirection(Position newPosition)
{
if (newPosition.ColumnIndex >= this.ColumnIndex)
{
return 1;
}
return -1;
}
}
}
}
No algorithms are involved. Only some coding.
def pos(a):
"""Compute coordinate for a
---- x
|
|
y
"""
code = ord(a) - ord("a")
return (code // 5, code % 5)
def line(a, b, less, bigger):
diff = abs(b - a)
if diff == 0: return
if a < b:
arrow = less
elif a > b:
arrow = bigger
print(arrow * diff)
# Move in x axis
def move_x(a, b):
line(a, b, "Right ", "Left ")
# Move in y axis
def move_y(a, b):
line(a, b, "Down ", "Up ")
# Move from a to b
def move(a, b):
(a_y, a_x) = pos(a)
(b_y, b_x) = pos(b)
# if a is above b, move in x axis and then in y axis. Otherwise, move in y
# axis and then in x axis. It is for handling invalid movements when "z" is
# involved.
if a_y <= b_y:
move_x(a_x, b_x)
move_y(a_y, b_y)
else:
move_y(a_y, b_y)
move_x(a_x, b_x)
print("Select {}".format(b))
def traverse(start, word):
print("From {} to traverse {}".format(start, word))
seq = start + word
n = len(seq)
for i in xrange(n - 1):
move(seq[i], seq[i + 1])
traverse("b", "con")
traverse("u", "zq")
traverse("c", "zza")
import java.util.*;
import java.io.*;
import java.lang.*;
public class SetTopBox {
// chars per line
public static final int N = 5;
public static void printDirection(int dx, int dy) {
String targetXString = "Right";
if (dx < 0) targetXString = "Left";
String targetYString = "Down";
if (dy < 0) targetYString = "Up";
for (int i=0; i < Math.abs(dx); ++i) {
System.out.println(targetXString);
}
for (int i=0; i < Math.abs(dy); ++i) {
System.out.println(targetYString);
}
System.out.println("OK");
}
public static void printInstructions(String word, char initialCharacter) {
int initialPosition = initialCharacter - 'a';
int currentX = initialPosition % N;
int currentY = initialPosition / N;
for (char target : word.toCharArray()) {
if ((target < 'a') || (target > 'z')) {
continue;
}
int targetPos = target - 'a' ;
int tx = targetPos % N;
int ty = targetPos / N;
int dx = tx - currentX;
int dy = ty - currentY;
printDirection(dx, dy);
currentX = tx;
currentY = ty;
}
}
public static void main(String[] args) {
try {
Scanner scanner = new Scanner(new FileInputStream("input.txt"));
String word = scanner.nextLine().toLowerCase();
char initialCharacter = scanner.nextLine().charAt(0);
printInstructions(word, initialCharacter);
}
catch(IOException e) {
}
}
}
void findRoute(char* word, char loc)
{
if (strlen(word) == 0 )
{
return;
}
char w = word[0];
int pr = row(loc);
int pc = col(loc);
int r = row(w);
int c = col(w);
if( w == loc )
{
printf("OK.\n");
return findRoute(word+1, loc);
}
else if( w == 'z' && pc != 0 )
{
printf("Left.\n");
return findRoute(word, loc - 1);
}
else if( r > pr )
{
printf("Down.\n");
return findRoute(word, loc + 5);
}
else if( r < pr )
{
printf("Up.\n");
return findRoute(word, loc - 5);
}
else if( c > pc )
{
printf("Right.\n");
return findRoute(word, loc + 1);
}
else if( c < pc )
{
printf("Left.\n");
return findRoute(word, loc - 1);
}
};
int main()
{
findRoute("yzy", 'a');
return 0;
}
public static void map(String str){
str = "a" + str;
char[] ar = str.toCharArray();
for(int i = 0; i<ar.length-1; i++){
int difference = ar[i+1] - ar[i];
System.out.println(difference);
do{
if(difference <0 && difference > -5){
System.out.println("left");
difference +=1;}
else if(difference >0 && difference <5){
System.out.println("right");
difference -=1;}
else if(difference >= 5){
System.out.println("down");
difference -=5;
}
else if(difference <=5){
System.out.println("up");
difference +=5;}
if(difference == 0)
System.out.println("Ok!");
}
while(difference!=0);}
}
public static void printSeq(char[] word) {
int xPos = 0;
int yPos = 0;
char c;
for (int i = 0; i < word.length; i++) {
c = word[i];
for (int j = xPos; j < (c - 'a') / 5; j++) {
System.out.println("Down");
}
for (int j = (c - 'a') / 5; j < xPos; j++) {
System.out.println("Up");
}
for (int j = yPos; j < (c - 'a') % 5; j++) {
System.out.println("Right");
}
for (int j = (c - 'a') % 5; j < yPos; j++) {
System.out.println("Left");
}
System.out.println("Ok");
xPos = (c - 'a') / 5;
yPos = (c - 'a') % 5;
}
}
#include <stdio.h>
inline char lowercase(char c)
{
if (c >= 65 && c <=90) return c + 32;
return c;
}
inline void tell_coordinate(char c, int *row, int *col)
{
int d = c - 'a';
*row = d / 5;
*col = d % 5;
}
int control(const char *input)
{
int curr_row = 0, curr_col = 0, row, col, n = 0;
const char *p = input;
char c;
for (; *p != '\0'; p++) {
c = lowercase(*p);
tell_coordinate(c, &row, &col);
printf("%c: (%d,%d)\n", *p, row, col);
if (curr_row < row) {
do {
printf("DOWN\n");
curr_row++;
n++;
} while (curr_row < row);
} else if (curr_row > row) {
do {
printf("UP\n");
curr_row--;
n++;
} while (curr_row > row);
}
if (curr_col < col) {
do {
printf("RIGHT\n");
curr_col++;
n++;
} while (curr_col < col);
} else if (curr_col > col) {
do {
printf("LEFT\n");
curr_col--;
n++;
} while (curr_col > col);
}
printf("SELECT %c\n", *p);
}
return n;
}
int main()
{
int n = control("CON");
printf("%d steps\n", n);
return 0;
}
class NavigateSetTopBox
{
public static void navigate(String s)
{
int x = 0; y = 0;
for(int i = 0; i < s.length(); i++)
{
Char c = s[i];
// assume a map from char -> int
// a - 0, z - 25
int index = alphaMap.get(c);
if(index <0 && index > 25)
throw new IllegalArgumentException("Invalid char at input " + index);
int newX = c/5;
int newY = c%5;
navigate(x, y, newX, newY);
oldX = newX;
oldY = newY;
}
}
public static void navigate(int sx, int sy, int dx, int dy)
{
boolean yDir = dy > sy;
navigateDirection(sy, dy, yDir ? 1 : -1, yDir : "Down" : "UP");
boolean xDir = dx > yx;
navigateDirection(sx, yx, xDir ? 1 : -1, xDir : "Right" : "Left");
}
private static void navigateDirection(int s, int d, int inc, String info)
{
while(s != d)
{
System.out.println(info);
s = s + inc;
}
}
}
#!/usr/bin/env python
import string
# First, create a hash map where a letter is the key, index is the value.
# for instance, letter o is at 14.
# using division and mod, find row and column.
# row = 14 / 5 = 2
# column = 14 % 5 = 4
# then find the difference in rows and columns
# print that many up/down or left/right
look_up_letters = {}
for i, c in enumerate(string.ascii_lowercase):
look_up_letters[c] = i
look_up_letters[' '] = 26
def key_pad(s):
initial_pos = [0, 0]
for c in s:
pos = look_up_letters[c]
row = pos / 5
column = pos % 5
# how many ups or downs?
diff_in_row = row - initial_pos[0]
# how many lefts or rights?
diff_in_column = column - initial_pos[1]
if diff_in_row > 0:
move_row = "down"
else:
move_row = "up"
for n in range(0, abs(diff_in_row)):
print move_row
if diff_in_column > 0:
move_column = "right"
else:
move_column = "left"
for n in range(0, abs(diff_in_column)):
print move_column
print "ok"
initial_pos = [row, column]
key_pad('con na')
#!/usr/bin/env python
import string
# First, create a hash map where a letter is the key, index is the value.
# for instance, letter o is at 14.
# using division and mod, find row and column.
# row = 14 / 5 = 2
# column = 14 % 5 = 4
# then find the difference in rows and columns
# print that many up/down or left/right
look_up_letters = {}
for i, c in enumerate(string.ascii_lowercase):
look_up_letters[c] = i
look_up_letters[' '] = 26
def key_pad(s):
initial_pos = [0, 0]
for c in s:
pos = look_up_letters[c]
row = pos / 5
column = pos % 5
# how many ups or downs?
diff_in_row = row - initial_pos[0]
# how many lefts or rights?
diff_in_column = column - initial_pos[1]
if diff_in_row > 0:
move_row = "down"
else:
move_row = "up"
for n in range(0, abs(diff_in_row)):
print move_row
if diff_in_column > 0:
move_column = "right"
else:
move_column = "left"
for n in range(0, abs(diff_in_column)):
print move_column
print "ok"
initial_pos = [row, column]
key_pad('con na')
#include <vector>
#include <string>
#include <iostream>
int main()
{
std::vector<char> row1 { 'a', 'b', 'c', 'd', 'e' };
std::vector<char> row2 { 'f', 'g', 'h', 'i', 'j' };
std::vector<char> row3 { 'k', 'l', 'm', 'n', 'o' };
std::vector<char> row4 { 'p', 'q', 'r', 's', 't' };
std::vector<char> row5 { 'u', 'v', 'w', 'x', 'y' };
std::vector<char> row6 { 'z' };
std::vector< std::vector<char> > screen;
screen.push_back(row1);
screen.push_back(row2);
screen.push_back(row3);
screen.push_back(row4);
screen.push_back(row5);
screen.push_back(row6);
const int ROWS = 6;
const int COLUMNS = 5;
std::string searchString = "con";
int searchIndex = 0;
int column = 0;
int row = 0;
while( searchIndex < searchString.size() )
{
char currentChar = screen[row][column];
char searchChar = searchString[searchIndex];
if ( currentChar == searchChar )
{
std::cout << "OK\n";
++searchIndex;
}
else if ( searchChar > (currentChar + (COLUMNS - column) - 1) )
{
std::cout << "DOWN\n";
++row;
}
else if ( searchChar < (currentChar - column) )
{
std::cout << "UP\n";
--row;
}
else if ( searchChar < currentChar )
{
std::cout << "LEFT\n";
--column;
}
else
{
std::cout << "RIGHT\n";
++column;
}
if( row > ROWS ||
column > COLUMNS ||
row == ROWS && column > 0 )
{
std::cout << "ERROR with row:" << row << " column:" << column << " currentChar:" << currentChar;
break;
}
}
}
Basically turning the char array into an int array to make easier decisions
which direction to move next. The decision is based on the following conditions:
RIGHT If current_char < target_char and target_char is within upper_bound
example, current_char=c, target_char=d
DOWN If current_char < target_char and upper_bound < target_char
example, current_char=c, target_char=x
UP If current_char > target_char and lower_bound > target_char
example, current_char=w, target_char=b
LEFT If current_char > target_char and target_char is within the lower_bound
example, current_char=e, target_char=b
current_char is the char you are currently traversing on in the array
target_char is the destination char you want to reach
lower_bound is determined based on the currently traversed row, these would be (a, f, k, p, u, z)
upper_bound is determined the same way, except these are on the opposite border (e, j, o, t, y).
def row_bounds(row, dimension, maxx=26):
upper = (row+1)*dimension
lower = upper-dimension+1
if upper > maxx:
upper = maxx
return (lower, upper)
def direction(array, row, col, target, dimension, max=26):
next_move = (-1, -1)
current = array[row][col]
# Get the row bounds
lower, upper = row_bounds(row, dimension)
# Figure out where your current position is
# w.r.t the target.
if current < target:
# Either move right or down
if upper < target:
# Special case, you can't move dow from v, w, x or y
# to reach "z". Instead move left to reach "z".
if row == (len(array) - 2) and (col >= 1):
next_move = (row, col-1, "LEFT")
else:
# Not on the same row, move down
next_move = (row+1, col, "DOWN")
else:
# On the same row, move right
next_move = (row, col+1, "RIGHT")
else:
# Either move left or upward
if lower > target:
# Not in the same row, so move up
next_move = (row-1, col, "UP")
else:
# On the same row, move left
next_move = (row, col-1, "LEFT")
return next_move
def trail(array, charseq, start_position):
# Convert character box array to num box array to do easy calculations
count = 1
array_num = []
char_dict = {}
for row in range(len(array)):
array_num.append([])
for col in range(len(array[row])):
val = array[row][col]
if val == "":
continue
char_dict[val] = count
array_num[row].append(count)
count += 1
row, col = start_position
current = array[row][col]
result = []
# Find the character sequence
for t_char in charseq:
# Keep traversing until target is found
t_num = char_dict[t_char]
while current != t_char:
next_move = direction(array_num, row, col, t_num, len(array[0]))
row, col, move = next_move
result.append((current, move))
current = array[row][col]
if current == t_char:
result.append((current, "OK"))
return result
def test():
array = [
["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", "", "", "", ""]
]
result = trail(array, "con", (0,1))
assert result == [
('b', 'RIGHT'), ('c', 'OK'), ('c', 'DOWN'), ('h', 'DOWN'),
('m', 'RIGHT'), ('n', 'RIGHT'), ('o', 'OK'), ('o', 'LEFT'), ('n', 'OK')
]
result = trail(array, "coz", (0,1))
assert result == [
('b', 'RIGHT'), ('c', 'OK'),
('c', 'DOWN'), ('h', 'DOWN'), ('m', 'RIGHT'), ('n', 'RIGHT'), ('o', 'OK'),
('o', 'DOWN'), ('t', 'DOWN'), ('y', 'LEFT'), ('x', 'LEFT'), ('w', 'LEFT'), ('v', 'LEFT'), ('u', 'DOWN'), ('z', 'OK')
], result
result = trail(array, "cozy", (0,1))
assert result == [
('b', 'RIGHT'), ('c', 'OK'),
('c', 'DOWN'), ('h', 'DOWN'), ('m', 'RIGHT'), ('n', 'RIGHT'), ('o', 'OK'),
('o', 'DOWN'), ('t', 'DOWN'), ('y', 'LEFT'), ('x', 'LEFT'), ('w', 'LEFT'), ('v', 'LEFT'), ('u', 'DOWN'), ('z', 'OK'),
('z', 'UP'), ('u', 'RIGHT'), ('v', 'RIGHT'), ('w', 'RIGHT'), ('x', 'RIGHT'), ('y', 'OK')
], result
test()
void NavigateGrid(char *s)
{
if(!*s)
return;
int i,j,val;
int prev_row=0, prev_col=0;
int cur_row,cur_col;
for(i=0;i<strlen(s);i++)
{
val=s[i]-'a';
cur_row=val/(ROW-1);
cur_col=val%(ROW-1);
if(cur_col>prev_col)
{
if(a[prev_row][prev_col+1]=='-')
printf("Moving Up to %c\n",a[--prev_row][prev_col]);
for(j=prev_col+1;j<=cur_col;j++)
printf("Moving Right to %c\n",a[prev_row][++prev_col]);
}
else
{
for(j=prev_col-1;j>=cur_col;j--)
printf("Moving Left to %c\n",a[prev_row][--prev_col]);
}
if(cur_row>prev_row)
{
for(j=prev_row+1;j<=cur_row;j++)
printf("Moving Down to %c\n",a[++prev_row][prev_col]);
}
else
{
for(j=prev_row-1;j>=cur_row;j--)
printf("Moving Up to %c\n",a[--prev_row][prev_col]);
}
printf("\nOK to pick %c\n\n",a[prev_row][prev_col]);
}
}
I forgot to include a check to ensure that only characters that actually belong to the given data set are checked. It can be easily fixed by adding the following to the code:
if(s[i]-'a'>=0 && s[i]-'a'<=25) // i.e., if a given character is within the a-z range.
{
val=s[i]-'a';
and the rest of the above code.
}
It can be solved by using DIRECTIONS :
use like,
""up==North""
""down==south""
""right==west""
""left==east""
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 , #, #, #, #
Base cases:
1)if u ever encounter a word in any directions like,
for(search=='a' to search=='z';search++)//for all letters
{
return 'a' to return 'z';
}
if(search=='#')//where #=end in any directions
{
return NULL;
}
Concept:
If a word is "CON"(given),then u hav to traverse in matrix like following ,
##starting frm first letter 'a'##
1)if ur word contains 'a' means just return it,Otherwise go next,west++;until u fnd the word..
for(i='a';i<'z';i++) //first u hav 2 set # a to z # values 1 to 26 in any set..
if(word[i]=='a'&&matrix[i][j]=='a')
{
return 'a';
}
else
{
west++;//until they found
i++;
}
i)if 'a' found,look for 'o' in matrix[i][j];
ii)else west++;
i++;//until they found..
2)from the given matrix[i][j],find 'o';this is in far dist from 'o'
i)go down until u reach the char 'o' present row//i thnk it s in 3RD row..
ii)once u reached 3rd row,at 'm' char position,u hav to traverse 2 more to reach 'o';
for(i='o';)//i at curr pos 'm'
{
i=0;
i=i+2;//traverse 2 more
west++;//(right++;)to reach 'o';
}
so on...find 'n' urself..
i hav posted ths concept..if u encnter any err, sorry dude..i tried..
Letter can be thought of as a=1; b=2;.......z=26.
Movie name can be iterated upon character by character.
After calculating/finding the value of a letter, move can be made.
From the grid width we can find out the row and column of the letter.
For an example, movie id "vh". v is 22 and h is 8.
Suppose grid width is 13.
22/13 = 1(r1) (second column) and 22%13 = 9(c1)(9th column)
so, v is drrrrrrrr!.
Now h
8/13 = 0 (r2) and 8%13 = 8(c2)
r2-r1 = 0-1 = -1 means u and c2-c1 = 8-9=-1 means l
so ul!
and vh is drrrrrrrr!ul!
Here is a full Java implementation. It's a bit long because I added utility methods for clarity.
public class DVR {
/*
*
* I need a function that takes the name of the movie to look up and
* the width of the letter grid, and computes the key presses that
* will enter that string on the DVR grid. The output should be a
* string, with "u", "d", "l", "r", and "!" corresponding to up,
* down, left, right, and select.
*
* For example, with a grid of width 5,
* 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
* the movie "up" would be "dddd!u!".
*
*
*/
static char[] alphabet = get_alphabet();
static String UP = "u";
static String DOWN = "d";
static String LEFT = "l";
static String RIGHT = "r";
static String SELECT = "!";
static char[] get_alphabet() {
/* Generates the english alphabet in a char array. */
char cur = 'a';
char[] alphabet = new char[26];
for (int i=0; i<26; i++) {
alphabet[i] = cur;
cur++;
}
return alphabet;
}
static int[] getcoords(char letter, int width) {
/* Given a character, return it's position
* in the alphabet matrix */
int pos = -1;
for (int i=0; i<alphabet.length; i++) {
if (letter==alphabet[i]) {
pos = i;
break;
}
}
int rownum = (int) Math.floor(pos / width);
int colnum = pos % width;
int[] ret = { rownum, colnum };
// System.out.println(rownum + " " + colnum);
return ret;
}
static String getsequence(String name, int width) {
/*
* We must take ceiling because sometimes it's not
* a perfect square, we need the extra row.
*
* I thought the two below vars would be needed, was wrong!
* int height = (int) Math.ceil(alphabet.length / width);
* char[][] matrix = new char[width][height];
*
*/
StringBuilder seq = new StringBuilder();
int[] curcoord = {0, 0}; // y, x
for (int i=0; i<name.length(); i++) {
char curnchar = name.charAt(i);
int[] nextcoord = getcoords(curnchar, width);
int deltay = nextcoord[0] - curcoord[0];
int deltax = nextcoord[1] - curcoord[1];
boolean goup = true;
boolean goright = true;
if (deltax < 0)
goright = false;
if (deltay > 0) // tricky, this one is flipped
goup = false;
deltax = Math.abs(deltax);
deltay = Math.abs(deltay);
for (int j=0; j<deltay; j++) {
if (goup) seq.append(UP);
else seq.append(DOWN);
}
for (int k=0; k<deltax; k++) {
if (goright) seq.append(RIGHT);
else seq.append(LEFT);
}
seq.append(SELECT);
curcoord[0] = nextcoord[0];
curcoord[1] = nextcoord[1];
}
return seq.toString();
}
public static void main(String[] args) {
// for (char c : alphabet)
// System.out.println("char " + c);
System.out.println(getsequence("sex", 5));
}
}
Lol sorry for making my test title name "sex", was bored. Please don't flag me. Mods can remove if its offensive.
C++ code solution
void printCharacter(int startX, int startY, int endX, int endY)
{
int x = endX - startX;
int direction[4];//right, left, down,up
if(x < 0)
direction[1] = -1*x;
else
direction[0] = x;
int y = endY-startY;
if(y< 0)
direction[3] = -1*y;
else direction[2] = y;
while(direction[0]-->0) cout<<"l";
while(direction[1]-->0) cout<<"r";
while(direction[2]-->0) cout<<"d";
while(direction[3]-->0) cout<<"u";
cout<<'!';
}
void printMovieName(string name, int n)
{
int startX = 0;
int startY = 0;
int endX = 0;
int endY = 0;
int n = 5;
for(int i= 0; i < name.size(); i++)
{
char charecter = name[i];
int value = charecter-'a';
endX = value%n;
endY = value/n;
printCharacter(startX, startY, endX, endY);
startX = endX;
startY = endY;
}
}
printMovieName("up", 5)
#include <stdlib.h>
#include <stdio.h>
#include <stddef.h>
int main(int argc, char* argv[])
{
int width = 0;
int row = 0, col = 0;
char *film = NULL;
char res[200] = {'\0'};
char *pRes = res;
char start = 0;
if (argc < 3) {
printf("enter the grid width and the film name\n");
return EXIT_FAILURE;
}
sscanf(argv[1], "%d", &width );
film = argv[2];
if ((width > 26) || (width < 0)) return -1;
while (*film != '\0') {
if (* film == ' ') {film++; continue; }
if (*film < 'a') start = 'A';
else start = 'a';
row = (*film - start) / width;
col = (*film - start) % width;
while (row-- > 0) {
*pRes = 'd';
pRes++;
}
while (col-- > 0) {
*pRes = 'r';
pRes++;
}
*pRes = '!';
pRes++;
film++;
}
printf("resulting key buttons sequence: %s\n", res);
return EXIT_SUCCESS;
}
Easy enough, you don't even need the matrix for given example
consider a = 0, b=1,....z=25.
we have a 5x5 matrix, coordinate of a = 0,0 , b =0,1 and so on.
coordinate of an alphabet is (n/5, n%5) n=> integer value of alphabet, (a=0...z=25).
scan the input string left to right, "CON"
coordinates of C in given matrix, is ( 2/5 , 2%5) = (0,2).
coordinates of O in given matrix, is (14/5 , 14%5) = (2,4).
coordinates of N in given matrix, is (13/5, 13%5) = (2,3).
so problem reduces to giving direction for reaching 2,3 from 0,0 and from given path.
(0,0) -> (0,2) -> (2,4) -> (2,3).
first reduce distance vertical distance
0,0 to 0,2 difference on x =0-0 hence print nothing for x.
Now reduce distance on horizontal distance
0,0 to 0,2 difference on y=+2 hence print right 2 times, if value is -ve print left difference no. of times.
now we are at (0,2) have to go to (2,4).
again reduce distance on vertical axis first.
(2,2) from (0,2) distance = +2 hence print down 2 times, if difference is -ve print up difference no. of times.
reduce distance on horizontal axis,
(2,4) from (2,2) distance = +2 hence print right 2 times.
(2,3) from (2,4) print distance on horizontal axis = -1 print left one time.
how about scalability of this solution?
can we extend it for any configuration of matrix as well?
Yes we can, in that case create a hash map, that will store coordiantes of each alphabet.
This can be done by scanning the given matrix as part of pre-processing step.
Now, once you get input string, you immediately have coordinates of each alphabet and problem again reduces to printing path from source to destination. This part of above solution remains unchanged.
This code will work ! Let me know if there are any issues.
public static void printDVRPath(String input) {
int start_row = 0;
int start_col = 0;
for(char c : input.toCharArray()) {
if(Character.isLowerCase(c)) {
// assuming input is all small chars
int charPos = (int) c - 96;
int end_row = charPos / 5;
int end_col = (charPos % 5) - 1 ;
while (start_row!=end_row) {
if(start_row > end_row) {
System.out.print("U");
start_row --;
}
else {
System.out.print("D");
start_row ++;
}
}
while(start_col!=end_col) {
if(start_col > end_col) {
System.out.print("L");
start_col --;
}
else {
System.out.print("R");
start_col ++;
}
}
System.out.print("!");
}
}
}
#include <stdio.h>
#include <string.h>
const char* direction_table[4] = {
"LEFT",
"RIGHT",
"UP",
"DOWN"
};
enum {
LEFT,
RIGHT,
UP,
DOWN
};
void echo_direction(int direction)
{
printf("%s\n", direction_table[direction]);
}
void selected()
{
printf("OK\n");
}
void move(char from, char to)
{
int src, tgt, direction, coe;
// same char
if(from == to) return;
// for x direction
src = (from-'a')%5;
tgt = (to -'a')%5;
if(tgt < src) {
direction = LEFT;
coe = -1;
} else if (tgt > src) {
direction = RIGHT;
coe = 1;
}
while(src != tgt) {
echo_direction(direction);
src += coe;
}
// for y direction
src = (from - 'a') / 5;
tgt = (to - 'a') / 5;
if(tgt<src) {
direction = UP;
coe = -1;
} else if(tgt > src) {
direction = DOWN;
coe = 1;
}
while(src != tgt) {
echo_direction(direction);
src += coe;
}
}
void show_sequence(char *text, int len)
{
char from='a', to;
int i=0;
if(len <2) return;
while(i<len) {
// assume all char in the string is [a-z]
// otherwise, add validation of to here
to = text[i];
if(from==to=='z')
selected();
else if(from=='z' || to=='z')
{
move(from, 'u');
move('u', to);
selected();
}
else
{
move(from, to);
selected();
}
from = to;
i++;
}
}
int main(void)
{
char* test[] = {
"abcdefgzv",
"defklmyzuvz",
};
int i;
for(i =0; i<2; i++)
{
printf("TEST string [%s]\n", test[i]);
show_sequence(test[i], strlen(test[i]));
}
}
public static void getCode(int m, String str) {
int index = 0;
int i;
int n = str.length();
for(i = 0; i < n; i++) {
int dest = str.charAt(i) - 'a';
while(index != dest) {
if(index + m <= dest) {
index += m;
System.out.print("d");
} else if(index - m >= dest) {
index -= m;
System.out.print("u");
} else if(index > dest) {
index -= 1;
System.out.print("l");
} else {
index += 1;
System.out.print("r");
}
}
System.out.print("!");
}
}
I don't think this is correct because you will wrap around.
For example in the following layout, moving from e -> f you will output 'r!' which is incorrect
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
Ohh Agree !!
Here is new updated code
public static void getCode(int m, String str) {
int index = 0;
int i;
int n = str.length();
for(i = 0; i < n; i++) {
int dest = str.charAt(i) - 'a';
while(index != dest) {
if(index + m <= dest) {
index += m;
System.out.print("d");
} else if(index - m >= dest) {
index -= m;
System.out.print("u");
} else if(index > dest) {
if(index % m < dest % m) {
index -= m;
System.out.print("u");
} else {
index -= 1;
System.out.print("l");
}
} else {
if(index % m > dest % m) {
index += m;
System.out.print("d");
} else {
index += 1;
System.out.print("r");
}
}
}
System.out.print("!");
}
}
- Anonymous October 10, 2013