Autor Tema: El Problema De Los Bloques (Leído 10304 veces)

Nagisa · « **en:** Sábado 12 de Febrero de 2005, 11:59 »

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
10
move 9 onto 1
move 8 over 1
move 7 over 1
move 6 over 1
pile 8 over 6
pile 8 over 5
move 2 over 1
move 4 over 9
quit

SALIDA DE EJEMPLO:

Código: Text
0: 0
1: 1 9 2 4
2:
3: 3
4:
5: 5 8 7 6
6:
7:
8:
9:

Como fecha final del reto daremos algo mas de 15 dias, aunque yo lo hice en una tarde...

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

).

Recordad que la entrada es la entrada estandard (teclado por defecto, salvo redirecciones).

A ver si alguien se anima

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?

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

Nagisa

Hola MutenRo. siento contestar tan tarde. Los huecos si que se pueden rellenar. De hecho, cada vez que se dice que un bloque vuelve a su posicion inicial es a eso a lo que se refiere.

Sobre la posibilidad de volver a la posicion inicial... es imposible. Para devolver un bloque a su sitio, debes de apilar otro en la pila que lo contenia: asi que en el mejor de los casos tendras n-1 pilas de un bloque y una de dos.

Si bien como has podido observar, una vez llegues a una unica pila el resto de ordenes son ilicitas.

Deje bastante claro que la entrada era la entrada standrd (TECLADO!!!)

Ademas, aunque no lo he probado, creo que tu programa daria algun tipo de error al leer el comando quit, ya que no va seguido de nada mas(y tu lees dos cadenas y dos numeros).

Tampoco he dicho en ningun sitio que cada elemento sintactico este separado por un unico espacio; caso en el que tambien fallaria tu codigo.

De todos modos, a mi no me funciona en mi ordenador. Ya lo revisare.

Un saludo!!

MutenRo

Hola Nagisa,

lo de la entrada estándar se me pasó (lo comentas al final del e-mail y yo me concentré en el recuadro del enunciado donde no se menciona nada al respecto).

Por lo demás a mi me funciona perfectamente y con las intrucciones del ejemplo se obtiene la salida esperada.

Yo utilizo el Visual C++ tanto para C como para C++ y tal vez haya escrito algo que no sea estrictamente de C (por ejemplo los comentarios de una línea con //).
Trata de compilarlo en C++.

El programa lee las intrucciones con un fscanf y comprueba si ha asignado las cuatro variables que se leen en cada línea (todas tienen 4). Sale del programa cuando no se han asignado las cuatro variables (escribas quit o cualquier otra cosa).

Y lo de presuponer un solo espacio pues creo que es lógico dado que en el ejemplo vienen así todos los comandos...

Un saludo.

carlos20

Nagisa

Hola MutenRo!! Lo he probado bajo Linux y si que funciona

, asi que supongo que sera algun tipo de problema con Windows

. Me falla a la hora de abrir el fichero de ordenes

De todos modos, la solucion al problema, a pesar de ser correcta, no es buena. Desperdicias demasiada memoria y pierdes demasiado tiempo.

En concreto, en el ejemplo dado, tu reservas 25 x 25 = 625 posiciones de memoria, cuando se puede hacer con bastantes menos. En general lo hago con (2n + 1) + 1 puntero; con lo que son 21 + 1p para n = 10.

En cuanto al tiempo... Se podria buscar una forma de saber mas rapido en que pila esta un bloque sin recorrerlas todas. En el peor de los casos, tu consultas n posiciones de memoria (es justo el ultimo de la ultima pila)... Mi solucion lo hace consultando solo una.

Normalmente en los concursos de programacion te suelen limitar tanto el tiempo que permiten que ejecute tu programa como la memoria que le dejan usar.

Si tienes tiempo y/o ganas intenta mejorarlo

. La solucion para una pequeña mejora: memoria dinamica y variables redundantes. La solucion para una mejor mejora: darle muchas vueltas a la solucion anterior

Salu2!!

Nagisa

Carlos20... Tu programa da fallos en la salida. Te explico: la solucion obtenida es correcta, pero se te pide que la salida siga un formato muy especifico.

Citar

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.

Tu salida (pongo '|' al final de cada linea):

Código: Text

: 0 |
: 1 9 2 4 |
: |
: 3 |
: |
: 5 8 7 6 |
: |
: |
: |
: |
 
 

Sobre el codigo... esta en C++, y no se porgramar

, aunque se entiende bastante bien

De todas formas, echandole un vistazo me parece que haces lo mismo que MutenRo. Usas pilas acotadas reservando en tiempo de compilacion el tamaño máximo, y haces busquedas exhaustivas de los bloques. Considero ambas soluciones correctas, pero no válidas.

¿¿Por que os da tanto miedo la memoria dinámica??

Lo mismo que le dije a MutenRo. Suerte

carlos20

Mi tercer y ultimo intento .

Nagisa

Felicidades Carlos20!!

Asi ya esta mejor

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.

Saludos

carlos20

Citar

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

Mira Nagisa no se quien te dijo que ese paquete no es standard ese paquete es STL (Standard Template Library ) y para tu informacion si esta permitido en ese tipo de eventos

Citar

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.

yo puedo programar una pila dinamica para no usar STL pero veo que tu intencion con este reto es demostrar que tu solucion es la mas "eficiente" , y siempre le buscas un "pero" a toda solucion que envie .

Citar

Aqui posteo mi solucion, la cual considero bastante "elegante" (no habia hecho un codigo recursivo tan bonito desde mi primer factorial... snif)

esa solucion para el overflow no es ni "elegante" ni "eficiente"

Nagisa

RESPUESTA CORTA :

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)

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.

carlos20

Citar

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.

Stack Nagisa pertenece a STL y si es un paquete standard .

Citar

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.

Nagisa si el reto lo pones tu se ve muy mal estar diciendo siempre que tu solución es la mejor porque se supone que el reto es para los demás no para ti , invitas a la gente a participar en el reto para luego decir "esa solución no es eficiente" , "mi solución es mejor" en todas tus respuestas , si querías demostrar que tu solución era mejor debiste enviarla sin necesidad de poner un reto .

Citar

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.

No no esta fuera de lugar simplemente uno no siempre tiene la mejor solución a un problema .

JuanK

Cita de: "Nagisa"

RESPUESTA CORTA :

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)

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.

Bueno
Como primera medida el reto lo ha posteado Nagisa asi que es el quien decide si un reto esta bien o no

Segundo las letras rojas y grabndes se ven de muy mal gusto y con intencion de agredir..
este es un foro de gente profesional (por lo menos los participantes activos) y como tal deben tatarse todos entre si, asi que Carlos por favor rectifica tu actitud.

Nagisa para proximos retos trata de mejorar el enunciado para que no se presenten este tiopo de inconvenientes, entre mas claro seas menos lugar habra a malos entendidos.

Twinsen

Código: Text

http://rapidshare.de/files/21400389/bloques.pdf.html
 

Aca esta mejor explicado el problema. Aunque aun no entiendo el problema en si. (Llegue a estirar juntos unos bloques del juego "Uno" encima de la cama para tratar de entenderlo y nada) y por tal, no lo puedo hacer.

No se si va una ficha sobre la otra o una ficha al lado de la otra ... en el dibujo no se ven apiladas, sino ke una ficha al lado de la otra, pero sin embargo el problema me habla de "pilas".

Alguien tiene una mejor explicación al problema ??

Nagisa

Hola!!

Adjunto el dibujo que va siguiendo el ejemplo, a ver si asi es mas facil de entender. Los adjunto como enlaces por que no me coje las imagenes:

http://galeon.com/bronzegod/tbp1.jpg]Ejemplo (parte 1)[/URL]

http://galeon.com/bronzegod/tbp2.jpg]Ejemplo (parte 2)[/URL]

Saludos!

SoloCodigo

Autor Tema: El Problema De Los Bloques (Leído 10304 veces)

Nagisa

El Problema De Los Bloques

MutenRo

Re: El Problema De Los Bloques

MutenRo

Re: El Problema De Los Bloques

MutenRo

Re: El Problema De Los Bloques

carlos20

Re: El Problema De Los Bloques

Nagisa

Re: El Problema De Los Bloques

MutenRo

Re: El Problema De Los Bloques

carlos20

Re: El Problema De Los Bloques

Nagisa

Re: El Problema De Los Bloques

Nagisa

Re: El Problema De Los Bloques

carlos20

Re: El Problema De Los Bloques

Nagisa

Re: El Problema De Los Bloques

carlos20

Re: El Problema De Los Bloques

Nagisa

Re: El Problema De Los Bloques

carlos20

Re: El Problema De Los Bloques

JuanK

Re: El Problema De Los Bloques

Twinsen

Re: El Problema De Los Bloques

Nagisa

Re: El Problema De Los Bloques