Un problema de programación sobre una serie de culto... ¿Una ventaja para sus seguidores?
Resumiendo el enunciado del ejercicio propuesto nos van a pasar una serie de elementos desordenados junto con unas relaciones del tipo este elemento va antes o después de este otro y se trata de desvelar el orden correcto de los elementos, si es que es posible cumplir todas las relaciones. Si la solución, además de posible, es única entonces tenemos que dar el orden de los elementos.
Cada caso a estudiar va a venir en una línea de nombres de escenas (que pueden incluir espacios) y que comienza con un punto (.) si la escena está en el orden cronológico, podemos decir que transcurre en el presente, con un signo menor que (<) si es un flashback (pasado) de la última escena en el orden cronológico, o un signo mayor que (>) si es un flashforward (futuro).
Como siempre lo primero que hay que pensar es cómo modelar los datos del problema. En este caso es sencillo: tenemos que manejar nombres de secuencias así que los almacenaremos en variables string.
En los datos vamos a recibir dos tipos de datos: las escenas en orden cronológico (.) y las escenas relacionadas temporalmente con la última escena cronológica recibida. Así que usaremos dos almacenes: uno en que almacenamos las escenas cronológicas y otro en que guardamos las escenas desordenadas y la(s) escena(s) del almacén de las ordenadas con las que se relacionan. Obviamente de una escena sólo tenemos que guardar una escena para la relación antes de y otra para después de porque si de una escena sabemos que va antes de otras dos sólo necesitamos guardar que la escena es anterior a la primera de las dos (cronológicamente) ya que si es anterior a la primera será anterior a todas las posteriores. Lo mismo ocurre con la relación inversa.
Como manejar las secuencias como datos de tipo string es tedioso vamos a asignar a cada secuencia (del orden cronológico) un número entero. La forma más simple es usar el almacén vector que, al ser un array cuyo tamaño puede variar, ya tiene un número entero asignado a cada elemento implícitamente: su posición. En este caso es ideal porque las secuencias cronológicas nos vienen ya ordenadas por lo que sólo añadimos datos al vector al final del mismo para lo que esta estructura de datos funciona de forma óptima.
El segundo almacén guardará las escenas desordenadas. Aunque no necesitemos numerar estas escenas usaremos también un vector para que el programa gane coherencia. La diferencia radica en que no sólo necesitamos guardar el nombre sino las hasta dos posibles escenas cronológicas con las que puede estar relacionadas. Vamos a tener que definir una estructura para estas escenas así:
struct _scenes
{
string scene;
int before,after;
};
typedef struct _scenes scenesPending;
En los enteros before y after guardamos el número de posición en el vector de escenas ordenadas o un valor negativo si no hay limitación.
El programa necesitará tres fases:
- lectura de la entrada con todas las escenas
- extracción de las escenas individuales y almacenamiento en el vector que le corresponda
- insertar las escenas no ordenadas entre las cronológicas para que se cumplan las relaciones y salida de resultados
Lectura entrada
Como no tenemos un método getline en cin que nos haga el trabajo de leer toda una línea del canal de entrada a un string (la que existe usa array de char) vamos a usar un bucle en el que iremos leyendo los trozos de línea en un string auxiliar (scene) que se irá añadiendo al string resultante (script) hasta que el carácter en el que se quede la lectura sea el final de línea:
script.clear(); // lectura script
while (true)
{
cin >> scene;
script+=scene;
if (cin.peek()=='\n')
break;
else
script+=" ";
}
if (script[0]!='.') // debe comenzar por punto
script="."+script;
Procesar secuencias
Usamos un bucle (¿qué si no?). Como en el momento que encontremos una secuencia que no pueda casar con las condiciones temporales no necesitamos procesar nada más definimos una variable boolean que forme parte de la condición de continuación del bucle:
bool valid=true;
while (valid && (script.size()>0)) // bucle script
{
El primer paso es extraer el nombre de la secuencia del script. Comenzamos en el carácter con índice 1, porque el 0 es el carácter que indica el tipo de secuencia, y avanzamos hasta el final del string script o hasta que encontremos un carácter separador de secuencias. Extraemos los datos y los eliminamos del script:
int i=1; // extraer escena
while ((i<script.size()) && (script[i]!='.') && (script[i]!='<') && (script[i]!='>'))
i++;
scene=script.substr(1, i-1);
char tipo=script[0];
script.erase(0, i);
Ahora que tenemos el nombre de la escena buscamos a ver si ya ha aparecido en el guión en su orden natural. Si ya ha sucedido en el pasado la única opción válida para esta escena es que sea un flashback (tipo <):
bool found=false;
for (vector<string>::iterator it=timeline.begin(); it!=timeline.end(); ++it)
{
if (scene.compare(*it)==0) // escena en time-line
{
found=true;
if ((tipo=='.') || (tipo=='>'))
valid=false;
break;
}
}
Si no ha aparecido con anterioridad en su orden natural ha podido hacerlo fuera del orden temporal. Las cosas que hay que hacer con una secuencia que ya ha aparecido dependen del tipo de secuencia que manejemos, así que primero suponemos que sea una escena del tipo (.).
Si ha aparecido la única opción válida es que haya sido como un flashforward, así que si tenemos guardada cualquier secuencia en la condición antes de el orden es imposible. Como ahora ya nos aparece en el orden correcto podemos quitar la escena de la lista de escenas pendientes de incluir en el orden temporal. Si la secuencia es válida la añadimos al vector timeline.
if (!found) // escena nueva
{
if (tipo=='.')
{
for (vector<scenesPending>::iterator it=pending.begin(); it!=pending.end(); ++it)
{
if (it->scene.compare(scene)==0)
{
if (it->before>=0)
valid=false;
pending.erase(it);
}
}
if (valid)
timeline.push_back(scene);
}
Si no es una secuencia en el orden temporal buscamos igualmente para ver si ya ha aparecido anteriormente. En caso afirmativo y según que sea flashback o flashforward guardamos en el registro correspondiente las nuevas condiciones si son más restrictivas. Si es un flashforward la condición después de será siempre más restrictiva. Si es un flasback sólo modificaremos la condición antes de si no hay ninguna condición guardada porque si la hay será más restrictiva, como fácilmente puede verse:
else
{
for (vector<scenesPending>::iterator it=pending.begin(); it!=pending.end(); ++it)
{
if (it->scene.compare(scene)==0)
{
if (tipo=='<')
{
if (it->before<0)
it->before=timeline.size()-1;
}
else
{
it->after=timeline.size()-1;
}
found=true;
break;
}
}
Si no ha aparecido con anterioridad simplemente creamos un nuevo registro para la secuencia, la inicializamos con las condiciones correspondientes a esta secuencia y la almacenamos al final del vector de secuencias pendientes:
if (!found)
{
item.scene=scene;
if (tipo=='<')
{
item.before=timeline.size()-1;
item.after=-1;
}
else
{
item.before=-1;
item.after=timeline.size()-1;
}
pending.push_back(item);
}
Ordenar las secuencias
Ya hemos guardado los datos que nos han suministrado de una forma simple de manejar, ahora es tiempo de aprovecharnos del esfuerzo y encontrar la secuencia correcta de secuencias.
En el vector timeline tenemos, ya ordenadas, las secuencias que han aparecido en el guión en orden cronológico. Para que haya un orden válido de todas las secuencias tendremos que encontrar una forma de intercalar todas las secuencias que nos han quedado en el vector pending. Hacemos un bucle que recorra estas secuencias pendientes de orden para ver la posibilidad de ser insertadas:
Las variables nstart y nend van a guardar el número de secuencias que pueden ir delante de la primera de timeline y detrás de la última. Como nos indican que la secuencia no es válida si existe más de una posible secuencia de inicio o final en cuanto calquiera de estas variables valga dos el guión no es válido.
Organizamos el bucle con una serie de instrucciones if - else if ... No es ninguna estructura especial, es la simple y conocida if-else pero así empleada resulta en una serie de bloques de código de los que sólo se ejecuta el primero que tenga su condición de if cierta. Es, por tanto, similar a una sentencia switch pero más versátil.
int nstart=0;
int nend=0;
bool varios=false;
for (vector<scenesPending>::iterator it=pending.begin(); valid && (it!=pending.end()); ++it)
{
if (it->after<0)
{
if ((it->before>0) || (nstart>0))
valid=false;
nstart++;
}
else if (it->before<0)
{
if ((it->after<timeline.size()-1) || (nend>0))
valid=false;
nend++;
}
else if (it->after>=it->before)
valid=false;
else if (it->before-it->after>1)
varios=true;
}
El primer bloque se ejecuta para las sentencias que no tienen limitación de ir detrás de ninguna sentencia. Por tanto pueden ir delante de la primera. Si la limitación no es que vayan delante de la primera el guión ya no es válida porque esta sentencia podría ir delante o detrás de la primera de las secuencias del timeline, con lo que tendríamos varios posibles comienzos y, por tanto, un guión no válido. Si sólo puede ir delante de la primera incrementamos el contador nstart porque la segunda secuencia que nos aparezca con la misma condición estaríamos en el mismo caso de dos posibles comienzos y un guión no válido.
El segundo bloque se ejecuta para las sentencias que no tienen limitación de ir delante de ninguna. Todo lo dicho en el párrafo anterior es aplicable a este caso para la secuencia final.
El tercer bloque se ejecuta para las sentencias que tengan las dos condiciones, delante y detrás de, y que resulten imposible porque tengan que ir detrás (o la misma) de una secuencia posterior a la de la condición delante de.
El último bloque se ejecuta para las secuencias con las dos condiciones, que sean compatibles pero en las que la separación entre la secuencia detrás de la que deben ir y la de delante esté separadas más de una posición. Esto implica que esta secuencia podría ir en distintos sitios pero todos válidos por lo que marcamos la variable varios como true.
Si ningún bloque es ejecutado significa que la secuencia sólo tiene una posición válida.
Las variables nstart y nend van a guardar el número de secuencias que pueden ir delante de la primera de timeline y detrás de la última. Como nos indican que la secuencia no es válida si existe más de una posible secuencia de inicio o final en cuanto calquiera de estas variables valga dos el guión no es válido.
Organizamos el bucle con una serie de instrucciones if - else if ... No es ninguna estructura especial, es la simple y conocida if-else pero así empleada resulta en una serie de bloques de código de los que sólo se ejecuta el primero que tenga su condición de if cierta. Es, por tanto, similar a una sentencia switch pero más versátil.
int nstart=0;
int nend=0;
bool varios=false;
for (vector<scenesPending>::iterator it=pending.begin(); valid && (it!=pending.end()); ++it)
{
if (it->after<0)
{
if ((it->before>0) || (nstart>0))
valid=false;
nstart++;
}
else if (it->before<0)
{
if ((it->after<timeline.size()-1) || (nend>0))
valid=false;
nend++;
}
else if (it->after>=it->before)
valid=false;
else if (it->before-it->after>1)
varios=true;
}
El segundo bloque se ejecuta para las sentencias que no tienen limitación de ir delante de ninguna. Todo lo dicho en el párrafo anterior es aplicable a este caso para la secuencia final.
El tercer bloque se ejecuta para las sentencias que tengan las dos condiciones, delante y detrás de, y que resulten imposible porque tengan que ir detrás (o la misma) de una secuencia posterior a la de la condición delante de.
El último bloque se ejecuta para las secuencias con las dos condiciones, que sean compatibles pero en las que la separación entre la secuencia detrás de la que deben ir y la de delante esté separadas más de una posición. Esto implica que esta secuencia podría ir en distintos sitios pero todos válidos por lo que marcamos la variable varios como true.
Si ningún bloque es ejecutado significa que la secuencia sólo tiene una posición válida.
Escritura de resultados
Si no es un guión válido o es válido pero con diferentes órdenes escribimos el mensaje correspondiente.
Si es válido con un orden único construimos en la variable string scene la lista con los nombres de las secuencias en el orden correcto.
Para ello nos valemos de un bucle que, por medio de una variable entera, recorrerá todos los elementos del vector timeline. El límite final se marca en uno más de lo habitual para que añada al final las secuencias del vector pending que van detrás de la última secuencia de timeline.
En cada iteración del bucle externo, ejecutamos un bucle interno que recorre los elementos del vector pending y extrae los que van delante de la posición procesada en el bucle externo. Como sólo puede ir un elemento entre cada dos de las secuencias del timeline, en el momento que encontramos una secuencia nos salimos ya del bucle.
Finalmente, excepto para la última iteración del bucle, escribimos el nombre de la secuencia procesada del vector timeline.
Cada vez que añadimos una secuencia al string scene comprobamos su longitud porque si es mayor que cero significa que no es el primer nombre que se añade y hay que incluir una coma antes del nombre para separar este nombre del anterior. Es más efectivo, aunque posiblemente menos elegante, añadir todos los nombres con una coma al final y cuando tengamos el string completo eliminar la coma final.
if (!valid)
cout << "invalid";
else
if (varios)
cout << "valid";
else
{
scene="";
for (int s=0; s<=timeline.size(); s++)
{
for (vector<scenesPending>::iterator it=pending.begin(); it!=pending.end(); ++it)
if (((it->after<0) || (it->after==s-1)) && ((it->before<0) || (it->before==s)))
{
if (scene.size()>0)
scene+=",";
scene+=it->scene;
break;
}
if (s<timeline.size())
{
if (scene.size()>0)
scene+=",";
scene+=timeline[s];
}
}
cout << scene;
}
cout << endl;
Ya sólo queda vaciar los vectores empleados para dejarlos listos para emplearlos en el siguiente caso de estudio.
Como siempre aquí dejo el programa completo
No hay comentarios:
Publicar un comentario