PeRsecución en los sótAnos de Palacio Según las novelas y las películas situadas en la Francia del siglo XVII (véanse Los Tres Mosqueteros o La Máscara de Hierro), los sótanos del palacio de Versalles constituían una compleja red de túneles y salas en las que a menudo tenían lugar espectaculares luchas y persecuciones. Los protagonistas solían ser los dos cuerpos de espadachines más famosos de la época, enemigos entre sí: los mosqueteros del Rey y la guardia del Cardenal. Aparentemente, los mosqueteros siempre defendían la causa más justa y eran más diestros con la espada, por lo que ganaban casi siempre, pero no dejaremos que ello nos influya demasiado. La mecánica de estas persecuciones se podría simular de la siguiente manera: en el sótano hay salas y túneles. Hay un subconjunto especial de salas, que llamaremos "salas iniciales", cuyo número es mayor o igual que 1 y menor o igual que una cierta constante N. De cada sala inicial se sale a un túnel. De tanto en tanto, dos túneles se juntan y dan lugar a una nueva sala. De estas nuevas salas, también sale un túnel y así sucesivamente. Todas las salas, salvo las iniciales, proceden de la unión de dos túneles. Al final se llega a una única sala, que da paso a la salida del sótano. Cada túnel tiene una longitud. Para simplificar, supondremos que si dos túneles se juntan en una sala tienen la misma longitud y que en el trayecto de una sala inicial a la salida no se pueden repetir salas. En cada sala inicial hay A LO SUMO un soldado (mosquetero o guardia). El conjunto de todos los soldados (mosqueteros y guardias) de los sótanos del palacio es lo que llamaremos "guarnición". Cada soldado tiene asociado un valor numérico que representa su "calidad". Básicamente, consiste en una medida conjunta de sus cualidades: fuerza, inteligencia, destreza, etc. Durante la persecución, el objetivo de un soldado es salir del sótano, partiendo de la sala inicial a la que está asignado, y que no salgan los rivales que se vaya encontrando por el camino. Se supone que todos comienzan la persecución al mismo tiempo, así que es posible que en una sala no inicial, incluída la última, coincidan grupos de soldados de bandos contrarios, en cuyo caso se produce una lucha, que reglamentamos a continuación. Dada una sala, llamamos "oleada" al conjunto formado por todos los soldados que hayan recorrido la misma distancia al llegar a ella. En una misma sala podrá haber tantas luchas como oleadas de soldados vayan llegando a ella. La lucha se produce si en la misma oleada llega a la sala un grupo de soldados de distinto bando por cada túnel. En las siguientes oleadas habrá nuevos combates en dicha sala si se repiten las mismas condiciones y así sucesivamente. Notad que estamos suponiendo que todos los soldados avanzan a la misma velocidad. También suponemos que los combates no se solapan, es decir, un combate dura menos tiempo que el necesario para que llegue otra oleada de soldados. En caso de lucha, vence el grupo que tenga mayor suma de calidades. En caso de empate de calidades, ganan los mosqueteros. Sólo siguen adelante los soldados (todos) del grupo vencedor. Obviamente, si todos los soldados que llegan a la sala en la misma oleada son del mismo bando no hay combate. Si llegan por los dos túneles, se unen y continúan todos. Si sólo llegan por uno de los túneles, avanzan directamente. Con este modelo, salen tantos grupos de soldados como oleadas se hayan producido en la salida. Cada grupo está compuesto sólo por guardias o por mosqueteros. Ejemplo. Tomemos la siguiente la situación inicial, donde las salas iniciales está numeradas del 1 al 5 y las demás contienen la longitud de los pasillos que llegan a ella. 1 4 \ / 1 3 2 5 \ / \ / 1 1 \ / 1 (salida) Supongamos que hay mosqueteros en las salas 1 y 3, guardias en la 2 y la 5 y, por último, en la 4 no hay nadie. Consideremos que todos tienen calidad 1. Como puede comprobarse, hay dos oleadas en la salida. Los soldados de la primera, el mosquetero de la 3 y los dos guardias (2 y 5) avanzan dos tramos sin luchar hasta que se encuentran y luchan entre sí. Ganan los guardias y eso les permite salir inmediatamente. El mosquetero de la 1 pertenece a la segunda oleada, va avanzando sin encontrarse con nadie, y sale sólo. En resumen, primero salen 2 guardias y luego un mosquetero. SE PIDE: Diseñar un programa modular razonablemente eficiente que simule la situación arriba descrita. En primer lugar, debe leer la estructura del sótano y una guarnición de soldados para las salas iniciales. Después tendrá que ir procesando las diversas tareas que se le pidan. Estas podrán ser las siguientes: * Simular una persecución como la arriba descrita. Informar del número de soldados de cada bando que logran salir del sótano, ordenados según las diversas oleadas, comenzando por la más cercana a la salida y acabando por la más lejana. En el ejemplo anterior la solución sería: primera oleada 2 guardias, segunda oleada 1 mosquetero. * Modificar la guarnición de las salas iniciales mediante la siguiente estrategia. Primero se leen dos guarniciones nuevas. Se puede suponer que serán válidas para el sótano, es decir, que todos sus soldados están entre la sala 1 y la sala N, no hay repeticiones, etc. Se dice que son compatibles entre sí si tienen el mismo número de soldados en total (mosqueteros más guardias) y estos están en las mismas salas iniciales (recordad que puede haber salas iniciales sin soldados). A continuación se comprueba si ambas guarniciones son compatibles entre sí. En caso afirmativo, a partir de ellas se obtiene otra, que contenga al soldado de mayor calidad de cada sala, independientemente de que sea guardia o mosquetero. Si dos soldados de distinto tipo empatan a calidad, gana el mosquetero, como siempre. Por último, la guarnición que acabamos de obtener sustituye a la original. En caso de que las dos guarniciones leídas no sean compatibles entre sí, la guarnición original no cambia. * Leer una nueva estructura de salas y pasillos del sótano que sustituya a la antigua. La forma de comunicarse con el programa para que realice dichas tareas será parecida a la de los casos de estudio de teoría: "Cubeta", "PseudoTetris", etc. Podéis diseñar un esquema provisional que ya refinaréis cuando conozcáis el juego de pruebas público. La sintaxis *exacta* de los datos y resultados, acompañada del juego de pruebas público, se conocerá dos semanas antes del día de la entrega del programa Java. Hasta entonces no podréis implementar de forma definitiva las operaciones de lectura y escritura necesarias para los tipos que utilicéis, aunque sí podréis especificarlas. Podéis consultar el ejemplo del cuatrimestre anterior para tener una idea aproximada.