TurtleStrawBerry.java

gistfile1.txt

import java.util.ArrayList;
import java.util.List;

/**
 * 
 * @author azeem
 *
 */

public class TurtleStrawBerry {
	
	private static boolean winningTicket(String ticket) {
		// Positions are 1 based in tickets
		int countOdd = 0;
		int countEven = 0;
		for(int i = 0; i < ticket.length(); i++) {
			if(ticket.charAt(i) == 't' && i % 2 == 0) {
				countOdd++;
			}
			if(ticket.charAt(i) == 't' && i % 2 > 0) {
				countEven++;
			}
		}
		if(countOdd == 2* countEven) {
			return true;
		}
		else {
			return false;
		}
	}
	
	public static int turtleStrawBerry(int n) {
		if(n % 2 > 0) return -1;
		List<String> result = new ArrayList<String>();
		String curr = "";
		getAllStrings(curr, n, result);
		return result.size();
	}

	private static void getAllStrings(String curr, int n, List<String> res) {
		if(n == 0) {
			if(winningTicket(curr)) {
				res.add(curr);
			}
			return;
		}
		// Try all placements
		getAllStrings("s"+curr+"s", n - 2, res);
		getAllStrings("t"+curr+"t", n - 2, res);
		getAllStrings("s"+curr+"t", n - 2, res);
		getAllStrings("t"+curr+"s", n - 2, res);
	}
	
	public static void main(String [] args) {
		System.out.println(turtleStrawBerry(4));
	}

}