CareerCup

1. Trace back O(logn) for both n1 and n2 then find root 1 and root 2. if not same, then different parents. count the nodes you pass, count1, count2
2. if count1 > count2, trace up (count1-count2) nodes of N1 then compare N2, if not same compare second level parents and so on

import java.util.*;

public class StringToLetts {
	public static void main(String[] args) {
		String input = "12342314517";
		char[] charArr = input.toCharArray();
		findCombs(charArr, 0, "");
		input = "11111";
		charArr = input.toCharArray();
		findCombs(charArr, 0, "");
	}

	public static void findCombs(char[] charArr, int fromI, String prefix) {
		String newPrefix = prefix;
		if (fromI > charArr.length -1){
			System.out.println(prefix );
		}
		for(int i = fromI; i< charArr.length; i++){
			char c = charArr[i];
			if((c=='1' || c=='2') && i+1 < charArr.length){
				Integer integer = Integer.parseInt(c +"" + charArr[i+1] );
				if(integer<=26){
					if(i+2<charArr.length){
						findCombs(charArr, i+2, newPrefix + "," + c + charArr[i+1]);
					} else {
						System.out.println(newPrefix + "," + c + charArr[i+1]);
					}
				}
			}
			newPrefix +=  "," + c ;
		}
		System.out.println(newPrefix);
	}
}

import java.util.*;

public class StringToLetts {
	public static void main(String[] args) {
		String input = "12342314517";
		char[] charArr = input.toCharArray();
		findCombs(charArr, 0, "");
	}

	public static void findCombs(char[] charArr, int fromI, String prefix) {
		String newPrefix = prefix;
		if(fromI == charArr.length -1){
			System.out.println(prefix + charArr[fromI]);
		} else if (fromI > charArr.length -1){
			System.out.println(prefix + ",");
		}
		for(int i = fromI; i< charArr.length; i++){
			char c = charArr[i];
			if(c=='1' || c=='2'){
				Integer integer = Integer.parseInt(c +"" + charArr[i+1] );
				if(integer<=26){
					if(i+2<charArr.length){
						findCombs(charArr, i+2, newPrefix + "," + c + charArr[i+1]);
					} else {
						System.out.println(newPrefix + "," + c + charArr[i+1]);
					}
				}
			}
			newPrefix +=  "," + c ;
		}
	}
}

import java.util.*;

public class MoveNonZeros {
	public static void main(String[] args) {
		int[] arr = new int[]{ 0, 17, 29, 0, 11, 25, 0, 0, 55, 62, 21, 0, 1001, 11, 0, 55, 190, 0};
		int pointer = arr.length -1;
		for(int i = 0; i <= pointer ; i++){
			if(arr[i] != 0){
				for(int k = pointer; k >=0; k--){
					if(arr[k] == 0) {
						arr[k] = arr[i];
						arr[i] = 0;
						pointer = k-1;
						break;
					}
				}
			}
		}
		for(int value: arr){
			System.out.println(value);
		}
	}
	
}

import java.util.*;

public class SubStringLetters {
	public static void main(String[] args) {
		System.out.println(findSubString("aabbccba"));
		System.out.println(findSubString("abbcac"));
	}

	public static String findSubString(String input) {
		String result = input;
		Set<Character> set = new HashSet<Character>();
		char[] charArr = input.toCharArray();
		for (int i = 0; i < charArr.length; i++) {
			if (!set.contains(charArr[i])) {
				set.add(new Character(charArr[i]));
			}
		}
		int size = set.size();
		Character previous = null;
		for (int i = 0; i < charArr.length; i++) {
			Character current = new Character(charArr[i]);
			if (previous == null) {
				previous = current;
			} else if (!current.equals(previous)) {
				String subString = findSubStringFromI(charArr, i - 1, size);
				if (subString != null && subString.length() < result.length()) {
					result = subString;
				}
			}
		}
		return result;
	}

	public static String findSubStringFromI(char[] charArr, int k, int setSize) {
		StringBuilder sb = new StringBuilder("");
		Set<Character> set = new HashSet<Character>();
		for (int i = k; i < charArr.length; i++) {
			Character c = new Character(charArr[i]);
			if (set.size() < setSize) {
				set.add(c);
				sb.append(charArr[i]);
			} else {
				break;
			}
		}
		if (set.size() < setSize) {
			return null;
		}
		return sb.toString();
	}
}

class Occupied {
	int from;
	int to;

	Occupied(int from, int to) {
		this.from = from;
		this.to = to;
	}
}

import java.util.*;

public class CoinProblem {
	public static void main(String[] args) {
		List<Coin> coinList = new ArrayList<Coin>();
		coinList.add(Coin.Fifteen);
		coinList.add(Coin.Ten);
		coinList.add(Coin.FiveFive);
		coinList.add(Coin.Ten);
		coinList.add(Coin.FiveFive);
		coinList.add(Coin.Fifteen);
		coinList.add(Coin.Ten);
		coinList.add(Coin.Ten);
		coinList.add(Coin.Fifteen);
		coinList.add(Coin.FiveFive);
		coinList.add(Coin.Ten);
		coinList.add(Coin.Fifteen);
		coinList.add(Coin.Fifteen);
		coinList.add(Coin.FiveFive);
		coinList.add(Coin.Ten);
		printCombs(coinList);
	}
	public static void printCombs(List<Coin> coinList) {
		Map<Coin, Integer> map = new HashMap<Coin, Integer>();
		for(Coin c: coinList){
			Integer in = map.get(c);
			if(in == null){
				map.put(c, new Integer(1));
			} else {
				map.put(c, in + 1);
			}
		}
		Set<Integer> result = new HashSet<Integer>();
		List<Set<Integer>> list = new ArrayList<Set<Integer>>();
		for(Coin c: map.keySet()){
			list.add(findCombs(c, map.get(c)));
		}
		// pick any Integer from each element to join or not join with any Integer from other Elements
		for(int i=0; i< list.size(); i++){
			Set<Integer> values = list.get(i);
			if(result.isEmpty()){
				result.addAll(values);
			} else {
				Set<Integer> tmpRs = new HashSet<Integer>();
				for(Integer value: values){
					for(Integer rsi: result){
						tmpRs.add(rsi + value);
					}
				}
				result.addAll(tmpRs);
			}
		}
		//sort result
		List<Integer> listRs = new ArrayList<Integer>(result);
		sort(listRs);
		for(Integer rsInt: listRs){
			System.out.println(rsInt);
		}
	}
	public static void sort(List<Integer> listRs) {
		//use any sort here, since its a small list for the examples, using insertion sort here:
		for(int i= 1; i< listRs.size(); i++){
			for(int j = 0; j< i; j++){
				if(listRs.get(i) < listRs.get(j)){
					Integer temp = listRs.get(i);
					for(int k = i; k> j; k--){
						listRs.set(k, listRs.get(k-1));
					}
					listRs.set(j, temp);
				}
			}
		}
	}
	public static Set<Integer> findCombs(Coin c, Integer count) {
		Set<Integer> set = new HashSet<Integer>();
		set.add(c.getValue());
		if(count > 1){
			Set<Integer> subSet= findCombs(c, count -1);
			for(Integer i: subSet){
				set.add(c.getValue() + i);
			}
		}
		return set;
	}
}


enum Coin{
	Ten(10),Fifteen(15),FiveFive(55);
	private int value;
	Coin(int value){
		this.value = value;
	}
	public int getValue(){
		return value;
	}
}

import java.util.*;

public class TimeIntervalProblem {
	public static void main(String[] args) {
		List<TimeInterval> ptList = new LinkedList<TimeInterval>();
		ptList.add(new TimeInterval(1, 4));
		ptList.add(new TimeInterval(2, 3));
		System.out.println(findSumIntervals(ptList));
		ptList = new ArrayList<TimeInterval>();
		ptList.add(new TimeInterval(4, 6));
		ptList.add(new TimeInterval(1, 2));
		System.out.println(findSumIntervals(ptList));
		ptList = new ArrayList<TimeInterval>();
		ptList.add(new TimeInterval(1, 4));
		ptList.add(new TimeInterval(6, 8));
		ptList.add(new TimeInterval(2, 4));
		ptList.add(new TimeInterval(7, 9));
		ptList.add(new TimeInterval(10, 15));
		System.out.println(findSumIntervals(ptList));
	}
	public static int findSumIntervals(List<TimeInterval> ptList) {
		// sort ptList by TimeInterval.in
		sort(ptList);
		//merge intervals if they are overlapping
		List<TimeInterval> list = mergeIntervals(ptList);
		return sumIntervals(list);
	}
	public static int sumIntervals(List<TimeInterval> ptList) {
		//use any sort here, since its a small list for the examples, using insertion sort here:
		int sum = 0;
		for(TimeInterval ti: ptList){
			sum += ti.out - ti.in;
		}
		return sum;
	}
	public static void sort(List<TimeInterval> ptList) {
		//use any sort here, since its a small list for the examples, using insertion sort here:
		for(int i= 1; i< ptList.size(); i++){
			for(int j = 0; j< i; j++){
				if(ptList.get(i).in < ptList.get(j).in){
					TimeInterval temp = ptList.get(i);
					for(int k = i; k> j; k--){
						ptList.set(k, ptList.get(k-1));
					}
					ptList.set(j, temp);
				}
			}
		}
	}
	public static List<TimeInterval> mergeIntervals(List<TimeInterval> ptList) {
		List<TimeInterval> list = new LinkedList<TimeInterval>();
		TimeInterval previousInterval = null;
		for(int i=0; i< ptList.size(); i++){
			TimeInterval ti = ptList.get(i);
			if(previousInterval == null){
				previousInterval = ti;
				continue;
			}
			//check overlapping
			if(ti.in <= previousInterval.out && ti.out > previousInterval.out){
				previousInterval.out = ti.out;
			} else if (ti.in > previousInterval.out){
				list.add(previousInterval);
				previousInterval = ti;
			}
			if(i == ptList.size() -1){
				list.add(previousInterval);
			}
		}
		return list;
	}
}
class TimeInterval{
	int in;
	int out;
	TimeInterval(int in, int out){
		this.in = in;
		this.out = out;
	}
}

import java.util.*;

public class SpaceShipProblem {
	public static void main(String[] args) {
		Coordinate source = new Coordinate(0, 0);
		Coordinate dest = new Coordinate(100, 200);
		/*
		WarmHole wh1 = 
		WarmHole wh2 = 
		...
		WarmHole whk = 
		*/
		List<WarmHole> list = new ArrayList<WarmHole>();
		/*
		list.add...
		*/
		WHPath minPath = findMinPath(source, dest, list);
	}

	public static WHPath findMinPath(Coordinate source, Coordinate dest,
			List<WarmHole> list) {
		if (source.x == dest.x && source.y == dest.y) {
			return new WHPath(null, 0);
		}
		WHPath minPath = null;
		Set<WarmHole> markout = new HashSet<WarmHole>();
		for (WarmHole wh : list) {
			if (markout.contains(wh)) {
				continue;
			}
			markout.add(wh);
			Iterator<Coordinate> it = wh.pairs.iterator();
			Coordinate whpointA = null;
			Coordinate whpointB = null;
			if (it.hasNext()) {
				whpointA = it.next();
			}
			if (it.hasNext()) {
				whpointB = it.next();
			}
			//find minPath from left and right point of the warm hole, compare which one is better to use
			WHPath pathA = findMinPath(whpointB, dest, list);
			WHPath pathB = findMinPath(whpointA, dest, list);
			List<WarmHole> path = null;
			int distance = 0;
			if (findDistance(source, whpointB) + pathA.distance < findDistance(
					source, whpointA) + pathB.distance) {
				path = pathB.path;
				distance = findDistance(source, whpointB) + pathA.distance;
			} else {
				path = pathA.path;
				distance = findDistance(source, whpointA) + pathB.distance;
			}
			if (path != null) {
				if (minPath == null) {
					minPath = new WHPath(path, distance);
				} else if (distance < minPath.distance) {
					minPath.distance = distance;
					minPath.path = path;
				}
			}
		}
		return minPath;
	}

	public static int findDistance(Coordinate source, Coordinate dest) {
		return Math.abs(source.x - dest.x) + Math.abs(source.y - dest.y);
	}
}

class WHPath {
	int distance;
	List<WarmHole> path;

	WHPath(List<WarmHole> path, int distance) {
		this.path = path;
		this.distance = distance;
	};
}

class Coordinate {
	int x;
	int y;

	Coordinate(int x, int y) {
		this.x = x;
		this.y = y;
	};
}

class WarmHole {
	Set<Coordinate> pairs = new HashSet<Coordinate>();
	WarmHole(Coordinate a, Coordinate b) {
		pairs.add(a);
		pairs.add(b);
	};
}

1. find all the rectangles overlapping the given area. by matching if any of the four corner points are in the area.

2. After step 1, try to find the minual set none overlapping - call findMinSet(rectList)

static List<Rectangle> findMinSet(List<Rectangle> rectList){
	Set<Rectangle> markedOut = new HashSet<Rectangle>();
	findMinSet(rectList, markedOut);
}
static List<Rectangle> findMinSet(List<Rectangle> rectList, Set<Rectangle> markedOut){
	Set<Rectangle> minSet = new HashSet<Rectangle>();
	for (Rectangle rect: rectList){
		if (markedOut.get(rect) != null) {
			continue;
		}
		markedOut.add(rect);
		List<Rectangle> nonOverlaps = findNonOverlaps(rect, rectList);
		Set<Rectangle> subMinSet = findMinSet(nonOverlaps);
		if(subMinSet.size() +1 < minSet.size()){
			subMinSet.add(rect);
			minSet = subMinSet;
		}
	}
	return minSet;
}
static List<Rectangle> findNonOverlaps(Rectangle rect, List<Rectangle> rectList){
	Set<Rectangle> markedOut = new HashSet<Rectangle>();
	List<Rectangle> nonOverlaps = new ArrayList<Rectangle>();
	for (Rectangle rectangle: rectList){
		if (markedOut.get(rect) != null || overlap(rect, rectangle) {
			continue;
		}
		nonOverlaps.add(rectangle);
	}
	return nonOverlaps;
}
static boolean overlap(Rectangle rect1, Rectangle rect2){
	//todo: compare corners and levels
}

I can't seem to delete or edit last answer. Here's the update

//By popping each one to another stack (counting real size), push each one back
public class SizedStack {
	public static void main(String[] args) {
		Stack test = new Stack(5);
		try {
			test.push(new NodeX("a"));
			test.push(new NodeX("b"));
			test.push(new NodeX("c"));
			test.push(new NodeX("d"));
			test.push(new NodeX("e"));
			test.push(new NodeX("f"));
		} catch (StackFullException e) {
			System.out.println("overflow");
		}
	}
}

class Stack {
	NodeX top;
	int size;

	Stack(int size) {
		this.size = size;
	}

	NodeX pop() {
		NodeX out = top;
		top = top.next;
		out.next = null;
		return out;
	}

	void push(NodeX in) throws StackFullException {
		int realSize = 0;
		NodeX bottom = null;
		while (top != null) {
			realSize++;
			if (bottom == null) {
				bottom = top;
				top = top.next;
				bottom.next = null;
			} else {
				NodeX currentBottom = bottom;
				bottom = top;
				top = top.next;
				bottom.next = currentBottom;
			}
		}
		if (realSize < size) {
			while (bottom != null) {
				NodeX currentTop = top;
				top = bottom;
				bottom = bottom.next;
				top.next = currentTop;
			}
			System.out.println(top);
			in.next = top;
			top = in;
		} else {
			throw new StackFullException();
		}
	}
}

class NodeX {
	String name;
	NodeX next;

	NodeX(String name) {
		this.name = name;
	}

	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		sb.append(this.name);
		if (this.next != null) {
			sb.append(this.next.toString());
		}
		return sb.toString();
	}
}

class StackFullException extends Exception {
	StackFullException() {
		super();
	}

	StackFullException(String message) {
		super(message);
	}

	StackFullException(String message, Throwable cause) {
		super(message, cause);
	}

	StackFullException(Throwable cause) {
		super(cause);
	}
}

//By pop each one to another stack (counting) and push each one backpublic class SizedStack {
	public static void main(String[] args) {
		Stack test = new Stack(5);
		try {
			test.push(new NodeX("a"));
			test.push(new NodeX("b"));
			test.push(new NodeX("c"));
			test.push(new NodeX("d"));
			test.push(new NodeX("e"));
			test.push(new NodeX("f"));
		} catch (StackFullException e) {
			System.out.println("overflow");
		}
	}
}

class Stack {
	NodeX top;
	int size;

	Stack(int size) {
		this.size = size;
	}

	NodeX pop() {
		NodeX out = top;
		top = top.next;
		out.next = null;
		return out;
	}

	void push(NodeX in) throws StackFullException {
		int realSize = 0;
		NodeX bottom = null;
		while (top != null) {
			realSize++;
			if (bottom == null) {
				bottom = top;
				top = top.next;
				bottom.next = null;
			} else {
				NodeX currentBottom = bottom;
				bottom = top;
				top = top.next;
				bottom.next = currentBottom;
			}
		}
		if (realSize < size) {
			while (bottom != null) {
				NodeX currentTop = top;
				top = bottom;
				bottom = bottom.next;
				top.next = currentTop;
			}
			System.out.println(top);
			in.next = top;
			top = in;
		} else {
			throw new StackFullException();
		}
	}
}

class NodeX {
	String name;
	NodeX next;

	NodeX(String name) {
		this.name = name;
	}

	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		sb.append(this.name);
		if (this.next != null) {
			sb.append(this.next.toString());
		}
		return sb.toString();
	}
}

class StackFullException extends Exception {
	StackFullException() {
		super();
	}

	StackFullException(String message) {
		super(message);
	}

	StackFullException(String message, Throwable cause) {
		super(message, cause);
	}

	StackFullException(Throwable cause) {
		super(cause);
	}
}

public class SizedStack {
public static void main(String[] args) {
Stack test = new Stack(5);
try {
test.push(new NodeX("a"));
test.push(new NodeX("b"));
test.push(new NodeX("c"));
test.push(new NodeX("d"));
test.push(new NodeX("e"));
test.push(new NodeX("f"));
} catch (StackFullException e) {
System.out.println("overflow");
}
}
}

class Stack {
NodeX top;
int size;

Stack(int size) {
this.size = size;
}

NodeX pop() {
NodeX out = top;
top = top.next;
out.next = null;
return out;
}

void push(NodeX in) throws StackFullException {
int realSize = 0;
NodeX bottom = null;
while (top != null) {
realSize++;
if (bottom == null) {
bottom = top;
top = top.next;
bottom.next = null;
} else {
NodeX currentBottom = bottom;
bottom = top;
top = top.next;
bottom.next = currentBottom;
}
}
if (realSize < size) {
while (bottom != null) {
NodeX currentTop = top;
top = bottom;
bottom = bottom.next;
top.next = currentTop;
}
System.out.println(top);
in.next = top;
top = in;
} else {
throw new StackFullException();
}
}
}

class NodeX {
String name;
NodeX next;

NodeX(String name) {
this.name = name;
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append(this.name);
if (this.next != null) {
sb.append(this.next.toString());
}
return sb.toString();
}
}

class StackFullException extends Exception {
StackFullException() {
super();
}

StackFullException(String message) {
super(message);
}

StackFullException(String message, Throwable cause) {
super(message, cause);
}

StackFullException(Throwable cause) {
super(cause);
}
}

import java.util.*;

/*
 * The core concept is to record and break the circle for each one you found.
 */
public class LgstCircleProblem {
	public static void main(String[] args) {
		Node a = new Node(1, "a");
		Node b = new Node(2, "b");
		Node c = new Node(3, "c");
		Node d = new Node(4, "d");
		Node e = new Node(5, "e");
		Node f = new Node(6, "f");
		Node g = new Node(7, "g");
		Node h = new Node(8, "h");
		Node i = new Node(9, "i");
		List<Node> aList = new ArrayList<Node>();
		aList.add(b);
		aList.add(c);
		aList.add(d);
		a.connected = aList;
		List<Node> bList = new ArrayList<Node>();
		bList.add(e);
		bList.add(a);
		b.connected = bList;
		List<Node> cList = new ArrayList<Node>();
		cList.add(a);
		cList.add(f);
		c.connected = cList;
		List<Node> dList = new ArrayList<Node>();
		dList.add(a);
		dList.add(e);
		dList.add(i);
		d.connected = dList;
		List<Node> eList = new ArrayList<Node>();
		eList.add(b);
		eList.add(d);
		eList.add(f);
		e.connected = eList;
		List<Node> fList = new ArrayList<Node>();
		fList.add(c);
		fList.add(e);
		fList.add(g);
		f.connected = fList;
		List<Node> gList = new ArrayList<Node>();
		gList.add(f);
		gList.add(h);
		g.connected = gList;
		List<Node> hList = new ArrayList<Node>();
		hList.add(g);
		hList.add(i);
		h.connected = hList;
		List<Node> iList = new ArrayList<Node>();
		iList.add(h);
		iList.add(d);
		i.connected = iList;
		List<Node> graph = new ArrayList<Node>();
		graph.add(a);
		graph.add(b);
		graph.add(c);
		graph.add(d);
		graph.add(e);
		graph.add(f);
		graph.add(h);
		graph.add(i);
		findlgstCircle(graph);
	}

	public static void findlgstCircle(List<Node> graph) {
		// for each node in graph, find the longest path with that node and the
		// remaining node.
		Set<Integer> markOut = new HashSet<Integer>();
		Circle circle = null;
		for (Node n : graph) {
			Circle newCircle = findlgstCircleWithN(n, n.connected, markOut);
			if(newCircle!=null ){
				newCircle.nodes.add(n);
				if (circle == null || newCircle.getLength() > circle.getLength()) {
					circle = newCircle;
				}
			}
			markOut.add(n.index);
		}
		System.out.println("length: " + circle == null ? 0 : circle.getLength());
		System.out.println(circle);
	}

	public static Circle findlgstCircleWithN(Node n, List<Node> connected,
			Set<Integer> markOut) {
		// for each neighbor not marked out, find the circle with
		Circle circle = null;
		if (n.connected != null) {
			for (Node x : n.connected) {
				// break a & x, then find a max way to get back to a from x
				removeLink(n, x);
				Set<Integer> markOut4X = new HashSet<Integer>();
				Circle circleX = findMaxCircleXToN(x, n, markOut4X);
				if (circleX != null) {
					if (circle == null
							|| circleX.getLength() > circle.getLength()) {
						circle = circleX;
					}
				}
			}
		}
		return circle;
	}

	public static Circle findMaxCircleXToN(Node x, Node n,
			Set<Integer> markOut4X) {
		Circle circleX = null;
		List<Node> connected = x.connected;
		markOut4X.add(x.index);
		if (connected != null && !connected.isEmpty()) {
			for (Node y : connected) {
				if (!markOut4X.contains(y.index) && !(x.breakLinks!= null && x.breakLinks.contains(y.index))) {
					Circle circle = null;
					if (y.index == n.index) {
						// break the end of the circle so it's not visited again.
						removeLink(x, n);
						circle = new Circle();
						circle.nodes = new ArrayList<Node>();
						circle.nodes.add(n);
						circle.nodes.add(x);
						if (circle != null) {
							if (circleX == null || circleX.getLength() < circle.getLength()) {
								circleX = circle;
							}
						}
					}else {
						markOut4X.add(y.index);
						circle = findMaxCircleXToN(y, n, markOut4X);
						if (circle != null) {
							circle.nodes.add(x);
						}
					}
					if (circle != null) {
						if (circleX == null || circleX.getLength() < circle.getLength()) {
							circleX = circle;
						}
	
					}
				}
			}
		}
		return circleX;
	}

	public static void removeLink(Node n, Node x) {
		Set<Integer> breakLinks = n.breakLinks;
		if(breakLinks == null){
			breakLinks = new HashSet<Integer>();
		}
		breakLinks.add(x.index);
		n.breakLinks = breakLinks;
		breakLinks = x.breakLinks;
		if(breakLinks == null){
			breakLinks = new HashSet<Integer>();
		}
		breakLinks.add(n.index);
		x.breakLinks = breakLinks;
	}

}

class Circle {
	List<Node> nodes;
	Circle() {
	}

	int getLength() {
		return nodes.size() > 0 ? nodes.size() : 0;
	}
	@Override
	public String toString(){
		StringBuilder sb = new StringBuilder();
		if(nodes!=null && !nodes.isEmpty()) {
			sb.append(nodes.get(0).name);
			for(int i=1; i< nodes.size(); i++){
				sb.append("->" + nodes.get(i).name);
			}
		}
		return sb.toString();
	}
}

class Node {
	List<Node> connected;
	Set<Integer> breakLinks;
	String name;
	int index;

	Node(int index, String name) {
		this.index = index;
		this.name = name;
	}
}

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); 
	}
}