Programa avión vs misiles

[Deividsillo]

Pues verán. Hace poco me planteó un problema un amigo. Soy un novato en el manejo de java pero me ha interesado bastante. He estado empezando a pensar como hacer este problema pero no he tenido muchas ideas.

El programa que me describió es el siguiente.

Yo tengo un avión, el cual debe de destruir la mayor cantidad posibles de misiles que se dirigen hacia mi. Dicho avión solo puede descender pero no puede subir. Es decir, si me lanzan 10 misiles (de la posición 1 a la 10) y el primer misil es lanzado desde la posición 9, al decidir destruirlo, ya no podré mandar mi avión a destruir al misil en la posición 10. Así como si el primer misil que me mandan lo hacen desde la posición 1, ya no podré destruir los otros 9 por que están arriba de la posición 1.

La idea es que con mi avión pueda destruir la mayor cantidad de misiles determinando con cuál de ellos debo empezar. Lo ideal sería que fuera con el 10, pero si me lanzan ese misil al final solo podría destruir uno (ese mismo de la posición 10). La cantidad de misiles se debe de dar por teclado y las alturas de la posición de cada uno serían aleatorias en cada compilación.

Le agradecería mucho su ayuda con este problema que por el nivel que tengo hasta el momento no le he encontrado alguna solución.

¡Gracias de antemano! ¡Bendiciones y saludos!...

[Kritik]

Olvídate de la posición de cada misil... y espérate el máximo de tiempo hasta que haya el máximo de misiles en el aire sin que ninguno vaya a llegar al avión.

Una vez que decidas que es justo el momento en el que el máximo de misiles sin que ninguno llegue al avión estén en el aire... empieza por el de más arriba y vas bajando.

Si el avión tiene un tiempo para bajar entre nivel y nivel, tendrás que tener ese tiempo en cuenta para apurar lo máximo.

Si este comentario no te sirve tendrás que detallar mucho mejor el problema propuesto. Como a cuanta distancia puede destriur el avión los misiles. Como funciona exactamente el avión con respecto a los misiles, y como funcionan exactamente los misiles con respecto al avión.

[Deividsillo]

Buen día Kiritik:

Tienes razón, me ha faltado bastante información, pero ya tengo a la mano el problema descrito específicamente. Sería básicamente lo siguiente:

El Pentágono ha desarrollado un nuevo y poderoso misil. Este puede moverse hacia delante y hacia abajo para interceptar proyectiles en vuelo sin sufrir daño alguno y continuar su vuelo. Sin embargo tiene un gran defecto a pesar de poder alcanzar, al inicio de su vuelo, cualquier altitud posteriormente no tendrá la capacidad de interceptar proyectiles por encima de la altitud del último proyectil interceptado.

Con la finalidad de evaluar este misil, se tiene una lista de las altitudes que podrían alcanzar los proyectiles enemigos en el orden en que serian lanzados. El objetivo es obtener la máxima cantidad de proyectiles interceptados por el misil a prueba.

Entrada: Archivo de texto in.txt que contiene en su primer renglón un entero positivo menor o igual a 10,000 el cual indica el total de proyectiles enemigos. Las siguientes líneas representan las altitudes (enteros positivos menores a 32767) a las cuales los proyectiles podrían ser interceptados y el orden en que serian enviados.

Salida. Archivo de texto out.txt que contiene un valor entero que representa el máximo numero de proyectiles que podrían ser interceptados por este nuevo misil.

Pruebe su programa con la entrada y salida siguientes:

in.txt
11
50
100
389
207
155
300
299
130
170
158
65

out.txt
5

Es decir, en este caso, la primera línea en el in.txt (11) son la cantidad de misiles lanzados. Los siguientes elementos de la lista son las altitudes de los misiles. En el out.txt sería la cantidad máxima de misiles que se podrían destruir (5)...

[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.