/*                        Copyright (C) 2016 Frans Faase

   This program generates the combinations of two non-overlapping
   polygon triagulations, and the number of ways they can be
   'coloured'.
      
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

GNU General Public License:
   http://www.iwriteiam.nl/GNU.txt

Details:
   http://www.iwriteiam.nl/D1602.html#16

*/

#include <stdio.h>

#define MAX_SIZE 30


class CatalanIterator
{
public:
    CatalanIterator(int n) : _n(n), _d(0)
    {
        iters[0].start = 0;
        iters[0].end = n;
        iters[0].i = 0;
        iters[0].value = 1;
        next();
    }
    bool more() { return _d >= 0; }
    void next()
    {
        if (_d > 0)
        {
            for (; _d >= 0; _d--)
            {
                if (++iters[_d].i < iters[_d].end)
                    break;
            }
            if (_d < 0)
                return;
        }
        for (;;_d++)
        {
            int start = iters[_d].start;
            int end = iters[_d].end;
            int i = iters[_d].i;
            int value = iters[_d].value;
            if (i == end)
            {
                i = start;
                iters[_d].i = i;
            }
            v[i] = value;
            if (_d == _n - 1)
                break;
            if (i > start)
            {
                int n_d = _d + 1;
                iters[n_d].start = start;
                iters[n_d].end = i;
                iters[n_d].i = start;
                iters[n_d].value = value + 1;
            }
            if (i + 1 < end)
            {
                int n_d = _d + 1 + i - start;
                iters[n_d].start = i + 1;
                iters[n_d].end = end;
                iters[n_d].i = i + 1;
                iters[n_d].value = value + 1;
            }
        }
    }
    int n() const { return _n; }
    void print(FILE *f)
    {
        for (int i = 0; i < _n; i++)
            fprintf(f,"%s%d", i > 0 ? " " : "", v[i]);
    }    
    
    int v[MAX_SIZE];
    
private:
    int _n;
    int _d;
    struct {
        int start;
        int end;
        int value;
        int i;
    } iters[MAX_SIZE];
};

class AbstractRingTranslation
{
public:
    virtual int translate(int i) const = 0;
};
    
class RegularPolygonTriangulation
{
public:
    RegularPolygonTriangulation() : _n(0) {}
    RegularPolygonTriangulation(const CatalanIterator& catalanIterator) : _n(0)
    {
        int n = catalanIterator.n();
        _n_d = n + 2;
        for (int i = 0; i < _n_d; i++)
            _d[i] = 0;
        for (int i = 0; i < n; i++)
        {
            int v = catalanIterator.v[i];
            int f = 0;
            for (int j = i - 1; j >= 0 && catalanIterator.v[j] > v; j--)
                f++;
            if (f > 0)
                _insert(i-f, i+1);
            int t = 0;
            for (int j = i + 1; j < n && catalanIterator.v[j] > v; j++)
                t++;
            if (t > 0)
                _insert(i+1, i+t+2);
        }
    }
    RegularPolygonTriangulation(const RegularPolygonTriangulation& source, const AbstractRingTranslation& translation) : _n(0)
    {
        for (int i = 0; i < source.n(); i++)
        {
            int f = translation.translate(source.from(i));
            int t = translation.translate(source.to(i));
            if (f < t)
                _insert(f,t);
            else
                _insert(t,f);
        }
    }
    int n() const { return _n; }
    int degrees() const { return _n_d; }
    int min_degree(const RegularPolygonTriangulation &other) const
    {
        int min_d = 1000;
        for (int i = 0; i < _n_d; i++)
        {
            int d = _d[i] + other._d[i] + 2;
            if (d < min_d)
                min_d = d;
        }
        return min_d;
    }
    int common(const RegularPolygonTriangulation &other) const
    {
        int c = 0;
        int i1 = 0;
        int i2 = 0;
        while (i1 < _n && i2 < _n)
            if (_f[i1] < other._f[i2])
                i1++;
            else if (_f[i1] > other._f[i2])
                i2++;
            else if (_t[i1] < other._t[i2])
                i1++;
            else if (_t[i1] > other._t[i2])
                i2++;
            else
            {
                c++;
                i1++;
                i2++;
            }
        return c;
    }
    int compare(const RegularPolygonTriangulation &lhs) const
    {
        for (int i = 0; i < _n; i++)
        {
            if (_f[i] < lhs._f[i])
                return -1;
            if (_f[i] > lhs._f[i])
                return 1;
            if (_t[i] < lhs._t[i])
                return -1;
            if (_t[i] > lhs._t[i])
                return 1;
        }
        return 0;
    }
    void print(FILE *f) const
    {
        for (int i = 0; i < _n; i++)
            fprintf(f, " %d-%d", _f[i], _t[i]);
    }
    void printDegrees(FILE *f) const
    {
        for (int i = 0; i < _n_d; i++)
            fprintf(f, " %d", _d[i]);
    }
        
    inline int from(int i) const { return _f[i]; }
    inline int to(int i) const { return _t[i]; }
    inline int degree(int i) const { return _d[i]; }
    
protected:
    void _clear()
    {
        _n = 0;
    }
    void _insert(int f, int t)
    {
        _d[f]++;
        _d[t]++;
        int i = 0;
        while (i < _n && (_f[i] < f || (_f[i] == f && _t[i] < t)))
            i++;
        _n++;
        for (int j = _n; j > i; j--)
        {
            _f[j] = _f[j-1];
            _t[j] = _t[j-1];
        }
        _f[i] = f;
        _t[i] = t;
    }
private:
    int _n;
    int _f[MAX_SIZE-1];
    int _t[MAX_SIZE-1];
    int _n_d;
    int _d[MAX_SIZE+1];
};

class RotMirTranslationIterator : public AbstractRingTranslation
{
public:
    RotMirTranslationIterator(int m, bool include_initial = false)
    : _m(m), _mir(false), _rot(include_initial ? 0 : 1)
    {
    }
    bool more() { return !_mir || _rot < _m; }
    void next()
    {
        _rot++;
        if (_rot == _m && !_mir)
        {
            _mir = true;
            _rot = 0;
        }
    }
    virtual int translate(int i) const
    {
        return (_mir ? _m + _rot - i : _rot + i) % _m;
    }
private:
    int _m;
    int _rot;
    bool _mir;
};

class RegularPolygonTriangulationRotMirIterator : public RegularPolygonTriangulation
{
public:
    RegularPolygonTriangulationRotMirIterator(const RegularPolygonTriangulation& rpt, int m)
    : _rpt(rpt), _m(m), _mir(false), _rot(1)
    {
        _fill();
    }
    bool more() { return !_mir || _rot < _m; }
    void next()
    {
        _rot++;
        if (_rot == _m && !_mir)
        {
            _mir = true;
            _rot = 0;
        }
        if (more())
            _fill();
    }
    int translate(int i)
    {
        return (_mir ? _m + _rot - i : _rot + i) % _m;
    }
private:
    void _fill()
    {
        _clear();
        for (int i = 0; i < _rpt.n(); i++)
        {
            int f = translate(_rpt.from(i));
            int t = translate(_rpt.to(i));
            if (f < t)
                _insert(f,t);
            else
                _insert(t,f);
        }
    }
    RegularPolygonTriangulation _rpt;
    int _m;
    int _rot;
    bool _mir;
};

inline int mod(int v, int d) { return (v = v % d) < 0 ? v + 3 : v; }

class Mod3Int
{
public:
    Mod3Int() : _v(0) {}
    Mod3Int(int v) : _v(mod(v,3)) {}
    Mod3Int(const Mod3Int& v) : _v(v._v) {}
    void clear() { _v = 0; }
    int value() { return _v; }
    Mod3Int invert() { return _v == 0 ? 0 : 3 - _v; }
    Mod3Int& operator++(int) { _v = (_v + 1) % 3; return (*this); }
    Mod3Int operator+(int rhs) { return mod(_v + rhs, 3); }
    Mod3Int operator+(const Mod3Int& rhs) { return (_v + rhs._v) % 3; }
    bool operator==(const Mod3Int& rhs) { return _v == rhs._v; }
    bool operator!=(const Mod3Int& rhs) { return _v != rhs._v; }
    bool operator<(const Mod3Int& rhs) { return _v < rhs._v; }
    Mod3Int& operator+=(int v) { _v = (_v + v) % 3; return (*this); }
    Mod3Int& operator+=(const Mod3Int& rhs) { _v = (_v + rhs._v) % 3; return (*this); }
private:
    char _v;
};

class AllSequencesIterator
{
public:
    AllSequencesIterator(const CatalanIterator& catalanIterator) : _n(catalanIterator.n()+2)
    {
        for (int i = 0; i < _n - 2; i++)
        {
            int v = catalanIterator.v[i];
            int l = i - 1;
            while (l >= 0 && catalanIterator.v[l] > v)
                l--;
            _l[i] = l + 1;    
            int r = i + 1;
            while (r < _n - 2 && catalanIterator.v[r] > v)
                r++;
            _r[i] = r + 1;
        }
        _np2 = 1 << (_n - 2);
        _i = 0;
        next();
    }
    bool more() { return _i <= _np2; }
    void next()
    {
        for (int i = 0; i < _n; i++)
            v[i].clear();
        unsigned int k = _i;
        for (int i = 0; i < _n - 2; i++)
        {
            int a = k & 1 ? 2 : 1;
            k = k / 2;
            v[_l[i]] += a;
            v[i+1] += a;
            v[_r[i]] += a;
        }
        _i++;
    }
    bool operator==(const AllSequencesIterator& rhs)
    {
        for (int i = 0; i < _n; i++)
            if (v[i] != rhs.v[i])
                return false;
        return true;
    }
    void print(FILE *f)
    {
        for (int i = 0; i < _n; i++)
            fprintf(f, "%d", v[i].value());
    }
    Mod3Int v[MAX_SIZE+2];
private:
    int _n;
    int _r[MAX_SIZE];
    int _l[MAX_SIZE];
    unsigned int _i;
    unsigned int _np2;
};

class PairCounter
{
public:
    PairCounter() : n(0) {}
    void add(int na, int nb, int c)
    {
        int i = 0;
        while (i < n && (a[i] < na || (a[i] == na && b[i] < nb)))
            i++;
        if (a[i] == na && b[i] == nb)
        {
            count[i] += c;
            return;
        }
        if (n < 100)    
            n++;
        for (int j = n; j > i; j--)
        {
            a[j] = a[j-1];
            b[j] = b[j-1];
            count[j] = count[j-1];
        }
        a[i] = na;
        b[i] = nb;
        count[i] = c;
    }
    
    int n;
    int a[100];
    int b[100];
    int count[100];
};
        
int main(int argc, char *argv[])
{
    FILE *fout = fopen("out.txt", "wt");
    for (int n = 4; n < 7; n++)
    {
        PairCounter counter;
        int c = 0;
        int c2 = 0;
        for (CatalanIterator catalanIterator(n); catalanIterator.more(); catalanIterator.next())
        {
            RegularPolygonTriangulation triangulation(catalanIterator);
            
            bool minimal = true;
            int symmetries = 1;
            for (RegularPolygonTriangulationRotMirIterator it(triangulation, n+2); it.more(); it.next())
            {
                int comp = it.compare(triangulation);
                if (comp < 0)
                {
                    minimal = false;
                    break;
                }
                if (comp == 0)
                    symmetries++;
            }
            int multiplicity;
            if (minimal)
            {
                multiplicity = 2*(n+2)/symmetries;
                c += multiplicity;
                c2++;
            }
            else
                continue;

            for (CatalanIterator catalanIterator2(n); catalanIterator2.more(); catalanIterator2.next())
            {
                RegularPolygonTriangulation triangulation2(catalanIterator2);
                
                int min_degree = triangulation.min_degree(triangulation2);

                int common_edge = triangulation.common(triangulation2);
                if (common_edge > 0)
                    continue;

                bool minimalCombo = true;
                for (RotMirTranslationIterator translationIt(n+2); translationIt.more(); translationIt.next())
                {
                    RegularPolygonTriangulation alt(catalanIterator, translationIt);
                    RegularPolygonTriangulation alt2(catalanIterator2, translationIt);
                    int compare = alt2.compare(catalanIterator);
                    if (   compare < 0 || (compare == 0 && alt.compare(catalanIterator2) < 0)
                        || (alt.compare(catalanIterator) == 0 && alt2.compare(catalanIterator2) < 0))
                    {
                        minimalCombo = false;
                        break;
                    }
                }
                if (!minimalCombo)
                    continue;
                         
                catalanIterator.print(stdout);
                triangulation.print(stdout);
                triangulation.printDegrees(stdout);
                printf("\n");
                catalanIterator2.print(stdout);
                triangulation2.print(stdout);
                triangulation2.printDegrees(stdout);
                printf("\n");
                int common_seq = 0;
                for (AllSequencesIterator allSeqIt(catalanIterator); allSeqIt.more(); allSeqIt.next())
                    for (AllSequencesIterator allSeqIt2(catalanIterator2); allSeqIt2.more(); allSeqIt2.next())
                        if (allSeqIt == allSeqIt2)
                        {
                            printf("  ");
                            allSeqIt.print(stdout);
                            printf("\n");
                            common_seq++;
                        }
                fprintf(fout, "\t{n:%d,m:%d,blue:", n, common_seq/2);
                char st = '[';
                for (int i = 0; i < triangulation.n(); i++)
                {
                    fprintf(fout, "%c%d,%d", st, triangulation.from(i), triangulation.to(i));
                    st = ',';
                }
                fprintf(fout, "],red:", common_seq/2);
                st = '[';
                for (int i = 0; i < triangulation2.n(); i++)
                {
                    fprintf(fout, "%c%d,%d", st, triangulation2.from(i), triangulation2.to(i));
                    st = ',';
                }
                fprintf(fout, "]},\n");
                counter.add(common_seq/2, min_degree, multiplicity);
            }
        }
        printf("Catalan(%d) = %d\n", n, c);
        for (int i = 0; i < counter.n; i++)
        {
            printf("%d:%d = %d\n", counter.a[i], counter.b[i], counter.count[i]);
        }
        fflush(stdout);
    }
    return 0;
}