Algoritmus "Lights" – C / C++ – Fórum – Programujte.com

Zdravim,

chystam se na implementaci tohoto algoritmu v c++, tak se chci jen zeptat, jestli byste nemeli nejake hinty do zacatku, treba jake datove struktury pouzit, nejake finty na snizeni casove slozitosti, apod.

Jedna se o problem Lights - mozna znate jako hru pro mobily (http://en.wikipedia.org/…t_%28game%29). Mam z nejake pocatecni zadane konfigurace zjistit nejmensi mozny pocet kroku tak, aby na konci vsechna svetla byla zhasnuta.

Takze jakym zpusobem si napriklad pamatovat kroky ve kterych uz jsem byl? Jakou datovou strukturu pouzit pro ten grid? Dvourozmerne pole? Mit jednotliva pole jako struktury nebo instance tridy?

Jenom si delam takovy pocatecni brainstorming, takze kdybyste kdokoliv cokoliv vedel, budu moc vdecny za jakekoliv postrehy.

Diky moc,

J.

Tak uz mam to "jadro" programu - dvourozmerne pole objektu (kazda instance pro jedno svetlo). Funkce switchlight prepne prislusna sousedni svetla. Nevedel by nekdo jak ted na ten algoritmus? Na zacatku si nastavim nejakou pocatecni konfiguraci a pote nad tim prozenu ten algoritmus tak, aby zhasla vsechna svetla.

#include <cstdlib>
#include <iostream>

using namespace std;
 
#define COLUMNS 4
#define ROWS 4


class Light {
public:
	bool value;
	int x;
	int y;
	void lightswitch();
};

Light **field;

void Light::lightswitch() {
	if(x-1>=0) {
		if(field[x-1][y].value==false) field[x-1][y].value=true;
		else field[x-1][y].value=false;
	}
	if(x+1<=COLUMNS) {
		if(field[x+1][y].value==false) field[x+1][y].value=true;
		else field[x+1][y].value=false;
	}
	if(y-1>=0) {
		if(field[x][y-1].value==false) field[x][y-1].value=true;
		else field[x][y-1].value=false;
	}
	if(y+1<=ROWS) {
		if(field[x][y+1].value==false) field[x][y+1].value=true;
		else field[x][y+1].value=false;
	}
	if(value==false) value=true;
	else value=false;
}

void display() {
	cout << endl << endl << "Aktualni stav:" << endl << endl;
	for(int i=0;i<COLUMNS;i++) {
		for(int j=0;j<ROWS;j++) {
			if(field[i][j].value==false) cout << "x ";
			else cout << "o ";
		}
		cout << endl;
	}
	cout << endl << endl;
}
	

int main(int argc, char *argv[])
{
	field = new Light*[COLUMNS];

	for(int i=0;i<COLUMNS;i++) {
		field[i] = new Light[ROWS];
	}

	for(int i=0;i<COLUMNS;i++) {
		for(int j=0;j<ROWS;j++) {
			field[i][j].value=false;
			field[i][j].x=i;
			field[i][j].y=j;
		}
	}

	/* pocatecni konfigurace */

	field[1][1].value=true;
	field[2][0].value=true;
	field[3][2].value=true;

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

	display();

	field[1][1].lightswitch();

	display();

    system("PAUSE");
    return EXIT_SUCCESS;
}

#2 Jay
nestačilo by dvourozměrné pole boolů?

bool pole[x][y];

#3 crazy
Nestačilo by 32 bitové číslo? Vše by se pak zjišťovalo přes bitové operace a přepínání by se mohlo dělat XORem. Bylo by to pekelně rychlé. Což bude nejspíše potřeba, protože tenhle problém se nedá řešit jinak než procházením stavového prostoru, na wiki je nějaký návod pro řešení, ale nevím jestli zaručuje nalezení nejkratší cesty. Já bych to psal jako nějaký iterative deepening A* a jako heuristiku bych použil počet rožnutých světel.

Sem si to jen tak pro zajimavost zkusil naprogramovat v c++ jako hledani do sirky (BFS)...

kolem 20ti nahodnych kliku (generator "resitelnych" kombinaci) tak to resilo klidne i 2minuty...

------------

Nicmene jak se zavedla priorita (tj. fronty rozdelene podle vzdalenosti od cile)

tak se reseni dalo najit behem 30 az 50 ms...

Ja mam ted tohle, funguje to dobre pro 3x3, ale z nepochopitelnych duvodu to spadne pri vyssich rozmerech, nevite proc?

#include <cstdlib>
#include <stack>
#include <queue>
#include <iostream>

using namespace std;
 
#define COLUMNS 3
#define ROWS 3

/* ************************************ */
/* Trida Field - predstavuje hraci pole */
/* ************************************ */

class Field {
public:
	bool gamefield[COLUMNS][ROWS];
	stack<pair<int,int> > steps;
	Field();
	Field(bool startfield[COLUMNS][ROWS]);
	Field(const Field& f);
	void lightswitch(int x, int y);
	bool isWin();
	void display();
};

Field::Field() {
	for(int i=0;i<COLUMNS;i++) {
		for(int j=0;j<ROWS;j++) {
			this->gamefield[i][j]=false;
		}
	}
}

Field::Field(const Field& f) {
	for(int i=0;i<COLUMNS;i++) {
		for(int j=0;j<ROWS;j++) {
			this->gamefield[i][j]=f.gamefield[i][j];
		}
	}
}

void Field::display() {	
	cout << endl << endl;
	cout << "Aktualni stav" << endl << endl;
	for(int i=0;i<COLUMNS;i++) {
		for(int j=0;j<ROWS;j++) {
			if(this->gamefield[i][j]==true) cout << "o ";
			else cout << "x ";
		}
		cout << endl;
	}
	cout << endl << endl;
}

void Field::lightswitch(int x, int y) {
	if(x-1>=0) {
		gamefield[x-1][y]=!gamefield[x-1][y];
	}
	if(x+1<=COLUMNS) {
		gamefield[x+1][y]=!gamefield[x+1][y];
	}
	if(y-1>=0) {
		gamefield[x][y-1]=!gamefield[x][y-1];
	}
	if(y+1<=ROWS) {
		gamefield[x][y+1]=!gamefield[x][y+1];
	}
	gamefield[x][y]=!gamefield[x][y];
}

bool Field::isWin() {
	bool result = true;
	for(int i=0;i<COLUMNS;i++) {
		for(int j=0;j<ROWS;j++) {
			if(this->gamefield[i][j]==true) {
				result = false;
				break;
			}
		}
	}
	return result;
}

/* ************************************ */
/*             Metoda solve             */
/* ************************************ */

void solve(Field currentState) {
int counter = 0;
Field newState = currentState;
queue<Field> q;
while(!newState.isWin()) {
  for(int i=0;i<COLUMNS;i++) {
		for(int j=0;j<ROWS;j++) {
			Field nextState = newState;
			nextState.lightswitch(i,j);
			nextState.steps.push(make_pair(i,j));
			q.push(nextState);
		}
  }
  newState = q.front();
  counter ++;
  q.pop();
}
cout << "Pocet kroku: " << counter << endl << endl;
}

/* ************************************ */
/*                 Main                 */
/* ************************************ */

int main(int argc, char *argv[])
{
	Field start;

	/* nejklasictejsi ukazka, melo by jit vyresit na dva tahy */
	
	start.gamefield[0][1]=true;
	start.gamefield[1][0]=true;
	start.gamefield[1][1]=true;
	start.gamefield[2][2]=true;

	start.display();

	solve(start);

    system("PAUSE");
    return EXIT_SUCCESS;
}

#6 Jay
Co na to valgrind?

Ja tipuju preteceni pameti :) Ani si nejspis neukladas stavy, kde uz si byl... takze se klidne muzes zacyklit

jen pro ilustraci stejne rozestaveni svetel, rychlejsi algoritmus to zvladl za 60milisekund ale na 34 kroku

pomalejsi nasel nejkratsi vzdalenost na 10 kroku za nejakych 49sekund

http://pastebin.com/mfzQL0Bw

a jakym zpusobem uchovavat stavy? V programovani nejsem prilis zdatny.. Pouzil jsem queue z stl, ale asi bych potreboval neco slozitejsiho, ze? A ty priority, jak konkretne pocitat ceny jednotlivych stavu?

Dik moc.

Zasláno z mobilního telefonu.

#9 jay
cena je napriklad pocet kroku a pocet sviticich svetel...

kazdopadne ja sem pouzil nekolik ruznejch kontejneru... map na stavy kde jsem uz byl, multimap na "prioritni" frontu, deque na ukladani uz zpracovanejch stavu (odkazuju se totiz na predchudce ukazatelem)

ukladam si data do struktury kde mam jedno cislo na stav pole (jak uz tu bylo zmineno staci 25bitu na ulozeni celeho pole), pocet sviticich svetel, pocet predchudcu, ukazatel na predchozi stav

nic zabijackyho :D