windmill.cpp

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef int64_t ll;

struct state {
	int numArms, numToken;
	vvi arms;
	state(int _numArms, int _numToken) {
		numArms = _numArms;
		numToken = _numToken;
		arms.resize(numArms);
		for (int i = 0; i < numToken; i++) {
			arms[0].push_back(i);
		}
	}
	state(const state& other) {
		numArms = other.numArms;
		numToken = other.numToken;
		arms = vvi(other.arms);
	}
	bool moveToLeft = true;
	void moveToken(int from) {
		int to = from;
		if (moveToLeft) to--;
		else to++;
		if (to < 0) to += numArms;
		if (numArms <= to) to -= numArms;
		arms[to].push_back(arms[from].back());
		arms[from].pop_back();
		moveToLeft = not moveToLeft;
	}
	void emptyArm(int from) {
		while (not arms[from].empty()) moveToken(from);
	}
	string toString() {
		stringstream buf;
		for (auto arm : arms) {
			for (auto token : arm) {
				buf << token << " ";
			}
			buf << endl;
		}
		return buf.str();
	}
	bool operator<(const state& other) const {
		return arms < other.arms;
	}
};

int main() {
	state root(3,5);
	set<state> visited;
	visited.insert(root);
	queue<pair<state,vi>> todo;
	todo.push({root,{}});
	while (not todo.empty()) {
		auto [s, path] = todo.front();
		todo.pop();
		if ((int)s.arms[0].size() == s.numToken) {
			for (auto token : s.arms[0]) {
				cout << token << " ";
			} 
			cout << ":";
			for (auto arm : path) {
				cout << " " << arm;
			}
			cout << endl;
		}
		for (int arm = 0; arm < s.numArms; arm++) {
			state next(s);
			next.emptyArm(arm);
			vi newpath(path);
			newpath.push_back(arm);
			if (not visited.contains(next)) {
				visited.insert(next);
				todo.push({next,newpath});
			}
		}
	}

	return 0;
}