Asuntos Oficiales > Retos
El Problema De Los Bloques
Nagisa:
Como esto esta muy sosete voy a publicar un reto :) . Es muy sencillo, y corresponde al problema 101 del UVA (del que hablo Binary en algun post anterior). El enunciado, traducido casi literalmente del ingles, es el siguiente:
--- Citar ---
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 ---10move 9 onto 1move 8 over 1move 7 over 1move 6 over 1pile 8 over 6pile 8 over 5move 2 over 1move 4 over 9quit
SALIDA DE EJEMPLO:
--- Código: Text ---0: 01: 1 9 2 42:3: 34:5: 5 8 7 66:7:8:9:
--- Fin de la cita ---
Como fecha final del reto daremos algo mas de 15 dias, aunque yo lo hice en una tarde... :whistling: Pongamos pues el dia 1 de Marzo como tope, dia en el cual publicare la solucion (me estoy currando un pdf que analiza el problema a fondo y lo desarrolla, aunque como ya dije no tiene mucha vuelta de hoja :smartass: ).
Recordad que la entrada es la entrada estandard (teclado por defecto, salvo redirecciones).
A ver si alguien se anima :lightsabre:
MutenRo:
Hola Nagisa, tengo una duda.
Según el esquema de funcionamiento descrito sería imposible volver a deshacer las pilas que se forman, verdad? Es decir, no hay ordenes para volver a llenar los 'huecos' que se ven en la salida del programa ejemplo. Lo cual significa que siempre se mueven los bloques de unas pilas a otras hasta que al final se pueda llegar a una situación en la que tienes una sola pila con todos los bloques, momento en el que ya ninguna orden sería válida.
¿Es así?
MutenRo:
Bueno, parece que sí se pueden deshacer los bloques mediante un "move a onto b" por ejemplo pero esto requiere hacer un movimiento que tal vez no te interesa sólo para deshacer una pila. De hecho creo que con este sistema es imposible volver a la posición inicial donde cada bloque está en su lugar de origen, ¿verdad? :blink:
MutenRo:
Bueno, aqui va mi solución, a ver qué os parece....
Las órdenes van en el fichero orden.txt (podeis copiar las del ejemplo).
#include <stdio.h>
#include <string.h>
void posicion(short array[][25], short bloque, short* fila, short* columna)
{
// devuelve la posición (en el array) en la que se encuentra un bloque
int i,j=-1;
for(i=0; i<25; i++, j=-1)
{
while(array[++j] != -1)
{
if (array[j] == bloque)
{
*fila=i;
*columna=j;
break;
}
}
if (array[j] == bloque) break;
}
}
void limpia(short array[][25], short fila, short columna)
{
// devuelve los bloques de encima a sus posiciones originales
short bloque;
while((bloque=array[fila][++columna]) != -1)
{
array[bloque][0]=bloque; // ponerlo en la posicion inicial
array[bloque][1]=-1; // fin de la pila
}
}
void main(void)
{
FILE *fichero;
short array[25][25];
short i, j, num_bloques=10, origen, destino, fila_o, col_o, fila_d, col_d;
char orden_1[6], orden_2[6];
//inicializo el array
for (i=0; i<25; i++)
{
for (j=0; j<25; j++)
array[j]=0;
}
for (i=0; i<25; i++)
{
array[0]=i;
array[1]=-1; // con -1 indicamos fin de pila
}
//lectura de órdenes y ejecución
fichero=fopen("orden.txt", "r");
if (fichero != NULL)
{
fscanf(fichero,"%d", &num_bloques);
while ((fscanf(fichero,"%s %d %s %d", orden_1, &origen, orden_2, &destino)) == 4)
{
posicion(array, origen, &fila_o, &col_o);
posicion(array, destino, &fila_d, &col_d);
if (origen == destino || fila_o == fila_d)
{
// printf("\nOrden incorrecta, origen y destino no pueden coincidir.");
}
else if (strcmp(orden_1,"move") == 0 && strcmp(orden_2,"onto") == 0)
{
limpia(array,fila_o, col_o);
limpia(array,fila_d, col_d);
array[fila_d][col_d + 1]=array[fila_o][col_o];// lo movemos
array[fila_d][col_d + 2]=-1; // indicamos fin de pila
array[fila_o][col_o]=-1; // indicamos fin de pila en el origen
}
else if (strcmp(orden_1,"move") == 0 && strcmp(orden_2,"over") == 0)
{
limpia(array,fila_o, col_o);
for (i=0;array[fila_d]!=-1;i++);
array[fila_d]=array[fila_o][col_o];// movemos el bloque
array[fila_d][++i]=-1;// fin de pila en el destino
array[fila_o][col_o]=-1; // indicamos fin de pila en el origen
}
else if (strcmp(orden_1,"pile") == 0 && strcmp(orden_2,"onto") == 0)
{
limpia(array,fila_d, col_d);
i=0;
while(array[fila_o][col_o + i] != -1)
{
array[fila_d][col_d + i + 1]=array[fila_o][col_o + i];
i++;
}
array[fila_d][col_d + i + 1]=-1; // indicamos fin de pila en el destino
array[fila_o][col_o]=-1; // indicamos fin de pila en el origen
}
else if (strcmp(orden_1,"pile") == 0 && strcmp(orden_2,"over") == 0)
{
for(j=0; array[fila_d][j]!=-1; j++); //localizamos el final
i=0;
while(array[fila_o][col_o + i] != -1)
{
array[fila_d][j + i]=array[fila_o][col_o + i];
i++;
}
array[fila_d][j + i]=-1; // indicamos fin de pila en el destino
array[fila_o][col_o]=-1; // indicamos fin de pila en el origen
}
else
{
// printf("\nComando incorrecto.\n");
}
}
fclose(fichero);
}
else
{
perror("Error al abrir el fichero");
}
//rutina de impresión
for (i=0; i<num_bloques; i++)
{
printf("\n%d:",i);
j=0;
while (array[j] != -1)
{
printf(" %d", array[j++]);
}
}
printf("\n");
}
carlos20:
:angry: :angry: :angry:
Navegación
[#] Página Siguiente
Ir a la versión completa