/*
 * Copyright (c) 2004 Daniel Hartmeier <daniel@benzedrine.ch>
 * All rights reserved.
 * 
 * "Four people come to a river in the night. There is a narrow bridge, but it
 *  can only hold two people at a time. Because it's night, the torch has to be
 *  used when crossing the bridge. Person A can cross the bridge in 1 minute,
 *  B in 2 minutes, C in 5 minutes, and D in 8 minutes. When two people cross
 *  the bridge together, they must move at the slower person's pace.
 *  The question is, can they all get across the bridge in 15 minutes or less?"
 *
 *  -- http://en.wikipedia.org/wiki/Bridge_and_torch_problem
 *
 */

#include <iostream>
#include <set>
#include <queue>
#include <list>
#include <string>
#include <stdio.h>

using namespace std;

struct Situation {
	set<int>	left, right;
	bool		torchLeft;
	int		minutesPassed;
	list<string>	description;
};

bool operator<(const Situation &a, const Situation &b)
{
	return a.minutesPassed > b.minutesPassed;
}

int main()
{
	const char *n[] = { 0, "A", "B", 0, 0, "C", 0, 0, "D" };
	priority_queue<Situation> q;
	Situation s;
	char d[256];

	// initial situation: all persons and torch on the left
	s.left.insert(1);
	s.left.insert(2);
	s.left.insert(5);
	s.left.insert(8);
	s.torchLeft = true;
	s.minutesPassed = 0;
	q.push(s);

	while (!q.empty()) {

		// q is sorted by minutesPassed increasing, get the top-most
		// entry, which has the shortest minutesPassed of the queue
		s = q.top();
		q.pop();

		// if all persons are on the right, this is a solution
		if (s.left.empty()) {
			cout << "solution found: " << s.minutesPassed <<
			    " minutes" << endl;
			for (list<string>::iterator i = s.description.begin();
			    i != s.description.end(); ++i)
				cout << "  " << *i << endl;
			cout << endl;
			break;
		}

		set<int> &src = s.torchLeft ? s.left : s.right;

		// single person moving
		for (set<int>::iterator i = src.begin(); i != src.end(); ++i) {
			Situation t = s;
			if (t.torchLeft) {
				t.left.erase(*i);
				t.right.insert(*i);
			} else {
				t.right.erase(*i);
				t.left.insert(*i);
			}
			t.minutesPassed += *i;
			if (t.minutesPassed >= 18)
				continue;
			snprintf(d, sizeof(d), "%s moves %s (%d minutes, %d "
			    "total)", n[*i], t.torchLeft ? "across" : "back",
			    *i, t.minutesPassed);
			t.description.insert(t.description.end(), d);
			t.torchLeft = !t.torchLeft;
			q.push(t);
		}

		// two persons moving
		for (set<int>::iterator i = src.begin(); i != src.end(); ++i)
			for (set<int>::iterator j = i; j != src.end(); ++j) {
				if (j == i)
					continue;
				Situation t = s;
				if (t.torchLeft) {
					t.left.erase(*i);
					t.left.erase(*j);
					t.right.insert(*i);
					t.right.insert(*j);
				} else {
					t.right.erase(*i);
					t.right.erase(*j);
					t.left.insert(*i);
					t.left.insert(*j);
				}
				t.minutesPassed += *i > *j ? *i : *j;
				if (t.minutesPassed >= 18)
					continue;
				snprintf(d, sizeof(d), "%s and %s move %s (%d "
				    "minutes, %d total)", n[*i], n[*j],
				    t.torchLeft ? "across" : "back",
				    *i > *j ? *i : *j, t.minutesPassed);
				t.description.insert(t.description.end(), d);
				t.torchLeft = !t.torchLeft;
				q.push(t);
			}
	}

	return 0;
}