El Problema de los bloques.
TRASFONDO:
Muchas areas de la Informatica usan dominios simples y abstractos para estudios tanto analiticos como empiricos. Por ejemplo, un estudio prematuro de IA de planificacion y robotica (STRIP) usaba un mundo de bloques en el cual un brazo robotico llevaba a cabo tareas que implicaban la manipulacion de los bloques.
EL PROBLEMA:
El problema es procesar unas series de mandatos que instruyen a un brazo robotico sobre como manipular los bloques que estan en una mesa plana. Inicialmente hay n bloques en la mesa (enumerados desde 0 hasta n-1) con el bloque b(i) adyacente al bloque b(i+1) para todo 0 <= i < (n-1).
Los mandatos validos para el brazo robotico que manipula los bloques son:
move a onto b
donde a y b son numeros de bloque, pone el bloque a encima del bloque b despues de devolver cualquier bloque que estuviera apilado encima de los bloques a y b a sus posiciones iniciales.
move a over b
donde a y b son numeros de bloque, pone el bloque a encima de la pila que contiene el bloque b, despues de devolver cualquier bloque que estuviera encima del bloque a a su posicion inicial.
pile a onto b
donde a y b son numeros de bloque, mueve la pila de bloques consistente en el bloque a, y cualquier bloque apilado encima del bloque a, encima del bloque b. Todos los bloques encima del bloque b son movidos a sus posiciones iniciales antes del que el apilado tenga lugar. Los bloques apilados encima del bloque a mantienen el orden cuando son movidos.
pile a over b
donde a y b son numeros de bloque, mueve la pila de bloques consistente en el bloque a, y cualquier bloque apilado encima del bloque a, encima de la pila que contenga al bloque b. Los bloques apilados encima del bloque a mantienen el orden cuando son movidos.
quit
termina las manipulaciones en el mundo de bloques.
Cualquier mandato con a = b o en el que a y b esten en la misma pila es un mandato ilegal. Todos los mandatos ilegales deberan de ser ignorados y no deberan de afectar a la configuracion de los bloques.
LA ENTRADA:
La entrada empieza con un entero n en una linea por si misma y representa el numero de bloques en el mundo de bloques. Puedes asumir que 0 < n < 25.
El numero de bloques esta seguido por una secuencia de mandatos de bloques, uno por linea. Tu programa debera procesar todos los mandatos hasta que se encuentre al mandato quit.
Puedes asumir que todos los mandatos seran de la forma especificada arriba. No habra mandatos sintacticamente incorrectos.
LA SALIDA:
La salida debera de consistir en el estado final del mundo de bloques. Cada posicion inicial del bloque i ( 0 <= i < n, donde n es el numero de bloques) debera aparecer seguida inmediatmente por dos puntos (':'). Si hay al menos un bloque en ella, los dos puntos deberan de estar seguidos por un espacio, seguido de la lista de bloques que estan apilados en esa posicion con cada numero de bloque separado del resto por un espacio. No poner espacios sobrantes al final de la linea.
Debera haber una linea de salida por cada posicion de bloque (es decir, n lineas de salida donde n es el entero de la primera linea de la entrada).
ENTRADA DE EJEMPLO:Código: Text
SALIDA DE EJEMPLO:Código: Text
LA SALIDA:
La salida debera de consistir en el estado final del mundo de bloques. Cada posicion inicial del bloque i ( 0 <= i < n, donde n es el numero de bloques) debera aparecer seguida inmediatmente por dos puntos (':'). Si hay al menos un bloque en ella, los dos puntos deberan de estar seguidos por un espacio, seguido de la lista de bloques que estan apilados en esa posicion con cada numero de bloque separado del resto por un espacio. No poner espacios sobrantes al final de la linea.
De todos modos usas un paquete no standard, y eso no suele estar permitido en este tipo de eventos, aunque al ser el de pilas lo pasamos por alto...
Aun tardare un poco en publicar mi solucion debido a una serie de problemas tecnicos con mi ordenador... De todos modos es dar unas pocas vueltas a la de Carlos para ahorrar un poco de memoria y tiempo.
Aqui posteo mi solucion, la cual considero bastante "elegante" (no habia hecho un codigo recursivo tan bonito desde mi primer factorial... snif)
El paquete no standard no es STL, si no stack (si me quejo de las pilas, es stack == pila); aunque eso es lo de menos.
Sobre mi solución... Realmente es muy similar a la tuya, solo que como implemento directamente las pilas, en lugar de usar memoria dinamica y listas enlazadas hago la reserva de memoria solo una vez en un vector de tamaño n y no uso punteros sino indexacion de posiciones; consiguiendo:
a) Menor tiempo de ejecucion (por que no hago apenas llamadas al Sistema Operativo => malloc y free)
Menor cantidad de memoria: En lugar de usar datos de tipo puntero para el enlace de los nodos, se usan shorts, que ocupan 2 bytes en lugar de 4.
Si posteas una solucion, y se que hay alguna mejor en algun aspecto, lo suyo seria postearla para que la gente la pueda ver. Si la tuya fuera mejor que la mia, no la pondria... O al menos el lo que yo pienso. "Cultura de foro" creo que lo llaman.
Y sobre lo ultimo.... simplemente dire que creo que esta fuera de lugar, sin compartir la impresion que da realmente el post en su conjunto. Si tienes una solucion mejor, posteala en el thread correspondiente, que NO es éste.
RESPUESTA CORTA : :huh: :blink:Bueno
RESPUESTA NO TAN CORTA :
Consideraria aun mas elegante no responder, pero weno...
El paquete no standard no es STL, si no stack (si me quejo de las pilas, es stack == pila); aunque eso es lo de menos.
Sobre mi solucion... Realmente es muy similar a la tuya, solo que como implemento directamente las pilas, en lugar de usar memoria dinamica y listas enlazadas hago la reserva de memoria solo una vez en un vector de tamaño n y no uso punteros sino indexacion de posiciones; consiguiendo:
a) Menor tiempo de ejecucion (por que no hago apenas llamadas al Sistema Operativo => malloc y free)
B) Menor cantidad de memoria: En lugar de usar datos de tipo puntero para el enlace de los nodos, se usan shorts, que ocupan 2 bytes en lugar de 4.
Si posteas una solucion, y se que hay alguna mejor en algun aspecto, lo suyo seria postearla para que la gente la pueda ver. Si la tuya fuera mejor que la mia, no la pondria... O al menos el lo que yo pienso. "Cultura de foro" creo que lo llaman.
Y sobre lo ultimo.... simplemente dire que creo que esta fuera de lugar, sin compartir la impresion que da realmente el post en su conjunto. <_< Si tienes una solucion mejor, posteala en el thread correspondiente, que NO es éste.