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.)
$ sdt 4 2 ---- ---- ||-- ||-- |--| |--| --|| --|| |||| |||| 5 $ sdt 4 2 scoring 5
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.
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.