[C++] Risolutore di indovinelli

Noixe · 31-01-2011, 09:19

Sicuramente conoscerete quegli indovinelli in cui ci sono dei recipienti con determinate capacità di contenimento e tramite versamenti da un recipiente all'altro e a svuotamenti, bisogna riuscire a far rimanere un certo quantitativo di liquido all'interno di un recipiente.

Ad esempio, si hanno 2 recipienti, uno con una capacità di 5 litri e l'altro di 3 litri. Considerando che non ci sono limiti di acqua e che quindi ogni recipiente può essere riempito e svuotato quante volte si vuole, in che modo si possono far rimanere 4 litri nel recipiente da 5?

Ho sviluppato questo programma che risolve indovinelli di questo tipo. L'idea che ho avuto è che ogni operazione che si svolge, si può associare ai termini delle disposizioni con ripetizione di N oggetti a K a K, dove N sono le possibili operazioni e K il numero di mosse per risolvere il problema.

Supponendo di avere N recipienti, le operazioni possibili sono N^2 infatti ogni recipiente può versare il suo liquido agli altri N-1 recipienti ottenendo un totale di N(N-1) = N^2 - N operazioni alle quali vanno sommati gli N svuotamenti (ogni recipienti può anche essere svuotato e quindi va considerata anche questa operazione) per cui avremo: N^2 - N + N = N^2
K invece varierà da 1 a un numero scelto a piacere (anche se per valori alti i tempi di calcolo aumentano molto) in modo da poter provare a risolvere il problema aggiungendo una nuova mossa alla volta.

Ad esempio supponiamo di avere 3 recipienti: 0, 1, 2.

Le operazioni possibili sono:

Verso 0 in 1
Verso 0 in 2
Verso 1 in 0
Verso 1 in 2
Verso 2 in 0
Verso 2 in 1
Svuoto 0
Svuoto 1
Svuoto 2

Sono 9 operazioni ovvero 3^2

I versamenti possibili si possono ottenere dalle disposizioni semplici (dato che un recipiente non può versarsi in se stesso) e visto che in questo caso gli elementi coinvolti sono sempre 2, sono sufficienti 2 cicli for annidati, che vanno a popolare un vettore di coppie come segue:

0, 1
0, 2
1, 0
1, 2
2, 0
2, 1

Che coincidono con i versamenti possibili.

Adesso ci serve gestire anche il caso degli svuotamenti.

Ritornando alle disposizioni con ripetizioni, le quali ci consentono di simulare le possibili mosse per trovare la soluzione, si ha che nel caso ad esempio delle disposizioni con ripetizioni di 9 oggetti, i valori possibili di ogni sequenza sono proprio 9:

0 1 2 3 4 5 6 7 8

Ai quali possiamo associare i versamenti:

0 -> 0, 1
1 -> 0, 2
2 -> 1, 0
3 -> 1, 2
4 -> 2, 0
5 -> 2, 1

e anche gli svuotamenti.

6 -> Svuoto 2
7 -> Svuoto 1
8 -> Svuoto 0

L'associazione degli svuotamenti l'ho fatta in maniera decrescente per maggior chiarezza a livello di codice, ma il risultato non cambia.
Tra le disposizioni con ripetizioni generate, bisogna escludere quelle in cui ci sono almeno 2 elementi adiacenti uguali (ad esempio 0 1 1) perché indicherebbe la stessa mossa ripetuta più volte consecutivamente la quale è una cosa inutile (non ha senso svuotare due volte di seguito un recipiente o versare due volte di seguito il recipiente 0 nel 1) infatti la funzione che genera le disposizioni con ripetizione esclude le sequenze in cui almeno 2 elementi adiacenti sono uguali.
Inoltre è bene anche salvare il contenuto di ogni contenitore per ogni mossa effettuata, perché se ci si accorge che dopo un certo numero di mosse, siamo ritornati ad una condizione precedente, vuol dire che la strada che abbiamo preso è sbagliata e quindi è inutile continuare e bisogna ripartire da capo con una nuova sequenza di mosse possibili.

Nel sorgente che segue ho impostato già i parametri per risolvere il quesito posto all'inizio. Notare che la possibilità di riempire all'infinito i recipienti, si simula aggiungendo un terzo recipiente con capacità e contenuto infinito e impostando tali parametri a -1.
Per risolvere l'indovinello scritto sopra dovete inserire questi parametri (tra parentesi spiego cosa indicano):

Quanti sono i recipienti?
3 (il recipiente da 5, quello da 3 e quello infinito)

Capacita' 1^ recipiente
5 (può contenere 5 litri)
Contenuto 1^ recipiente
0 (inizialmente e' vuoto)

Capacita' 2^ recipiente
3 (può contenere 3 litri)
Contenuto 2^ recipiente
0 (inizialmente e' vuoto)

Capacita' 3^ recipiente
-1 (il quantitivo che può contenere e' infinito)
Contenuto 3^ recipiente
-1 (il contenuto e' infinito)

Quanti sono i recipienti che dovranno contenere il contenuto richiesto?
1 (A noi interessa solo quello da 5...)

Contenuto 1^ recipiente
4 (...che conterrà 4 litri come specificato adesso)

Quante sono le mosse massime per cui cercare la soluzione?
1 (per risolvere l'indovinello con il minor numero possibile di mosse bisogna fare i tentativi partendo da 1)

Quante sono le mosse massime per cui cercare la soluzione?
6 (6 è il numero di mosse minime per risolvere questo indovinello specifico quindi 6 va bene)

1. Trova una soluzione qualsiasi.
2. Trova tutte le soluzioni.
1 (in questo caso la soluzione e' una sola quindi 1 va bene)

Codice:

#include <iostream>
#include <string>
#include <vector>
#include <sstream>

using namespace std;

vector<vector<int> > Backup;
vector<pair<int, int> > Versamenti;
vector<string> Mosse;

enum {Soluzione = -2, Infinito = -1};

string Int2Str (int i) {

    ostringstream o;
    o << i;
    return o.str();
}

bool Maggiore(vector<int> a, vector<int> b) {

    int i = 0;

    while (i < a.size() && a[i] == b[i])
	i++;

    return i < a.size() && a[i] > b[i];
}

vector<int> DispoR_AdiacDiversi (int n, int k, bool init = false, int pos = 0) {

    static vector<int> v;
    static vector<int> c;
    static vector<int> Mag;

    if (init) {
	v.clear();
	c.clear();
	Mag.clear();

	for (int i = 0; i < n; i++)
	    v.push_back(i);

	for (int i = 0; i < k; i++)
	    c.push_back(i % 2);

	Mag.resize(k);

	Mag[0] = -1;

	c[c.size() - 1]--;
    };

    int i = k - 1;

    while ((i >= 0 && c[i] == v[v.size() - 1]) || (i > pos && pos > 0))
	i--;

    if (i >= 0)
	c[i]++;

    while (i > 0 && c[i] == c[i - 1]) {
	while (i >= 0 && c[i] == v[v.size() - 1])
	    i--;

	if (i >= 0)
	    c[i]++;
    };

    for (int j = i + 1, h = 0; j < k; j++, h++)
	c[j] = v[h % 2];

    if (Maggiore(c, Mag))
	Mag = c;
    else
	c.resize(0);

    return c;
}

class Recipiente {

    private :
	int cap, cont;

    public :
	Recipiente (int capacita, int contenuto = 0) {
	    if (contenuto > capacita)
		contenuto = capacita;
	    if (contenuto == Infinito)
		capacita = Infinito;

	    cap = capacita;
	    cont = contenuto;
	}

	void operator<< (Recipiente& c) {

	    if (cap != Infinito && c.cap != Infinito) {
		int vuoto = cap - cont;

		cont += c.cont;
		c.cont -= vuoto;

		if (cont > cap)
		    cont = cap;
		if (c.cont < 0)
		    c.cont = 0;
	    }
	    else
	    if (cap != Infinito && c.cap == Infinito) {
		int vuoto = cap - cont;

		cont = cap;

		if (c.cont != Infinito) {
		    c.cont -= vuoto;
		    if (c.cont < 0)
			c.cont = 0;
		};
	    }
	    else
	    if (cap == Infinito && c.cap != Infinito) {
		if (cont != Infinito)
		    cont += c.cont;
		c.cont = 0;
	    };
	}

	int Cap() {
	    return cap;
	}

	int Cont() {
	    return cont;
	}

	void Svuota() {
	    cont = 0;
	}

	string Info() {

	    string s = "";
	    if (cap == Infinito)
		s = "inf";
	    else
		s = Int2Str(cap);

	    s += "(";

	    if (cont == Infinito)
		s += "inf";
	    else
		s += Int2Str(cont);

	    s += ")";

	    return s;
	}
};

void Salva (vector<Recipiente> r, vector<vector<int> >& v) {

    vector<int> n_upla;

    for (int i = 0; i < r.size(); i++)
	n_upla.push_back(r[i].Cont());

    v.push_back(n_upla);
}

bool Esiste (vector<int> v, vector<vector<int> > b) {

    int con = 0;

    for (int i = 0; i < b.size() - 1; i++) {
	for (int j = 0; j < v.size(); j++) {
	    if (v[j] == b[i][j])
		con++;
	    if (con == v.size())
		return true;
	};
	con = 0;
    };
    return false;
}

bool Risolto (vector<Recipiente> r, vector<int> vf) {

    bool risolto = true;

    for (int i = 0; i < vf.size(); i++)
	risolto = risolto && r[i].Cont() == vf[i];

    return risolto;
}

int Elabora (vector<Recipiente> r, vector<int> vf, vector<int> v) {

    for (int i = 0; i < v.size(); i++) {

	string stato = "";

	if (v[i] < r.size() * (r.size() - 1)) {

	    if ((r[Versamenti[v[i]].first].Cont() < r[Versamenti[v[i]].first].Cap() ||
		r[Versamenti[v[i]].first].Cap() == Infinito && r[Versamenti[v[i]].first].Cont() >= 0) &&
		r[Versamenti[v[i]].second].Cont() != 0) {

		int cont_second = r[Versamenti[v[i]].second].Cont();

		r[Versamenti[v[i]].first] << r[Versamenti[v[i]].second];

		for (int j = 0; j < r.size(); j++)
		    stato += r[j].Info() + " ";

		if (cont_second > 0)
		    Mosse.push_back("Verso " + Int2Str(Versamenti[v[i]].second + 1) + " in " + Int2Str(Versamenti[v[i]].first + 1) + "\t" + stato);
		else
		    Mosse.push_back("Riempio " + Int2Str(Versamenti[v[i]].first + 1) + "\t" + stato);
	    };
	}
	else {

	    if (r[r.size() * r.size() - v[i] - 1].Cont() != 0) {

		r[r.size() * r.size() - v[i] - 1].Svuota();

		for (int j = 0; j < r.size(); j++)
		    stato += r[j].Info() + " ";

		Mosse.push_back("Svuoto " + Int2Str(r.size() * r.size() - v[i]) + "\t" + stato);
	    };
	};

	vector<int> contenuti;

	for (int j = 0; j < r.size(); j++)
	    contenuti.push_back(r[j].Cont());

	if (Backup.size() > 0)
	    if (Esiste(contenuti, Backup))
		return i;

	Salva(r, Backup);

    };

    if (Risolto(r, vf))
	return Soluzione;

    return 0;
}


int main() {

    int Recip, MinMosse, MaxMosse, capinput, continput, sol;
    bool esci = false;

    vector<Recipiente> R;
    vector<int> VF;

    cout << "Quanti sono i recipienti?" << endl;
    cin >> Recip;

    cout << "\nInserisci capacita' e contenuto partendo dai recipienti che dovranno contenere" << endl;
    cout << "il contenuto richiesto. Se il valore e' infinito inserire -1.\n" << endl;

    for (int i = 0; i < Recip; i++) {
	cout << "Capacita' " << (i + 1) << "^ recipiente" << endl;
	cin >> capinput;
	cout << "Contenuto " << (i + 1) << "^ recipiente" << endl;
	cin >> continput;
	cout << endl;
	R.push_back(Recipiente(capinput, continput));
    };

    cout << "Quanti sono i recipienti che dovranno contenere il contenuto richiesto?" << endl;
    cin >> Recip;

    cout << endl;

    for (int i = 0; i < Recip; i++) {
	cout << "Contenuto " << (i + 1) << "^ recipiente" << endl;
	cin >> continput;
	VF.push_back(continput);
    };

    cout << "\nQuante sono le mosse minime per cui cercare la soluzione?" << endl;
    cin >> MinMosse;

    cout << "\nQuante sono le mosse massime per cui cercare la soluzione?" << endl;
    cin >> MaxMosse;

    cout << "\n1. Trova una soluzione qualsiasi." << endl;
    cout << "2. Trova tutte le soluzioni." << endl;
    cin >> sol;

    cout << "\nStato iniziale capacita'(contenuto)\n" << endl;

    for (int j = 0; j < R.size(); j++)
	cout << (j + 1) << "^ recipiente: " << R[j].Info() << endl;
    cout << endl;

    cout << "Soluzione da trovare: ";

    for (int j = 0; j < VF.size(); j++) {
	if (R[j].Cap() == Infinito)
	    cout << "inf";
	else
	    cout << R[j].Cap();
	cout << "(" << VF[j] << ") ";
    };

    cout << "\n\n" << endl;

    for (int i = 0; i < R.size(); i++)
	for (int j = 0; j < R.size(); j++)
	    if (i != j)
		Versamenti.push_back(pair<int, int>(i, j));

    for (int k = MinMosse; k <= MaxMosse && !esci; k++) {

	cout << "Ricerca della soluzione con " << k << " moss" << (k > 1 ? "e" : "a") << "\n" << endl;
	vector<int> v;
	bool init = true;
	int pos = 0;

	do {
	    v = DispoR_AdiacDiversi(R.size() * R.size(), k, init, pos);
	    init = false;

	    Backup.clear();
	    Mosse.clear();
	    if (v.size() > 0)
		if ((pos = Elabora(R, VF, v)) == Soluzione && Mosse.size() == k) {
		    cout << "*** " << k << " mosse ***" << endl;
		    for (int i = 0; i < Mosse.size(); i++)
			cout << Mosse[i] << endl;
		    cout << endl;
		    esci = true;
		    if (sol == 1)
			break;
		};
	}
	while (v.size() > 0);
    };

    cout << "Elaborazione terminata" << endl;

    while (cin.get() != '\n');
    while (cin.get() != '\n');

    return 0;
}

L'output generato è il seguente:

Codice:

*** 6 mosse ***
Riempio 1       5(5) 3(0) inf(inf)
Verso 1 in 2    5(2) 3(3) inf(inf)
Svuoto 2	5(2) 3(0) inf(inf)
Verso 1 in 2    5(0) 3(2) inf(inf)
Riempio 1       5(5) 3(2) inf(inf)
Verso 1 in 2    5(4) 3(3) inf(inf)

E come si può notare il recipiente da 5 contiene 4 litri.

Saluti

Strumenti
Mostra una versione stampabile Invia questa pagina per email