// Function: To partition a square number into square numbers.
//           Produces A037444.
//
// Developed by Don Reble and subsequently by Chris Gribble in 2013.

#include <cstdlib>
#include <iostream>
#include <fstream>

using namespace std;

static const int MaxSize = 128;		// Maximum side length of square.

static int NumPartitions;			// Number of partitions generated.
static int NumParts;				// Number of parts in a partition.
static int PrevQuants2;				// Previous value of Quants[2].
static int Quants[MaxSize];			// Parts 2:Size of partition of square number into squares.
static int Size;					// User specified size of square root of square number.
static int TotalParts;				// Total number of parts in all partitions.
static int TotalRuns;				// Total number of runs of 2 X 2 squares in the set of partitions.
static int Totals[MaxSize];			// Total number of parts of each size in all partitions.

fstream OpFile;						// Output file.

void doPartitions (int maxsize, int arealeft)
{
	int area;
	int i;							// Loop counter.
	int maxquan;

	if (maxsize <= 1)
	{
		// Output partition.
		// Here, arealeft = number of 1 X 1 squares in the partition,
		// and Quants[2:Size] contains the numbers of larger squares.
		// Quants[0:1] are unused.

		NumPartitions++;

//		OpFile << arealeft;
		NumParts = arealeft;
		Totals[1] = Totals[1] + arealeft;

		for (i = 2; i <= Size; i++)
		{
			if (i == 2)
			{
//				OpFile << " " << Quants[i];

				if (Quants[2] >= PrevQuants2)
				{
					TotalRuns++;
					OpFile << Quants[2] + 1 << endl;
				}

				PrevQuants2 = Quants[2];
			}

//			NumParts = NumParts + Quants[i];
			Totals[i] = Totals[i] + Quants[i];
		}

//		OpFile << "    " << NumParts << endl;
//		OpFile << NumParts << endl;

		TotalParts = TotalParts + NumParts;

		return;
	}

	int &qu = Quants[maxsize];
	area = maxsize * maxsize;
	maxquan = arealeft / area;
	arealeft = arealeft - maxquan * area;

	for (qu = maxquan; qu >= 0; qu--)
	{
		doPartitions (maxsize - 1, arealeft);
		arealeft = arealeft + area;
	}
}

int main ()
{
	int i;							// Loop counter.

	/* Create output file. */

	OpFile.open("sqPartition 2.txt", ios_base::out | ios_base::trunc);

	/* Get side length of square. */

	cout << "Enter square root of square number ";
	cin  >> Size;

	OpFile << "Square root of square number = "<< Size << endl << endl;

	if ((Size <= 0) || (Size >= MaxSize))
	{
		OpFile << "Square root of square number " << Size << "out of range." << endl;
		return 1;
	}

	OpFile << endl << "Lengths of 2 X 2 runs" << endl;

	doPartitions (Size, Size * Size);

//	for (i = 1; i <= Size; i++)
//	{
//		OpFile << Totals[i] << "  ";
//	}

//	OpFile << "  " << TotalParts << endl;

	OpFile << endl << "Number of 2 X 2 runs = " << TotalRuns << endl;
	OpFile << endl << "Number of partitions = " << NumPartitions << endl;
	OpFile << endl << "Program complete" << endl;

	return 0;
}