December 2014

[alpertron]

OK, so the program can be made a lot faster by only saving non-decreasing sums in order not to save permutations. Most of the time in the program is lost when sorting the intermediate file.

Using this information I changed the program to handle binary matrices of 4x8:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(int argc, char *argv[])
{
  char oldstr[100];
  char newstr[100];
  int a,b,c,d,e,f,g,h,i,j,k,l,m;
  int count = 0;
  FILE *fpFile = fopen("test", "wt");
  for (a=0; a<2147483648; a+=2)
  {
    b =                   ((a >> 27) & 1) + ((a >> 23) & 1) + ((a >> 19) & 1) + ((a >> 15) & 1) + ((a >> 11) & 1) + ((a >> 7) & 1) + ((a >> 3) & 1);
    c = ((a >> 30) & 1) + ((a >> 26) & 1) + ((a >> 22) & 1) + ((a >> 18) & 1) + ((a >> 14) & 1) + ((a >> 10) & 1) + ((a >> 6) & 1) + ((a >> 2) & 1);
    d = ((a >> 29) & 1) + ((a >> 25) & 1) + ((a >> 21) & 1) + ((a >> 17) & 1) + ((a >> 13) & 1) + ((a >> 9) & 1) + ((a >> 5) & 1) + ((a >> 1) & 1);
    e = ((a >> 28) & 1) + ((a >> 24) & 1) + ((a >> 20) & 1) + ((a >> 16) & 1) + ((a >> 12) & 1) + ((a >> 8) & 1) + ((a >> 4) & 1);

    f =                   ((a >> 30) & 1) + ((a >> 29) & 1) + ((a >> 28) & 1);
    g = ((a >> 27) & 1) + ((a >> 26) & 1) + ((a >> 25) & 1) + ((a >> 24) & 1);
    h = ((a >> 23) & 1) + ((a >> 22) & 1) + ((a >> 21) & 1) + ((a >> 20) & 1);
    i = ((a >> 19) & 1) + ((a >> 18) & 1) + ((a >> 17) & 1) + ((a >> 16) & 1);
    j = ((a >> 15) & 1) + ((a >> 14) & 1) + ((a >> 13) & 1) + ((a >> 12) & 1);
    k = ((a >> 11) & 1) + ((a >> 10) & 1) + ((a >> 9) & 1) + ((a >> 8) & 1);
    l = ((a >> 7) & 1) + ((a >> 6) & 1) + ((a >> 5) & 1) + ((a >> 4) & 1);
    m = ((a >> 3) & 1) + ((a >> 2) & 1) + ((a >> 1) & 1);
    if (b<=c && c<=d && d<=e && f<=g && g<=h && h<=i && i<=j && j<=k && k<=l && l<=m)
    {
      fprintf(fpFile, "[%d %d %d %d] [%d %d %d %d %d %d %d %d]\n",b,c,d,e,f,g,h,i,j,k,l,m);
    }
    if (b+1<=c && c<=d && d<=e && f+1<=g && g<=h && h<=i && i<=j && j<=k && k<=l && l<=m)
    {
      fprintf(fpFile, "[%d %d %d %d] [%d %d %d %d %d %d %d %d]\n",b+1,c,d,e,f+1,g,h,i,j,k,l,m);
    }
    if (b<=c && c<=d && d<=e+1 && f<=g && g<=h && h<=i && i<=j && j<=k && k<=l && l<=m+1)
    {
      fprintf(fpFile, "[%d %d %d %d] [%d %d %d %d %d %d %d %d]\n",b,c,d,e+1,f,g,h,i,j,k,l,m+1);
    }
    if (b+1<=c && c<=d && d<=e+1 && f+1<=g && g<=h && h<=i && i<=j && j<=k && k<=l && l<=m+1)
    {
      fprintf(fpFile, "[%d %d %d %d] [%d %d %d %d %d %d %d %d]\n",b+1,c,d,e+1,f+1,g,h,i,j,k,l,m+1);
    }
  }
  fclose(fpFile);
  system("sort test /O test2");

  fpFile = fopen("test2", "rt");
  oldstr[0] = 0;
  while (!feof(fpFile))
  {
    fgets(newstr, 100, fpFile);
    if (strcmp(newstr, oldstr))
    {
      if (count == 29)
      {
        printf("%s", oldstr);
      }
      count = 0;
      strcpy(oldstr, newstr);
    }
    count++;
  }
}

The output is:

[1 2 3 5] [0 0 1 1 1 2 3 3]
[1 3 4 5] [0 0 1 1 2 3 3 3]
[2 3 4 6] [0 1 1 1 2 3 3 4]
[2 4 5 6] [0 1 1 2 3 3 3 4]
[3 4 5 7] [1 1 1 2 3 3 4 4]
[3 5 6 7] [1 1 2 3 3 3 4 4]

[alpertron]

I changed the program to handle the 5x7 case.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(int argc, char *argv[])
{
  char oldstr[100];
  char newstr[100];
  int a,b,c,d,e,f,g,h,i,j,k,l,m,z;
  int count = 0;
  FILE *fpFile = fopen("test", "wt");
  for (z=0; z<32; z++)
  {
    g = ((z >> 4) & 1) + ((z >> 3) & 1) + ((z >> 2) & 1) + ((z >> 1) & 1) + (z & 1);
    for (a=0; a<1073741824; a+=2)
    {
      b = ((z >> 4) & 1) + ((a >> 29) & 1) + ((a >> 24) & 1) + ((a >> 19) & 1) + ((a >> 14) & 1) + ((a >> 9) & 1) + ((a >> 4) & 1);
      c = ((z >> 3) & 1) + ((a >> 28) & 1) + ((a >> 23) & 1) + ((a >> 18) & 1) + ((a >> 13) & 1) + ((a >> 8) & 1) + ((a >> 3) & 1);
      d = ((z >> 2) & 1) + ((a >> 27) & 1) + ((a >> 22) & 1) + ((a >> 17) & 1) + ((a >> 12) & 1) + ((a >> 7) & 1) + ((a >> 2) & 1);
      e = ((z >> 1) & 1) + ((a >> 26) & 1) + ((a >> 21) & 1) + ((a >> 16) & 1) + ((a >> 11) & 1) + ((a >> 6) & 1) + ((a >> 1) & 1);
      f = ( z       & 1) + ((a >> 25) & 1) + ((a >> 20) & 1) + ((a >> 15) & 1) + ((a >> 10) & 1) + ((a >> 5) & 1); 

      h = ((a >> 29) & 1) + ((a >> 28) & 1) + ((a >> 27) & 1) + ((a >> 26) & 1) + ((a >> 25) & 1);
      i = ((a >> 24) & 1) + ((a >> 23) & 1) + ((a >> 22) & 1) + ((a >> 21) & 1) + ((a >> 20) & 1);
      j = ((a >> 19) & 1) + ((a >> 18) & 1) + ((a >> 17) & 1) + ((a >> 16) & 1) + ((a >> 15) & 1);
      k = ((a >> 14) & 1) + ((a >> 13) & 1) + ((a >> 12) & 1) + ((a >> 11) & 1) + ((a >> 10) & 1);
      l = ((a >> 9) & 1) + ((a >> 8) & 1) + ((a >> 7) & 1) + ((a >> 6) & 1) + ((a >> 5) & 1);
      m = ((a >> 4) & 1) + ((a >> 3) & 1) + ((a >> 2) & 1) + ((a >> 1) & 1);
      if (b<=c && c<=d && d<=e && e<=f && g<=h && h<=i && i<=j && j<=k && k<=l && l<=m)
      {
        fprintf(fpFile, "[%d %d %d %d %d] [%d %d %d %d %d %d %d]\n",b,c,d,e,f,g,h,i,j,k,l,m);
      }
      if (b<=c && c<=d && d<=e && e<=f+1 && g<=h && h<=i && i<=j && j<=k && k<=l && l<=m+1)
      {
        fprintf(fpFile, "[%d %d %d %d %d] [%d %d %d %d %d %d %d]\n",b,c,d,e,f+1,g,h,i,j,k,l,m+1);
      }
    }
  }
  fclose(fpFile);
  system("sort test /O test2");

  fpFile = fopen("test2", "rt");
  oldstr[0] = 0;
  while (!feof(fpFile))
  {
    fgets(newstr, 100, fpFile);
    if (strcmp(newstr, oldstr))
    {
      if (count == 29)
      {
        printf("%s", oldstr);
      }
      count = 0;
      strcpy(oldstr, newstr);
    }
    count++;
  }
}

After 13 minutes writing to the intermediate file (353 108 292 bytes) and 1 minute more for the sort process, the program found the following solutions:

[0 1 2 3 5] [0 1 1 1 2 3 3]
[0 1 3 4 5] [0 1 1 2 3 3 3]
[0 2 3 4 6] [1 1 1 2 3 3 4]
[0 2 4 5 6] [1 1 2 3 3 3 4]
[1 1 1 5 5] [0 1 2 2 2 2 4]
[1 1 3 3 4] [0 0 1 1 3 3 4]
[1 1 5 5 5] [0 1 3 3 3 3 4]
[1 2 2 4 4] [0 0 1 2 2 4 4]
[1 2 3 4 6] [1 1 1 2 3 3 5]
[1 2 3 5 6] [0 2 2 2 3 4 4]
[1 2 3 5 7] [1 2 2 2 3 4 4]
[1 2 4 5 6] [1 1 2 3 3 3 5]
[1 3 4 5 6] [0 2 2 3 4 4 4]
[1 3 4 5 7] [1 2 2 3 4 4 4]
[2 2 2 6 6] [1 2 2 2 2 4 5]
[2 2 4 4 5] [0 1 1 3 3 4 5]
[2 2 6 6 6] [1 3 3 3 3 4 5]
[2 3 3 5 5] [0 1 2 2 4 4 5]
[2 3 4 6 7] [2 2 2 3 4 4 5]
[2 4 5 6 7] [2 2 3 4 4 4 5]
[3 3 5 5 6] [1 1 3 3 4 5 5]
[3 4 4 6 6] [1 2 2 4 4 5 5]

I think this time there should be several independent solutions.

[Xyzzy]

http://domino.research.ibm.com/Comm/...ember2014.html