/* 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/D1508.html#26 */ #include #include #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 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("

\n

\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("
\n

\n"); printf("The total number is "FORMAT". \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("

\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("
\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 < (1 << 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); 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); } int main(int argc, char *argv[]) { printf("\n"); printf("Counting PARR solutions\n"); printf("\n"); printf("\n"); printf("

Counting PARR solutions

\n"); printf("\n"); printf("This page contains some results with respect to counting\n"); printf("the number of PARR's with various properties. This page\n"); printf("is generated with the program PARR.cpp.\n"); printf("\n"); printf("

All

\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("

No crossings

\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("
\n"); printf("Home\n"); printf("| Puzzels\n"); printf("
\n"); printf("\n"); printf("\n"); return 0; }