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 ("-|");
}