création
authorDenise sur sakamain <sekhmet@sakamain.(none)>
Sun, 21 Dec 2014 11:07:15 +0000 (12:07 +0100)
committerDenise sur sakamain <sekhmet@sakamain.(none)>
Sun, 21 Dec 2014 11:07:15 +0000 (12:07 +0100)
cube.c [new file with mode: 0644]

diff --git a/cube.c b/cube.c
new file mode 100644 (file)
index 0000000..f170bd2
--- /dev/null
+++ b/cube.c
@@ -0,0 +1,464 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#define N              3               /* Taille du cube */
+#define Taille         N*N*N   /* Nombre de petits cubes */
+//#define Nb_sit       1               /* Nombre de situations de départ : pour 2, une seule */
+#define Nb_sit 3               /* Nombre de situations de départ : pour 3 et 4, il y en a 3 */
+#define D              3               /* On travaille en 3 dimensions */
+                                               /* NB : pas adapté à faire autre chose que 3 dimensions ! 
+                                               Ou en tous cas pas sans un peu de boulot */
+#define STOP           0               /* STOP : est-ce qu'on s'arrête après avoir trouvé une solution.
+                                               Quand STOP vaut 0, il teste tout ! */
+
+#define V              0               /* Mode verbeux (attention les zyeux) */
+
+/* Pour changer la taille : changer N, changer la séquence des longueurs (en dessous),
+et changer l'initialisation (voir le main) */
+
+// nombre de situations
+static int nb_tests = 0 ;
+
+/* La séquence des longueurs : spécifique au cube */
+/* N = 3 */
+int sequence[Taille] =
+{ 3, 0, 0, 1, 1, 2, 0, 1, 2, 0, 1, 1, 2, 0, 2, 0, 1, 1, 1, 2, 0, 2, 0, 2, 0, 2, 0 } ;
+
+
+/* N = 2 */
+/*int sequence[N*N*N] =
+{ 2, 0, 1, 1, 1, 1, 1, 1} ;
+*/
+/* N = 4 */
+/*
+int sequence[Taille] = 
+{
+4, 0, 0, 0, 1, 1, 3, 0, 0, 3, 0, 0, 1, 2, 0, 2, 0, 1, 1, 1, 1, 3, 0, 0, 3, 0, 0, 1, 1, 1, 2, 0,
+1, 3, 0, 0, 1, 3, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 0, 2, 0, 1, 3, 0, 0, 1, 1, 1, 1, 1, 2, 0
+} ;
+*/
+
+/* La liste des orientations possibles */
+int orientations[2*D][D] = 
+{
+{0, 0, 1},  {0, 0, -1}, { 0, 1, 0},  {0, -1, 0},
+{1, 0, 0},  {-1, 0, 0}
+} ;
+
+
+
+
+/*** Structure ***/
+
+
+typedef struct Situation {
+       int Cube[N][N][N] ;     /* Le cube, rempli d'entiers */
+       int X ;                 /* Coord du dernier cube qu'on y a mis */
+       int Y ;
+       int Z ;
+       int Orientation[D] ;    /* L'orientation du dernier cube : par ex (0, +1, 0) */
+       int Num ;               /* Le numéro du dernier cube qu'on y a mis */
+} t_sit ;
+
+int taillesituation=sizeof(struct Situation) ;
+
+
+/*********************************************/
+/*** Affichage ***/
+
+/* Affichage du cube */
+void affiche_cube(int (*cube)[N][N][N])
+{
+       int i, j, k ;
+       for(k=0;k<N; k++)
+       {
+               printf("*** z=%i :\n", k) ;
+               for(j=0;j<N;j++)
+               {
+                       for(i=0;i<N; i++)
+                               printf("%i\t", (*cube)[i][j][k]) ;
+                       printf("\n") ;
+               }
+               //printf("\n") ;
+       }
+}
+
+/* Affichage d'une situation */
+void affiche_situation(t_sit* situation)
+{
+       printf("-> Cube : \n") ;
+       affiche_cube(&situation->Cube) ;
+       printf("-> Coordonnées du dernier cube : %i, %i, %i\n", situation->X, situation->Y, situation->Z) ;
+       printf("-> Numéro du dernier cube : %i\n", situation->Num) ;
+       printf("-> Orientation : %i, %i, %i\n", 
+               situation->Orientation[0], situation->Orientation[1], situation->Orientation[2]) ;
+
+       return ;
+}
+
+/********************************************/
+/*** Fonctions d'initialisation diverses ***/
+
+/* Vérifie que la séquence a la bonne taille */
+int verif_sequence(int* seq)
+{
+       int somme=0 ;
+       int i ;
+
+       for(i=0; i<Taille; i++)
+       {
+               somme+=sequence[i] ;
+       }
+       // test de la taille
+       if(somme != Taille)
+       {
+               printf("verif_seq : somme = %i, Taille = %i\n", somme, Taille) ;
+               return 0 ;
+       }
+
+       //test des zéros bien placés
+       int j ;
+       j=0 ;
+       for(i=0; i<Taille; i++)
+       {       
+               if(seq[i] !=0)
+               {
+                       if(j !=0) //raté
+                       {       
+                               printf("verif_seq : j=%i, i=%i, seq[%i] = %i\n", j, i, i, seq[i]) ;
+                               return 0 ;
+                       }
+                       j=seq[i] ;
+               }
+               j-- ;
+       }
+       return 1 ;
+}
+
+/* Prépare une situation initialisée */
+t_sit * initialise_sit()
+{
+       int i, j, k ;
+
+       t_sit * situation ;
+       situation = malloc(taillesituation) ;
+
+       //  le cube 
+       for(i=0; i<N; i++)
+       for(j=0; j<N; j++)
+       for(k=0; k<N; k++)
+               situation->Cube[i][j][k] = 0 ;
+
+       // l'orientation : rien pour le moment
+       for(i=0; i<D; i++)
+       {
+               situation->Orientation[i] = 0 ;
+       }
+       // le reste
+       situation->X = 0 ;
+       situation->Y = 0 ;
+       situation->Z = 0 ;
+       situation->Num = 0 ;    
+       
+       return situation ;
+
+}
+
+
+/* Effectue une copie de la situation. */
+void copie_sit(t_sit *originale, t_sit *nouvelle) 
+{
+       int i, j, k ;
+       // copie du cube 
+       for(i=0; i<N; i++)
+       for(j=0; j<N; j++)
+       for(k=0; k<N; k++)
+               nouvelle->Cube[i][j][k] = originale->Cube[i][j][k] ;
+       
+       // copie de l'orientation
+       for(i=0; i<D; i++)
+       {
+               nouvelle->Orientation[i] = originale->Orientation[i] ;
+       }
+       // copie du reste
+       nouvelle->X = originale->X ;
+       nouvelle->Y = originale->Y ;
+       nouvelle->Z = originale->Z ;
+
+       nouvelle->Num = originale->Num ;
+
+       return;
+}
+
+
+
+/* Prépare une situation de départ : on donne un point de départ du cube et l'orientation, 
+et la fonction "place" la première séquence dans le cube */
+/* depart est censée être une situation déjà initialisée */
+int prepare(t_sit * depart, int x, int y, int z, int* orientation)
+{
+       int longueur, i, xp, yp, zp ;
+
+       // la longueur de la première séquence
+       longueur = sequence[0] ;
+
+       if(V)
+               printf("Initialisation : longueur de la première séquence : %i\n", longueur) ;
+
+       // coordonnées du cube à mettre
+       xp = x ;
+       yp = y ;
+       zp = z ;
+
+       for(i=0; i<longueur; i++)
+       {
+               // coordonnées valides ? (pas hors du cube)
+               if(hors_cube(xp, yp, zp) )
+               {
+                       printf("Initialisation : les coord sont hors du cube ! Pas normal !\n") ;
+                       return 0 ;
+               }
+               depart->Cube[xp][yp][zp] = i+1 ;
+               if(i != longueur -1)
+               {
+                       xp += orientation[0] ;
+                       yp += orientation[1] ;
+                       zp += orientation[2] ;
+               }
+       }
+       if(V)
+               printf("Initialisation : cubes placés\n") ;
+
+       depart->Num = longueur ;
+       // copie de l'orientation
+       for(i=0; i<D; i++)
+               depart->Orientation[i] = orientation[i] ;
+
+       // la position du dernier cube
+       depart->X = xp ;
+       depart->Y = yp ;
+       depart->Z = zp ;
+
+       return 1 ;
+}
+
+/***********************************************/
+/*** Manipulation du cube ***/
+
+// Est-ce que les coordonnées sont hors du cube ?
+int hors_cube(int x, int y, int z)
+{
+       return (x<0 || x>=N || y<0 || y>=N || z<0 || z>=N) ;
+}
+
+// Vérifie que deux orientations sont compatibles, ie si elles sont bien différentes (sans compter le sens)
+// ex : (1, 0, 0) et (0, -1, 0) ok, mais pas (1, 0, 0) et (-1, 0, 0)
+int valide_orientations(int* orient1, int* orient2)
+{
+       return (abs(orient1[0]) != abs(orient2[0]) 
+               || abs(orient1[1]) != abs(orient2[1]) 
+               || abs(orient1[2]) != abs(orient2[2]) ) ; 
+}
+
+
+/* teste de placer les cubes suivants selon l'orientation donnée */
+/* Renvoie une situation t_sit. Si ça plante, on renvoie la situation, mais avec Num=-1 */
+t_sit * tester_cas(t_sit * situation, int * nouvelle_orientation)
+{
+       int i, longueur ;
+       int x, y, z, num ;
+
+       // incrémentation du nombre de tests
+       nb_tests++ ;
+
+       // copie de la situation actuelle
+       t_sit *situation2 ;
+       situation2 = malloc(taillesituation) ;
+       copie_sit(situation, situation2) ;
+
+       if(V)
+       {
+               printf("Tester_cas : situation actuelle : \n") ;
+               affiche_situation(situation) ;
+               printf("-----\n") ;
+
+       }
+       // quelle est la longueur de la prochaine séquence ?
+       longueur = sequence[situation->Num] ;
+       
+       if(V)
+               printf("Tester_cas : longueur de la séquence à appliquer : %i\n", longueur) ;
+       if(longueur ==0)
+       {
+               printf("Tester_cas : problème >_< : la séquence à appliquer est de longueur nulle...\n") ;
+               printf("Situation obtenue :\n") ;
+               affiche_situation(situation) ;
+       }
+
+       x = situation2->X ;
+       y = situation2->Y ;
+       z = situation2->Z ;
+       num = situation2->Num ;
+
+       for(i=0; i<longueur; i++)
+       {
+               // calculer les nouvelles coordonnées
+               x += nouvelle_orientation[0] ;
+               y += nouvelle_orientation[1] ;
+               z += nouvelle_orientation[2] ;
+
+               if(hors_cube(x,y,z) || situation2->Cube[x][y][z]>0)
+               {
+                       if(V)
+                       {
+                               printf("Tester_cas %i : l'orientation (%i, %i, %i) ne marche pas\n", i, 
+                                       nouvelle_orientation[0], nouvelle_orientation[1], nouvelle_orientation[2]) ;
+                               printf("Nouvelles coordonnées : %i, %i, %i\n", x, y, z) ; 
+                       }
+                       situation2->Num = -1 ;
+                       return situation2 ;             
+               }
+               // c'est bon !
+               if(V)
+                       printf("Tester_cas %i : l'orientation (%i, %i, %i) marche\n", i, 
+                                       nouvelle_orientation[0], nouvelle_orientation[1], nouvelle_orientation[2]) ;
+               num++ ; // il ne faut pas oublier que num commence à 0
+               situation2->Cube[x][y][z] = num ;
+
+       }
+       
+       if(V)
+               printf("Tester_cas : tout bon\n") ;
+
+       // tout a été bon jusque là, on remet dans la structure
+       situation2->X = x ;
+       situation2->Y = y ;
+       situation2->Z = z ;
+       situation2->Num = num ;
+
+       // copier la nouvelle orientation
+       for(i=0; i<D; i++)
+               situation2->Orientation[i] = nouvelle_orientation[i] ;
+
+       if(V)
+       {
+               printf("Nouvelle situation : \n") ;
+               affiche_situation(situation2) ;
+               printf("-----\n") ;
+       }
+
+       return situation2 ;
+}
+
+/********** La résolution **********/
+
+
+int resoudre(t_sit * situation)
+{
+       int i ;
+       int reussi ;
+       t_sit *retour ;
+
+       // si on est arrivé à la fin de la séquence 
+       if(situation->Num == Taille)    
+       {
+               printf("Solution trouvée, youhouuuu \\o/\n\n") ;
+               affiche_cube(&(situation->Cube)) ;
+               printf("--------------\n") ;
+               printf("Nombre de cas testés jusque là : %i\n",nb_tests) ;
+               if(STOP)
+                       return 1 ;
+               else
+                       return 0 ;
+       }
+
+       for(i=0; i<6; i++)
+       {
+               // est-ce que cette orientation est valide ?
+               if(valide_orientations(situation->Orientation, orientations[i]))
+               {
+                       if(V)
+                               printf("Test de l'orientation : %i, %i, %i\n", 
+                                       orientations[i][0], orientations[i][1], orientations[i][2]) ;
+
+                       // tester ce cas précis
+                       retour = tester_cas(situation, orientations[i]) ;
+                       if(retour->Num ==-1)
+                       {
+                               if(V)
+                                       printf("Test échoué ! On passe à la suite\n") ;              
+                       }
+                       else
+                       {
+                               // on récurre
+                               reussi = resoudre(retour) ;
+                               if(reussi)
+                                       return 1 ;
+                               // si pas réussi, il faut tester d'autres orientations !
+                       }
+               }
+       }
+       if(V)
+               printf("Toutes les orientations sont testées.\n") ;
+       return 0 ;
+}
+
+
+
+/****************************************************/
+
+int main(argc, argv)
+{
+       int i ;
+       
+       if(!verif_sequence(sequence))
+       {
+               printf("La séquence des cubes n'est pas valide, c'est mal barré !\n") ;
+               return 1 ;
+       }
+
+       // Créer les situations de départ
+
+       /* Situations de départ */
+       t_sit * situations_depart[Nb_sit] ;
+       
+       for(i=0; i<Nb_sit; i++)
+       {
+               situations_depart[i] = initialise_sit() ;
+       }
+
+
+       int orX[D] = {1,0,0} ;
+       /* Spécifique à la taille N donnée */
+       /* N = 3 */
+
+       prepare(situations_depart[0], 0, 0, 0, orX) ;
+       prepare(situations_depart[1], 0, 1, 0, orX) ;
+       prepare(situations_depart[2], 0, 1, 1, orX) ;
+
+       /* N = 2 */
+//     prepare(situations_depart[0], 0, 0, 0, orX) ;   
+       
+       /* Fin spécifique taille N donnée */
+
+       if(V)
+       {       
+               for(i=0; i<Nb_sit; i++)
+               {
+                       printf("-- Situation de départ %i --\n", i) ;
+                       affiche_situation(situations_depart[i]) ;
+               }
+               printf("----------\n") ;
+       }
+       /* Et c'est partiiiii i*/
+
+       for(i=0; i<Nb_sit; i++)
+       {
+               if(V)
+                       printf("---------\nTest de la situation de départ %i\n-----------\n",i) ;
+               resoudre(situations_depart[i]) ;
+       
+       }
+       printf("Nombre de cas testés au total : %i\n",nb_tests) ;
+       return 0 ;
+}