#include <iostream>
#include <vector>
#include <set>
#include <memory.h>
#include "math.h"

using namespace std;

#define MAXNUM 3

static vector<int*> permutations;

struct Data
{
    int* arrangement;
    bool* isEmpty;
    int nextNumberToInsert;
};

void Permute(struct Data *input)
{
    if (input->nextNumberToInsert == MAXNUM)
    {
        for (int i=0; i<=MAXNUM; i++)
        {
            if (input->isEmpty[i])
            {
                input->arrangement[i] = input->nextNumberToInsert;
                break;
            }
        }

        cout << "Pushing onto back: ";
        for (int a=0; a<=MAXNUM; a++) cout << input->arrangement[a] << " ";
        permutations.push_back(input->arrangement);
        cout << endl;
        cout << "Back is: ";
        for (int a=0; a<=MAXNUM; a++) cout << permutations.back()[a] << " ";
        cout << endl;
        cout << "Front is: ";
        for (int a=0; a<=MAXNUM; a++) cout << permutations.front()[a] << " ";
        cout << endl;
        sleep(5);
    }
    else
    {
        // Iterate over all the empty spaces, inserting the next number in each, spawning a new search branch each time.
        for (int i=0; i<=MAXNUM; i++)
        {
            if (input->isEmpty[i])
            {
                // Copy the input data
                struct Data *inputCopy = new struct Data;
                inputCopy->arrangement = new int[MAXNUM+1];
                inputCopy->isEmpty = new bool[MAXNUM+1];
                memcpy(inputCopy->arrangement, input->arrangement, (MAXNUM+1)*sizeof(int));
                memcpy(inputCopy->isEmpty, input->isEmpty, (MAXNUM+1)*sizeof(bool));

                inputCopy->arrangement[i] = input->nextNumberToInsert;
                inputCopy->isEmpty[i] = false;
                inputCopy->nextNumberToInsert = input->nextNumberToInsert + 1;

                Permute(inputCopy);

                delete inputCopy->arrangement;
                delete inputCopy->isEmpty;
                delete inputCopy;
            }
        }
    }
}

int main()
{
    struct Data seed;
    seed.arrangement = new int[MAXNUM+1];
    seed.isEmpty = new bool[MAXNUM+1];

    seed.nextNumberToInsert = 0;
    memset(seed.isEmpty, true, (MAXNUM+1)*sizeof(bool));

    Permute(&seed);

    cout << permutations[0][0] << endl;

    cout << "permutations complete: " << permutations.size() << endl;

    return 0;

    std::set<int> pandigital_product;
    //for (std::vector<int*>::iterator iter=permutations.begin(); iter != permutations.end(); iter++)
    for (int index=0; index<permutations.size(); index++)
    {
        cout << index << endl;
        for (int a=0; a<=MAXNUM; a++) cout << (permutations[index])[a] << endl;
        cout << endl;
        sleep(1);
        for (int i=0; i<=MAXNUM-2; i++)
        {
            for (int j=i+1; j<=MAXNUM-1; j++)
            {
                long lhs1 = 0;
                for (int a=0; a<=i; a++)
                {
                    lhs1 *= 10;
                    lhs1 += (permutations[index])[a];
                }

                long lhs2 = 0;
                for (int a=i+1; a<=j; a++)
                {
                    lhs2 *= 10;
                    lhs2 += (permutations[index])[a];
                }

                long rhs = 0;
                for (int a=j+1; a<=MAXNUM; a++)
                {
                    rhs *= 10;
                    rhs += (permutations[index])[a];
                }

//                for (int a=0; a<=9; a++) cout << (*iter)[a];
//                cout << endl;
//                cout << lhs1 << ", " << lhs2 << ", " << rhs << endl;
//                sleep(1);

                if (lhs1*lhs2 == rhs) pandigital_product.insert(rhs);
            }
        }
    }

    int sum = 0;
    for (std::set<int>::const_iterator iter=pandigital_product.begin(); iter != pandigital_product.end(); iter++)
    {
        sum += *iter;
    }
    cout << sum;

    return 0;
}