Programa avión vs misiles

[Kritik]

Yo entiendo el problema de la siguiente manera:

Si el misil decide no alcanzar el 1º misil, sino empezar por el 3º misil que es el que más alto va, al haber pasado del 1º y del 2º ya no podrá alcanzarlos. Solo podrá ir eligiendo de los siguientes.

Así pues no es solo elegir la altura, sino también el no pasar de demasiados misiles, porque de todos aquellos de los que se pase ya no se podrán alcanzar después.

Ejemplo de combinaciones para el out.txt:

389 - 207 - 170- 158 - 65. -->5

En este caso, después de escoger el 389 para derrumbar a ese primero, sería imposible derrumbar al que va a 50 unidades de altura (el primero de la lista), porque aunque esté más abajo, ya habría quedado atrás. Y nuestro misil solo puede caer o adelantarse.

Se me ocurre una manera de llegar a la solución más idónea. Y es por medio de permutaciones. No recuerdo muy bien como funcionaban, pero se de claro que necesitas calcular permutaciones.

Ahora bien, también puedes usar un algoritmo de fuerza bruta, que es el que paso a describir:

Coge el 1º número y compáralo con el siguiente. Si es menor es válido en la sucesión de una cadena. Si no, no.

Así pues, empezando por el 1º número dado, el 50 empezamos una cadena de explosiones. Y resulta que ningún otro proyectil va más bajo. Así pues, empezando por el 50 acaba ahí.

Ahora empiezas por el 2º proyectil: 100. Y haces una nueva cadena de explosiones. El primer misil que aparezca más bajo que ese, será el escogido. Y asi llegamos al 65.

Tenemos otra cadena que es 100 - 65. Comprobamos si, escogiendo el 1º habría más opciones. Y vemos que no. Empezando con 100 solo hay esa cadena de 100 - 65 --> 2 proyectiles.

Ahora empezamos por el 3º proyectil (ahora llega lo chungo)

El siguiente número es el 207. como es menor es escogido como válido. Y hacemos una rama

389 - 207 - 155 - 130 - 65 -->5

Pero... empezando por el 389 habría más opciones de llegar a otras cadenas distintas? Como puedo saber todas las cadenas que empiezan por 389 y que cumplan las reglas del juego?

Empieza por la cadena dada. E intenta cambiar el último número, a ver si puede haber otro, por debajo de 130 y que no sea 65...

No hay, así la siguiente permutación es:

389 - 207 - 155 - 130 -->4

Ahora cambia el anterior (el 130). A ver si hay algún otro número por debajo de 155 y que no sea el 130, y a ver qué pasa si lo escoges:

389 - 207 - 155 - (y llegas al 65 después de saltarte el 130) - 65 ---> 4

Y como no hay más alternativas que el 65 terminas, y vas al número anterior... el 155, a ver si escogiendo algún otro número que no sea el 155 a ver cuantas ramas me salen:

tenemos:

389 - 207 - (Y el siguiente más bajo de 207 es: 130) 130 - 65 --->4

Pero aquí, con el 389 - 207 tenemos otra opción para el 3º número, a ver qué pasa si la cogemos:

389 - 207 - 170 - 158 - 65 -- > 5

------------------------

Resumen: Tienes que ir construyendo ramas de combinaciones, y luego mirar el tamaño de cuantas ramificaciones han tenido. Si es mayor, que la mayor, perdurará y será escogida como la combinación ganadora, y si no, pasarás a la siguiente.

Se me ocurre que en java esto se puede hacer en un bucle mientras haya combinaciones no estudiadas, continuar haciendo combinaciones. Y cada combinación que sea un ArrayList, que se declara dentro del while y por lo tanto existe únicamente en cada una de las iteraciones, y que se borra cuando empieza de nuevo la iteración del while. Y otro ArrayList de la combinación ganadora que se declara fuera del while, de forma que perdura durante los recorridos del While. Si el tamaño del ArrayList que guarda las combinaciones dentro del while es mayor que el que se declara fuera que guarda las ganadoras... asignas los valores del de dentro al de fuera, para que se guarden para siempre. Si el tamaño es igual o menor, no asigna y termina el bucle y empieza con el siguiente ramaje. A ver cuan de largo es el siguiente.

Cuando termines, tendrás en el arrayList que declaraste fuera del bucle la combinación que más misiles has derrumbado.

Así pues... necesitas:
- Un array del tamaño del 1º número dado, y que en cada posición almacene las alturas de los misiles en el mismo orden que el dado.
- Un ArrayList con la combinación con más misiles derrumbados, declarada fuera del bucle que estudia las combinaciones.
- Un bucle que estudie las combinaciones mientras haya combinaciones (while) de la manera que he explicado antes.
- Un ArrayList que se declara dentro del bucle (y que por tanto únicamente existe dentro de él, pues en cada pasada es reiniciado al ser declarado como nuevo) y que guarda cada combinación.
- Una condición que compara los 2 ArrayList y que asigna al de fuera del bucle los valores del de dentro SI y solo si el de dentro tiene mayor tamaño.

Ahora bien... con esta idea, sabrías abstraerla para diseñar ese bucle de cálculo de combinaciones?

PD: Me encantan este tipo de ejercicios para practicar la programación.