Fibonacci domino tiling

Question

There's classic combinatorial result that the number of ways to tile a 2*n strip by 1*2 dominoes is the n^th Fibonacci number. You goal is to print all the tilings for a given n, drawn with dashes and vertical lines like these 8 tilings for n=5:

|————
|————
——|——
——|——
|||——
|||——
————|
————|
||——|
||——|
|——||
|——||
——|||
——|||
|||||
|||||

You are to provide a program or named function that take n as input and prints the required output. Fewest bytes wins.

Input

A number n between 1 and 10 inclusive via STDIN or function input.

Output

Print every possible domino tilings of the 2*n strip, drawn horizontally. The tilings may be in any order, but each should appear exactly once. They must be separated by a blank line.

A vertical domino is made of two vertical bars (|) and a horizontal domino is made of two em dashes (—). You may use hyphens (-) in place of em dashes to stay in ASCII.

You can do anything with whitespace as long as the printed output looks the same.

• Dennis: Would an extra linefeed after the last tiling fall under anything with whitespace?
• xnor: @Dennis Yes, extra blank lines are fine.
• Level River St: I'm really surprised to see so many different approaches to solving the same problem. Did you expect that?
• xnor: @steveverrill No, I totally did not, and am delighted to see the variety! And yours takes the cake for unexpectedness. I mostly had in mind a Fibonacci-style recursion, as most solutions used I used. I didn't expect filtering to be effective, and to the extent I did, I though it would be filtering strings of —— and | by length like Dennis's, not length-n strings of — and | filtered by — appearing in pairs. And for the latter, I'd expect it to be via regexes or string operations on the produced string, like s.split('——)`, not by an arithmetic approach like yours.
• SuperJedi224: I think "1x2 dominoes" is redundant.

Answer 1

C, 106

Golfed version

f(n){
 for(int i,h=n*2<<n;h--;(i/3|i/3*2)-i||(putchar(i>>h%n&1?45:124),h%n||puts(h%(n*2)?"":"\n")))
 i=h/2/n;
}

Original version

i,j,n;
main(){
 scanf("%d",&n);
 for(i=1<<n;i--;)if((i/3|i/3*2)==i){
 for(j=1<<n;j/=2;)printf("%c",i&j?'-':'|');puts("");
 for(j=1<<n;j/=2;)printf("%c",i&j?'-':'|');puts("\n");
 }
}

How it works

The variable i runs from 1<<n-1 down to 0, producing all possible binary numbers with n digits. 0 encodes for | and 1 encodes for -. We are interested in numbers that contain 1's in pairs. Obviously such numbers are divisible by 3.

When a number is divided by 3, the original number can be recovered by multiplying the result by 2 and adding it to itself (effectively mutliplying by 3.) Most numbers will require a carry, but when the process is carried out on the numbers of interest, no carry is required, so in these cases only, OR can be used instead of addition. This is used to test for the numbers of interest, as they are the only ones where the expression i/3|i/3*2 returns the original value of i. See example below.

1111=15 ---> 0101=5 ---> 1111=15 (valid, 0101|1010==0101+1010)

1001=9 ---> 0011=3 ---> 0111=7 (invalid, 0011|0110 != 0011+0110)

The test value is always equal or less than the original value. As numbers that are not multiples of 3 also return a number less than the original when divided by 3 then multipled by 3, the test gives the desired FALSE on these numbers too.

In the original version a couple of loops in j are used to scan through the bits of i and produce the output. In the golfed version a single for loop is used, in which h runs through all numbers from (n*2)*(1<<n)-1 down to 0. Values of i are generated by h/2/n. The variable j is no longer used, as the equivalent quantity is obtained from h%n. The use of n*2 enables both lines to be printed from the same loop, with some nifty multiplexing in the puts statement to print either one or two newlines at the end of the row.

Note that the meat of this is in the increment position of the for() bracket and therefore gets executed after the i=h/2/h.

Sample output n=6:

$ ./a
6
------
------
----||
----||
--|--|
--|--|
--||--
--||--
--||||
--||||
|----|
|----|
|--|--
|--|--
|--|||
|--|||
||----
||----
||--||
||--||
|||--|
|||--|
||||--
||||--
||||||
||||||

• xnor: The i/3|i/3*2 trick is ingenious! I didn't expect an arithmetic expression for grammar.

Answer 2

CJam, (削除) 33 (削除ここまで) 27 bytes

LN{_'|f+@"——"f++}ri*\;{_N}/

Thanks to @jimmy23013 for golfing off 6 bytes!

Try it online!

Background

This is an iterative implementation of a recursive algorithm:

The possible tilings for n can be obtained by adding a vertical domino to the possible tilings for n - 1 and two horizontal dominos to the possible tilings for n - 2.

This way, the number of tilings for n is the sum of the numbers of tilings for n - 1 and n - 2, i.e., the n^th Fibonacci number.

How it works

LN " A:= [''] B:= ['\n'] ";
 { }ri* " Repeat int(input()) times: ";
 _'|f+ " C = copy(B); for T ∊ C: T += '|' ";
 @ " Swap A and B. ";
 "——"f+ " for T ∊ B: T += "——" ";
 + " B = C + B ";
 \; " Discard A. ";
 {_N}/ " for T ∊ B: print T, T + '\n' ";

Example run

$ alias cjam='java -jar cjam-0.6.2.jar'
$ cjam domino.cjam <<< 3
|||
|||
——|
——|
|——
|——
$ for i in {1..10}; do echo $[$(cjam domino.cjam <<< $i | wc -l) / 3]; done1
2
3
5
8
13
21
34
55
89

• jimmy23013: LNli{_'|f\@"——"f\+2/}*\;{_N}/.
• Dennis: f\ hadn't been implemented in 0.6.2 yet, but I was able to combine our approaches. Thanks!

Answer 3

Haskell, 89 bytes

f(-1)=[]
f 0=[""]
f n=map('|':)(f$n-1)++map("--"++)(f$n-2)
g=unlines.(>>= \x->[x,x,""]).f

f is a function that given a number returns a list of one lines of all the possible Fibonacci tilings of length n possible. it doesn't matter that it returns one line, because both lines of all tilings are the same.

f works by calling recursively on n-1 and n-2 and adding "|" and "--" (respectively) to the strings.

g is the function that answers the questions. it basically calls f on the input, doubles every string so that it would show two lines and joins them all by newlines.

example output:

*Main> putStrLn $ g 5
|||||
|||||
|||--
|||--
||--|
||--|
|--||
|--||
|----
|----
--|||
--|||
--|--
--|--
----|
----|

Answer 4

CJam, (削除) 42 (削除ここまで) 37 bytes

3li:L#,{3b"——|"2/f=s}%{,L=},_&{N+_N}/

I've counted the dashes as one byte each since the question allows to replace them with ASCII hyphens.

Try it online.

How it works

To obtain all possible tilings of 2 ×ばつ L, we iterate over all non-negative integers I < 3^L, making even digits in base 3 correspond to horizontal dominos and odd digits to vertical ones.

Since each I has L or less digits in base 3, this generates all possible ways of covering the 2 ×ばつ L strip. All that's left is to filter out the coverings that are bigger or smaller than 2 ×ばつ L and print the remaining coverings.

3li:L#, " Read an integer L from STDIN and push A := [ 0 1 ... (3 ** N - 1) ]. ";
{ " For each integer I in A: ";
 3b " Push B, the array of I's base 3 digits. ";
 "——|"2/ " Push S := [ '——' '|' ]. ";
 f= " Replace each D in B with S[D % 2] (the modulus is implicit). ";
 s " Flatten B. ";
}% " Collect the result in an array R. ";
{,L=}, " Filter R so it contains only strings of length L. ";
_& " Intersect R with itself to remove duplicates. ";
{N+_N}/ " For each string T in B, push (T . '\n') twice, followed by '\n'. ";

Example run

$ cjam domino.cjam <<< 3
|——
|——
——|
——|
|||
|||
$ for i in {1..10}; do echo $[$(cjam domino.cjam <<< $i | wc -l) / 3]; done
1
2
3
5
8
13
21
34
55
89

• Level River St: Cool. I'm just wondering why you didn't use base 2 like edc65 instead of base 3. That would have saved you from having duplicates. I assume it's because leading zeroes probably get truncated in the step 3b. Is that right?
• Dennis: @steveverrill: Yes, that's precisely the reason. As it is, leading zeros correspond to no domino at all. But not having duplicates would allow me to replace the three blocks with a single one. I'll have to think about this some more.
• Dennis: @steveverrill: I didn't manage to make base 2 work, but a recursive approach seems to be even shorter.

Answer 5

JavaScript (E6) 102

Generate configurations from bit sequences, 0 -> '--' and 1 -> '|'.

F=n=>{
 for(i=0;(j=++i)<2<<n;s.length==1+n&&console.log('\n'+s+s))
 for(s='\n';j>1;j>>=1)s+=j&1?'|':'--';
}

Test In firefox/firebug console

F(5)

Output

|----
|----
--|--
--|--
----|
----|
|||--
|||--
||--|
||--|
|--||
|--||
--|||
--|||
|||||
|||||

Answer 6

Haskell: 109 bytes

This is a translation of the well-known Haskell one-liner for lazily computing the sequence of Fibonacci numbers:

b=map.map.(++)
w=zipWith
z=w(++)
s=["\n"]:["|\n"]:z(b"--"s)(b"|"$tail s)
f=sequence_.map putStrLn.(w z s s!!)

The main sequence of tiling strings, ungolfed:

dominos = [""] : ["|"] : zipWith (++) ("--" `before` dominos) ("|" `before` tail dominos)
 where before = map . map . (++)

And the Fibonacci one-liner for comparison:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Usage example:

$ ghci fibtile
GHCi, version 7.6.3: http://www.haskell.org/ghc/ :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
[1 of 1] Compiling Main ( fibtile.hs, interpreted )
Ok, modules loaded: Main.
*Main> f 5
----|
----|
--|--
--|--
--|||
--|||
|----
|----
|--||
|--||
||--|
||--|
|||--
|||--
|||||
|||||
*Main>

Answer 7

Cobra - 176

Can't wait till I've finished the Cobra golfing package.

def m(n)
 for t in.f(n),print t+t
def f(n,x='')as String*
 if x.length<n,for i in.f(n,x+'-').toList+.f(n,x+'|').toList,yield i
 else if not'-'in x.replace('--',''),yield x+'\n'

Answer 8

J - 54 char

Function taking n as argument on the right.

0{::(];'--'&,"1@[,'|',"1])&>/@[&0&((1 2,ドル:)&.>'';,'|')

The main root of this golf is the (];'--'&,"1@[,'|',"1])&>/. This takes a list of tilings of length (N-2) and (N-1), and returns a list of tilings of length (N-1) and N. This is the standard Fibonacci recurrence, à la linear algebra. ]; returns the right list as the new left (as there is no change). '--'&,"1@[ adds -- tiles to the left list, while '|',"1] adds | tiles to the right list, and those together are the new right list.

We iterate that over and over n times (that's the @[&0) and start with the empty tiling and the single tiling of length 1. Then we return the first of the pair with 0{::. Meaning, if we run it zero times, we just return the first i.e. the empty tiling. If we run it n times, we calculate up to the n and (n+1) pair, but discard the latter. It's extra work but less characters.

The (1 2,ドル:) is something J has to do in order to make the tilings in the lists easily extendable. We make the left starting list be a 1-item list of a 2-row matrix of characters, each row having length 0. The right starting list is the same, but has the rows be of length 1, filled with |. Then, we add the new tiles to each row, and append the lists of matrices when we're joining the two sets of tilings together. It's a simple application of a concept J calls rank: essentially manipulating the dimensionality of its arguments, and implicitly looping when necessary.

 0{::(];'--'&,"1@[,'|',"1])&>/@[&0&((1 2,ドル:)&.>'';,'|')5
----|
----|
--|--
--|--
--|||
--|||
|----
|----
|--||
|--||
||--|
||--|
|||--
|||--
|||||
|||||

Try it for yourself at tryj.tk.

Answer 9

Python 3: 70 bytes

f=lambda n,s="\n":n>0and f(n-1,"|"+s)==f(n-2,"--"+s)or n or print(s*2)

Recursively builds all possible strings s representing one row of dominos, which are duplicated and printed. Starting s as the newline character makes the blank line happen automatically.

The == between the two calls for f is just to perform both function calls. These usually return None because they just print, and == is one of few operators defined for None.

The ands and ors are to produce the right short-circuiting behavior to reproduce the ifs and elses of the ungolfed code.

Ungolfed:

def f(n,s="\n"):
 if n==-1:pass
 elif n==0: print(s*2)
 else: f(n-1,"|"+s);f(n-2,"--"+s)

Answer 10

Retina, 44 bytes

Note: Retina is younger than this challenge.

+`([-|]*)11(1*#)
1ドル|12ドル1ドル--2ドル
1
|
.*?#
0ドル0ドル#

Takes input in unary with a trailing newline.

Each line should go to its own file and # should be changed to newline in the file. This is impractical but you can run the code as is as one file with the -s flag, keeping the # markers (and changing the newline to # in the input too). You can change the #'s back to newlines in the output for readability if you wish. E.g.:

> echo 1111# | retina -s fib_tile | tr # '\n'
||||
||||
||--
||--
|--|
|--|
--||
--||
----
----

Method:

• Starting from the input we swap every line with two other: one with the first 1 change to | and one with the first two 1's changed to --. We do this until we have lines with at least two 1's.
• When there are only single 1's left we changed those to |'s.
• We double each line and add an extra newline to it and we get the desired output.

• xnor: Trailing newline is fine.