TCHS-5-1000

Problem Statement

When programming, I don't like to take my fingers off the keyboard, and hence, I don't use the mouse. So, when navigating my source, I like to do so in such a way as to minimize keystrokes. My text editor supports the following keystrokes: left, right, up, down, home, end, top, bottom, word left and word right. The word left and word right keystrokes position the cursor at a word beginning; a word beginning is the first letter of the word. None of the keystrokes cause the cursor to wrap. When moving the cursor vertically, my text editor does not change the cursor's horizontal position. So, if the cursor is at column 50 and the up arrow is pressed, moving the cursor to a row with only 10 characters, only the row changes. My text editor does not allow the cursor to be positioned left of the first column, above the first row or below the last row.

The keys left, right, up, down, home, end, top, bottom, word left and word right behave as described below:

1. left, right, up and down - move the cursor one position in the indicated direction (see notes).
2. home - causes the cursor to move to column 0 of the current row.
3. end - causes the cursor to move to the last character of source in the current row.
4. top - causes the cursor to move to the top row (row 0) retaining its column position.
5. bottom - causes the cursor to move to the bottom row retaining its column position.
6. word left - causes the cursor to jump to the first word beginning that is strictly left of the cursor position, if one exists. Otherwise does nothing.
7. word right - causes the cursor to jump to the first word beginning that is strictly right of the cursor position, if one exists. Otherwise does nothing.

You will be given a String[] source representing the source code, a int[] start representing the starting position of the cursor and a int[] finish representing the ending position of the cursor. The first int in both start and finish specifies the 0-indexed row and the second int specifies the 0-indexed column. You are to calculate and return the minimum number of keystrokes required to get from start to finish.

Definition

Class:	TextEditorNavigation
Method:	keystrokes
Parameters:	String[], int[], int[]
Returns:	int
Method signature:	int keystrokes(String[] source, int[] start, int[] finish)
(be sure your method is public)

Notes

-

For the purposes of this problem, we use the convention that the cursor covers each character. Some editors (normally in "insert mode") have the cursor preceding each character.

-

A keypress may not have any effect. For example, pressing up in the top row does nothing, pressing left in the first column does nothing and pressing down in the bottom row does nothing. Pressing right always has an effect.

Constraints

-

source will contain between 1 and 50 elements, inclusive.

-

Each element of source will contain between 1 and 50 characters, inclusive.

-

Each character must be a letter ('a'-'z', 'A'-'Z') or ' '.

-

start and finish will each contain exactly 2 elements.

-

start and finish will each represent character positions that exist in source.

Examples

0)

{"AAAAA AAA AAAAAAAAAAAAA  AAAA",
 "AA   AAAAAAAAA AAAA     AAAA",
 "BBBBBBBBBBBBBBBBBBBBBBBBBBB",
 "BBBBBBB BBBBBBBBBB BBBBBBB",
 "CCC CCCC CCCCCC      CCCC",
 "DDDDDDDDDDDDDDDDDDD"}

{5, 7}

{2, 2}

Returns: 6

This can be achieved by the following keystrokes in the given order: home, top, down, down, right, right.

1)

{"A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "BB BB BB BB BB BB BB BB BB BB BB BB BB BB BB BB BB",
 "CCC CCC CCC CCC CCC CCC CCC CCC CCC CCC CCC CCC CC",
 "DDDD DDDD DDDD DDDD DDDD DDDD DDDD DDDD DDDD DDDD ",
 "EEEEE EEEEE EEEEE EEEEE EEEEE EEEEE EEEEE EEEEE EE",
 "FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF ",
 "GGG GGG GGG GGG GGG GGG GGG GGG GGG GGG GGG GGG GG",
 "HHHHHHHHHHH HHHHHHHHHH HHHHHHHHHH HHHHHHHHHH HHHHH",
 "IIIIIIIIIIIIIII IIIIIIIIIIIIIII IIIIIIIIIIIIIII   ",
 "JJJJJJJJ JJJJJJJJ JJJJJJJJ JJJJJJJJ JJJJJJJJ JJJJJ",
 "KKKKKKKKKKKKKKKKKKKKKKKKKK KKKKKKKKKKKKKKKKKKKKKKK",
 "LLLLLLLLLL LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL",
 "MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM",
 "N N N N N N N N N N N N N N N N N N N N N N N N N ",
 "OOOOO OOOO OOO OO O O OO OOO OOOO OOOOO OOOOOO OOO",
 "PPPPPPP PPPPPP PPPPP PPPP PPP PP P P PP PPP PPPP P",
 "QQQQQQ QQQQQ QQQQ QQQ QQ Q Q QQ QQQ QQQQ QQQQQ QQQ",
 "ZZZZ ZZ ZZZ ZZ ZZZZ ZZ ZZZ ZZ ZZZZ ZZ ZZZ ZZ ZZZZ ",
 "SSS S SSS S SSS S SSS S SSS S SSS S SSS S SSS S SS",
 "TT TT TT TT TT TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT"}

{12, 20}

{4, 36}

Returns: 8

2)

{"A A A A AAAAAAA A A A A A A A A A A",
 "B BBBBB B B B B BBBBB B B B B B B B B"}

{1, 0}

{1, 22}

Returns: 6

3)

{"AAAAAAAAAAAAAA A A A A A A A A A A"}

{0, 2}

{0, 15}

Returns: 1

4)

{"A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "N N N N N N N N N N N N N N N N N N N N N N N N N ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 "A A A A A A A A A A A A A A A A A A A A A A A A A ",
 " O O O O O O O O O O O O OO O O O O O O O O O O O ",
 " P P P P P P P P P P P P P PP P P P P P P P P P P ",
 " Q Q Q Q Q Q Q Q Q Q Q Q Q Q QQ Q Q Q Q Q Q Q Q Q ",
 " R R R R R R R R R R R R R R R RR R R R R R R R R ",
 " S S S S S S S S S S S S S S S S SS S S S S S S S ",
 " T T T T T T T T T T T T T T T T T TT T T T T T T ",
 " U U U U U U U U U U U U U U U U U U UU U U U U U ",
 " V V V V V V V V V V V V V V V V V V V VV V V V V ",
 " W W W W W W W W W W W W W W W W W W W W WW W W W ",
 " X X X X X X X X X X X X X X X X X X X X X XX X X ",
 " Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y YY Y ",
 " Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z ZZZ"}

{49, 49}

{38, 26}

Returns: 23

5)

{"AAA", "BB", "CCC"}

{1, 1}

{1, 1}

Returns: 0

6)

{"AAAAA AAA AAAAAAAAAAAAA  AAAA",
 "AA   AAAAAAAAA AAAA     AAAA",
 "BBBBBBBBBBBBBBBBBBBBBBBBBBB",
 "BBBBBBB BBBBBBBBBB BBBBBBB",
 "CCC CCCC CCCCCC      CCCC",
 "DDDDDDDDDDDDDDDDDDD"}

{2, 17}

{1, 2}

Returns: 4

7)

{"A PC to do CAD huh  Sounds reasonable",
 "Aurthor go out and buy us five new PCs",
 "Dont you want to think about this for a minute",
 "No every second counts and we want to be ahead of",
 "the competition",
 "       OK Greate idea Please place lOOk worth of",
 "unmarked bills in my suitcase and Ill be on my way"}

{0, 11}

{1, 15}

Returns: 2

import java.util.*;

public class TextEditorNavigation {

	class Pos {
		int row;
		int col;

		Pos(int row, int col) {
			this.row = row;
			this.col = col;
		}

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + col;
			result = prime * result + row;
			return result;
		}

		@Override
		public boolean equals(Object o) {
			Pos p = (Pos) o;
			if (p != null && p.row == row && p.col == col)
				return true;
			return false;
		}
	}

	enum Keys {LEFT, RIGHT, UP, DOWN, HOME, END, TOP, BOTTOM, WORD_LEFT, WORD_RIGHT}

	String[] code;
	List<List<Integer>> bounds = new LinkedList<List<Integer>>();

	public int keystrokes(String[] code, int[] from, int[] to) {
		this.code = code;
		for (int i = 0; i < code.length; i++) {
			List<Integer> bound = new LinkedList<Integer>();
			for (int j = 0, n = code[i].length(); j < n; ) {
				for ( ; j < n && code[i].charAt(j) == ' '; j++) ;
				if (j < n)
					bound.add(j);
				for ( ; j < n && code[i].charAt(j) != ' '; j++) ;
			}
			bounds.add(bound);
		}
		int[][] map = new int[50][50];
		for (int[] a : map)
			Arrays.fill(a, Integer.MAX_VALUE);
		
		Pos s = new Pos(from[0], from[1]), t = new Pos(to[0], to[1]);
		LinkedList<Pos> open = new LinkedList<Pos>();
		LinkedList<Pos> close = new LinkedList<Pos>();
		map[s.row][s.col] = 0;
		open.add(s);
		int times = 0;
		while (!open.isEmpty() && ++times < 9999) {
			Pos a = open.poll();
			close.add(a);
			for (int i = 0; i < Keys.values().length; i++) {
				Pos b = getNext(a, Keys.values()[i]);
				if (b == null || open.contains(b) || close.contains(b))
					continue;
				map[b.row][b.col] = map[a.row][a.col] + 1;
				if (b.equals(t))
					return map[b.row][b.col];
				open.add(b);
			}
		}
		return 0;
	}

	private Pos getNext(Pos a, Keys key) {
		Pos b = null;
		switch (key) {
		case LEFT:
			if (a.col > code[a.row].length() - 1)
				b = new Pos(a.row, code[a.row].length() - 1);
			else if (a.col > 0)
				b = new Pos(a.row, a.col - 1);
			break;
		case RIGHT:
			if (a.col > code[a.row].length() - 1)
				b = new Pos(a.row, code[a.row].length() - 1);
			else if (a.col < code[a.row].length() - 1)
				b = new Pos(a.row, a.col + 1);
			break;
		case UP:
			if (a.row > 0)
				b = new Pos(a.row - 1, a.col);
			break;
		case DOWN:
			if (a.row < code.length - 1)
				b = new Pos(a.row + 1, a.col);
			break;
		case HOME:
			if (a.col > 0)
				b = new Pos(a.row, 0);
			break;
		case END:
			if (a.col != code[a.row].length() - 1)
				b = new Pos(a.row, code[a.row].length() - 1);
			break;
		case TOP:
			if (a.row > 0)
				b = new Pos(0, a.col);
			break;
		case BOTTOM:
			if (a.row < code.length - 1)
				b = new Pos(code.length - 1, a.col);
			break;
		case WORD_LEFT:
			if (a.col > code[a.row].length() - 1)
				b = new Pos(a.row, code[a.row].length() - 1);//?
			else {
				for (int i = bounds.get(a.row).size() - 1; i >= 0; i--)
					if (bounds.get(a.row).get(i) < a.col) {
						b = new Pos(a.row, bounds.get(a.row).get(i));
						break;
					}
			}
			break;
		case WORD_RIGHT:
			if (a.col > code[a.row].length() - 1)
				b = new Pos(a.row, code[a.row].length() - 1);//?
			else {
				for (int i = 0; i < bounds.get(a.row).size(); i++)
					if (bounds.get(a.row).get(i) > a.col) {
						b = new Pos(a.row, bounds.get(a.row).get(i));
						break;
					}
			}
			break;
		}
		return b;
	}

}