CareerCup

The solution works fine except for the part that it doesn't cater to the bullet proof requirement.

can you please post code for this

As mentioned here, convert the board into a graph.
Connect every cell to its neighbors with weight 1. O(n*m)
Connect the target cell to all other cells that it can be shot from with weight 0. O(n*m*b) where b is the number of bulletproof cells.
Run Dijkstra's algorithm on the soldier's cell.O(n*m) for the Fibonacci heap implementation.
Iterate over all of the target's neighbors to find the ones with the shortest paths. O(n*m*lg(n*m))
Sort and output the neighbors.

this need not be solved as a graph.

>the terrorist/target can be shot only in eight directions in the 2d matrix
>sort the bullet proof cells according to distance to soldier.
>see if he could shoot terrorist from the bullet proof cell
>store the least path of above
>the terrorists eight shot directions should be analyzed ,if the soldier can move linearly and take a shot ,(theres no bullet proof cell in the direction of the shot)
>the above can be optimized ,we need not look into all eight directions(if terrorist is the origin we need to check the quadrant in which soldier is present),only at most three paths of shot need be analyzed.

I believe the best thing to use is x,y coordinates, if person is in x,y then target is hittable if target present in any of below:
any, y
x, any
x+-i, x+-i

can pls post code for this..PLZz

Post the code

Post the code

import java.util.Arrays;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;

public class CandidateCode {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] field = { 3, 3 };
int[] startPoint = { 3, 1 };
int[] endPoint = { 2, 3 };
String[] BulletCell = { "2#2", "3#3" };
System.out.println(Arrays.toString(nearest_shoot_point(field,
startPoint, endPoint, BulletCell)));
}

// size of Battle Field, Start Position, Target and Bullet proof cell
public static String[] nearest_shoot_point(int[] input1, int[] input2,
int[] input3, String[] input4) {
// Write code here
if (input1 == null || input2 == null || input3 == null
|| input4 == null) {
System.exit(0);
}
int x = input2[0] - 1;
int y = input2[1] - 1;
/*System.out.println("final x and y" + (input3[0] - 1) + "="
+ (input3[1] - 1));*/
int count = 0;
String s = "";
Set<String> list = new TreeSet<String>();
int[][] directions = { { x, y }, { x, y }, { x, y }, { x, y },
{ x, y }, { x, y }, { x, y }, { x, y } };
// Ready the battle field
int[][] battleField = new int[input1[0]][input1[1]];

battleField[input2[0] - 1][input2[1] - 1] = 1;
battleField[input3[0] - 1][input3[1] - 1] = 1;

for (String p : input4) {
String[] tmp = p.split("#");
battleField[Integer.parseInt(tmp[0]) - 1][Integer.parseInt(tmp[1]) - 1] = 2;
}
//System.out.println(Arrays.deepToString(battleField));

// solveBattleField(battleField, 2, 2, input3[0] - 1, input3[1] - 1,"");
//System.out.println(list.isEmpty());
while (list.isEmpty()) {
//System.out.println(Arrays.deepToString(directions));
for (int z = 0; z < directions.length; z++) {
// System.out.println(Arrays.deepToString(directions));
try {
if (battleField[directions[z][0]][directions[z][1]] == 2) {
battleField[directions[z][0]][directions[z][1]] = 0;
}
} catch (ArrayIndexOutOfBoundsException e) {
// Do nothing in case of exception
}
if (solveBattleField(battleField, directions[z][0],
directions[z][1], input3[0] - 1, input3[1] - 1) == true) {
s = s + (directions[z][0] + 1) + "#" + (directions[z][1] + 1);
}
try {
if (battleField[directions[z][0]][directions[z][1]] == 2) {
battleField[directions[z][0]][directions[z][1]] = 2;
}
} catch (ArrayIndexOutOfBoundsException e) {

}
if (!s.equals("")) {
list.add(s);
s = "";
}
//System.out.println("Loop Ending");
}

directions[0][0] = directions[0][0] - 1; // up
directions[0][1] = directions[0][1];
directions[1][0] = directions[1][0] + 1; // Down
directions[1][1] = directions[1][1];
directions[2][0] = directions[2][0]; // Left
directions[2][1] = directions[2][1] - 1;
directions[3][0] = directions[3][0]; // right
directions[3][1] = directions[3][1] + 1;
directions[4][0] = directions[4][0] - 1; // diagonal
directions[4][1] = directions[4][1] + 1;
directions[5][0] = directions[5][0] + 1; // diagonal
directions[5][1] = directions[5][1] - 1;
directions[6][0] = directions[6][0] + 1; // diagonal
directions[6][1] = directions[6][1] + 1;
directions[7][0] = directions[7][0] - 1; // diagonal
directions[7][1] = directions[7][1] - 1;
if (!list.isEmpty()) {
break;
}
// count++;
}
//System.out.println(Arrays.toString(list.toArray()));
Iterator<String> iterate = list.iterator();
while (iterate.hasNext()) {
s = s + iterate.next() + " ";
}

String [] rtStr = s.split(" ");
Arrays.sort(rtStr);
return rtStr;
}

public static boolean solveBattleField(int[][] battleField, int x, int y,
int finalX, int finalY) {
if (checkUP(battleField, x, y, finalX, finalY) == true
|| checkDOWN(battleField, x, y, finalX, finalY) == true
|| checkLEFT(battleField, x, y, finalX, finalY) == true
|| checkRIGHT(battleField, x, y, finalX, finalY) == true
|| checkDIAGUP1(battleField, x, y, finalX, finalY) == true
|| checkDIAGUP2(battleField, x, y, finalX, finalY) == true
|| checkDIAGUP3(battleField, x, y, finalX, finalY) == true
|| checkDIAGUP4(battleField, x, y, finalX, finalY) == true) {
//System.out.println("****String Found****");
return true;
}
//System.out.println("String Not found");
return false;
}

public static boolean checkUP(int[][] battleField, int x, int y,
int finalX, int finalY) {
//System.out.println("checkUP" + x + "=" + y);
if (x < 0 || x >= battleField.length || y < 0
|| y >= battleField[0].length || battleField[x][y] == 2) {
return false;
} else if (x == finalX && y == finalY) {
return true;
} else
return checkUP(battleField, x - 1, y, finalX, finalY);
}

public static boolean checkDOWN(int[][] battleField, int x, int y,
int finalX, int finalY) {
//System.out.println("checkDOWN" + x + "=" + y);
if (x < 0 || x >= battleField.length || y < 0
|| y >= battleField[0].length || battleField[x][y] == 2) {
return false;
} else if (x == finalX && y == finalY) {
return true;
} else
return checkDOWN(battleField, x + 1, y, finalX, finalY);
}

public static boolean checkRIGHT(int[][] battleField, int x, int y,
int finalX, int finalY) {
//System.out.println("checkRIGHT" + x + "=" + y);
if (x < 0 || x >= battleField.length || y < 0
|| y >= battleField[0].length || battleField[x][y] == 2) {
return false;
} else if (x == finalX && y == finalY) {
return true;
} else
return checkRIGHT(battleField, x, y + 1, finalX, finalY);
}

public static boolean checkLEFT(int[][] battleField, int x, int y,
int finalX, int finalY) {
//System.out.println("checkLEFT" + x + "=" + y);
if (x < 0 || x >= battleField.length || y < 0
|| y >= battleField[0].length || battleField[x][y] == 2) {
return false;
} else if (x == finalX && y == finalY) {
return true;
} else
return checkLEFT(battleField, x, y - 1, finalX, finalY);
}

public static boolean checkDIAGUP1(int[][] battleField, int x, int y,
int finalX, int finalY) {
//System.out.println("checkDIAGUP1" + x + "=" + y);
if (x < 0 || x >= battleField.length || y < 0
|| y >= battleField[0].length || battleField[x][y] == 2) {
return false;
} else if (x == finalX && y == finalY) {
return true;
} else
return checkDIAGUP1(battleField, x - 1, y + 1, finalX, finalY);
}

public static boolean checkDIAGUP2(int[][] battleField, int x, int y,
int finalX, int finalY) {
//System.out.println("checkDIAGUP2" + x + "=" + y);
if (x < 0 || x >= battleField.length || y < 0
|| y >= battleField[0].length || battleField[x][y] == 2) {
return false;
} else if (x == finalX && y == finalY) {
return true;
}
return checkDIAGUP2(battleField, x + 1, y - 1, finalX, finalY);
}

public static boolean checkDIAGUP3(int[][] battleField, int x, int y,
int finalX, int finalY) {
//System.out.println("checkDIAGUP3" + x + "=" + y);
if (x < 0 || x >= battleField.length || y < 0
|| y >= battleField[0].length || battleField[x][y] == 2) {
return false;
} else if (x == finalX && y == finalY) {
return true;
} else
return checkDIAGUP3(battleField, x + 1, y + 1, finalX, finalY);
}

public static boolean checkDIAGUP4(int[][] battleField, int x, int y,
int finalX, int finalY) {
//System.out.println("checkDIAGUP4" + x + "=" + y);
if (x < 0 || x >= battleField.length || y < 0
|| y >= battleField[0].length || battleField[x][y] == 2) {
return false;
} else if (x == finalX && y == finalY) {
return true;
} else
return checkDIAGUP4(battleField, x - 1, y - 1, finalX, finalY);
}

}

Trying to post but getting error :(

Corrections in the code: Below is the perfect running code..

import java.util.Arrays;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;

public class CandidateCode {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] field = { 3, 3 };
		int[] startPoint = { 3, 2 };
		int[] endPoint = { 1, 1 };
		String[] BulletCell = { "2#2", "3#3" };
		System.out.println(Arrays.toString(nearest_shoot_point(field,
				startPoint, endPoint, BulletCell)));
	}

	// size of Battle Field, Start Position, Target and Bullet proof cell
	public static String[] nearest_shoot_point(int[] input1, int[] input2,
			int[] input3, String[] input4) {
		// Write code here
		if (input1 == null || input2 == null || input3 == null
				|| input4 == null) {
			System.exit(0);
		}
		int x = input2[0] - 1;
		int y = input2[1] - 1;
		/*System.out.println("final x and y" + (input3[0] - 1) + "="
				+ (input3[1] - 1));*/
		int count = 0;
		String s = "";
		Set<String> list = new TreeSet<String>();
		int[][] directions = { { x, y }, { x, y }, { x, y }, { x, y },
				{ x, y }, { x, y }, { x, y }, { x, y } };
		// Ready the battle field
		int[][] battleField = new int[input1[0]][input1[1]];

		battleField[input2[0] - 1][input2[1] - 1] = 1;
		battleField[input3[0] - 1][input3[1] - 1] = 1;

		for (String p : input4) {
			String[] tmp = p.split("#");
			battleField[Integer.parseInt(tmp[0]) - 1][Integer.parseInt(tmp[1]) - 1] = 2;
		}
		//System.out.println(Arrays.deepToString(battleField));

		// solveBattleField(battleField, 2, 2, input3[0] - 1, input3[1] - 1,"");
		//System.out.println(list.isEmpty());
		while (list.isEmpty()) {
			//System.out.println(Arrays.deepToString(directions));
			for (int z = 0; z < directions.length; z++) {
				// System.out.println(Arrays.deepToString(directions));
				try {
					if (battleField[directions[z][0]][directions[z][1]] == 2) {
						battleField[directions[z][0]][directions[z][1]] = 0;
					}
				} catch (ArrayIndexOutOfBoundsException e) {
					// Do nothing in case of exception
				}
				if (solveBattleField(battleField, directions[z][0],
						directions[z][1], input3[0] - 1, input3[1] - 1) == true) {
					s = s + (directions[z][0] + 1) + "#" + (directions[z][1] + 1);
				}
				try {
					if (battleField[directions[z][0]][directions[z][1]] == 0) {
						battleField[directions[z][0]][directions[z][1]] = 2;
					}
				} catch (ArrayIndexOutOfBoundsException e) {

				}
				if (!s.equals("")) {
					list.add(s);
					s = "";
				}
				//System.out.println("Loop Ending");
			}
			
			directions[0][0] = directions[0][0] - 1; // up
			directions[0][1] = directions[0][1];
			directions[1][0] = directions[1][0] + 1; // Down
			directions[1][1] = directions[1][1];
			directions[2][0] = directions[2][0]; // Left
			directions[2][1] = directions[2][1] - 1;
			directions[3][0] = directions[3][0]; // right
			directions[3][1] = directions[3][1] + 1;
			directions[4][0] = directions[4][0] - 1; // diagonal
			directions[4][1] = directions[4][1] + 1;
			directions[5][0] = directions[5][0] + 1; // diagonal
			directions[5][1] = directions[5][1] - 1;
			directions[6][0] = directions[6][0] + 1; // diagonal
			directions[6][1] = directions[6][1] + 1;
			directions[7][0] = directions[7][0] - 1; // diagonal
			directions[7][1] = directions[7][1] - 1;
			if (!list.isEmpty()) {
				break;
			}
			// count++;
		}
		//System.out.println(Arrays.toString(list.toArray()));
		Iterator<String> iterate = list.iterator();
		while (iterate.hasNext()) {
			s = s + iterate.next() + " ";
		}
		
		String [] rtStr = s.split(" ");
		Arrays.sort(rtStr);
		return rtStr;
	}

	public static boolean solveBattleField(int[][] battleField, int x, int y,
			int finalX, int finalY) {
		if (checkUP(battleField, x, y, finalX, finalY) == true
				|| checkDOWN(battleField, x, y, finalX, finalY) == true
				|| checkLEFT(battleField, x, y, finalX, finalY) == true
				|| checkRIGHT(battleField, x, y, finalX, finalY) == true
				|| checkDIAGUP1(battleField, x, y, finalX, finalY) == true
				|| checkDIAGUP2(battleField, x, y, finalX, finalY) == true
				|| checkDIAGUP3(battleField, x, y, finalX, finalY) == true
				|| checkDIAGUP4(battleField, x, y, finalX, finalY) == true) {
			//System.out.println("****String Found****");
			return true;
		}
		//System.out.println("String Not found");
		return false;
	}

	public static boolean checkUP(int[][] battleField, int x, int y,
			int finalX, int finalY) {
		//System.out.println("checkUP" + x + "=" + y);
		if (x < 0 || x >= battleField.length || y < 0
				|| y >= battleField[0].length || battleField[x][y] == 2) {
			return false;
		} else if (x == finalX && y == finalY) {
			return true;
		} else
			return checkUP(battleField, x - 1, y, finalX, finalY);
	}

	public static boolean checkDOWN(int[][] battleField, int x, int y,
			int finalX, int finalY) {
		//System.out.println("checkDOWN" + x + "=" + y);
		if (x < 0 || x >= battleField.length || y < 0
				|| y >= battleField[0].length || battleField[x][y] == 2) {
			return false;
		} else if (x == finalX && y == finalY) {
			return true;
		} else
			return checkDOWN(battleField, x + 1, y, finalX, finalY);
	}

	public static boolean checkRIGHT(int[][] battleField, int x, int y,
			int finalX, int finalY) {
		//System.out.println("checkRIGHT" + x + "=" + y);
		if (x < 0 || x >= battleField.length || y < 0
				|| y >= battleField[0].length || battleField[x][y] == 2) {
			return false;
		} else if (x == finalX && y == finalY) {
			return true;
		} else
			return checkRIGHT(battleField, x, y + 1, finalX, finalY);
	}

	public static boolean checkLEFT(int[][] battleField, int x, int y,
			int finalX, int finalY) {
		//System.out.println("checkLEFT" + x + "=" + y);
		if (x < 0 || x >= battleField.length || y < 0
				|| y >= battleField[0].length || battleField[x][y] == 2) {
			return false;
		} else if (x == finalX && y == finalY) {
			return true;
		} else
			return checkLEFT(battleField, x, y - 1, finalX, finalY);
	}

	public static boolean checkDIAGUP1(int[][] battleField, int x, int y,
			int finalX, int finalY) {
		//System.out.println("checkDIAGUP1" + x + "=" + y);
		if (x < 0 || x >= battleField.length || y < 0
				|| y >= battleField[0].length || battleField[x][y] == 2) {
			return false;
		} else if (x == finalX && y == finalY) {
			return true;
		} else
			return checkDIAGUP1(battleField, x - 1, y + 1, finalX, finalY);
	}

	public static boolean checkDIAGUP2(int[][] battleField, int x, int y,
			int finalX, int finalY) {
		//System.out.println("checkDIAGUP2" + x + "=" + y);
		if (x < 0 || x >= battleField.length || y < 0
				|| y >= battleField[0].length || battleField[x][y] == 2) {
			return false;
		} else if (x == finalX && y == finalY) {
			return true;
		}
		return checkDIAGUP2(battleField, x + 1, y - 1, finalX, finalY);
	}

	public static boolean checkDIAGUP3(int[][] battleField, int x, int y,
			int finalX, int finalY) {
		//System.out.println("checkDIAGUP3" + x + "=" + y);
		if (x < 0 || x >= battleField.length || y < 0
				|| y >= battleField[0].length || battleField[x][y] == 2) {
			return false;
		} else if (x == finalX && y == finalY) {
			return true;
		} else
			return checkDIAGUP3(battleField, x + 1, y + 1, finalX, finalY);
	}

	public static boolean checkDIAGUP4(int[][] battleField, int x, int y,
			int finalX, int finalY) {
		//System.out.println("checkDIAGUP4" + x + "=" + y);
		if (x < 0 || x >= battleField.length || y < 0
				|| y >= battleField[0].length || battleField[x][y] == 2) {
			return false;
		} else if (x == finalX && y == finalY) {
			return true;
		} else
			return checkDIAGUP4(battleField, x - 1, y - 1, finalX, finalY);
	}

}

You can think of the board as a graph, where each cell is connected by a 1 weight edge, you have starting x,y of the soldier which will be on a certain vertex, you have starting point of targets which will be on some vertexes, based on this you can use solution:

1. calculate shortest distance from origin to target using djikstra.
2. Let's call it N the distance from Origin to Target, Starting from O traverse through path from O to T stopping at Node (N - 8), return that node as nearest shooting point. If there are more than one path choose any bullet-proof one (although not implicit in the question I guess shooting from a bullet proof cell must be safer than a non bullet-proof one).

Obs1 : If path length is shorter than (N - 8) soldier can shoot target from Origin, so return O.

Obs2 : If target is in a bullet-proof cell, solider must walk over that same cell in order to shoot target, so in this case nearest distance would be N.