Supersonic domino tilings 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.
C

A straightforward implementation...

#include&lt;stdio.h&gt;
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&lt;&lt;b)-1&amp;~x;
    if(i&lt;a-1){
        s[i+1]=j;
        w(i+1,j,1);
        for(k=j&amp;j/2&amp;-o;j=k&amp;-k;k&amp;=~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&lt;b;r[k++,l++]=10)
                    for(j=0;j&lt;a;j++)
                        r[l++]=45+79*!((s[j]|s[j+1])&amp;(1&lt;&lt;k));
            else
                for(j=0;j&lt;a;r[j++,l++]=10)
                    for(k=0;k&lt;b;k++)
                        r[l++]=124-79*!((s[j]|s[j+1])&amp;(1&lt;&lt;k));
            r[l++]=10;
            if(l&gt;=100000){
                fwrite(r,l,1,stdout);
                l=0;
            }
        }
}

int main(){
    scanf("%d %d %d",&amp;a,&amp;b,&amp;countonly);
    c=b;
    if(a&lt;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&lt;stdio.h&gt;
#include&lt;string.h&gt;
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&lt;a-1;i++){
        for(k=1;k&lt;(1&lt;&lt;(b-1));k*=2)
            for(x=0;x&lt;(1&lt;&lt;(b-2));x++)
                d[(x+x/k*k*3+k*3)^j]+=d[(x+x/k*k*3)^j];
        j^=(1&lt;&lt;b)-1;
    }
    for(x=0;x&lt;(1&lt;&lt;b);x++)
        if((x/3|x/3*2)==x)
            m+=d[x^((1&lt;&lt;b)-1)^j];
    printf("%llu\n",m);
}

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

int main(){
    scanf("%d %d %d",&amp;a,&amp;b,&amp;countonly);
    c=b;
    if(a&lt;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).