/* 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 #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 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("

\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 < (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"); 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 second method.\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("\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. 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("

## First method

\n"); printf("\n"); printf("The first method I applied was a straight forward counting algorithm. These were\n"); printf("generated on August 26, 2015.\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("

## Second method

\n"); printf("\n"); printf("The second method I applied involved slicing. These were\n"); printf("generated on September 3, 2015.\n"); printf("\n"); printf("

### Connected

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

### Connected and 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"); 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("

\n"); printf("
\n"); printf("Home\n"); printf("| Puzzels\n"); printf("
\n"); printf("\n"); printf("\n"); return 0; }