ClimbSort

ClimbSort.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class ClimbSort {
	public static void main(String[] args) throws IOException{
		BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
		ArrayList<String> output = new ArrayList<String>();

		int numberOfTestCases = Integer.parseInt(input.readLine());
		for (int i = 0; i < numberOfTestCases; i++) {
			// create arrays for the ordered and unordered lists of turtles
			int stackSize = Integer.parseInt(input.readLine());
			String[] unsortedTurtles = new String[stackSize];
			for (int j = 0; j < stackSize; j++) {
				unsortedTurtles[j] = input.readLine();
			}
			String[] sortedTurtles = new String[stackSize];
			for (int k = 0; k < stackSize; k++) {
				sortedTurtles[k] = input.readLine();
			}

			// find the first (from the bottom) turtle which is in the wrong place
			int index = -1;
			for (int m = stackSize-1; m >= 0; m--) {
				//Find the first occuring missmatch from the bottom up and keep that index.
				if (!sortedTurtles[m].equals(unsortedTurtles[m])){
					index = m;
					break;
				}
			}
			// output all turtles above m
			for (int n = index -1; n >= 0; n--) {
				output.add(sortedTurtles[n]);
			}
			// each test case must be terminated by a blank line
			output.add("");
		}
		input.close();
		// print the output
		for (String str : output) {
			System.out.println(str);
		}
	}
}