CareerCup

import java.util.LinkedList;
import java.util.Queue;

public class PathFinder {

    private Queue<Coordinator> queue;
	public class Coordinator{
		int x;
		int y;
		
		public Coordinator(int x , int y){
			this.x = x;
			this.y = y;			
		}
	}
	
	public PathFinder(){
		queue = new LinkedList<Coordinator>();
	}
	
	char [][] maze = {{'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',' ',' ',' ',' '}};
	
	
	public void setupCoordinator(String word){
	   for (int i = 0 ;i<word.length() ;++i){
		   queue.add(new Coordinator((word.charAt(i)-'a')/5,(word.charAt(i)-'a')%5));
	   }
	}
	
	public void findPath(){
		Coordinator pre = new Coordinator(0,0);
		int xMove = 0;
		int yMove = 0;
		while (!queue.isEmpty()){
		     Coordinator cur = queue.poll();
		     xMove = cur.x - pre.x;
		     yMove = cur.y - pre.y;		     
		     int i = pre.x;
		     int j = pre.y;
		     if (xMove >0){
		    	 for (i = pre.x+1 ; i<=pre.x + xMove;++i){
		    		 System.out.println("Down//now we are at " + maze[i][j]);
		    	 }
		    	 i-=1;
		     }else if (xMove<0){
		    	 for (i = pre.x-1; i>=pre.x - Math.abs(xMove);--i){
		    		 System.out.println("up//now we are at " + maze[i][j]);
		    	 }
		    	 i+=1;
		     }
		     
		     
             if (yMove >0){            	 
		    	 for (j = pre.y+1 ; j<=pre.y + yMove;++j){		    		 
		    		 System.out.println("Right//now we are at " + maze[i][j]);
		    	 }
		    	 j-=1;
		     }else if (yMove<0){		    	
		    	 for (j = pre.y-1; j>=pre.y - Math.abs(yMove);--j){		    		 
		    		 System.out.println("Left//now we are at " + maze[i][j]);
		    	 }
		    	 j+=1;
		     }
             System.out.println("OK//to select " + maze[i][j]);
             
             pre = cur;
		}
		
	}

}

assume its a graph as links to element on left, right, top and bottom. use bellman ford or any other algorithms to find shortest path between all nodes. Then its just about searching the start and end points in a 26x26 array.

C++ solution.

void Remote(string word)
{
    // Start at top left
    int cur_x = 0;
    int cur_y = 0;

    cout << "Starting at: a" << endl << endl;

    for(size_t i=0; i < word.size(); i++) {
        cout << word[i] << ": ";

        int idx = word[i] - 'a';

        // 6x5 grid
        int dst_y = idx / 5;
        int dst_x = idx % 5;

        if(word[i] == 'z') { // special case: dest is 'z', can reach always with left + down
            int left = cur_x;
            int down = dst_y - cur_x;

            for(int j=0; j < left; j++)
                cout << "Left ";

            for(int j=0; j < down; j++)
                cout << "Down ";
        }
        else { // can reach any letter with up/down + left/right
            int dx = dst_x - cur_x;
            int dy = dst_y - cur_y;

            for(int j=0; j < abs(dy); j++) {
                if(dy > 0)
                    cout << "Down ";
                else 
                    cout << "Up ";
            }

            for(int j=0; j < abs(dx); j++) {
                if(dx > 0)
                    cout << "Right ";
                else 
                    cout << "Left ";
            }
        }

        cout << "OK" << endl;
      
        cur_x = dst_x;
        cur_y = dst_y;
    }
}

int main()
{
    Remote("zoosi");
}

Starting at: a

z: Down Down Down Down Down OK
o: Up Up Up Right Right Right Right OK
o: OK
s: Left Down OK
i: Up Up OK

#include "stdio.h"
#include "conio.h"
#include "string.h"
#define kColumnCount 5
char maze[6][kColumnCount] ={
{'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',' ',' ',' ',' '}};
int xp = 0, yp = 0;
void printStepsForMessage(char *mess)
{
for(int i=0;i<strlen(mess);i++)
{
int asciVal = mess[i]-'a';
if(asciVal<0||asciVal>25)
continue;
int y = asciVal/kColumnCount;
int x = asciVal%kColumnCount;
if(xp<x)
{
for(;xp<x;xp++)
printf("Move Right\n");
}
else if(xp>x)
{
for(;xp>x;xp--)
printf("Move Left\n");
}

if(yp<y)
{
for(;yp<y;yp++)
printf("Move Down\n");
}
else if(yp>y)
{
for(;yp>y;yp--)
printf("Move Up\n");
}

printf ("OK/to select %c\n", mess[i]);
}
}

int _tmain(int argc, _TCHAR* argv[])
{
printStepsForMessage(" ");
printStepsForMessage("mapzansz ");
getch();
return 0;
}

Not sure why so much very hard to read code is dumped here...

Let's consider 'con'. The distance between 'c' and 'o' is 'o'-'c'=12. This means currently we are 12/5=2 rows up and 12%5=2 cols left. So go down 2 and right 2. Similarly 'n'-'o'=1, so we are 0 rows down/up and 1 col to the left. Thus just go 1 to the right. We must be careful to stay in bounds, i.e. if the word is 'conq' then diff is 3 but we are at distance of 2 from the border (we always know where we are) then we have to wrap, i.e. add a row and go left instead of right. I guess the devil is in details :)

public void findCharSequence(String word) {
		int currX = 0, currY = 0;
		
		for (int i = 0; i < word.length(); i++) {
			int charValue = word.charAt(i) - 'a';
			int destX = charValue % 5; // no need to -1 since charValue already starts from 0
			int destY = charValue / 5;
			
			for (int j = 0; j <= Math.abs(currY-destY); j++) {
				if (currY-destY < 0)  // if currY is row 1, and destY is row 3
					print "Down"
				else
					print "Up"
			}
			for (int j = 0; j <= Math.abs(currX-destX); j++) {
				if (currX-destX < 0)  // if currX is col 1, and destX is col 3
					print "Right"
				else
					print "Left"
			}
			print "OK"
			currX = destX;
			currY = destY;
		}
	}

Will this work? Anyone?

public static void findCharSequence(char[][] m, String word) {
			int currX = 0, currY = 0;
			
			for (int i = 0; i < word.length(); i++) {
				int charValue = word.charAt(i) - 'a';
				int destX = charValue % 5; // no need to -1 since charValue already starts from 0
				int destY = charValue / 5;
				// inclusive, a -> c, starting from 1, so that we can use j to print
				for (int j = 1; j <= Math.abs(currY-destY); j++) {  
					if (currY-destY < 0)  // if currY is row 1, and destY is row 3
						System.out.println("Down //we are at " + m[currY+j][currX]);
					else
						System.out.println("Up //we are at "+ m[currY-j][currX]);
				}
				for (int j = 1; j <= Math.abs(currX-destX); j++) {
					if (currX-destX < 0)  // if currX is col 1, and destX is col 3
						System.out.println("Right //we are at "+ m[destY][currX+j]);
					else
						System.out.println("Left //we are at " + m[destY][currX-j]);
				}
				System.out.println("OK //to select " + m[destY][destX]);
				currX = destX;
				currY = destY;
			}
		}

For "zoosi":
Down //we are at f
Down //we are at k
Down //we are at p
Down //we are at u
Down //we are at z
OK //to select z
Up //we are at u
Up //we are at p
Up //we are at k
Right //we are at l
Right //we are at m
Right //we are at n
Right //we are at o
OK //to select o
OK //to select o
Down //we are at t
Left //we are at s
OK //to select s
Up //we are at n
Up //we are at i
OK //to select i

I don't think we will need a special case for z if we process y direction before x direction.

You need take care of z case even if you process y before x. Take into consideration "acz", the correct order should be: OK
RIGHT
RIGHT
OK
LEFT
LEFT
DOWN
DOWN
DOWN
DOWN
DOWN
OK

{
// typepat.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"


#include<stdio.h>
#include<conio.h>
#include<string.h>

int main()
{
char str[6][5],sub[20];
int i,j,loci,locj,m,n,p,len,k=0;
m=0;
n=0;
p=97;
for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
{
str[i][j]=p;
p++;
}
}
str[5][0]=p;
str[5][1]=str[5][2]=str[5][3]=str[5][4]=32;
for(i=0;i<6;i++)
{
for(j=0;j<5;j++)
{
printf("%c\t",str[i][j]);
}
printf("\n");
}
printf("\nEnter a string: ");
gets(sub);
printf("\n------------------\n");
len=strlen(sub);
p=0;
while(sub[p]!='\0')
{
for(i=0;i<6;i++)
{
for(j=0;j<5;j++)
{
if((sub[p]==str[i][j]&&sub[p]!='\0'))
{
loci=i;
locj=j;
break;
}
}
}
p++;
while(m<loci)
{
printf("PRESS DOWN ARROW\n");
m++;
}
while(n<locj)
{
printf("PRESS RIGHT ARROW\n");
n++;
}
while(n>locj)
{
printf("PRESS LEFT ARROW\n");
n--;
}
while(m>loci)
{
printf("PRESS UP ARROW\n");
m--;
}
if(m==loci&&n==locj)
{
printf("PRESS OK\n");
}
k++;
}
getch();
return 0;
}


}

import java.util.LinkedList;
import java.util.Queue;

public class Maze
{

	private static char[][] maze = null;
	static
	{
		maze = new char[6][5];
		maze[0][0] = 'a';
		maze[0][1] = 'b';
		maze[0][2] = 'c';
		maze[0][3] = 'd';
		maze[0][4] = 'e';

		maze[1][0] = 'f';
		maze[1][1] = 'g';
		maze[1][2] = 'h';
		maze[1][3] = 'i';
		maze[1][4] = 'j';

		maze[2][0] = 'k';
		maze[2][1] = 'l';
		maze[2][2] = 'm';
		maze[2][3] = 'n';
		maze[2][4] = 'o';

		maze[3][0] = 'p';
		maze[3][1] = 'q';
		maze[3][2] = 'r';
		maze[3][3] = 's';
		maze[3][4] = 't';

		maze[4][0] = 'u';
		maze[4][1] = 'v';
		maze[4][2] = 'w';
		maze[4][3] = 'x';
		maze[4][4] = 'y';

		maze[5][0] = 'z';
		maze[5][1] = ' ';
		maze[5][2] = ' ';
		maze[5][3] = ' ';
		maze[5][4] = ' ';
	}

	public void pathFinder(String word)
	{
		if (word == null || word.length() == 0)
		{
			return;
		}
		Queue<Corridante> queue = new LinkedList<>();

		for (char c : word.toCharArray())
		{
			queue.add(new Corridante((c - 'a') / 5, (c - 'a') % 5));
		}

		findPath(queue, word);

	}

	private void findPath(Queue<Corridante> queue, String word)
	{
		Corridante pre = new Corridante(0, 0);
		int xMove = 0;
		int yMove = 0;
		while (!queue.isEmpty())
		{
			Corridante cur = queue.poll();
			xMove = cur.x - pre.x;
			yMove = cur.y - pre.y;

			int i = pre.x;
			int j = pre.y;
			if (xMove > 0)
			{
				for (i = pre.x + 1; i <= pre.x + xMove; i++)
				{
					System.out.println("DOWN//Now we are on: " + maze[i][j]);
				}
				i--;
			}
			else if (xMove < 0)
			{
				for (i = pre.x - 1; i >= pre.x + xMove; i--)
				{
					System.out.println("UP//Now we are on: " + maze[i][j]);
				}
				i++;
			}

			if (yMove > 0)
			{
				for (j = pre.y + 1; j <= pre.y + yMove; j++)
				{
					System.out.println("LEFT//Now we are on: " + maze[i][j]);
				}
				j--;
			}
			else if (yMove < 0)
			{
				for (j = pre.y - 1; j >= pre.y + yMove; j--)
				{
					System.out.println("RIGHT//Now we are on: " + maze[i][j]);
				}
				j++;
			}

			System.out.println("OK//To select: " + maze[i][j]);
			pre = cur;
		}
		
		System.out.println("------------------------------------");
	}
}

Python:

def find_path(word, box):
  curs = 0
  steps = []
  for letter in word:
    code = ord(letter) - ord(box[0][0])
    curs_row = curs / len(box[0])
    code_row = code / len(box[0])
    dy = code_row - curs_row
    curs_pos = curs - curs_row * len(box[0])
    code_pos = code - code_row * len(box[0])
    dx = code_pos - curs_pos
    dy_before_dx = True
    if len(box[curs_row]) < len(box[0]):
      dy_before_dx = True
    elif len(box[code_row]) < len(box[0]):
      dy_before_dx = False
    if dy_before_dx:
      items = ((dy, 'down', 'up'), (dx, 'right', 'left'))
    else:
      items = ((dx, 'right', 'left'), (dy, 'down', 'up'))
    for d, first_dir, second_dir in items:
      while d != 0:
        if d > 0:
          d -= 1
          steps.append(first_dir)
        else:
          d += 1
          steps.append(second_dir)
    steps.append('click')
    curs = code
  for step in steps:
    print step


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

find_path('zonez', box)