#include <iostream>
#include <algorithm>
#include <vector>

template <typename T>
class matrix {
public:

	size_t cols;
	size_t rows;

private:

	std::vector<T> data;

public:

	matrix() : cols(0), rows(0) {

	}
	matrix(const size_t cols, const size_t rows) : cols(cols), rows(rows) {
		data = std::vector<T>(cols * rows);
	}
	matrix(const size_t cols, const size_t rows, const T val) : cols(cols), rows(rows) {
		data = std::vector<T>(cols * rows, val);
	}

	T& operator()(const size_t col, const size_t row) {
		return data[col * rows + row];
	}

	const T& operator()(const size_t col, const size_t row) const {
		return data[col * rows + row];
	}

	matrix<T> rotate() const {
		matrix<T> new_mat;

		new_mat = matrix(rows, cols);
		for (size_t col = 0; col < new_mat.cols; col++) {
			for (size_t row = 0; row < new_mat.rows; row++) {
				new_mat(col, row) = operator()(row, (rows - 1) - col);
			}
		}

		return new_mat;
	}

	matrix<T> copy(const size_t c_col, const size_t c_row, size_t c_cols, size_t c_rows) const {

		if (c_col + c_cols > cols - 1) {
			c_cols = cols - c_col;
		}
		if (c_row + c_rows > rows - 1) {
			c_rows = rows - c_row;
		}

		matrix<T> new_mat = matrix(c_cols, c_rows);

		for (size_t col = 0; col < c_cols; col++) {
			for (size_t row = 0; row < c_rows; row++) {
				//std::cout << "(" << c_col + col << ", " << c_row + row << ") --> (" << col << ", " << row << ")" << std::endl;
				new_mat(col, row) = operator()(c_col + col, c_row + row);
				//std::cout << "(" << col << ", " << row << ") = " << i << std::endl;

			}
		}

		return new_mat;
	}

	// You should change this to use a predicate to decide whether or not a value should be cropped.
	matrix<T> crop(const T empty_val) const {

		matrix<T> new_mat = *this;
		// Use rotation to help crop!

		int i = 4;
		while (i --> 0) {
			bool do_break = false;
			for (size_t col = 0; col < new_mat.cols; col++) {
				if (do_break) {
					break;
				}

				for (size_t row = 0; row < new_mat.rows; row++) {
					if (new_mat(col, row) != empty_val) {
						new_mat = new_mat.copy(col, 0, new_mat.cols - col, new_mat.rows).rotate();
						do_break = true;
						break;
					}
				}
			}
		}
		return new_mat;
	}

	// You have to go first by rows and then by columns since printing is sort of "row major".
	void print() const {
		for (size_t row = 0; row < rows; row++) {
			for (size_t col = 0; col < cols; col++) {
				std::cout << this->operator()(col, row) << ' ';
			}
			std::cout << std::endl;
		}

		std::cout << std::endl;
	}
};

int main() {

	std::vector<std::string> words = { "colorful", "dividend", "fourteen", "alsatian" };

	size_t side_size = 28;

	matrix<char> empty_mat(side_size, side_size, ' ');
	matrix<char> best_mat(side_size, side_size, ' ');

	// Try each possible sequence of words. For each word that you try, try every possible place that word can fit.
	std::sort(words.begin(), words.end());
	do {
		matrix<char> mat(empty_mat);
		for (std::string s : words) {
			size_t this_col = 0;
			size_t this_row = 0;

			bool good = true;
			bool do_break = false;

			int r = 4;
			while (r--> 0) {
				if (do_break == true) break;

				// Rotate the matrix ninety degrees each time and only deal with the forward horizontal case.
				mat = mat.rotate();

				// Find a place to try the word.
				for (size_t i = 0; i < s.size(); i++) {
					char& c = s[i];
					if (do_break == true) break;
					for (size_t col = 0; col < mat.cols; col++) {
						if (do_break == true) break;
						for (size_t row = 0; row < mat.rows; row++) {
							good = false;
							if (mat(col, row) == c) {
								good = true;
								// Make sure that the word isn't colliding with anything already there.
								for (size_t k = col - i; k < col - i + s.size(); k++) {
									for (size_t q = row - 1; q <= row + 1; q++) {
										if (q == 0) {
											if ((mat(k, row) != ' ') && (mat(k, row) != s[(k) - (col - i)])) {
												good = false;
												break;
											}
										}
										else if (k != col) {
											if (mat(k, q) != ' ') {
												good = false;
												break;
											}
										}
									}
								}
							}
							if (good) {
								this_col = col - i;
								this_row = row;

								do_break = true;
								break;
							}
						}
					}
				}
			}

			if (this_col == 0 && this_row == 0) {
				this_col = side_size / 2;
				this_row = side_size / 2;
			}

			for (char c : s) {
				mat(this_col++, this_row) = c;
			}
		}

//		for (std::string s : words) {
//			std::cout << s << ' ';
//		}
		std::cout << std::endl;

		mat.crop(' ').print();

	} while (std::next_permutation(words.begin(), words.end()));

	return 0;
}