TODOPIC

Microcontroladores PIC => Lenguaje C para microcontroladores PIC => Mensaje iniciado por: jgpeiro06 en 28 de Abril de 2009, 20:28:09

Título: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: jgpeiro06 en 28 de Abril de 2009, 20:28:09
Mini-Concurso de programacion en C, parte 2: Las 8 reinas.
El concurso empezará el 5 de Mayo y terminará el 20. Hasta el 5 se irán modelando las reglas, condiciones y premios del concurso según vuestros comentarios.


De momento el concurso esta planteado así:

El problema de las 8 reinas consiste en situar 8 reinas en un tablero de ajedrez sin que ninguna se toque entre si.
Cada participante debe implementar un algoritmo que encuentre las 92 soluciones posibles.

Ejemplo de una solucion valida.
+---+---+---+---+---+---+---+---+
|     |     |     |  X |    |     |     |     |
+---+---+---+---+---+---+---+---+
|     |     |     |     |    | X  |     |     |
+---+---+---+---+---+---+---+---+
|     |     |     |     |    |     |     | X  |
+---+---+---+---+---+---+---+---+
|     | X  |     |     |     |     |    |     |
+---+---+---+---+---+---+---+---+
|     |     |     |     |    |     |  X |     |
+---+---+---+---+---+---+---+---+
| X  |     |     |     |     |    |     |     |
+---+---+---+---+---+---+---+---+
|     |     | X  |     |     |    |     |     |
+---+---+---+---+---+---+---+---+
|     |     |     |     | X |     |     |     |
+---+---+---+---+---+---+---+---+

Se dará una función main.c con la estructura básica para que todos podamos probar los programas cómodamente.

Las categorias son las siguientes:
Algoritmo más rápido:
   Gana el algoritmo que encuentre las 92 soluciones en el menor tiempo( menor numero de instrucciones ejecutadas ).
   Requisitos:
   C30: PIC24. Compilador MPLAB C30, sin optimizaciones. No esta permitido el ensamblador incrustado.
   CCS: PIC24. Compilador CCS. ""
   
Algoritmo más sencillo
   Gana el que implemente el algoritmo más simple, más comprensible, mejor organizado...

Algoritmo más lioso
   Gana el más absurdo, el más loco, el que realiza calculos complicando lo más posible sin necesidad...
   No esta permitido añadir código "inútil", todo el código debe ser util para el algoritmo, pero si es posible implementar nuestras propias funciones para
   punto flotante o declarar todas las variables dinamicamente, utilizar switch en lugar de if, utilizar goto...todo aquello que nunca deberíamos hacer.

Algoritmo mas robusto
   Despues de compilar el programa se remmplazan unas cuantas instrucciones, escogidas al azar, por NOPs y se ejecuta el programa para ver que pasa.
   El algoritmo debe estar preparado para poder sobrevivir a estas u otras posibles "putadas"...

Cada concursante tendrá que votar los programas de los demás en las tres ultimas categorías.

El concurso finalizara el 20 de Mayo.
Sobre los premios...son solo algo simbólico para darle gracia al concurso:
   Algoritmo más lioso:
      2º Premio   Pagina web con muchos proyectos interesantes de electrónica. Link
      1º Premio   Librería para trabajar con matrices en C30. Archivo matrices.c
   Algoritmo más sencillo:
      2º Premio   Documental sobre ciencia y tecnología. VideoLink
      1º Premio   Pagina web con animaciones interactivas en flash. Link
   Algoritmo más rapido:
      2º Premio   Foto de el interior de un procesador Pentium 4 (4000x4000 pixels). Link
      1º Premio   Pack de 16 libros de programacion para sistemas empotrados. Link en rapidshare.
   Algoritmo más robusto:
      2º Premio   Entrevista a Bill Gates mostrando el nuevo Windows Paradise. VideoLink en youtube
      1º Premio   Versión moderna del juego The Increible Machine. Link en rapidshare.


El día 5 se colgaran las reglas oficiales y el archivo main.c con el esqueleto del programa.

Bueno, esto es lo que se me ocurre. Hasta el 5 de Mayo hay tiempo añadir o modificar cualquier cosa.
Quien este interesado en participar que se apunte añadiendo un post al hilo.
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: gera en 28 de Abril de 2009, 20:46:07
Excelente iniciativa!!! :-/ :-/ Lamentablemente yo voy a estar preparando finales durante ese periodo, pero voy a hacer todo lo posible para generar un algoritmo.
Por cierto... nunca trabaje con pic24, habra alguna posibilidad de hacer el algoritmo en gcc y despues tratar de portarlo?
saludos!!!
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: BrunoF en 29 de Abril de 2009, 01:26:15
A mi ya se me ocurrió el algoritmo pa resolverlo, pero esta vez voy a abstenerme. Al menos esperaré hasta que vengan otros primero. :D
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: gera en 29 de Abril de 2009, 11:44:33
podriamos mandar las soluciones por privado, y asi evitar el robo de ideas :P
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: migsantiago en 29 de Abril de 2009, 11:46:39
Cita de: gera en 29 de Abril de 2009, 11:44:33
podriamos mandar las soluciones por privado, y asi evitar el robo de ideas :P

Sí es buena idea. Que al final Jgpeiro publique una lista de lo recibido.
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: Nocturno en 29 de Abril de 2009, 12:09:13
Entiendo que el algoritmo no recibirá ninguna entrada y devolverá la salida mediante printf() a la salida por defecto, ¿verdad?.

Quizás estaría bien preparar un pequeño esqueleto en Proteus para poder ejecutar las soluciones sin necesidad de montar el circuito en real.

Me encantan estos concursos.
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: jgpeiro06 en 29 de Abril de 2009, 15:47:27
Citar
nunca trabaje con pic24, habra alguna posibilidad de hacer el algoritmo en gcc y despues tratar de portarlo
Lo normal es que el código sea independiente de la plataforma y del compilador. Si usas las librerías más comunes de C seguro que el código no necesita ninguna modificación para compilarlo con C30 o CCS.

Citar
podriamos mandar las soluciones por privado, y asi evitar el robo de ideas
No me parece mala idea. La idea era que cada usuario valorase los códigos de los demás usuarios, pero es cierto que seria muy difícil no dejarse influenciar. Se podrían enviar por privado los códigos, indicar en el hilo la versión que cada uno va enviando, si el código es para alguna categoría en concreto... y el dia 20 publico todos los codigos, durante una semana la gente que quiera los prueba, los vota(también por privado) y el día 25 se publican los ganadores.

Citar
Entiendo que el algoritmo no recibirá ninguna entrada y devolverá la salida mediante printf() a la salida por defecto, ¿verdad?.
Sip. Aun no tengo preparado el main.c con las funciones básicas para el concurso, pero supongo que con usar el printf sera suficiente.

Citar
Quizás estaría bien preparar un pequeño esqueleto en Proteus para poder ejecutar las soluciones sin necesidad de montar el circuito en real.
Las soluciones, como en el mini-concurso anterior, se pueden probar en el MPLAB. Con el MPLAB SIM como debugger la opción de UARTIO habilitada. De esta manera aparece una pestaña en la ventana Output que se llama "Sim Uart1" que permite visualizar lo que imprime un printf.
Con el IDE de CCS no se si esto se puede hacer, pero supongo que también habrá alguna manera de visualizar una consola.
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: migsantiago en 29 de Abril de 2009, 18:22:17
Una pregunta, ¿la posición de la foto de abajo es válida? ¿No, verdad?

(http://img179.imageshack.us/img179/1179/dsc00147w.th.jpg) (http://img179.imageshack.us/img179/1179/dsc00147w.jpg)
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: Nocturno en 29 de Abril de 2009, 18:56:31
En ajedrez, las reinas comen tanto en horizontal, como en vertical, como en las dos diagonales, así que no es válida.
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: jgpeiro06 en 29 de Abril de 2009, 19:01:12
Citar
Una pregunta, ¿la posición de la foto de abajo es válida? ¿No, verdad?
Nop, no lo es.

Mírate el articulo sobre el problema de las 8 reinas en la wikipedia. Encontraras toda esta información:

Problema de las ocho reinas
    1 Planteamiento del Problema
        1.1 Establecimiento del Algoritmo
        1.2 Descripción del Algoritmo
    2 El problema de las n Reinas
    3 Soluciones al Problema de las Ocho Reinas
    4 Referencias
    5 Enlaces externos
        5.1 Enlaces a Soluciones

http://es.wikipedia.org/wiki/Problema_de_las_ocho_reinas
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: jgpeiro06 en 30 de Abril de 2009, 05:01:38
Ejemplo del archivo main.c. Solo es una prueba, aun no compila, pero sirve para dar una idea.
El concursante deberá implementar las funciones:
void calculaNuevaPosicion( const Tablero *ptablrero1 );
int verificaPosicion( const Tablero *ptablrero1 );


Código: C
  1. /**********************
  2. Mini-Concurso de programacion
  3. ***********************/
  4.  
  5. #include        <stdlib.h>
  6. #include        <stdio.h>
  7. #include        <math.h>
  8.  
  9. enum ficha { vacia, reina };
  10.  
  11. casilla{
  12.         enum ficha ficha1;
  13. };
  14.  
  15. tablero{
  16.         casillas1[8][8];
  17. };
  18.  
  19. void calculaNuevaPosicion( const Tablero *ptablrero1 );
  20. int verificaPosicion( const Tablero *ptablrero1 );
  21.  
  22. void imprimeTablero( const Tablero *ptablrero1 ){
  23.         printf("\n\n");
  24.         for( i = 0 ; i < 8 ; i++ ){
  25.                 for( j = 0 ; j < 8 ; j++ ){
  26.                         if( ptablero1->casillas1[i][j].ficha1 == reina )
  27.                                 printf("Q");    // Pinta una reina.
  28.                         else if((j&1)^(i&1))
  29.                                 printf("#");    // Pinta casilla negra.
  30.                         else
  31.                                 printf(" ");    // Pinta casilla blanca.
  32.                 }
  33.                 printf("\n");
  34.         }
  35. }
  36.  
  37. int main(){
  38.  
  39.         Tablero tablero1;
  40.         int i, j;
  41.  
  42.         printf("www.TODOPIC.com.ar\n");
  43.         printf("Mini-Concurso de progracion en C, Parte 2:\n");
  44.         printf("Las 8 reinas.\n");
  45.         printf("Nombre del concursante: XXXX");
  46.        
  47.         long long tested = 0;
  48.         for( i = 0 ; i < 92 ; i++ ){
  49.                 while( !verificaPosicion( &tablero1 ) );
  50.                         tested++;
  51.                         calculaNuevaPosicion( &tablrero1 );
  52.                 }
  53.                 printf( "\nSe han escaneado %d tableros. Solucion %d de 92: ", tested, i );
  54.                 imprimeTablero( &tablero1 );
  55.         }
  56.  
  57.         printf("\n\nTest terminado.");
  58.         return 0;
  59. }

Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: jgpeiro06 en 03 de Mayo de 2009, 07:13:49
Bueno, quedan 2 días y aun somos muy pocos para el concurso...si no se apunta nadie más no tiene sentido seguir con el concurso...:-(
Si nadie tiene ningún comentario sobre las reglas del concurso quedaran así.

Saludos
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: migsantiago en 03 de Mayo de 2009, 11:28:18
¿El archivo main.c ya es definitivo?

No importa si son pocos los interesados. Estoy seguro que más gente está participando con solo leer el tema.
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: gera en 03 de Mayo de 2009, 11:49:42
Yo estoy hasta las manos con la facultad, pero voy a tratar de aportar mi algoritmo :)
por cierto, no seria mas facil definir un arreglo 8x8 cuyo contenido sea 0 ó 1 dependiendo si hay reina o no? (es mas, seria mas eficiente con un arreglo de 8x1 jeje, pero seria incomodo).
saludos!!
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: jgpeiro06 en 03 de Mayo de 2009, 17:16:40
Citar
¿El archivo main.c ya es definitivo?
Aun no, el original lo publicaré el día 5. Sera lo mismo, pero con las modificaciones que hagan los concursantes.

Citar
no seria mas facil definir un arreglo 8x8 cuyo contenido sea 0 ó 1 dependiendo si hay reina o no
Supongo que si que seria mas sencillo. Creo que seria conveniente que cada usuario pueda definir las estructuras tablero y casilla a su gusto.
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: jgpeiro06 en 05 de Mayo de 2009, 04:52:23
Bueno, aqui va el archivo main.c oficial y comienza el concurso.

Código: C
  1. /**********************
  2. Mini-Concurso de programacion
  3.  
  4. El concursante deme implementar:
  5.         Estructuras Casilla y Tablero
  6.         Funciones calculaNuevaPosicion, verificaPosicion y imprimeTablero.
  7. Se puede añadir o eliminar cualquier cosa en estas estructuras o funciones.
  8. ***********************/
  9.  
  10. #include        <stdlib.h>
  11. #include        <stdio.h>
  12. #include        <math.h>
  13.  
  14. enum Ficha { vacio, reina };
  15.  
  16. typedef struct {
  17.         enum Ficha ficha1;
  18. }Casilla;
  19.  
  20. typedef struct {
  21.         Casilla casillas1[8][8];
  22. }Tablero;
  23.  
  24. void calculaNuevaPosicion( const Tablero *ptablrero1 ){
  25.         return;
  26. }
  27. int verificaPosicion( const Tablero *ptablrero1 ){
  28.         return 0;
  29. }
  30. void imprimeTablero( const Tablero *ptablrero1 ){
  31.         return;
  32. }
  33.  
  34. int main(){
  35.  
  36.         Tablero tablero1;
  37.         int i;
  38.  
  39.         printf("www.TODOPIC.com.ar\n");
  40.         printf("Mini-Concurso de progracion en C, Parte 2:\n");
  41.         printf("Las 8 reinas.\n");
  42.         printf("Nombre del concursante: XXXX");
  43.        
  44.         long long tested = 0;
  45.         for( i = 0 ; i < 92 ; i++ ){
  46.                 while( !verificaPosicion( &tablero1 ) ){
  47.                         tested++;
  48.                         calculaNuevaPosicion( &tablero1 );
  49.                 }
  50.                 printf( "\nTableros comprobados: %f", (double)tested );
  51.                 printf( "\nSolucion %d de 92: ", i );
  52.                 imprimeTablero( &tablero1 );
  53.         }
  54.  
  55.         printf("\n\nTest terminado.");
  56.         return 0;
  57. }
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: Nocturno en 07 de Mayo de 2009, 02:50:57
Dices que se pueden añadir o eliminar cualquier cosa en estructuras y funciones; entiendo que lo único que hay que respetar son los nombres de las mismas para que el main funcione, ¿no?

¿Eso significa que podemos montar otra estructura distinta de casillas y tablero?
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: jgpeiro06 en 07 de Mayo de 2009, 16:14:43
Citar
Dices que se pueden añadir o eliminar cualquier cosa en estructuras y funciones...
Si, así cada concursante podrá trabajar más cómodo.

Citar
...entiendo que lo único que hay que respetar son los nombres de las mismas para que el main funcione, ¿no?
En principio si que hay que mantener los nombres, pero si alguien cree que puede obtener un código mejor modificando también el main...es libre de hacerlo. Siempre el mensaje impreso sea comprensible.

Citar
¿Eso significa que podemos montar otra estructura distinta de casillas y tablero?
Si, cada usuario puede definir las estructuras como mas le convenga, así habrá códigos mas variados...

Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: migsantiago en 07 de Mayo de 2009, 16:49:22
¿Se vale usar C# en vez de C?
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: jgpeiro06 en 08 de Mayo de 2009, 10:19:21
Citar
¿Se vale usar C# en vez de C?
No, el concurso es en C, y el programa se compilará con el MPLAB o el CCS.
Solo por curiosidad ¿ofrece alguna ventaja el C# para este problema?
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: migsantiago en 08 de Mayo de 2009, 13:00:39
Pues es que quería hacer una grafiquita que dibujara las reinas en el tablero. Pero bueno, lo intentaré con C normal.
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: migsantiago en 09 de Mayo de 2009, 22:46:35
Ya terminé mi algoritmo. Primero lo hice en C# para poderlo depurar a gusto.

Implementé un algoritmo por fuerza bruta, es decir, pasa por todas las posibles posiciones que pueden tener las reinas. Después de cada combinación se busca si hay al menos 2 reinas en la misma fila o en la misma diagonal usando la detección propuesta en el link de Wikipedia que Jgpeiro da.

Si la combinación es apropiada, imprime el tablero con ceros y unos, siendo los unos las reinas.

No conté las combinaciones correctas ya que al hacer un barrido de todas las combinaciones posibles tienen que salir las 92 correctas siempre.

El archivo resultante con los 92 tableros dibujados es este:
http://www.4shared.com/file/104418320/64e40fd2/Reinas.html

Pero como no se vale en C# migré el código a CCS usando un PIC16 que fácilmente puede migrarse a PIC24. El código compila correctamente sin errores ni advertencias, pero no lo puedo probar porque no uso MPLAB. Si alguien lo emula en MPLAB o Proteus por favor que me diga si funciona.

Este es el código de CCS:
http://www.4shared.com/file/104418325/148efb5d/Ocho_Reinas_CCS.html

Y para los interesados, el código en C#.
http://www.4shared.com/file/104418343/abb7f9ee/Ocho_Reinas_VC_2008.html

 :-/
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: jgpeiro06 en 12 de Mayo de 2009, 19:07:15
Citar
Ya terminé mi algoritmo.
Ok, lo he revisado y parece todo correcto. No es compatible con el "main.c", pero es igual. No lo he probado con el MPLAB, aunque seguro que funciona con algunas modificaciones mínimas.

Yo también he terminado el código. Lo cuelgo por si alguien lo quiere mirar o probar.
Tarda unos tres minutos en un PIC24 a 120MHz( >7200 millones de instrucciones ). Ocupa <300 instrucciones de ROM y 0 de RAM (+el stack) si no incluimos las funciones de printf.

Utiliza también un algoritmo por fuerza bruta.



Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: migsantiago en 13 de Mayo de 2009, 13:24:13
Vientos Jgpeiro.

Una pregunta... ¿el tiempo de 3 minutos es al simularlo en tu pc o el tiempo que da el stopwatch de mplab?

Es que si corres el simulador de MPLAB en una pc lenta, el tiempo real crecerá. El stopwatch de MPLAB da el tiempo de forma exacta.
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: jgpeiro06 en 13 de Mayo de 2009, 14:29:13
Citar
Vientos Jgpeiro.
¿que significa?

Citar
¿el tiempo de 3 minutos es al simularlo en tu pc o el tiempo que da el stopwatch de mplab?
Es el tiempo que aparece en el stopwatch, claro, y por eso especifico la velocidad del pic y las instrucciones ejecutadas en ese tiempo. Simularlo en el PC tarda bastante más, quizás 10 o 15 min...
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: migsantiago en 13 de Mayo de 2009, 18:10:23
Vientos Huracanados Arremolinados significa... buen trabajo... bien hecho  :D

A ver si me doy un tiempo para instalar MPLAB y CCS para medir el tiempo como tú lo haces.
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: gera en 13 de Mayo de 2009, 18:49:58
Fuerza bruta?? :shock:
Si mis calculos no fallan esas son 64C8=4.426.165.368 posibilidades!! Yo tengo algo pensado para descartar todas las posibilidades donde las reinas se atacan por filas o columnas, pero creo q eso solo sigue siendo ineficiente. Lo ideal seria descartar tambien los ataques diagonales y ya estariamos, cada posibilidad seria una solucion.
Saludos!!
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: migsantiago en 13 de Mayo de 2009, 20:42:00
Por fuerza bruta son 8x8x8x8x8x8x8x8 combinaciones porque cada reina puede ocupar 8 posiciones en su columna.

Total 16,777,216 combinaciones.
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: gera en 13 de Mayo de 2009, 21:05:45
Ahh, trampa ahi!! jaja. Eso es fuerza no tan bruta jeje. Ahi estas descartando que las reinas se ataquen por columnas. Y si aplicas el metodo de permutar un arreglo para evitar q tambien se ataquen por filas? supongo q te ahorrarias muchos ciclos. :wink:
saludos!
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: migsantiago en 13 de Mayo de 2009, 21:23:53
Oye tienes razón  :D

Pero bueno, haría la actualización el fin de semana jeje
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: jgpeiro06 en 14 de Mayo de 2009, 11:29:24
Citar
Yo tengo algo pensado para descartar todas las posibilidades donde las reinas se atacan por filas o columnas
Pues creo que seria interesante que participases. De momento los dos algoritmos que hay publicados solo "eliminan" la posibilidad de que dos reinas estén en la misma fila, o columna, según se mire. Pero si tu algoritmo evita ambos casos a la vez sera mucho más rápido...
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: migsantiago en 15 de Mayo de 2009, 17:10:14
Hola Jgpeiro

Quise probar tu código en mplab con ccs pero no lo pude compilar. CCS me envía un error de que falta agregar #device al código. Elegí un PIC24 y puse el reloj a 120MHz pero aún así no me dejó compilar, ¿qué me está faltando?

Yo estoy probando mi programa pero el pic16f877a corriendo a 120MHz (overclocked) está en plena desventaja frente a tu PIC24  :D

Quiero compilarlo para PIC24 pero no tengo idea de cómo lo lograste.  :( Nunca he usado PIC24.

Edito: Te adelanto que mi PIC16 logra barrer las casi 17 millones de combinaciones en 18 minutos aproximadamente corriendo a 120MHz. No ha terminado la simulación porque mi pc es lenta, pero es un estimado a partir de una pausa que hice en la simulación...

(http://img35.imageshack.us/img35/9867/reinasf.th.jpg) (http://img35.imageshack.us/img35/9867/reinasf.jpg)
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: gera en 15 de Mayo de 2009, 19:05:21
Cita de: jgpeiro06 en 14 de Mayo de 2009, 11:29:24
Citar
Yo tengo algo pensado para descartar todas las posibilidades donde las reinas se atacan por filas o columnas
Pues creo que seria interesante que participases. De momento los dos algoritmos que hay publicados solo "eliminan" la posibilidad de que dos reinas estén en la misma fila, o columna, según se mire. Pero si tu algoritmo evita ambos casos a la vez sera mucho más rápido...


Me encantaria participar, pero estoy muy corto de tiempos. Estoy preparando 2 materias de la facu bastante pesaditas y no tengo tiempo para sentarme a codear. Me hago ratos para pasar por el foro y tirar una q otra idea, pero de verdad se me complica.
Y hablando de tirar ideas, les comento rapidito un par de ideas que se me ocurrieron a ver si las pueden aplicar en sus algoritmos. La primera es la que ya mencione:
Cada reina tiene asignada una columna y una fila (de primera podrian estar posicionadas ocupando la diagonal principal). Y para encontrar una nueva posicion donde no se ataquen por filas o columnas, basta con permutar dos filas (o columnas). Entonces de cada permutacion obtendriamos un nuevo tablero donde las reinas no se atacan por filas ni por columnas.
Ademas para descartar una q otra posibilidad, podriamos chequear que en los casilleros adyacentes donde haya una reina, no haya otra. Ningun ser humano colocaria dos reinas pegadas mientras resuelve el problema.. por q nuestro algoritmo tendria q hacerlo? :wink:

Saludos!!!
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: omix en 18 de Mayo de 2009, 16:39:40
Hola a todos,
espero no llegar tarde, he conseguido sacar un ratillo libre para realizar la implementación del algoritmo, lo adjunto para quien quiera echarle un vistazo.
Para buscar las soluciones he usado la tecnica de programación de backtraking, el algoritmo está realizado en C para CCS en un PIC18F, en concreto lo he hecho para el 18F4520@20Mhz. He realizado la simulación con proteus y las 92 soluciones las encuentra en aproximadamente 24 segundos imprimiendo el tablero con la solución por la usart, sin imprimir nada tarda aproximadamente 8 segundos.

Un saludo.
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: migsantiago en 18 de Mayo de 2009, 17:27:05
Wow, creo que ya hay un ganador.

Oye Omix, ¿dónde puedo investigar sobre el algoritmo backtracking y árboles? Tu tiempo de búsqueda es excelente.
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: Nocturno en 18 de Mayo de 2009, 17:39:05
¡Mierda!, ya ha salido y no me ha dado tiempo  :D

Estaba convencido que una solución con recursividad era la solución más rápida y de hecho la tengo medio implementada. Pero no me ha dado tiempo a terminarla.

Felicidades por la implementación Omix. De todas formas no voy a mirar cómo lo has hecho por si me da tiempo a publicar la mía mañana.
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: migsantiago en 18 de Mayo de 2009, 17:43:38
¿Recursividad en CCS? ¿Se puede?  :shock:
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: omix en 18 de Mayo de 2009, 17:46:09
Hola migsantiago,
en la wikipedia puedes encontrar algo más de información sobre como funciona los algoritmos de backtracking (vuelta atras), te dejo el enlace:
http://es.wikipedia.org/wiki/Backtracking

Tambien puedes encontrar información, en la web del profesor que me dio clases de algoritmos y estructuras de datos en su dia.

http://dis.um.es/~nmarin/index07-08.html

Busca el apartado de teoria de algoritmos y estructuras de datos, ahi podras encontrar información sobre las diferentes tecnicas de programación, entre otras la de backtracking.

Un saludo.
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: migsantiago en 18 de Mayo de 2009, 18:27:03
Enterado Omix, gracias.
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: Nocturno en 19 de Mayo de 2009, 02:32:35
No soy capaz de simular mi programa en MPLAB para ver cuánto tarda con el Stopwatch. Lo compila bien, pero cuando le doy al Play del debugger me sale esto:
CORE-E0003: Trap due to unimplemented RAM memory access, occurred from instruction at 0x00020a
CORE-E0003: Trap due to unimplemented RAM memory access, occurred from instruction at 0x0002de

El debugger se queda clavado con ese error en la primera línea del programa:
#device PIC24FJ256GA110

¿Sabéis cómo se resuelve?

EDITADO
Ya lo he resuelto. Por alguna razón no es capaz de simular programas con el 24F; lo he cambiado por un 18F y ya veo los printf en la ventana del debugger.
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: Nocturno en 19 de Mayo de 2009, 08:03:10
¡Buahhhhhhhhhhhhhhhh  :( :( :( :( !

Mi gozo en un pozo.

Acabo de terminar el algoritmo en DEV-C para PC y funciona que te cagas.
Cuando me he ido a CCS  a compilarlo me dice: "Error 69: Recursion not permited"

¡Me cago en su puta madre, después de tanto curro  :5] :5] :5] !. Y mira que ya andaba con la mosca tras la oreja después del mensaje de Migsantiago.

En fin, aquí no tengo C30 para probarlo, así que esta noche lo probaré en casa a ver si consigo que funcione en C30 al menos.

Os dejo aquí el programa por si alguien quiere probarlo y puede medir el tiempo que tarda.

Dejo también el programa REINAS.EXE que funciona en un PC con Windows y obtiene todas las soluciones a velocidad de vértigo.
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: BrunoF en 19 de Mayo de 2009, 14:53:38
:D :D

Lástima Mano..El CCS es un compilador que no permite recursividad. El C18 y C30 sí lo hacen. Vas a tener que migrar código o encontrar la forma de hacerlo sin recursividad...:)

Me gustó el algoritmo. Está sencillo.

Saludos.
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: Nocturno en 19 de Mayo de 2009, 15:25:38
Ahora ya soy feliz  :-/ :-/ :-/

El C30 es completamente compatible con el programa que había escrito en DEV-C para Windows y ha compilado a la primera.

Y mi felicidad ha crecido exponencialmente cuando he podido comprobar el tiempo que tarda mi rutina: ¡¡¡ sólo tarda 152ms en encontrar las 92 soluciones!!!, para ello necesita ejecutar un total de 9.134.399 ciclos de instrucción.

Aquí una captura de un PIC24 corriendo a 120MHz.
(http://img145.imageshack.us/img145/5536/reinas.jpg)

Os adjunto el proyecto en MPLAB y el fuente con un while(1) al final para poder probarlo tal y como yo lo he probado.

 :-/ :-/ :-/ :-/


Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: omix en 19 de Mayo de 2009, 15:35:24
Enhorabuena nocturno!!

tendre que probar mi algoritmo en C30 con un PIC24 a ver cuanto tarda en ejecutarse, que como es logico deberia de ejecutarse mucho más rapido a ser un micro de 16bits y tener que ejecutar menos instrucciones.

Un saludo.
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: Nocturno en 19 de Mayo de 2009, 15:41:46
Pues sí, pruébalo, que me come la curiosidad por saber el tiempo que tarda.
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: Nocturno en 19 de Mayo de 2009, 16:30:04
Omix, he modificado tu programa para poder compilarlo con C30 y PIC24 y este es el resultado:
(http://img145.imageshack.us/img145/6720/reinasomix.jpg)

Te dejo el proyecto y el fuente, no sea que haya cometido algún error.
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: jgpeiro06 en 19 de Mayo de 2009, 16:42:23
Bien!, este era el objetivo del concurso, implementar algoritmos y descubrir nuevos. Yo no conocía el backtracking, pero si sabia que daba igual que optimizase mi código o no, que para reducir enormemente el tiempo de ejecución (si se podia) había que cambiar de algoritmo. Las implementaciones de omix y de nocturno son validas. El concurso termina mañana, y somos 4 participantes. Colgare una pequeña tabla con 3 o 4 caracteristicas y cada uno votara los códigos, incluyendo el suyo(pero este ultimo no sera valido). Después sumaremos puntos y entregare los premios.

La verdad me ha sorprendido mucho que haya tanta diferencia entre implementar un algoritmo u otro. Eso me hace ver lo importante que es dedicar tiempo a escoger "el buen camino" para resolver un problema antes de lanzarse a resolverlo.
¿De verdad no soporta la recursividad el CCS?¿ni para los PIC de 16 bits? Si es así, yo no utilizaría más ese compilador. ¿Porque la gente lo utiliza tanto si luego, según leo,  tiene más limitaciones que el C30?
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: migsantiago en 19 de Mayo de 2009, 16:58:58
Hey Jgpeiro

Hace unos días encontré estas tablas de comparación entre los compiladores más populares de C, talvez resuelvan tu duda de porqué se usa más CCS que C18 o C30 de Microchip.

http://www.todopic.com.ar/foros/index.php?topic=25946.msg212271#msg212271

A este ritmo creo que quedaré en 4to lugar con mi algoritmo súper lento  :D
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: omix en 19 de Mayo de 2009, 17:02:22
Nocturno, he intentado simular mi algorimo, pero no estoy seguro de si lo estoy haciendo bien o no, porque me sale un warning a la hora de simular, es este "CORE-E0004: Trap due to unimplemented FLASH memory access, occurred from instruction at 0x000982". Hay que configurar algo?.
De todas formas lo he simulado y comentando la parte de la impresión de las soluciones me sale un tiempo de 85ms aprox. y con la impresion unos 237ms, que es lo que has obtenido tu.

Un saludo.
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: Nocturno en 19 de Mayo de 2009, 17:42:39
Tienes razón, Omix, quitando los printf tu algoritmo se convierte en super-rápido. Enhorabuena campeón.
No sé porqué sale ese error CORE-E0004, ni idea.

Jgpeiro, te confieso que también he sufrido una terrible decepción con CCS al comprobar que ni siquiera compila si hay recursividad.
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: BrunoF en 19 de Mayo de 2009, 18:03:33
Cita de: jgpeiro06 en 19 de Mayo de 2009, 16:42:23
¿De verdad no soporta la recursividad el CCS?¿ni para los PIC de 16 bits? Si es así, yo no utilizaría más ese compilador. ¿Porque la gente lo utiliza tanto si luego, según leo,  tiene más limitaciones que el C30?

Era sabido que el CCS no soporta recursividad...He aquí lo que yo había leído hace rato:

http://www.ccsinfo.com/content.php?page=newcompilercomp
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: cerebro en 19 de Mayo de 2009, 18:26:20
 :shock: mis ojos ven mal o dice que el CCS permite sobrecarga de funciones??.
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: BrunoF en 19 de Mayo de 2009, 18:29:26
Eso parece! No lo probé...
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: Nocturno en 20 de Mayo de 2009, 14:44:47
¡Lo logré!

Reconozco que picado por la asombrosa velocidad del algoritmo de Omix no he parado de darle vueltas al coco a ver de dónde podía recortar ciclos de programa hasta que se me ocurrió la idea.

Os dejo el algoritmo en su nueva versión y una captura de pantalla del Stopwatch: ¡¡¡77ms en 4671897 ciclos!!!.
(http://img43.imageshack.us/img43/5536/reinas.jpg)

De todas formas, estoy convencido que en cuanto Omix le eche una pensada al suyo batirá el record, yo ya no tengo de donde recortar.
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: omix en 20 de Mayo de 2009, 15:05:04
Cita de: Nocturno en 20 de Mayo de 2009, 14:44:47
¡Lo logré!

Reconozco que picado por la asombrosa velocidad del algoritmo de Omix no he parado de darle vueltas al coco a ver de dónde podía recortar ciclos de programa hasta que se me ocurrió la idea.

Os dejo el algoritmo en su nueva versión y una captura de pantalla del Stopwatch: ¡¡¡77ms en 4671897 ciclos!!!.
(http://img43.imageshack.us/img43/5536/reinas.jpg)

De todas formas, estoy convencido que en cuanto Omix le eche una pensada al suyo batirá el record, yo ya no tengo de donde recortar.

jeje, superar ese tiempo va a ser dificil, pero lo le voy a echar un vistazo a algoritmo a ver que se me ocurre.
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: migsantiago en 20 de Mayo de 2009, 16:02:47
Apúrense porque ya es 20 de mayo y el tiempo está corto.  :mrgreen:
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: omix en 20 de Mayo de 2009, 16:59:42
Bueno haciendo unas minimas modificaciones en el código he podido reducir un poco más el tiempo en encontrar las 92 soluciones. ¡¡Ahora tarda 72ms!!.
(http://img217.imageshack.us/img217/3253/8reinas.th.jpg) (http://img217.imageshack.us/my.php?image=8reinas.jpg)

Por otro lado viendo como son las soluciones, se me ocurre otra posible optimización que podria reducir más aun el tiempo de busqueda de las soluciones, pero ahora mismo no estoy lo suficientemente inspirado para que se me ocurra como implementarlo.

Os dejo el código, aunque sigue siendo el mismo, solo lo he reorganizado.

Saludos.


Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: jgpeiro06 en 20 de Mayo de 2009, 17:23:45
Se que este caso no cuenta, ya que esto es un concurso y se premia la velocidad. Pero como programador se el tiempo que dedicamos a revisar nuestros programas con el fin del recortar de aquí y de allá. Y creo que es un gran error sacrificar la simplicidad de un código por ganar algo de tiempo de ejecución (a no ser que sea necesario). Ademas los códigos excesivamente optimizados se vuelven difíciles de manejar, mantener y ampliar, sobre todo si abandonamos el proyecto un tiempo... Una vez leí que "la optimización excesiva es una muerte rápida", y creo que es algo muy cierto, y con los resultados que esta mostrando este concurso creo que queda claro que es mejor intentar reducir el tiempo de un programa con papel y lápiz (o con google y wikipedia) que cambiando/reordenando lineas de código.

Por cierto nocturno, he visto tu código por encima y he visto que tiene muchos comentarios. No los he leído por que aun no he tenido tiempo, pero lo haré. Pero creo que tanto comentario hará tu algoritmo más fácil de entender y te llevarás el premio al algoritmo más sencillo...Por cierto, ¿Alguien ha usado alguna vez herramientas de documentación automática, tipo doxygen?

Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: migsantiago en 20 de Mayo de 2009, 17:39:25
Hace algunos ayeres Diego Redpic nos hablaba de Doxygen...

http://www.todopic.com.ar/foros/index.php?topic=19081.0
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: Nocturno en 20 de Mayo de 2009, 18:11:25
Nueva versión: "Reinas Vista"
(http://img43.imageshack.us/img43/8356/reinasy.jpg)

Te lo advierto, Omix, no sigas, que tengo que trabajar  :D
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: omix en 20 de Mayo de 2009, 18:37:33
Cita de: Nocturno en 20 de Mayo de 2009, 18:11:25
Nueva versión: "Reinas Vista"
(http://img43.imageshack.us/img43/8356/reinasy.jpg)

Te lo advierto, Omix, no sigas, que tengo que trabajar  :D


Tranquilo, hoy no me encuentro muy fino para ponerme a pensar como implementar la optimización que tengo en mente. Si lo llego hacer, aunque este fuera de concurso lo postearé.
Asi que enhorabuena Nocturno, eres el ganador.
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: Nocturno en 20 de Mayo de 2009, 18:44:31
Claro que soy ganador, he ganado el entusiasmo por un algoritmo que hace tiempo que no sentía, y también he ganado otra cosa: el descubrimiento de la técnica del backtracking gracias a ti.

Creo que si alguien merece un premio es jgpeiro por darnos la oportunidad de disfrutar de esta manera.

Por cierto, acabo de caer en la cuenta de que no he explicado en qué consisten las optimizaciones para reducir el tiempo. Son fundamentalmente dos las más importantes:
1. Buscar sólo la mitad de soluciones
En lugar de generar la semilla en las 8 celdas de la primera fila, sólo genero 4 semillas. A las 46 soluciones encontradas les hago el espejo y obtengo las otras 46 sin invertir nada en tiempo de cálculo.
2. Crear un array nuevo
La posición de la reina en el tablero viene dada por un bit dentro de un byte. En una parte del programa, me interesa saber qué posición ocupa. En el algoritmo original recorría el byte hasta encontrarlo.
En el algoritmo optimizado, almaceno su posición en otro array, así que sólo tengo que leerlo.

Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: jgpeiro06 en 21 de Mayo de 2009, 16:23:24
Bueno, creo que ya es momento de empezar con las votaciones. Os pido disculpas por el retraso, ya que estaban previstas para los dias 20 a 25, y va a ser del 21 al 28, así tendremos suficiente tiempo para evaluar los codigos de cada concursante.

                                 Categorias
Concursantes              Sencillo          Lioso             Rapido          Robusto
migsantiago                   X                  X                 X                  X
jgpeiro                          X                  X                 X                  X
omix                             X                  X                 X                  X
nocturno                       X                  X                 X                  X

Cada concursante deberá rellenar la tabla con números del 1 al 4. Los criterios de cada categoría están descritos en el primer post de este hilo.
El dia 28 se sumaran los puntos y se entregaran los increíbles premios valorados en miles de millones de dollarsss.
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: migsantiago en 21 de Mayo de 2009, 17:32:01
Dejo mi opinión sobre los demás y sobre mi  :mrgreen:

                                 Categorías
Concursantes              Sencillo          Lioso             Rápido          Robusto
migsantiago                   4                  3                 -4  :D            1
jgpeiro                          3                  4                 1                  1
omix                             1                  1                 4                  4
nocturno                       2                  1                 4                  4

Asumo que...

4 = súper
3 = muy
2 = algo
1 = nada

y pues ya sabrán que opino al decir que la rapidez de mi algoritmo es -4  :D
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: Nocturno en 21 de Mayo de 2009, 17:48:11
Las mías:
                                 Categorías
Concursantes              Sencillo          Lioso             Rápido          Robusto
migsantiago                   4                  1                 1                  x
jgpeiro                          4                  1                 1                  x
omix                             2                  3                 4                  x

No sé cómo valorar la robustez.

Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: jgpeiro06 en 21 de Mayo de 2009, 18:34:49
Citar
y pues ya sabrán que opino al decir que la rapidez de mi algoritmo es -4
Quizas sea lento, pero es un algoritmo facil de entender y eso siempre es positivo. Ademas, voy a descalificar a nocturno y a omix por utilizar un algorimo mas rapido y no avisarnos de nuestro fracaso!!!

Citar
migsantiago                   4                  1                 1                  x
jgpeiro                          4                  1                 1                  x
omix                             2                  3                 4                  x
nocturno, no vale escaquearse, tienes que puntuarte a ti mismo también, así si ganas te acusaremos de imparcialidad...jajaja

Sobre como puntuar la robustez... bueno, la idea inicial era presentar un algoritmo para cada categoria, pero no ha habido suficientes participantes...La categoria de robustez pretendia probar que programas estaban mejor preparados frente a un fallo en alguna instruccion de la ROM. Un algoritmo robusto debe chequear los resultados de las rutinas y si no cumplen unos criterios volver a probar, o utilizar rutinas distintas...... se me esta resultando curioso,¿creeis que seria interesante un nuevo mini-concurso con el objetivo crear algoritmos robustos?
De momento podemos puntuar esa categoria a ojo, bajo el criterio de programa robusto de cada uno.

Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: Nocturno en 21 de Mayo de 2009, 19:20:40
Naaaaa, paso de puntuarme a mí mismo, que soy un hijoputa poniendo notas  :D
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: migsantiago en 27 de Mayo de 2009, 16:57:43
Bu, faltan los votos de Omix y del organizador Jgpeiro.
Título: Re: Mini-Concurso de programacion 2. Las 8 reinas.
Publicado por: jgpeiro06 en 27 de Mayo de 2009, 17:59:05
Citar
Bu, faltan los votos de Omix y del organizador Jgpeiro.
Si, este jgpeiro...que vergüenza...
Mañana la entrega de premios. La ceremonia de apertura será en un hotel de lujo en Tokio, el Shumusuka,  planta 23. Allí nos vemos.

Concursantes              Sencillo          Lioso             Rapido          Robusto
migsantiago                   2                  2                 1                  3
jgpeiro                          3                  1                 1                  2
omix                             2                  2                 3                  2
nocturno                       2                  1                 4                  3

1 bien... 4 mejor