15 kwietnia 2012 (niedziela), 20:13:13

Programować każdy może (3)

Nie wiem czy jeszcze dziś potrafię, bo nie mam stosownego narzędzia - ale mam dowód, że kiedyś potrafiłem.

Napisałem to, ponieważ nie umiałem ułożyć układanki w pudełku, ale potrafiłem napisać program, który szukał rozwiązania.

 

Łamigłówka była elementem jakiejś fajnej gry przygodowej, którą A. zainstalowała na domowym iPadze, i której nie potrafiłem przejść, bo była właśnie ta łamigłówka. Programowanie zajęło mi z 8 godzin jak nic, przy czym dużo czasu kosztowało stworzenie środowiska do pisania w C (wyszło, że gcc na Linixie i vi jest nawłaściwsze), a dużo ponowne nauczenie się podstaw tego języka. Algorytm rekurencyjny był najmiejszym problemem.

Programowanie jest fajne!

 

#include 
#include 

#define DEBUG 2

#define NN 8
#define MM 6

int Lww = 0, Lwu =0;

struct Figura {
 int n;		// wielkosc w poziomie
 int m;		// wielkosc w pionie
 int F[NN][MM];	// wskaznik na tablice opisującą
 int EEi;		// wspolrzędna i punktu EE figury
 int PPi;		// położenie figury na planszy - współrzędna i punktu EE lub -1
 int PPj;		// jak wyżej dla drugiej współrzędnej
};

// #include "z2.h"

#define LICZBA_FIGUR 11

struct Figura FFF [LICZBA_FIGUR] = {
 { 1, 1, {		// #0 - pojedynczy kwadracik
   { 12 },
   },
 },

 { 3, 3, {		// #1 - odwrócone T 
  { 0, 0, 1 },		// uwaga: wiersze są pionami!
  { 1, 1, 1 }, 
  { 0, 0, 1 },
  },
 },

 { 3, 3, {		// #2 - krzyżyk
  { 0, 2, 0 },
  { 2, 2, 2 },
  { 0, 2, 0 },
  },
 },

 { 3, 3, {		// #3 takie M albo W - niebieskie schodki
   { 3, 3, 0 },
   { 0, 3, 3 },
   { 0, 0, 3 },
   },
 },

 { 2, 3, {		// #4 duże Gama - zielony, do górnego lewego rogu pasuje
   { 4, 4, 4 },
   { 4, 0, 0 },
   },
 },

 { 4, 2, {		// #5 takie Zet ale naciągnięte
   { 5, 0 },
   { 5, 5 },
   { 0, 5 },
   { 0, 5 },
   },
 },

 { 4, 2, {		// #6 T z przeciągniętym na prawo daszkiem
   { 6, 0 },
   { 6, 6 },
   { 6, 0 },
   { 6, 0 },
   },
 },

 { 3, 2, {		// #7 takie L ale żeby je wstawić w prawy dolny róg
   { 0, 7 },
   { 0, 7 },
   { 7, 7 },
   },
 },

 { 3, 3, {		// #8 - ??
   { 0, 8, 0 },
   { 8, 8, 0 },
   { 0, 8, 8 },
   },
 },

 { 1, 5, {		// #9 - pionowa pałka o dlugości 5 kratek
   { 9, 9, 9, 9, 9 },
   },
 },

 { 2, 3, {		// #10 - do wstawienia w prawy górny róg
   { 10,  0,  0 },
   { 10, 10, 10 },
   },
 },

};

void drukuj_tablice (int PP [NN][MM]);
void drukuj_figure (struct Figura F);


// najważniejsza i jedyna funkcja co kładze figurę na planszy i woła siebie dla nasztępnej figury

int wstaw_figure (int PPP[NN][MM], struct Figura FFF [LICZBA_FIGUR], int kk, int level) {
 int i, j, n, m, a, l;
 int Xi, Xj, Ei;
 int tmpEEi, tmpIIe;			// trudne zmienne wykorzystywane przy obróbce wciętych figur
 int PP[NN][MM];			// lokalna tablica z planszą
 struct Figura FF [LICZBA_FIGUR];	// lokalny zestaw figur wraz z ich stanem i położeniem

 Lww++;				// to jest statystyka dla ciekawych

 // Przekonany byłem, że w C może przenosić jako argumenty całe złożone struktury danyc...
 // ... to na pewno się da, ale ja nie wiem jak się to robi. A może to dało się w C++?
 // ... nie pamiętam, więc na głupka kopiuję nawet nie strncpy() ale for()

 for (j=0; j<MM; j++)		// naprawdę nie pamiętam, kiedy przekazuje się do funkcji...
   for (i=0; i<NN; i++)	// ... tablicę, a kiedy adres do tablicy
     PP[i][j] = PPP[i][j];	// ... wiec wolę skopiować aby mieć to lokalnie u siebie

 for (l=0; l<LICZBA_FIGUR; l++) {	// to też ma być lokalne a nie wiem czy jest
   FF[l].n = FFF[l].n;
   FF[l].m = FFF[l].m;
//  FF[l].F = FFF[l].F;		// tu kopiowany jest adres tych tablic z kształtem
   for (j=0; j<FFF[l].m; j++)	
     for (i=0; i<FFF[l].n; i++)	
       FF[l].F[i][j] = FFF[l].F[i][j];
   FF[l].EEi = FFF[l].EEi;
   FF[l].PPi = FFF[l].PPi;
   FF[l].PPj = FFF[l].PPj;
 }

 // początek analizy figur na planszy
 // czy da sie tą figure posadzić?

 // wyznacz współrzędne punktu X - a więc najwyżej położonego pustego punktu

 j=0; a=1;
 while ( a && j 1) {
   printf ("\n* * * * * * Wciśnij Enter * * * * *");
   getchar();
   system ("clear");	// czy nie ma jakiejś tańszej metody czyszczenia ekranu niż wołanie powłoki systemu?
 }

 if (DEBUG > 0) {
   printf ("\nPoziom: %i, figura: %i \n\nStan pola PP:", level, kk);
   drukuj_tablice (PP);

   printf ("\nTestowana figura: %i, rozmar: %i, %i Ei: %i\nKształt figury:", kk, FF[kk].n, FF[kk].m, FF[kk].EEi);
   drukuj_figure (FF[kk]);

   printf ("\nProba polożenia figury na Xi=%i Xj=%i", Xi, Xj);
 }

 if (a) {		// niemożliwe, aby nie było pustego punktu - poważnie?
   if (DEBUG > 0) {
     printf ("\n* ponoć wszystkie pola są zajęte? dziwne! Coś nie tak wieć wciśnij Enter!");
     getchar ();
   }
   return -2;		// znak, że błąd w danyc, sterowaniu, albo algorytmie
 }

 // sprawdzam, czy figura FF[kk] wlezie w obszar PP

 if (Xi + FF[kk].n - FF[kk].EEi > NN) {	// nie wlezie w obszaw pola PP
   if (DEBUG > 0) 
     printf ("\n- figura nie mieści sie w poziomie z prawej");
   return -17;
 }
 if (Xi - FF[kk].EEi < 0) {
   if (DEBUG > 0) 
     printf ("\n- figura nie mieści się z lewej");
   return -18;
 }
 if (Xj + FF[kk].m > MM) { 
   if (DEBUG > 0) 
     printf ("\n- figura mie mieści się pionie");
   return -19;
 }

 // sprawdzam, czy da się położyć figurę aby nie zawadzać o inne, już położone

 tmpEEi = FF[kk].EEi; a=1;		// tmpEj - bo pierwsza linia jest krótsza o blade znaki figury
 tmpIIe = 0;
 j = Xj; m = 0;			// przebieganie po drugim wymiarze
 while (a && m < FF[kk].m) {
   i = Xi - tmpIIe; n = tmpEEi;  
   while (a && n < FF[kk].n) {
     if (PP[i][j] && FF[kk].F[n][m]) {	// czy nakładają się pola z PP planszy i F figury
       a = 0; break;
     }
   i++; n++;
   }
   if (!a)
     break;
   tmpIIe = FF[kk].EEi;
   tmpEEi = 0;				// druga linia analizowana normalnie

   j++; m++;
 }

 if (!a) {				// nakładają się, więc koniec procedury
   if (DEBUG > 0) 
     printf ("\n- figura %i nakłada się przy i=%i j=%i dla n=%i m=%i", kk, i, j, n, m);
   return -27;
 }


 // posadz figure skoro sie da
 // - tzn zmiana planszy PP
 // - tzn zmiana tabeli figur FFF bo kk-figura ma zapisane współrzędne gdzie posadzona

 Lwu++;		// to jakaś statystyka dla ciekawych

 FF[kk].PPi = Xi; 	// ustaw wspolrzednne gdzie sie miesci ta figura - tj. wskaźnik używalności jej
 FF[kk].PPj = Xj;	// uwaga na te dane, bo w PPi nie uwzględniono korekty EEi

 // posadź figurę na planszy

 tmpEEi = FF[kk].EEi;			// tmpEj - bo pierwsza linia jest krótsza o blade znaki figury
 tmpIIe = 0;
 j = Xj; m = 0;			// przebieganie po drugim wymiarze
 while (m < FF[kk].m) {
   i = Xi - tmpIIe; n = tmpEEi;  
   while (n < FF[kk].n) {
     if (FF[kk].F[n][m]) 		// czy nakładają się pola z PP planszy i F figury
       PP[i][j] = FF[kk].F[n][m];	// numer figury znacznikiem, że pole zajęte tą figurą   
   i++; n++;
   }
   tmpIIe = FF[kk].EEi;
   tmpEEi = 0;				// druga linia analizowana normalnie
   j++; m++;
 }

 printf ("\n+ zmieściło się, więc położyłem figurę %i w Xi=%i Xj=%i\nNowy stan tablicy PP:", kk, Xi, Xj);
 drukuj_tablice (PP);

 // przeleć się po wszystkich figurach nie uzywanych probujac je wstawic
 // jeżeli nie ma już figur to sukces !

 l=0; a=1;
 while (a && l<LICZBA_FIGUR) {
   if (FF[l++].PPi == -1)
     a = 0;
 }

 if (a) {
   printf ("\n+ oto jest rozwiązanie ! TaTaM !!! * * * * * Wciśnij Enter!");
   getchar ();
   return 0;
 }

 for (l=0; l<LICZBA_FIGUR; l++) {
   // czy figura jest jeszcze nie używana
   if (FF[l].PPi == -1) {	// jeżeli nie używana to ją wstawiaj
     printf ("\n+ wywoluje dla figury %i kolejny poziom %i", l, level+1);
     wstaw_figure ((PP), (FF), l, level+1);
   }
 }

 printf ("\n- na tym poziomie (%i) wszystko wywołano już wszystko i wszystko wróciło", level);

}  

/*********************************************************************/


int main () {
 int i, j, k, l, n, m;
 int PP[NN][MM];

 // wyzeruj plansze PP na której się będzie pracować
 for (i=0; i<NN; i++)
   for (j=0; j<MM; j++)
     PP[i][j] = 0;

 // przygotuj tabele figur
 // - policz ile jest figur
 // - wyznacz punkty EE
 // - wyzeruj położenie

 for (k=0; k<LICZBA_FIGUR; k++) {
   FFF[k].PPi = FFF[k].PPj = -1;	// znacznik, że figura nie używana

   // tu jeszcze wyznaczam punkt EEi
   // wyjaśnienie - EEi to ile punktów pustych jest w pierwszym rzędzie od lewej
   FFF[k].EEi=0;
   for (i=0; i<FFF[k].n; i++)
     if (FFF[k].F[i][0]) {
       FFF[k].EEi = i;
       break;
     }

 } 

 // główny kod programu

 printf ("\nProgram do rozwiązywania łaigłówki. 2012 (c) Eniac Software\n");
 printf ("\nLiczba figur: %i", LICZBA_FIGUR);
 printf ("\nWydruk figur aby je sobie pooglądać");

 for (k=0; k<LICZBA_FIGUR; k++) {
   printf ("\nFigura nr %i ma wymiary n=%i m=%i i parametr Ei=%i", k, FFF[k].n, FFF[k].m, FFF[k].EEi);
   drukuj_figure (FFF[k]);
 }

 for (k=0; k<LICZBA_FIGUR; k++) {
   printf ("\n");
   wstaw_figure (PP, FFF, k, 0);
 }
 printf ("\nStatystyka - Wywołań: %i, Postawień: %i", Lww, Lwu);

return 0;
}


void drukuj_tablice (int PP [NN][MM]) {
 int i, j;

 printf ("\n|"); 
 for (i=0; i<NN; i++) 
   printf (" %1i", i); 
 printf (" |");    

 printf ("\n|"); 
 for (i=0; i<NN; i++) 
   printf ("--"); 
 printf ("-|");    

 for (j=0; j<MM; j++) {
   printf ("\n|");
   for (i=0; i<NN; i++)
     printf (" %1C", PP[i][j] ? '@' + PP[i][j] : '.');
   printf (" |");
 }

 printf ("\n|"); 
 for (i=0; i<NN; i++) 
   printf ("--"); 
 printf ("-|");    

 printf ("\n|"); 
 for (i=0; i<NN; i++) 
   printf (" %1i", i); 
 printf (" |");    

 printf ("\n");

}  


void drukuj_figure (struct Figura F) {
 int i, j;

 printf ("\n|");
 for (i=0; i<F.n; i++)
   printf ("--");
 printf ("-|");

 for (j=0; j<F.m; j++) {
   printf ("\n|");
   for (i=0; i<F.n; i++) {
     printf (" %1C", F.F[i][j] ? '@' + F.F[i][j] : '.');
   }
   printf (" |");
 }

 printf ("\n|");
 for (i=0; i<F.n; i++)
   printf ("--");
 printf ("-|");
}


Kategorie: zawodowe, _blog


Słowa kluczowe: programowanie, język c


Komentarze: (0)

Skomentuj notkę

Disclaimers :-) bo w stopce coś wyglądającego mądrze można napisać. Wszystkie powyższe notatki są moim © wymysłem i jako takie związane są ze mną. Ale są też materiały obce, które tu przechowuję lub cytuje ze względu na ich dobrą jakość, na inspiracje, bądź ilustracje prezentowanego lub omawianego tematu. Jeżeli coś narusza czyjeś prawa - proszę o sygnał abym mógł czym prędzej naprawić błąd i naruszeń zaniechać.