Supersonic domino tilings

Question

Task

Write a program that reads three integers m, n either from STDIN or as command-line arguments, prints all possible tilings of a rectangle of dimensions m × n by 2 × 1 and 1 × 2 dominos and finally the number of valid tilings.

Dominos of an individual tiling have to be represented by two dashes (-) for 2 × 1 and two vertical bars (|) for 1 × 2 dominos. Each tiling (including the last one) has to be followed by a linefeed.

For scoring purposes, you also have to accept a flag from STDIN or as command line argument that makes your program print only the number of valid tilings, but not the tilings itself.

Your program may not be longer than 1024 bytes. It has to work for all inputs such that m × n ≤ 64.

(Inspired by Print all domino tilings of 4x6 rectangle.)

Example

$ sdt 4 2
----
----

||--
||--

|--|
|--|

--||
--||

||||
||||

5
$ sdt 4 2 scoring
5

Scoring

Your score is determined by the execution time of your program for the input 8 8 with the flag set.

To make this a fastest code rather than a fastest computer challenge, I will run all submissions on my own computer (Intel Core i7-3770, 16 GiB PC3-12800 RAM) to determine the official score.

Please leave detailed instructions on how to compile and/or execute your code. If you require a specific version of your language's compiler/interpreter, make a statement to that effect.

I reserve the right to leave submissions unscored if:

• There is no free (as in beer) compiler/interpreter for my operating system (Fedora 21, 64 bits).

• Despite our efforts, your code doesn't work and/or produces incorrect output on my computer.

• Compilation or execution take longer than an hour.

• Your code or the only available compiler/interpreter contain a system call to rm -rf ~ or something equally fishy.

Leaderboard

I've re-scored all submissions, running both compilations and executions in a loop with 10,000 iterations for compilation and between 100 and 10,000 iterations for execution (depending on the speed of the code) and calculating the mean.

These were the results:

User          Compiler   Score                              Approach

jimmy23013    GCC (-O0)    46.11 ms =   1.46 ms + 44.65 ms  O(m*n*2^n) algorithm.
steveverrill  GCC (-O0)    51.76 ms =   5.09 ms + 46.67 ms  Enumeration over 8 x 4.
jimmy23013    GCC (-O1)   208.99 ms = 150.18 ms + 58.81 ms  Enumeration over 8 x 8.
Reto Koradi   GCC (-O2)   271.38 ms = 214.85 ms + 56.53 ms  Enumeration over 8 x 8.

Answer 1

C

A straightforward implementation...

#include<stdio.h>
int a,b,c,s[65],l=0,countonly;
unsigned long long m=0;
char r[100130];
void w(i,x,o){
    int j,k;
    j=(1<<b)-1&~x;
    if(i<a-1){
        s[i+1]=j;
        w(i+1,j,1);
        for(k=j&j/2&-o;j=k&-k;k&=~j)
            w(i,x|3*j,j);
    }
    else if((j/3|j/3*2)==j)
        if(countonly)
            m++;
        else{
            if(c==b)
                for(k=0;k<b;r[k++,l++]=10)
                    for(j=0;j<a;j++)
                        r[l++]=45+79*!((s[j]|s[j+1])&(1<<k));
            else
                for(j=0;j<a;r[j++,l++]=10)
                    for(k=0;k<b;k++)
                        r[l++]=124-79*!((s[j]|s[j+1])&(1<<k));
            r[l++]=10;
            if(l>=100000){
                fwrite(r,l,1,stdout);
                l=0;
            }
        }
}

int main(){
    scanf("%d %d %d",&a,&b,&countonly);
    c=b;
    if(a<b){a^=b;b^=a;a^=b;}
    s[0]=s[a]=0;
    w(0,0,1);
    if(countonly)
        printf("%llu\n",m);
    else if(l)
        fwrite(r,l,1,stdout);
}

The cheating version

#include<stdio.h>
#include<string.h>
int a,b,c,s[65],l=0,countonly;
unsigned long long m=0,d[256];
char r[100130];
void w2(){
    int i,j,k,x;
    memset(d,0,sizeof d);
    d[0]=1;
    j=0;
    for(i=0;i<a-1;i++){
        for(k=1;k<(1<<(b-1));k*=2)
            for(x=0;x<(1<<(b-2));x++)
                d[(x+x/k*k*3+k*3)^j]+=d[(x+x/k*k*3)^j];
        j^=(1<<b)-1;
    }
    for(x=0;x<(1<<b);x++)
        if((x/3|x/3*2)==x)
            m+=d[x^((1<<b)-1)^j];
    printf("%llu\n",m);
}

void w(i,x,o){
    int j,k;
    j=(1<<b)-1&~x;
    if(i<a-1){
        s[i+1]=j;
        w(i+1,j,1);
        for(k=j&j/2&-o;j=k&-k;k&=~j)
            w(i,x|3*j,j);
    }
    else if((j/3|j/3*2)==j){
        if(c==b)
            for(k=0;k<b;r[k++,l++]=10)
                for(j=0;j<a;j++)
                    r[l++]=45+79*!((s[j]|s[j+1])&(1<<k));
        else
            for(j=0;j<a;r[j++,l++]=10)
                for(k=0;k<b;k++)
                    r[l++]=124-79*!((s[j]|s[j+1])&(1<<k));
        r[l++]=10;
        if(l>=100000){
            fwrite(r,l,1,stdout);
            l=0;
        }
    }
}

int main(){
    scanf("%d %d %d",&a,&b,&countonly);
    c=b;
    if(a<b){a^=b;b^=a;a^=b;}
    s[0]=s[a]=0;
    if(countonly)
        w2();
    else{
        w(0,0,1);
        if(l)
            fwrite(r,l,1,stdout);
    }
}

Explanation of the faster algorithm

It scans from left to right, and maintain the state d[i][j], where:

• i is in [0,m), which means the current column.
• j is a bit vector of size n, where the bit would be 1 if the corresponding position in column i is already occupied before starting working on this column. I.e. it is occupied by the right half of a --.
• d[i][j] is the total number of different tilings.

Then say e[i][j] = the sum of d[i][k] where you can put vertical dominoes base on k to form a j. e[i][j] would be the number of tilings where each 1 bit in j is occupied by anything but the left half of a --. Fill them with -- and you'll get d[i+1][~j] = e[i][j]. e[m-1][every bit being 1] or d[m][0] is the final answer.

A naive implementation will get you the time complexity somewhere near g[n]=2*g[n-1]+g[n-2] = O((sqrt(2)+1)^n) (already fast enough if n=m=8). But you can instead firstly loop for each possible domino, and try to add it to every tiling that can have this domino added, and merge the result to the original array d (like the algorithm for the Knapsack problem). And this becomes O(n*2^n). And everything else are implementation details. The whole code runs in O(m*n*2^n).

Answer 2

C

After a round of optimizations, and adapted for the modified rules:

typedef unsigned long u64;

static int W, H, S;
static u64 RM, DM, NSol;
static char Out[64 * 2 + 1];

static void place(u64 cM, u64 vM, int n) {
  if (n) {
    u64 m = 1ul << __builtin_ctzl(cM); cM -= m;

    if (m & RM) {
      u64 nM = m << 1;
      if (cM & nM) place(cM - nM, vM, n - 1);
    }

    if (m & DM) {
      u64 nM = m << W;
      vM |= m; vM |= nM; place(cM - nM, vM, n - 1);
    }
  } else if (S) {
    ++NSol;
  } else {
    char* p = Out;
    for (int y = 0; y < H; ++y) {
      for (int x = 0; x < W; ++x) { *p++ = vM & 1 ? '|' : '-'; vM >>= 1; }
      *p++ = '\n';
    }
    *p++ = '\0';
    puts(Out);
    ++NSol;
  }
}

int main(int argc, char* argv[]) {
  W = atoi(argv[1]); H = atoi(argv[2]); S = (argc > 3);

  int n = W * H;
  if (n & 1) return 0;

  for (int y = 0; y < H; ++y) {
    RM <<= W; RM |= (1ul << (W - 1)) - 1;
  }
  DM = (1ul << (W * (H - 1))) - 1;

  place(-1, 0, n >> 1);
  printf("%lu\n", NSol);

  return 0;
}

I started bumping into the length limit of 1024 characters, so I had to reduce the readability somewhat. Much shorter variable names, etc.

Build instructions:

> gcc -O2 Code.c

Run with solution output enabled:

> ./a.out 8 8 >/dev/null

Run with only solution count:

> ./a.out 8 8 s

Some comments:

• With the larger test example, I do want optimization now. While my system is different (Mac), around -O2 seems to be good.
• The code has gotten slower for the case where output is generated. This was a conscious sacrifice for optimizing the "count only" mode, and for reducing the code length.
• There will be a few compiler warnings because of missing includes and external declarations for system functions. It was the easiest way to get me to below 1024 characters in the end without making the code totally unreadable.

Also note that the code still generates the actual solutions, even in "count only" mode. Whenever a solution is found, the vM bitmask contains a 1 for the positions that have a vertical bar, and a 0 for positions with a horizontal bar. Only the conversion of this bitmask into ASCII format, and the actual output, is skipped.

Answer 3

C

The concept is to first find all possible arrangements of horizontal dominoes in a row, store them in r[] and then organize them to give all possible arrangements of vertical dominoes.

The code for positioning the horizontal dominoes in a row is modified from this answer of mine: https://codegolf.stackexchange.com/a/37888/15599. It's slow for the wider grids but that isn't a problem for the 8x8 case.

The innovation is in the way the rows are assembled. If the board has an odd number of rows it is turned through 90 degrees in the input parsing, so it now has an even number of rows. Now I place some vertical dominoes across the centreline. Because of symmetry, if there are c ways of arranging the remaining dominoes in the bottom half, there must also be c ways of arranging the remaining dominoes in the top half, meaning that for a given arrangement of vertical dominoes on the centreline, there are c*c possible solutions. Therefore only the centreline plus one half of the board is analysed when the program is required to print only the number of solutions.

f() builds the table of possible arrangements of horizontal dominoes, and scans through the possible arrangements of vertical dominoes on the centreline. it then calls recursive function g() which fills in the rows. If printing is required, function h() is called to do this.

g() is called with 3 parameters. y is the current row and d is the direction (up or down) in which we are filling the board from the centre outwards. x contains a bitmap indicates the vertical dominoes that are incomplete from the previous row. All possible arrangements of dominoes in a row from r[] are tried. In this array, a 1 represents a vertical domino and a pair of zeroes a horizontal domino. A valid entry in the array must have at least enough 1's to finish any incomplete vertical dominoes from the last row: (x&r[j])==x. It may have more 1's which indicates that new vertical dominoes are being started. For the next row, then, we need only the new dominoes so we call the procedure again with x^r[j].

If an end row has been reached and there are no incomplete vertical dominoes hanging of the top or bottom of the board x^r[j]==0 then the half has been succesfully completed. If we are not printing, it is sufficient to complete the bottom half and use c*c to work out the total number of arrangements. If we are printing, it will be necessary to complete also the top half and then call the printing function h().

CODE

unsigned int W,H,S,n,k,t,r[1<<22],p,q[64];
long long int i,c,C;


//output: ascii 45 - for 0, ascii 45+79=124 | for 1
h(){int a;
  for(a=n;a--;a%W||puts(""))putchar(45+(q[a/W]>>a%W)%2*79);
  puts("");
}

g(y,d,x){int j;
  for(j=0;j<p;j++)if((x&r[j])==x){
    q[y]=r[j];
    if(y%(H-1)==0){
       (x^r[j])==0?
        y?c++,S||g(H/2-1,-1,i):h() 
       :0;
    }else{
      g(y+d,d,x^r[j]);
    }

  }    
}

e(z){int d;
  for(d=0;z;d++)z&=z-1;return n/2+1+d&1; 
}

f(){
  //k=a row full of 1's
  k=(1ULL<<W)-1;

  //build table of possible arrangements of horizontal dominoes in a row;
  //flip bits so that 1=a vertical domino and save to r[]
  for(i=0;i<=k;i++)(i/3|i/3<<1)==i?r[p++]=i^k:0;

  //for each arrangement of vertical dominoes on the centreline, call g()
  for(i=0;i<=k;i++)e(i)?c=0,g(H/2,1,i),C+=c*c:0;
  printf("%llu",C);
}


main(int argc, char* argv[]) {
  W = atoi(argv[1]); H = atoi(argv[2]); S = (argc > 3);
  1-(n=W*H)%2?
      H%2?W^=H,H^=W,W^=H,t=1:0,f()
    :puts("0");

}

Note that input with an odd number of rows and even number of columns is turned though 90 degrees in the parsing phase. If this is unacceptable, the printing function h() can be changed to accomodate it. (EDIT: not required, see comments.)

EDIT: A new function e() has been used to check the parity of i (i.e the number of dominoes straddling the centreline.) The parity of i (the number of half-dominoes on the centreline protruding into each half of the board) must be the same as the oddness of the total number of spaces in each half (given by n/2) because only then can the dominoes fill all available space. This edit eliminates half the values of i and therefore makes my program approximately twice as fast.