Cleartrip.com Interview Question
Software DevelopersCountry: India
import java.util.*;
public class RockProblem{
public static void main(String[] args){
int shore_b = 3;
int shore_a = 0;
List<Rock> rockList = new ArrayList<Rock>();
rockList.add(new Rock(1, 1, 1, 1, shore_a, shore_b));
rockList.add(new Rock(2, 1, 2, 1, shore_a, shore_b));
rockList.add(new Rock(3, 3, 4, 1, shore_a, shore_b));
solve(rockList, shore_a, shore_b);
}
public static void solve(List<Rock> rockList, int shore_a, int shore_b){
Path path = null;
for(Rock r: rockList){
if(r.touchShoreA && r.touchShoreB){
path = new Path(r);
break;
}
if(r.touchShoreA){
path = findPath(r, rockList);
if(path != null){
break;
}
}
}
if(path != null ){
System.out.println(path);
}
}
public static Path findPath(Rock rock, List<Rock> rockList){
if(rock.neighbers != null){
return null;
}
for(Rock r: rockList){
if(rock.index != r.index
&& rock.r + r.r - Math.sqrt(Math.pow(rock.y - r.y, 2) + Math.pow(rock.x - r.x, 2))>0 ){
if(r.touchShoreB){
//found path
Path p = new Path(rock);
p.next = new Path(r);
return p;
}
List<Rock> neighbers = rock.neighbers;
if(neighbers == null){
neighbers = new ArrayList<Rock>();
}
neighbers.add(r);
rock.neighbers = neighbers;
}
}
for(Rock r: rock.neighbers){
Path next = findPath(r, rockList);
if(next != null){
Path p = new Path(rock);
p.next = next;
return p;
}
}
return null;
}
}
class Path{
Rock r;
Path next;
Path(Rock r){
this.r = r;
}
@Override
public String toString(){
return r.index + (next == null ? "" : ("->" + next.toString()));
}
}
class Rock{
int index;
int x;
int y;
int r;
boolean touchShoreA = false;
boolean touchShoreB = false;
// neighbersClosertoShore, y + r bigger or equals this
List<Rock> neighbers;
Rock(int index, int x, int y, int r, int shore_a, int shore_b){
this.x = x;
this.y = y;
this.r = r;
this.index = index;
this.touchShoreA = (Math.abs(y - r) <= r) ;
this.touchShoreB = (Math.abs(shore_b - y)<= r);
}
}
Cutting to the cheese - dropping all useless information the problem is succinctly summarised by :
=======================================
Given a list of circles of various radii and centre:
1. Would it be possible to move from one starting point to another
2. What would be the min path and the circles
=======================================
Thus we end up having a directed graph, where :
======
1. Nodes are the circles
2. Edges between nodes exist, if and only if the circles overlap
3. Circles having centre with y larger than the North bank y are north bank stones
4. Circles having centre with y smaller than the South bank y are south bank stones
=========
Now, we need to find out all paths from one bank to another, and the minimum path.
This is doable by iterating over all source nodes - and rejecting paths.
I'm removing those rocks that are completely contained in bigger rocks and with remaining rocks creating a directed graph and using BFS to find the shortest route
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
/**
*
* @author Nalin.Sharma
*
*/
/*
*
* BFS implementation
*/
public class RockClimb {
static class Node{
public Node(int x, int y, int r, int n) {
super();
this.x = x;
this.y = y;
this.r = r;
num = n;
}
int x;
int y;
int r; //radius
int num;
Node parent;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = Integer.parseInt(sc.nextLine());
List<Node> list = new ArrayList<>();
for (int i = 0; i < n; i++) {
String [] arr = sc.nextLine().split(" ");
list.add(new Node(Integer.parseInt(arr[0]), Integer.parseInt(arr[1]), Integer.parseInt(arr[2]), i));
}
String[] Y = sc.nextLine().split(" ");
int ylow = Integer.parseInt(Y[1]);
int yhigh = Integer.parseInt(Y[0]);
boolean [] [] adj = new boolean[n][n];
boolean [] visited = new boolean[n];
for (int i = 0; i < list.size(); i++) {
for (int j = i+1; j < list.size(); j++) {
Node INode = list.get(i);
Node JNode = list.get(j);
//added
int ix1 = INode.x - INode.r;
int ix2 = INode.x + INode.r;
int iy1 = INode.y - INode.r;
int iy2 = INode.y + INode.r;
int jx1 = JNode.x - JNode.r;
int jx2 = JNode.x + JNode.r;
int jy1 = JNode.y - JNode.r;
int jy2 = JNode.y + JNode.r;
//clean rocks being completely engulfed by other rocks
if(jx1 <= ix1 && ix1 <=jx2 && jx1 <= ix2 && ix2 <=jx2
&& jy1 <= iy1 && iy1 <=jy2 && jy1 <= iy2 && iy2 <=jy2 ){
list.remove(i);
i -= 1;
continue;
}
else if(ix1 <= jx1 && jx1 <=ix2 && ix1 <= jx2 && jx2 <=ix2
&& iy1 <= jy1 && jy1 <=iy2 && iy1 <= jy2 && jy2 <=iy2 ){
list.remove(j);
j -= 1;
continue;
}
int x = Math.abs(INode.x - JNode.x);
int y = Math.abs(INode.y - JNode.y);
long hypot = x*x + y*y;
if(hypot <= INode.r + JNode.r){
//i,j rocks touch each other
adj [i] [j] = true;
adj [j] [i] = true;
}
}
}
Queue<Node> bfs = new LinkedList<>();
bfs.add(list.get(0));
Node fNode = null;
while(!bfs.isEmpty()){
Node node = bfs.remove();
if(visited[node.num] == true){
continue;
}
if(node.y + node.r >= yhigh){
fNode = node;
break;
}
visited[node.num] = true;
for (int i = 0; i < n; i++) {
if(adj[node.num][i] == true){
//line up connected neighbors
list.get(i).parent = node;
bfs.add(list.get(i));
}
}
}
if(fNode == null){
System.out.println("-1");
}
else{
int count = 0;
while(fNode != null){
fNode = fNode.parent;
count++;
}
System.out.println(count);
}
}
}
Build a graph with rocks as vertices, with edges representing overlaps between rocks.To find overlap between rocks use this code
}
Add source and destination vertices.Source vertex is connected to the "shore rocks" of
one shore. Destination vertex is connected to the "shore rocks" of other shore. Use this code to find shore rocks
}
- Srinivasan February 11, 2017Now we got a graph, we have to find shortest path from source to destination. We can use djikstra algorithm for this.