Rabbit.java

// 2015 Sitting 1 - Rabbit.java

public class Rabbit {

	private Integer[][] r; // Array of past sequences
	private int n; // Number of sequences in r
	
	public Rabbit(int n) {
		this.n = n;
		r = new Integer[n][];
	}
	
	public void init() {
		if(n < 2) return;
		// Fill in the first two sequences
		r[0] = new Integer[]{1};
		r[1] = new Integer[]{1, 0};
		// Fill in the rest
		for(int i = 2; i < n; i++) {
			r[i] = new Integer[r[i-1].length + r[i-2].length];
			// Copy in the previous sequence
			for(int k = 0; k < r[i-1].length; k++) {
				r[i][k] = r[i-1][k];
			}
			// Copy in the one before that
			for(int k = 0; k < r[i-2].length; k++) {
				r[i][k + r[i-1].length] = r[i-2][k];
			}
		}
	}
	
	public String toString() {
		String str = "";
		for(Integer[] seq : r) {
			for(int i = 0; i < seq.length; i++) {
				// Beginning
				if(i == 0) str += "[" + seq[i];
				// Middle
				else str += ", " + seq[i];
				// End
				if(i == seq.length-1) str += "]\n";
			}
		}
		return str;
	}
	
	public int subsequenceIndex(Integer[] subseq) {
		Integer[] longest = r[r.length-1];
		int index = -1;
		for(int i = 0; i < longest.length - subseq.length + 1; i++) {
			boolean success = true;
			for(int k = 0; k < subseq.length; k++) {
				if(!longest[i+k].equals(subseq[k])) {
					success = false;
				}
			}
			if(success) {
				index = i;
				break;
			}
		}
		return index;
	}
	
	public static void main(String[] args) {
		int n = Integer.parseInt(args[0]);
		if(n < 2) return;
		Rabbit rabbit = new Rabbit(n);
		rabbit.init();
		System.out.print(rabbit);
		System.out.println(rabbit.subsequenceIndex(new Integer[]{1, 1, 0}));
		System.out.println(rabbit.subsequenceIndex(new Integer[]{1, 1, 1}));
	}
	
}