Coin Puzzle

main.cpp

#include <vector>
#include <iostream>
using namespace std;

int ans[] = {100, 10, 100, 10, 100, 10, 100, 10};

void debug(vector<int> v)
{
	int i;

	for(i = 0; i < v.size(); i++)
		cout << v[i] << " ";
	cout << endl;
}

bool search(vector<int> v, int n)
{
	int i, j;
	vector<int> w;

	for(i = 0; i < v.size(); i++)
		if(v[i] != 0)
			break;
	for(j = i; j < v.size(); j++)
		w.push_back(v[j]);
	v.assign(w.begin(), w.end());
	w.clear();

	for(i = v.size() - 1; i > -1; i--)
		if(v[i] != 0)
			break;
	for(j = 0; j <= i; j++)
		w.push_back(v[j]);
	v.assign(w.begin(), w.end());
	w.clear();

	if(n == 0) {
		for(j = 0; j < 8; j++)
			if(v[j] != ans[j])
				break;
		if(j == 8)
			return true;
		return false;
	} else {
		for(i = 0; i < v.size() - 1; i++) {
			if(!v[i] || !v[i + 1])
				continue;

			w.assign(v.begin(), v.end());
			w[i] = 0;
			w[i + 1] = 0;
			w.push_back(v[i]);
			w.push_back(v[i + 1]);
			if(search(w, n - 1)) {
				debug(w);
				return true;
			}
			w.clear();

			w.push_back(v[i]);
			w.push_back(v[i + 1]);
			for(j = 0; j < v.size(); j++)
				w.push_back(v[j]);
			w[i + 2] = 0;
			w[i + 3] = 0;
			if(search(w, n - 1)) {
				debug(w);
				return true;
			}
			w.clear();

			for(j = 0; j < v.size() - 1; j++) {
				if(v[j] || v[j + 1])
					continue;
				w.assign(v.begin(), v.end());
				w[j] = w[i];
				w[j + 1] = w[i + 1];
				w[i] = 0;
				w[i + 1] = 0;
				if(search(w, n - 1)) {
					debug(w);
					return true;
				}
				w.clear();
			}
		}
		return false;
	}
}

int main(void)
{
	int i;
	vector<int> v;

	for(i = 0; i < 4; i++)
		v.push_back(10);
	for(i = 0; i < 4; i++)
		v.push_back(100);

	search(v, 4);
	return 0;
}