10
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ Why not make this a GOLF contest? :( \$\endgroup\$ – orlp May 31 '15 at 14:36
  • 2
    \$\begingroup\$ If you had suggested that in the sandbox, I might have. That would have saved my CPU and me a lot of work... \$\endgroup\$ – Dennis May 31 '15 at 15:11
  • 3
    \$\begingroup\$ @kirbyfan64sos The way I understand it, there's only one type of domino, which you can rotate. If it's horizontal, it looks like this: --. If it's vertical, it is two |, one below the other. \$\endgroup\$ – Reto Koradi May 31 '15 at 18:41
  • 1
    \$\begingroup\$ Your challenge is not bad. The problem is that our top coders are too strong. My solution that checks validity of rows and columns stays near 1 minute for 6x8. \$\endgroup\$ – edc65 Jun 2 '15 at 7:00
  • 1
    \$\begingroup\$ I think the best strategy now is to use assembly, and try to get a binary file less than 1024 bytes, to get rid of the complication time. \$\endgroup\$ – jimmy23013 Jun 4 '15 at 7:44
5
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ @Dennis You probably want to start a poll to change it. \$\endgroup\$ – jimmy23013 Jun 1 '15 at 1:37
  • \$\begingroup\$ @Dennis Not sure increasing the size would have helped much. While it increases the computation time substantially, it also produces about 100 times more output. Relatively speaking, the amount of output is actually larger. \$\endgroup\$ – Reto Koradi Jun 1 '15 at 2:34
  • \$\begingroup\$ 1st version Execution: 0.286 s Compilation: 0.053 s Sum: 0.339 s 2nd version Execution: 0.002 s Compilation: 0.061 s Sum: 0.063 s (What did just happen here?) \$\endgroup\$ – Dennis Jun 2 '15 at 4:29
  • \$\begingroup\$ @Dennis It used another algorithm in O(m*n*2^n) if the flag is set. \$\endgroup\$ – jimmy23013 Jun 2 '15 at 4:38
  • 1
    \$\begingroup\$ Execution: 190 ms Compilation: 68 ms Sum: 258 ms (-O1 seems to be the sweet spot. I've tried all optimization levels.) \$\endgroup\$ – Dennis Jun 2 '15 at 15:03
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ @Dennis New version. Execution should be unchanged, but compilation faster. If we need to optimize for compile time, we don't need no system headers! \$\endgroup\$ – Reto Koradi Jun 1 '15 at 4:49
  • \$\begingroup\$ @Dennis Updated for new scoring, and for a round of optimizations. Note that I do want optimization now, something like -O2 should be good. \$\endgroup\$ – Reto Koradi Jun 2 '15 at 7:32
  • \$\begingroup\$ Execution: 256 ms Compilation: 65 ms Sum: 321 ms (-O2 seems to be the sweet spot. I've tried all optimization levels.) \$\endgroup\$ – Dennis Jun 2 '15 at 14:58
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Execution: 18 ms Compilation: 50 ms Sum: 68 ms (-O0 was the sweet spot for the total. Other options slowed down compilation.) \$\endgroup\$ – Dennis Jun 3 '15 at 2:53
  • \$\begingroup\$ This either never terminates, or at least takes a very long time, for input 32 2 s. I stopped it after about 15 minutes. \$\endgroup\$ – Reto Koradi Jun 3 '15 at 5:08
  • \$\begingroup\$ @RetoKoradi indeed, yet 2 32 s runs almost instantly. The scanning through all possible vertical dominoes is extremely wasteful for the H=2 case, because in fact we already have all necessary info in r[]. I'm very pleased with the official time for 8 8 s Here's a patch for the case you mention: if(H==2){C=p;if(!S)for(i=0;i<p;i++)q[0]=q[1]=r[i],h();}else for(i=0;i<=k;i++)c=0,g(H/2,1,i),C+=c*c; As you can see this snippet will run instantly for H=2 with the flag set. The overall runtime is then limited by the building of r[] which certainly has room for improvement. \$\endgroup\$ – Level River St Jun 3 '15 at 6:55
  • \$\begingroup\$ For completeness here's the patch for turning the output the right way up, if required: if(t)for(a=n;a--;a%H||puts(""))putchar(124-(q[a%H]>>a/H)%2*79);else for(a=n;a--;a%W||puts(""))putchar(45+(q[a/W]>>a%W)%2*79); Codelength is still well below 1000 bytes and impact on compile time should be minimal. I didn't include these patches last night as I was too tired. \$\endgroup\$ – Level River St Jun 3 '15 at 7:36
  • \$\begingroup\$ I meant to comment on that last night, but I forgot. Since the scoring is done on a square, I'm not going to insist on a particular order. \$\endgroup\$ – Dennis Jun 3 '15 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.