/* PARR -- counting PARR's   Copyright (C) 2015 Frans Faase

   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://home.planet.nl/~faase009/GNU.txt

Details:
   http://www.iwriteiam.nl/D1509.html#3

*/

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

#define MAX_N 5
#define MAX_M 4
#define MAX_POINTS MAX_M*MAX_N
#define MAX_LINES (MAX_M-1)*MAX_N + MAX_M*(MAX_N-1) + 2*(MAX_M-1)*(MAX_N-1)
#define MAX_DIAG (MAX_M-1)*(MAX_N-1)

//#define USE_DOUBLE
#ifdef USE_DOUBLE
typedef double Counter;
#define FORMAT "%.0lf"
#define DFORMAT "%*.0lf"
#else
typedef unsigned long long Counter;
#define FORMAT "%lld"
#define DFORMAT "%*lld"
#endif

void countWithTransitions(bool all_lines, bool no_cross, bool connected, bool verify);


Counter counters[MAX_POINTS+1][MAX_LINES+1][MAX_DIAG+1];

void init_counters(int m, int n)
{
    const int points = n*m;
    const int lines = m*(n-1) + (m-1)*n + 2*(m-1)*(n-1);
    const int diags = (m-1)*(n-1);
    for (int p = 0; p <= points; p++)
        for (int l = 0; l <= lines; l++)
            for (int d = 0; d <= diags; d++)
                counters[p][l][d] = 0;
}

void print_counters_by_lines(int m, int n)
{
    const int points = n*m;
    const int lines = m*(n-1) + (m-1)*n + 2*(m-1)*(n-1);
    const int diags = (m-1)*(n-1);
    int filled_lines = 0;
    // determine formating of table
    int digits[MAX_POINTS+1];
    for (int p = 1; p <= points; p++)
        digits[p] = p < 10 ? 1 : 2;
    for (int l = 0; l <= lines; l++)
        for (int p = 1; p <= points; p++)
        {
            Counter counter = 0;
            int f = 1;
            for (int d = 0; d <= diags; d++, f*=2)
                counter += counters[p][l][d] * f;
            if (counter != 0)
                filled_lines = l+1;
            char buffer[30];
            sprintf(buffer, FORMAT, counter);
            int d = strlen(buffer);
            if (d > digits[p])
                digits[p] = d;
        }
    printf("<P>\n<PRE>\n    ");
    for (int p = 1; p <= points; p++)
        printf(" %*d", digits[p], p);
    printf("\n   +");
    for (int p = 1; p <= points; p++)
        for (int i = 0; i <= digits[p]; i++)
            printf("-");
    printf("\n");
    Counter total = counters[0][0][0];
    for (int l = 0; l < filled_lines; l++)
    {
        printf("%3d:", l);
        for (int p = 1; p <= points; p++)
        {
            Counter counter = 0;
            int f = 1;
            for (int d = 0; d <= diags; d++, f*=2)
                counter += counters[p][l][d] * f;
            printf(" "DFORMAT, digits[p], counter);
            total += counter;
        }
        printf("\n");
    }
    printf("</PRE>\n<P>\n");

    printf("The total number is  "FORMAT". <!-- (%ld)-->\n", total, (1L << 20));
}

/*
void print_counters_by_points(int m, int n, int digits)
{
    int points = n*m;
    int lines = m*(n-1) + (m-1)*n + 2*(m-1)*(n-1);
    printf("<PRE>\n    ");
    for (int l = 0; l <= lines; l++)
        printf(" %*d", digits, l);
    printf("\n   +");
    for (int l = 0; l <= lines; l++)
        printf("-%*.*s", "--------------------", digits, digits);
    printf("\n");
    for (int p = 0; p <= points; p++)
    {
        printf("%3d|", p);
        for (int l = 0; l <= lines; l++)
            printf(" "DFORMAT, digits, counters[p][l]);
        printf("\n");
    }
    printf("</PRE>\n");
}
*/

long long over(int m, int n)
{
    long long result = 1;
    for (int i = 1; i <= n; i++, m--)
        result = result * m / i;
    return result;
}

void all(int m, int n, bool no_cross)
{
    init_counters(m, n);

    const int points = n*m;
    
    for (long long c = 0; c < (1L << points); c++)
    {
        bool field[MAX_M][MAX_N];
        int k = 0;
        int d = 0;
        int p = 0;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++, k++)
            {
                field[i][j] = (c & (1L << k)) != 0;
                if (field[i][j])
                    p++;
            }
        int l = 0;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n-1; j++, k++)
                if (field[i][j] && field[i][j+1])
                    l++;
        for (int i = 0; i < m-1; i++)
            for (int j = 0; j < n; j++, k++)
                if (field[i][j] && field[i+1][j])
                    l++;
        for (int i = 0; i < m-1; i++)
            for (int j = 0; j < n-1; j++, k++)
            {
                bool a = (field[i][j] && field[i+1][j+1]);
                if (a)
                    l++;
                bool b = (field[i][j+1] && field[i+1][j]);
                if (b)
                    l++;
                if (no_cross && a && b)
                {
                    l--;
                    d++;
                }
            }
        counters[p][l][d]++;    
    }
        
    print_counters_by_lines(m, n);
    
    countWithTransitions(true, no_cross, false, true);


    const int lines = m*(n-1) + (m-1)*n + 2*(m-1)*(n-1);
    const int diags = (m-1)*(n-1);
    for (int l = 0; l <= lines; l++)
        for (int p = 0; p <= points; p++)
            for (int l2 = l+1; l2 <= lines; l2++)
            {
                for (int d2 = 0; d2 <= diags; d2++)
                    for (int d = 0; d <= d2; d++)
                    {
                        int hvl = l - d;
                        int hvl2 = l2 - d2;
                        if (hvl >= 0 && hvl2 >= hvl)
                            counters[p][l][d] += counters[p][l2][d2] * over(d2, d) * over(hvl2, hvl);
                    }
            }

    printf("And when we add all the PARR's where not all neighbour points are connected,\n");
    printf("we get the following table:\n");

    print_counters_by_lines(4, 5);

    countWithTransitions(false, no_cross, false, true);
}

bool trace = false;

#define WIDTH 4
#define MAX_LINES_WITH_WIDTH WIDTH+3*(WIDTH-1)

class State;

class Transition
{
public:
    Transition(State *n_to)
    {
        to = n_to;
        next = 0;
        for (int p = 0; p <= WIDTH; p++)
            for (int l = 0; l <= MAX_LINES_WITH_WIDTH; l++)
                counts[p][l] = 0L;
    }
    ~Transition()
    {
        delete next;
    }
    long counts[WIDTH+1][MAX_LINES_WITH_WIDTH+1];
    State *to;
    Transition *next;
};

class State
{
public:
    State(int *n_value, bool n_first)
    {
        for (int i = 0; i < WIDTH; i++)
            value[i] = n_value[i];
        first = n_first;
        transitions = 0;
        next = 0;
        for (int p = 0; p <= MAX_POINTS; p++)
            for (int l = 0; l <= MAX_LINES; l++)
                old_counters[p][l] = 0L;
        if (first)
            old_counters[0][0] = 1;
                
    }
    ~State()
    {
        delete next;
        delete transitions;
    }
    int value[WIDTH];
    bool first;
    Counter old_counters[MAX_POINTS+1][MAX_LINES+1];
    Counter new_counters[MAX_POINTS+1][MAX_LINES+1];
    Transition *transitions;
    State *next;
};

State *all_states = 0;

State* get_state(int *value, bool first)
{
    State** ref_state = &all_states;
    for (; *ref_state != 0; ref_state = &(*ref_state)->next)
    {
        bool equal = (*ref_state)->first == first;
        for (int i = 0; equal && i < WIDTH; i++)
            equal = (*ref_state)->value[i] == value[i];
        if (equal)
            return *ref_state;
    }
    if (trace) 
    {
        printf("add state: ");
        for (int i = 0; i < WIDTH; i++)
            printf("%2d", value[i]);
        printf("\n");
    }
    return *ref_state = new State(value, first);
}

Transition* get_transition(State *from, State* to)
{
    Transition** ref_trans = &from->transitions;
    for (; *ref_trans != 0; ref_trans = &(*ref_trans)->next)
        if ((*ref_trans)->to == to)
            return *ref_trans;
    if (trace) printf("add transition\n");
    return *ref_trans = new Transition(to);
}

void combine(int v1, int v2, int *old_value, int *new_value)
{
    if (v1 == 0 || v2 == 0)
        return;
    if (v2 < v1)
    {
        int h = v2;
        v2 = v1;
        v1 = h;
    }
    if (v1 < v2)
    {
        for (int i = 0; i < WIDTH; i++)
        {
            if (old_value[i] == v2)
                old_value[i] = v1;
            if (new_value[i] == v2)
                new_value[i] = v1;
        }
    }
}

void normalize(int *new_value)
{
    int mapping[2*WIDTH];
    for (int i = 0; i < 2*WIDTH; i++)
        mapping[i] = 0;
    int next_value = 1;
    for (int i = 0; i < WIDTH; i++)
    {
        int v = new_value[i];
        if (v > 0)
        {
            if (mapping[v] == 0)
                mapping[v] = next_value++;
            new_value[i] = mapping[v];
        }
    }
}

void countWithTransitions(bool all_lines, bool no_cross, bool connected, bool verify)
{
    delete all_states;
    all_states = 0;

    // Fill initial element
    int value[WIDTH];
    for (int i = 0; i < WIDTH; i++)
        value[i] = 0;
    get_state(value, true);
    
    if (trace) printf("<!--\n");
    
    // expand states
    for (State *state = all_states; state != 0; state = state->next)
    {
        if (trace)
        {
            printf("Processing state:");
            for (int i = 0; i < WIDTH; i++)
                printf("%2d", state->value[i]);
            printf("\n");
        }
        bool final = !state->first;
        for (int i = 0; final && i < WIDTH; i++)
            final = state->value[i] == 0;
        for (int ps = 0; ps < (1 << WIDTH); ps++)
        {
            if (trace) printf(" points %d\n", ps);
            bool new_points[WIDTH];
            int nr_points = 0;
            for (int i = 0; i < WIDTH; i++)
            {
                new_points[i] = (ps & (1 << i)) != 0;
                if (new_points[i])
                    nr_points++;
            }
            int max_nr_lines = 0;
            for (int i = 0; i < WIDTH; i++)
                if (state->value[i] != 0 && new_points[i])
                    max_nr_lines++;
            for (int i = 0; i < WIDTH-1; i++)
            {
                bool diag1 = (state->value[i] != 0 && new_points[i+1]);
                bool diag2 = (state->value[i+1] != 0 && new_points[i]);
                if (diag1)
                    max_nr_lines++;
                if (diag2)
                    max_nr_lines++;
                if (no_cross && diag1 && diag2)
                    max_nr_lines--;
                    
                if (new_points[i] && new_points[i+1])
                    max_nr_lines++;
            }
            for (long ls = 0L; ls < (1L << MAX_LINES_WITH_WIDTH); ls++)
            {
                //fprintf("  lines %d\n", ls);
                bool new_lines[MAX_LINES_WITH_WIDTH];
                int nr_lines = 0;
                for (int i = 0; i < MAX_LINES_WITH_WIDTH; i++)
                {
                    new_lines[i] = (ls & (1 << i)) != 0;
                    if (new_lines[i])
                        nr_lines++;
                }
                bool okay = !all_lines || nr_lines == max_nr_lines;
                if (no_cross)
                    for (int i = 0; okay && i < WIDTH-1; i++)
                        okay = !new_lines[WIDTH+i] || !new_lines[2*WIDTH-1+i];
                for (int i = 0; okay && i < WIDTH; i++)
                    okay = !new_lines[i] || (state->value[i] != 0 && new_points[i]);
                for (int i = 0; okay && i < WIDTH-1; i++)
                    okay = !new_lines[WIDTH+i] || (state->value[i] != 0 && new_points[i+1]);
                for (int i = 0; okay && i < WIDTH-1; i++)
                    okay = !new_lines[2*WIDTH-1+i] || (state->value[i+1] != 0 && new_points[i]);
                for (int i = 0; okay && i < WIDTH-1; i++)
                    okay = !new_lines[3*WIDTH-2+i] || (new_points[i] && new_points[i+1]);
                if (okay)
                {
                    if (!connected)
                    {
                        int new_value1[WIDTH];
                        for (int i = 0; i < WIDTH; i++)
                            new_value1[i] = new_points[i] ? 1 : 0;
                        int new_value2[WIDTH];
                        for (int i = 0; i < WIDTH; i++)
                            new_value2[WIDTH-1-i] = new_points[i] ? 1 : 0;
                        int diff = 0;
                        for (int i = 0; diff == 0 && i < WIDTH; i++)
                            if (new_value1[i] < new_value2[i])
                                diff = -1;
                            else if (new_value1[i] > new_value2[i])
                                diff = 1;
                        State *new_state = get_state(diff < 0 ? new_value1 : new_value2, false);
                        Transition *new_transition = get_transition(state, new_state);
                        new_transition->counts[nr_points][nr_lines]++;
                    }
                    else if (ps == 0)
                    {
                        for (int i = 0; okay && i < WIDTH; i++)
                            okay = state->value[i] < 2;
                        if (okay)
                        {
                            int new_value[WIDTH];
                            for (int i = 0; i < WIDTH; i++)
                                new_value[i] = 0;
                            State *new_state = get_state(new_value, nr_points == 0 && state->first);
                            Transition *new_transition = get_transition(state, new_state);
                            new_transition->counts[nr_points][nr_lines]++;
                            /*
                            for (int i = 0; i < WIDTH; i++)
                                printf("%d ", state->value[i]);
                            printf("%s (%d %2d) ", state->first ? "f" : " ", nr_points, nr_lines);
                            for (int i = 0; i < WIDTH; i++)
                                printf("%d ", new_state->value[i]);
                            printf("%s\n", new_state->first ? "f" : " ");
                            */
                        }
                    }
                    else if (!final)
                    {
                        int old_value[WIDTH];
                        int new_value[WIDTH];
                        for (int i = 0; i < WIDTH; i++)
                        {
                            old_value[i] = state->value[i];
                            new_value[i] = new_points[i] ? WIDTH+i : 0;
                        }
                        for (int i = 0; i < WIDTH; i++)
                            if (new_lines[i])
                                combine(old_value[i], new_value[i], old_value, new_value);
                        for (int i = 0; i < WIDTH-1; i++)
                            if (new_lines[WIDTH+i])
                                combine(old_value[i], new_value[i+1], old_value, new_value);
                        for (int i = 0; i < WIDTH-1; i++)
                            if (new_lines[2*WIDTH-1+i])
                                combine(old_value[i+1], new_value[i], old_value, new_value);
                        for (int i = 0; i < WIDTH-1; i++)
                            if (new_lines[3*WIDTH-2+i])
                                combine(new_value[i], new_value[i+1], old_value, new_value);
                        for (int i = 0; okay && i < WIDTH; i++)
                            if (old_value[i] != 0)
                            {
                                okay = false;
                                for (int j = 0; !okay && j < WIDTH; j++)
                                    okay = new_value[j]    == old_value[i];
                            }
                        if (okay)
                        {
                            int new_value1[WIDTH];
                            for (int i = 0; i < WIDTH; i++)
                                new_value1[i] = new_value[i];
                            normalize(new_value1);
                            int new_value2[WIDTH];
                            for (int i = 0; i < WIDTH; i++)
                                new_value2[WIDTH-1-i] = new_value[i];
                            normalize(new_value2);    
                            int diff = 0;
                            for (int i = 0; diff == 0 && i < WIDTH; i++)
                                if (new_value1[i] < new_value2[i])
                                    diff = -1;
                                else if (new_value1[i] > new_value2[i])
                                    diff = 1;
                            //State *new_state = get_state(diff < 0 ? new_value1 : new_value2, false);
                            State *new_state = get_state(new_value1, false);
                            Transition *new_transition = get_transition(state, new_state);
                            new_transition->counts[nr_points][nr_lines]++;
                            /*
                            for (int i = 0; i < WIDTH; i++)
                                printf("%d ", state->value[i]);
                            printf("%s (%d %2d) ", state->first ? "f" : " ", nr_points, nr_lines);
                            for (int i = 0; i < WIDTH; i++)
                                printf("%d ", new_state->value[i]);
                            printf("%s\n", new_state->first ? "f" : " ");
                            */
                        }
                    }
                }
            }
        }
    }
    if (trace) printf("-->\n");
    
    for (int loop = 0; loop < 6; loop++)
    {
        for (State *state = all_states; state != 0; state = state->next)
            for (int p = 0; p <= MAX_POINTS; p ++)
                for (int l = 0; l <= MAX_LINES; l++)
                    state->new_counters[p][l] = 0L;
        for (State *state = all_states; state != 0; state = state->next)
            for (Transition *transition = state->transitions; transition != 0; transition = transition->next)
            {
                State *to_state = transition->to;
                for (int p = 0; p <= MAX_POINTS; p++)
                    for (int l = 0; l <= MAX_LINES; l++)
                    {
                        Counter old_counter = state->old_counters[p][l];
                        for (int pc = 0; pc <= WIDTH && p+pc <= MAX_POINTS; pc++)
                            for (int lc = 0; lc <= MAX_LINES_WITH_WIDTH && l+lc <= MAX_LINES; lc++)
                                to_state->new_counters[p+pc][l+lc] += transition->counts[pc][lc] * old_counter;
                    }
            }
        for (State *state = all_states; state != 0; state = state->next)
            for (int p = 0; p <= MAX_POINTS; p ++)
                for (int l = 0; l <= MAX_LINES; l++)
                    state->old_counters[p][l] = state->new_counters[p][l];
    }
    State* final_state = 0;
    for (State *state = all_states; state != 0; state = state->next)
    {
        bool final = !state->first;
        for (int i = 0; final && i < WIDTH; i++)
            final = state->value[i] == 0;
        if (final)
        {
            final_state = state;
            break;
        }
    }
    if (final_state == 0)
    {
        printf("No final state\n");
        return;
    }
    
    if (verify)
    {
        const int diags = (5-1)*(4-1);
        bool equal = true;
        for (int l = 0; equal && l <= MAX_LINES; l++)
            for (int p = 0; equal && p <= MAX_POINTS; p ++)
            {
                Counter counter = 0;
                int f = 1;
                for (int d = 0; d <= diags; d++, f*=2)
                    counter += counters[p][l][d] * f;
                equal = (counter == final_state->new_counters[p][l]);
            }
        if (equal)
        {
            printf("Result match with <A HREF=\"#sec\">second method</A>.\n");
            return;
        }
        else
            printf("Result does not match with second method. Result of second method is:\n");
            
    }

    init_counters(4, 5);
    for (int l = 0; l <= MAX_LINES; l++)
        for (int p = 0; p <= MAX_POINTS; p ++)
            counters[p][l][0] = final_state->new_counters[p][l];
    print_counters_by_lines(4, 5);
}

int main(int argc, char *argv[])
{
    printf("<HTML><HEAD>\n");
    printf("<TITLE>Counting PARR solutions</TITLE>\n");
    printf("</HEAD><BODY BACKGROUND=\"greybgd.jpg\">\n");
    printf("\n");
    printf("<H1>Counting PARR solutions</H1>\n");
    printf("\n");
    printf("This page contains some results with respect to counting\n");
    printf("the number of <A HREF=\"Dpuzzle.html\">PARR's</A> with various properties. This page\n");
    printf("is generated with the program <A HREF=\"PARR_cpp.txt\">PARR.cpp</A>. This program went\n");
    printf("through a number of versions. Only the final version is released and likewise this page\n");
    printf("presents the results of the last version. The page is devided in the methods that were\n");
    printf("employed.\n");
    printf("\n");
    printf("<H2>First method</H2>\n");
    printf("\n");
    printf("The first method I applied was a straight forward counting algorithm. These were\n");
    printf("generated on <A HREF=\"D1508.html#26\">August 26, 2015</A>.\n");
    printf("\n");

    printf("<H3><A NAME=\"all\">All</A></H3>\n");
    printf("\n");
    printf("This table gives the number of all PARR's per number of points (columns)\n");
    printf("and per number connections (rows), including those with crossing diagonal connections,\n");
    printf("where all neighbour points are connected.\n");
    printf("\n");
    all(4, 5, false);

    printf("<H3><A NAME=\"all_nc\">No crossings</A></H3>\n");
    printf("\n");
    printf("This table gives the number of all PARR's per number of points (columns)\n");
    printf("and per number of connections (rows) where all neighbouring points are connected,\n");
    printf("except for crossing diagonal connections where either one or the other is included.\n");
    all(4, 5, true);

    printf("\n");
    printf("<H2><A NAME=\"sec\">Second method</H2>\n");
    printf("\n");
    printf("The second method I applied involved slicing. These were\n");
    printf("generated on <A HREF=\"D1509.html#3\">September 3, 2015</A>.\n");
    printf("\n");
    
    printf("<H3><A NAME=\"all_con\">Connected</A></H3>\n");
    printf("\n");
    printf("This table gives the number of all PARR's per number of points (columns)\n");
    printf("and per number connections (rows), including those with crossing diagonal connections,\n");
    printf("where all neighbour points are connected and where all points are connected through\n");
    printf("one or more connections.\n");
    printf("\n");
    countWithTransitions(true, false, true, false);
    printf("And when we add all the PARR's where not all neighbour points are connected,\n");
    printf("we get the following table:\n");
    countWithTransitions(false, false, true, false);

    printf("<H3><A NAME=\"all_con_nc\">Connected and no crossings</A></H3>\n");
    printf("\n");
    printf("This table gives the number of all PARR's per number of points (columns)\n");
    printf("and per number of connections (rows) where all neighbouring points are connected,\n");
    printf("except for crossing diagonal connections where either one or the other is included.\n");
    printf("Futhermore, all points are connected through one or more connections.\n");
    countWithTransitions(true, true, true, false);
    State* all_con_nc = all_states;
    all_states = 0;
    printf("And when we add all the PARR's where not all neighbour points are connected,\n");
    printf("we get the following table:\n");
    countWithTransitions(false, true, true, false);
    
    printf("<P><HR>\n");
    printf("<ADDRESS>\n");
    printf("<A HREF=\"index.html\">Home</A>\n");
    printf("| <A HREF=\"Dpuzzle.html\">Puzzels</A>\n");
    printf("</ADDRESS>\n");
    printf("\n");
    printf("</BODY></HTML>\n");
    return 0;
}