Algoritmus "Lights" – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

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

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Jay
~ Anonymní uživatel
14 příspěvků
13. 10. 2011   #1
-
0
-

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.

Nahlásit jako SPAM
IP: 90.183.137.–
Reklama
Reklama
Jay
~ Anonymní uživatel
14 příspěvků
13. 10. 2011   #2
-
0
-

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;
}
Nahlásit jako SPAM
IP: 90.183.137.–
crazy
~ Moderátor
+10
Grafoman
14. 10. 2011   #3
-
0
-

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

bool pole[x][y];
Nahlásit jako SPAM
IP: 147.32.113.–
All you need is vision and time.
H4wk.cz0
Newbie
14. 10. 2011   #4
-
+2
-
Zajímavé

#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.

Nahlásit jako SPAM
IP: 195.113.21.–
http://ksp.mff.cuni.cz - Nauč se opravdu programovat
KIIV+42
God of flame
14. 10. 2011   #5
-
0
-

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...

Nahlásit jako SPAM
IP: 62.168.56.–
Program vždy dělá to co naprogramujete, ne to co chcete...
Jay
~ Anonymní uživatel
14 příspěvků
14. 10. 2011   #6
-
0
-

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;
}
Nahlásit jako SPAM
IP: 90.183.137.–
KIIV+42
God of flame
14. 10. 2011   #7
-
0
-

#6 Jay
Co na to valgrind?

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

Nahlásit jako SPAM
IP: 62.168.56.–
Program vždy dělá to co naprogramujete, ne to co chcete...
KIIV+42
God of flame
14. 10. 2011   #8
-
0
-

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

Nahlásit jako SPAM
IP: 62.168.56.–
Program vždy dělá to co naprogramujete, ne to co chcete...
jay
~ Anonymní uživatel
14 příspěvků
17. 10. 2011   #9
-
0
-

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.

Nahlásit jako SPAM
IP: 85.160.173.–
KIIV+42
God of flame
17. 10. 2011   #10
-
0
-

#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

Nahlásit jako SPAM
IP: 94.112.32.–
Program vždy dělá to co naprogramujete, ne to co chcete...
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 69 hostů

Podobná vlákna

Algoritmus — založil Jirina.K

C++ algoritmus — založil silent

Algoritmus — založil RePRO

Algoritmus — založil LuckaH

Algoritmus - priklad — založil Booty

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý