#include <stdio.h>
#include <string.h>

void swap(int &x, int &y)
{
    int h = x;
    x = y;
    y = h;
}

class Permutations
{
public:
    Permutations(int val_n) : n(val_n), _more(true)
    {
        a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = i;
    }
    ~Permutations()
    {
        delete []a;
    }
    bool more() { return _more; }
    void next()
    {
        _more = false;
        for (int i = n-2; i >= 0; i--)
            if (a[i] < a[i+1])
            {
                _more = true;
                for (int j = n-1; j > i; j--)
                    if (a[j] > a[i])
                    {
                        swap(a[j], a[i]);
                        break;
                    }
                i++;
                for (int j = n-1; j > i; j--, i++)
                    swap(a[j], a[i]);
                break;
            }
    }
    inline int operator[](int i) { return a[i]; }
private:
    int n;
    int *a;
    bool _more;
};

#define EMPTY 'x'

char v[7][7];

int x[21];
int y[21];

bool f[7][3];

int otherside(const char *sol, int f, int v)
{
    for (int p = 0; p < 21; p++)
        if (sol[p] == v + 'a')
        {
            if (x[p] == f) return y[p];
            if (y[p] == f) return x[p];
        }
    return -1;
}

int shape(const char *sol, int a, int b)
{
    for (int i = 0; i < 7; i++)
        if (f[i][a] && !f[i][b])
        {
            int n;
            n = otherside(sol, i, a);
            n = otherside(sol, n, b);
            n = otherside(sol, n, a);
            return (n == -1) ? 1 : 0;
        }
    return 2;
}

struct TriSol
{
    TriSol() : next(0) {}
    char v[22];
    int pattern[3];
    int sym;
    TriSol* next;
};
TriSol *all_tri_sols = 0;
TriSol **ref_next_tri_sol = &all_tri_sols;

bool pos_pattern[3][3][3];

void fill(char c, int p, int t)
{
    if (p == 3)
    {
        c++;
        p = 0;
        t = 0;
    }
    if (c == 'd')
    {
        char sol[22];
        char* s = sol;
        for (int i = 0; i < 6; i++)
            for (int j = i+1; j < 7; j++)
                *s++ = v[i][j];
        *s = '\0';
        bool smaller = false;
        int sym = 0;
        for (Permutations perms(7); perms.more(); perms.next())
        {
            char alt_sol[22];
            char *s = alt_sol;
            char rep[3] = { ' ', ' ', ' ' };
            char cn = 'a';
            for (int t = 0; t < 21; t++)
            {
                int i = perms[x[t]];
                int j = perms[y[t]];
                char ac = i < j ? v[i][j] : v[j][i];
                if (ac == EMPTY)
                    *s++ = EMPTY;
                else
                {
                    if (rep[ac-'a'] == ' ')
                        rep[ac-'a'] = cn++;
                    *s++ = rep[ac-'a'];
                }
            }
            *s = '\0';
            if (strcmp(alt_sol, sol) < 0)
            {
                smaller = true;
                break;
            }
            else if (strcmp(alt_sol, sol) == 0)
                sym++;
        }
        if (!smaller)
        {
            *ref_next_tri_sol = new TriSol;
            strcpy((*ref_next_tri_sol)->v, sol);
            (*ref_next_tri_sol)->pattern[0] = shape(sol, 0, 1);
            (*ref_next_tri_sol)->pattern[1] = shape(sol, 1, 2);
            (*ref_next_tri_sol)->pattern[2] = shape(sol, 2, 0);
            (*ref_next_tri_sol)->sym = sym;
            for (int r = 0; r < 3; r++)
                for (int s = 1; s <= 2; s++)
                    pos_pattern[(*ref_next_tri_sol)->pattern[r]]
                               [(*ref_next_tri_sol)->pattern[(r + s)%3]]
                               [(*ref_next_tri_sol)->pattern[(r + 2*s)%3]] = true;
            ref_next_tri_sol = &(*ref_next_tri_sol)->next;
        }
        return;
    }
    for (; t < 21; t++)
        if (v[x[t]][y[t]] == EMPTY && !f[x[t]][c-'a'] && !f[y[t]][c-'a'])
        {
            v[x[t]][y[t]] = c;
            f[x[t]][c-'a'] = true;
            f[y[t]][c-'a'] = true;
            fill(c, p+1, t+1);
            f[x[t]][c-'a'] = false;
            f[y[t]][c-'a'] = false;
            v[x[t]][y[t]] = EMPTY;
            if (p == 0)
                break;
        }
}

class OctoGroup
{
public:
    OctoGroup()
    {
        for (int i = 0; i < 12; i++)
            elements[0][i] = i;
        for (int i = 0; i < 6; i++)
            vertices[0][i] = i;
        _nr = 1;

        for (int j = 0; j < 24; j++)
        {
            int element[12];
            int vertex[6];
            
            for (int r = 0; r < 2; r++)
            {
                for (int i = 0; i < 12; i++)
                    element[_t[r][i]] = elements[j][i];
                for (int i = 0; i < 6; i++)
                    vertex[_v[r][i]] = vertices[j][i];
                _insert(element, vertex);
            }
        }
        printf("%d\n", _nr);
    }
    int elements[24][12];
    int vertices[24][6];
private:
    void _insert(int *element, int *vertex)
    {
        for (int j = 0; j < _nr; j++)
        {
            bool equal = true;
            for (int i = 0; i < 12; i++)
                if (elements[j][i] != element[i])
                    equal = false;
            for (int i = 0; i < 6; i++)
                if (vertices[j][i] != vertex[i])
                    equal = false;
            if (equal)
                return;
        }
        if (_nr == 24)
        {
            printf("Error\n");
            return;
        }
        for (int i = 0; i < 12; i++)
            elements[_nr][i] = element[i];
        for (int i = 0; i < 6; i++)
            vertices[_nr][i] = vertex[i];
        _nr++;
    }
    int _nr;
    int _t[2][12] = {
       /*  0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11 */
        {  1,  2,  0,  5,  6,  7,  8,  3,  4, 10, 11,  9 },
        {  3,  4,  1, 10,  5,  2,  0,  8,  9, 11,  6,  7 }
    };
    int _v[2][6] = {
       /*  0, 1, 2, 3, 4, 5 */
        {  1, 2, 0, 4, 5, 3 },
        {  0, 2, 3, 4, 1, 5 }
    };
};

class OctoIterator
{
public:
    OctoIterator(const OctoGroup& group) : _group(group)
    {
        for (int i = 0; i < 12; i++)
            _value[i] = 3;
        _i = 1;
        next();
    }
    bool more() { return _i == 12; }
    void next()
    {
        _i--;
        for (; _i >= 0 && _i < 12;)
        {
            if (_value[_i] == 2)
            {
                _value[_i] = 3;
                _i--;
            }
            else
            {
                if (_value[_i] == 3)
                    _value[_i] = 0;
                else
                    _value[_i]++;
                bool okay = true;
                switch (_i)
                {
                    case  2: okay = pos_pattern[_value[ 0]][_value[ 1]][_value[ 2]]; break;
                    case  4: okay = pos_pattern[_value[ 1]][_value[ 3]][_value[ 4]]; break;
                    case  6: okay = pos_pattern[_value[ 2]][_value[ 5]][_value[ 6]]; break;
                    case  8: okay = pos_pattern[_value[ 0]][_value[ 7]][_value[ 8]]; break;
                    case  9: okay = pos_pattern[_value[ 3]][_value[ 8]][_value[ 9]]; break;
                    case 10: okay = pos_pattern[_value[ 4]][_value[ 5]][_value[10]]; break;
                    case 11: okay = pos_pattern[_value[ 7]][_value[ 7]][_value[11]]
                                 && pos_pattern[_value[ 9]][_value[10]][_value[11]]; break;
                }
                for (int s = 0; s < 24 && okay; s++)
                {
                    sym[s] = true;
                    for (int i = 0; i < 12; i++)
                        if (_value[_group.elements[s][i]] != _value[i])
                        {
                            okay = _value[_group.elements[s][i]] > _value[i];
                            sym[s] = false;
                            break;
                        }
                }
                if (okay)
                    _i++;
            }
        }
    }
    int operator[](int i) { return _value[i]; }
    bool sym[24];
private:
    const OctoGroup& _group;
    int _i;
    int _value[12];
};

class Patterns
{
public:
    Patterns()
    {
        for (int i = 0; i < 3; i++)
            _used[i] = 0;
        _c = 0;
        _fill_pattern(0, 0, false);
        
        for (int i = 0; i < 105; i++)
        {
            int *p1 = all_patterns[i];
            for (int j = 0; j < 105; j++)
            {
                match[i][j] = 2;
                int *p2 = all_patterns[j];
                for (int k = 0; k < 7; k++)
                    if (p1[k] != 3 && p2[k] != 3 && _pmatch(k, p1) == _pmatch(k, p2))
                    {
                        match[i][j] = 3;
                        break;
                    }
                if (match[i][j] == 2)
                {
                    for (int k = 0; k < 7; k++)
                        if (p1[k] < 3 && p2[k] == 3)
                        {
                            k = _pmatch(k, p1);
                            k = _pmatch(k, p2);
                            k = _pmatch(k, p1);
                            match[i][j] = k == -1 ? 1 : 0;
                            break;
                        }
                }
            }
        }
    }
    int all_patterns[105][7];
    char match[105][105];
private:
    int _pattern[7];
    int _used[3];
    int _c;
    
    void _fill_pattern(int i, int j, bool e)
    {
        if (i == 7)
        {
            for (int k = 0; k < 7; k++)
                all_patterns[_c][k] = _pattern[k];
            _c++;
            return;
        }
        
        for (int k = 0; k <= j && k < 3; k++)
            if (_used[k] < 2)
            {
                _used[k]++;
                _pattern[i] = k;
                _fill_pattern(i+1, k+1 > j ? k+1 : j, e);
                _used[k]--;
            }
        if (!e)
        {
            _pattern[i] = 3;
            _fill_pattern(i+1, j, true);
        }
    }
    int _pmatch(int k, int *p)
    {
        for (int i = 0; i < 7; i++)
            if (i != k && p[k] == p[i])
                return i;
        return -1;
    }
};

int main(int argc, char *argv[])
{
    int t = 0;
    for (int i = 0; i < 6; i++)
        for (int j = i+1; j < 7; j++)
        {
            v[i][j] = EMPTY;
            x[t] = i;
            y[t] = j;
            t++;
        }    
    
    for (int i = 0; i < 7; i++)
        for (int j = 0; j < 3; j++)
            f[i][j] = false;
    
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            for (int k = 0; k < 3; k++)
                pos_pattern[i][j][k] = false;
    
    fill('a', 0, 0);

    for (TriSol *triSol = all_tri_sols; triSol != 0; triSol = triSol->next)
    {
        printf("%d %d %d %s %d\n",
            triSol->pattern[0], triSol->pattern[1], triSol->pattern[2], triSol->v, triSol->sym);
    }

    Patterns patterns;
    
    OctoGroup octoGroup;

    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
            for (int k = 0; k < 3; k++)
                printf("%c", pos_pattern[i][j][k] ? 'T' : 'F');
        printf("\n");
    }
    
    FILE *fout = fopen("out2.txt","wt");
    
    int c = 0;
    int c2 = 0;
    int c3 = 0;
    for (OctoIterator it(octoGroup); it.more(); it.next())
    {
        for (int i = 0; i < 12; i++)
            printf("%2d", it[i]);
        printf("\n");
        c++;
        
        int sol[8];
        sol[0] = 0;
        for (sol[1] = 0; sol[1] < 105; sol[1]++) 
            if (patterns.match[sol[0]][sol[1]] == it[2])
            {
                for (sol[2] = 0; sol[2] < 105; sol[2]++)
                    if (   patterns.match[sol[0]][sol[2]] == it[1] 
                        && patterns.match[sol[1]][sol[2]] == it[0])
                        for (sol[3] = 0; sol[3] < 105; sol[3]++)
                            if (   patterns.match[sol[0]][sol[3]] == it[4] 
                                && patterns.match[sol[2]][sol[3]] == it[3])
                                for (sol[4] = 0; sol[4] < 105; sol[4]++)
                                    if (   patterns.match[sol[0]][sol[4]] == it[5] 
                                        && patterns.match[sol[1]][sol[4]] == it[6] 
                                        && patterns.match[sol[3]][sol[4]] == it[10])
                                        for (sol[5] = 0; sol[5] < 105; sol[5]++)
                                            if (   patterns.match[sol[1]][sol[5]] == it[7] 
                                                && patterns.match[sol[2]][sol[5]] == it[8] 
                                                && patterns.match[sol[3]][sol[5]] == it[9] 
                                                && patterns.match[sol[4]][sol[5]] == it[11])
                                            {
                                                printf("  ");
                                                for(int i = 0; i < 6; i++)
                                                    printf(" %3d", sol[i]);
                                                bool some_smaller = false;
                                                int symmetries = 1;
                                                for (int r = 1; r < 24; r++)
                                                    if (it.sym[r])
                                                    {
                                                        bool smaller = false;
                                                        bool equal = true;
                                                        for (int v = 0; v < 6; v++)
                                                            if (sol[octoGroup.vertices[r][v]] != sol[v])
                                                            {
                                                                smaller = sol[octoGroup.vertices[r][v]] < sol[v];
                                                                equal = false;
                                                                break;
                                                            }
                                                        if (smaller)
                                                        {
                                                            some_smaller = true;
                                                            printf(" (%d)", r);
                                                        }
                                                        if (equal)
                                                            symmetries++;
                                                    }
                                                for (int r = 0; r < 24; r++)
                                                    if (it.sym[r])
                                                    {
                                                        Permutations perm(7);
                                                        for (perm.next(); perm.more() && !some_smaller; perm.next())
                                                        {
                                                            bool smaller = false;
                                                            bool equal = true;
                                                            for (int v = 0; v < 6; v++)
                                                            {
                                                                int new_vector[7];
                                                                int map[3] = { -1, -1, -1 };
                                                                int nr = 0;
                                                                for (int k = 0; k < 7; k++)
                                                                {
                                                                    int m = patterns.all_patterns[sol[v]][perm[k]];
                                                                    if (m < 3)
                                                                    {
                                                                        if (map[m] == -1)
                                                                            map[m] = nr++;
                                                                        m = map[m];
                                                                    }
                                                                    new_vector[k] = m;
                                                                }
                                                                int new_sol;
                                                                for (new_sol = 0; new_sol < 105; new_sol++)
                                                                {
                                                                    bool equal = true;
                                                                    for (int k = 0; k < 7; k++)
                                                                        if (new_vector[k] != patterns.all_patterns[new_sol][k])
                                                                        {
                                                                            equal = false;
                                                                            break;
                                                                        }
                                                                    if (equal)
                                                                        break;
                                                                }
                                                                if (new_sol == 105)
                                                                {
                                                                    printf("\nError\n");
                                                                    for (int k = 0; k < 7; k++)
                                                                        printf(" %d", perm[k]);
                                                                    printf("\n");
                                                                    for (int k = 0; k < 7; k++)
                                                                        printf(" %d", patterns.all_patterns[sol[v]][k]);
                                                                    printf("\n");
                                                                    for (int k = 0; k < 7; k++)
                                                                        printf(" %d", new_vector[k]);
                                                                    printf("\n");
                                                                    
                                                                    return -1;
                                                                }
                                                                
                                                                if (new_sol != sol[v])
                                                                {
                                                                    smaller = new_sol < sol[v];
                                                                    equal = false;
                                                                    break;
                                                                }
                                                            }
                                                            if (smaller)
                                                            {
                                                                some_smaller = true;
                                                                printf(" (%d", r);
                                                                for (int k = 0; k < 7; k++)
                                                                    printf("%c%d", k == 0 ? ':' : ',', perm[k]);
                                                                printf(")");
                                                            }
                                                            if (equal)
                                                                symmetries++;
                                                        }
                                                    }
                                                printf(" = %d\n", symmetries);
                                                c2++;
                                                if (!some_smaller)
                                                {
                                                    for (int k = 0; k < 6; k++)
                                                        fprintf(fout, "%4d", sol[k]);
                                                    fprintf(fout, "\n");
                                                    c3++;
                                                }
                                            }
                break;
            }
    }
    fclose(fout);
    printf("# = %d %d %d\n", c, c2, c3);
    
}