#include <stdlib.h>
#include <iostream.h>
#define DEBUG_STATE_MANAGER
#define DEBUG_QUEUE
//#define BRUTE_FORCE
#define MAX_PRIORITY 1000
#define EXAMPLE3
#define SUBEXAMPLE6
#include "zadani.cpp"
/* trida pro uchovani jednoho stavu stavoveho prostoru */
class State {
private:
State *prev; // ukazatel na predchozi stav
State *next; // dalsi stav stav. prostoru
unsigned bucket[BUCKETS]; // obsah kybliku v tomto stavu
// je i platny index kyble?
static int check(int i) {
return (i>=0 && i<BUCKETS);
}
public:
// bezparametricky konstruktor
State() {
prev = next = NULL;
for(int i=0; i<BUCKETS; i++) bucket[i] = 0;
}
// konstruktor pro naplneni defaultnimi hodnotami
State(unsigned bucket_start[]) {
prev = next = NULL;
for(int i=0; i<BUCKETS; i++) bucket[i] = bucket_start[i];
}
// konstruktor - kybliky se zdedi z predchoziho stavu
State(State *tprev) {
for(int i=0; i<BUCKETS; i++) bucket[i] = tprev->bucket[i];
prev = tprev;
next = NULL;
}
// vrat obodovani stavu, 0 je nejlepsi (spravne) reseni
int getScore() {
int score = 0;
#ifndef BRUTE_FORCE
for(int i=0; i<BUCKETS; i++) {
// score += abs(bucket[i] - bucket_final[i]);
if(bucket[i] != bucket_final[i]) {
// if(bucket[i] == 0) score += 5;
// if(bucket[i] == bucket_size[i]) score += 5;
score += 1;
}
}
#endif
if(score > MAX_PRIORITY) score = MAX_PRIORITY;
return score;
}
// je to vysledek?
int isResult(unsigned bucket_final[]) {
for(int i=0; i<BUCKETS; i++) if(bucket[i] != bucket_final[i]) return 0;
return 1;
}
// jsou stavy stejne?
int compare(State *s) {
for(int i=0; i<BUCKETS; i++) if(bucket[i] != s->bucket[i]) return 0;
return 1;
}
// prelij vodu z from do to
int pour(int from, int to) {
if(!check(from) || !check(to)) return 0;
int pour_from = bucket[from];
int pour_to = bucket_size[to] - bucket[to];
if(pour_from > pour_to) {
bucket[to] += pour_to;
bucket[from] -= pour_to;
} else {
bucket[to] += pour_from;
bucket[from] -= pour_from;
}
return 1;
}
// vyprazdni kyblik
int empty(int i) {
if(!check(i)) return 0;
bucket[i] = 0;
return 1;
}
// napln kyblik
int fill(int i) {
if(!check(i)) return 0;
bucket[i] = bucket_size[i];
return 1;
}
// je kyblik plny?
int isFull(int i) {
if(!check(i)) return 0;
return bucket[i] == bucket_size[i];
}
// je kyblik prazdny?
int isEmpty(int i) {
if(!check(i)) return 0;
return bucket[i] == 0;
}
// vrat obsah kybliku
int getBucket(int i) {
if(check(i)) return bucket[i]; else return -1;
}
// vrat dalsi stav prostoru
State *getNext() {
return next;
}
// vrat predchazejici stav na ceste prostorem
State *getPrev() {
return prev;
}
// napoj dalsi stav v prostoru
State *add(State *tnext) {
return next = tnext;
}
// vypis stavu pro debug
void echo() {
cout << "(";
for(int i=0; i<BUCKETS; i++) {
if(i) cout << ", ";
cout << bucket[i];
}
cout << ")";
}
};
/* trida pro reprezentaci stavoveho prostoru */
class StateManager {
private:
State *first;
int size;
public:
// konstruktor
StateManager() {
first = NULL;
size = 0;
}
// destruktor
~StateManager() {
State *temp = first;
while(temp != NULL) {
first = temp->getNext();
delete temp;
temp = first;
}
}
// existuje tento stav jiy v prostoru?
int exists(State *s) {
State *temp = first;
while(temp != NULL) {
if(temp->compare(s)) return 1;
temp = temp->getNext();
}
return 0;
}
// pridej dalsi stav, pokud v prostoru jeste neni
int add(State *s) {
#ifdef DEBUG_STATE_MANAGER
cout << "StateManager: add: ";
s->echo();
#endif
if(exists(s)) {
#ifdef DEBUG_STATE_MANAGER
cout << " - jiz existuje" << endl;
#endif
return 0;
}
s->add(first);
first = s;
size++;
#ifdef DEBUG_STATE_MANAGER
cout << " - pridan" << endl;
#endif
return 1;
}
};
/* trida pro jednu bunku prioritni fronty */
class QueueCell {
private:
int priority;
State *s;
QueueCell *next;
public:
// konstruktor...
QueueCell(int tpriority, State *ts) {
s = ts;
next = NULL;
if(tpriority > MAX_PRIORITY) tpriority = MAX_PRIORITY;
priority = tpriority;
}
// pripoj dalsi bunku
QueueCell *add(QueueCell *tnext) {
return next = tnext;
}
// zjisti prioritu
int getPriority() {
return priority;
}
// vrat odkaz na stav
State *getState() {
return s;
}
// vrat dalsi bunku
QueueCell *getNext() {
return next;
}
};
/* trida pro prioritni frontu */
class Queue {
private:
int size;
QueueCell *first, *last;
int pushs;
public:
// konstruktor
Queue() {
first = last = new QueueCell(-1, NULL);
size = 0;
pushs = 0;
}
// je prazdna?
int empty() {
return size==0;
}
// velikost
int getSize() {
return size;
}
// vloz prvek
void push(int priority, State *s) {
QueueCell *qc = new QueueCell(priority, s);
last = last->add(qc);
size++;
pushs++;
#ifdef DEBUG_QUEUE
cout << "Queue: push: ";
s->echo();
cout << " - priorita " << priority;
cout << ", ve fronte " << getSize() << endl;
#endif
}
// vyber prvek s nejnizsi prioritou
State *pop() {
QueueCell *temp = first->getNext(), *found = NULL;
QueueCell *prev = first, *prefound = NULL;
State *result;
int min = MAX_PRIORITY;
int priority;
#ifdef DEBUG_QUEUE
cout << "Queue: pop: ";
#endif
// prohledavej
while(temp != NULL) {
priority = temp->getPriority();
if(priority < min) {
min = priority;
found = temp;
prefound = prev;
}
prev = temp;
temp = temp->getNext();
}
if(found == NULL) return NULL;
// vyrad z fronty a vrat vysledek
size--;
result = found->getState();
prefound->add(found->getNext());
if(last == found) last = prefound;
delete found;
#ifdef DEBUG_QUEUE
found->getState()->echo();
cout << " - priorita " << min;
cout << ", ve fronte " << getSize() << endl;
#endif
return result;
}
// kolikrat bylo celkove pusnuto
int getPushs() {
return pushs;
}
};
int main() {
StateManager *sm = new StateManager();
State *s = new State(bucket_start);
State *t;
Queue *q = new Queue();
int i, j, d;
q->push(s->getScore(), s);
while(!q->empty()) {
// vezmi celo fronty
s = q->pop();
if(s->isResult(bucket_final)) break;
// zkousej plnit kyble
for(i=0; i<BUCKETS; i++) if(!s->isFull(i)) {
t = new State(s);
t->fill(i);
if(sm->add(t)) q->push(t->getScore(), t);
}
// zkousej vylivat kyble
for(i=0; i<BUCKETS; i++) if(!s->isEmpty(i)) {
t = new State(s);
t->empty(i);
if(sm->add(t)) q->push(t->getScore(), t);
}
// zkousej prelevat kyble
for(i=0; i<(BUCKETS-1); i++) {
for(j=i+1; j<BUCKETS; j++) {
if(!s->isEmpty(i) && !s->isFull(j)) {
t = new State(s);
t->pour(i, j);
if(sm->add(t)) q->push(t->getScore(), t);
}
}
}
}
// vyhodnoceni
if(s->isResult(bucket_final)) {
cout << endl << "Nalezeno reseni!" << endl;
d = 0;
while(s != NULL) {
d++;
s = s->getPrev();
}
cout << "Delka cesty: " << d << endl;
} else {
cout << endl << "Reseni neexistuje!" << endl;
}
cout << "Prozkoumanych stavu " << q->getPushs() << endl;
system("PAUSE");
return 0;
}