Las matrioshkas

Matrioshkas.java

package com.makzk.prueba.acm;

/**
 * This product contains software technology licensed from OGL. OGL (c) 1994 All
 * Rights Reserved.
 * 
 * @author Jonathan Gutiérrez
 */

public class Matryoshkas {

	public static void main(String[] args) {
		System.out.println(Matryoshkas.solve(5, "1 2 1 2 4 3 3"));
		System.out.println(Matryoshkas.solve(7, "1 2 3 2 4 1 3"));
	}

	public static String solve(int n, String line) {
		int[] num;
		do {
			line = line.replaceAll("  ", " ");
		} while (line.indexOf("  ") != -1);

		if (!line.replaceAll(" ", "").matches("[0-9]*")) {
			return "impossible";
		}

		num = new int[line.split(" ").length];

		for (int i = 0; i < num.length; i++) {
			num[i] = Integer.parseInt(line.split(" ")[i]);
		}

		return esPosibleUImposible(num);
	}

	public static int lugardivision(int[] dolls, int div) {
		int prevDiv = div;
		div = dolls.length;
		for (int i = prevDiv; i < dolls.length; i++) {
			for (int j = i; j < dolls.length; j++) {
				if (i != j && dolls[j] == dolls[i] && j < div && j > prevDiv) {
					div = j;
				}
			}
		}

		return div;

	}

	public static String esPosibleUImposible(int[] sizes) {
		int div = 0;
		int aperturas = 0;
		boolean ok = true;

		do {

			int[] grupo = new int[sizes.length];
			int adiv = lugardivision(sizes, div);

			for (int i = div; i < adiv; i++) {
				grupo[i] = sizes[i];
				if (adiv == sizes.length) {
					grupo[sizes.length - 1] = sizes[sizes.length - 1];
				}
			}
			
			int min = 0;
			int max = 0;

			for (int i = 0; i < grupo.length; i++) {
				if (i == 0 || grupo[i] > max) {
					max = grupo[i];
				}
				if (i == 0 || grupo[i] < min) {
					min = grupo[i];
				}
			}
			
			if (min == max) {
				return "imposible";
			}


			aperturas += aperturas(grupo, 1, 0, 0, min);

			div = lugardivision(sizes, div);
			if (div == grupo.length) {
				ok = false;
			}
		} while (ok);

		return aperturas + "";
	}

	public static int aperturas(int arr[], int j, int i, int aperturas,
			double menor) {
		do {
			while (j < arr.length) {
				aperturas++;
				if (arr[j] < menor) {
					menor = arr[j];
					arr[i] = arr[j];
				} else {
					menor = arr[i];
					i++;
					j++;
					aperturas(arr, j, i, aperturas, menor);
				}
			}
		} while (i < arr.length - 1);

		return aperturas;

	}
}