7
\$\begingroup\$

This is an extension of Fibonacci Domino Tiling. Your goal is to print all 281 ways to tile a 4x6 rectangle with 1x2 and 2x1 dominoes. Fewest bytes wins.

Use the vertical bar | to indicate a space covered by the vertical domino, and an em-dash (count it as if it were ASCII) or hyphen - for horizontal ones.

Example output: (281 tilings, 1405 lines)

——————
——————
——————
——————

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

||||||
||||||
||||||
||||||

Input

There is no input -- you only have to print 4x6 tilings. In theory, you could hardcode an output, but that would likely take more bytes that producing it.

Output

Print the 281 tilings in any order in the format shown in the example, with each one appearing exactly once. There must be exactly one empty line between tilings. Any other whitespace is OK if it doesn't affect the visible output. Empty lines at the start and end are also OK.

Other requirements

Your code should not be horribly slow; it should produce output within 10 minutes, which should be ample time. Functions to produce or enumerate tilings are disallowed.

In case people are wondering if this is sufficiently distinct from Fibonacci Domino Tiling, I expect the answers to use a different strategies as one can no longer take advantage of the particular Fibonacci structure of 2-by-n domino tilings and them being specified by their top row.

\$\endgroup\$
5
\$\begingroup\$

CJam, 75 67 63 58 57 bytes

La'|a{_'|f+@:C"--"f++}5*\;_m*_m*{~+}%{zC{81f^}%-!},Nf+Nf*

Try it online.

Example run

$ cjam 4x6.cjam | head -9
||||||
||||||
||||||
||||||

||||||
||||||
--||||
--||||
$ cjam 4x6.cjam | tail -10
------
------
||----
||----

------
------
------
------

$ cjam 4x6.cjam | wc -l
1405
$ cjam 4x6.cjam | md5sum
83b5de42157ace906ed5c0173fb99027  -

Background

A covering of the rectangle by domino halves is a valid tiling if:

  1. Horizontal domino halves occur in pairs in each row.
  2. Vertical domino halves occur in pairs in each column.

The valid configurations for rows of length n can be obtained by adding a vertical domino half to the valid configurations for n - 1 and a two horizontal domino halves to the valid configurations for n - 2.

The valid configurations for columns of length n can be computed as the configurations of rows of the same length, exchanging vertical domino halves and horizontal domino halves.

To generate all 281 possible tilings, it suffices to generate all possible combinations of rows, all possible combinations of columns and intersect the two sets.

Implementation

Rather than generating combinations twice and intersecting, we can generate all possible combinations of rows and check if their columns have a valid pattern.

" Leave an array of valid row configurations of length 6 on the stack and save the valid
  row configurations of length 4 in C. In http://codegolf.stackexchange.com/a/38000,
  I explain in detail how this is achieved.                                               ";

La'|a{_'|f+@:C"--"f++}5*\;

" Compute the Cartesian product of four copies of the array.                              ";

_m*_m*

" Flatten the arrays of strings of the Cartesian product.                                 ";

{~+}%

" Transpose rows and columns, swap vertical bars and hyphens in C (note that ord('-') ==
 ord('-') ^ 81) and check if all rows of the first array belong to the second.            ";

{zC{81f^}%-!},

" Separate the rows of a tiling and the tilings from each other.                          ";

Nf+ Nf*
\$\endgroup\$
  • \$\begingroup\$ Cool, I wonder if this method would work in general. I see no reason why not. It would be interesting to check it on 5x5 and confirm it returns nothing. BTW, I have though of a massive improvement to my program (same philosophy as my current one, but different implementation) but I have no time to write it today. Don't worry, it will still be about twice as long as yours ;-D \$\endgroup\$ – Level River St Sep 20 '14 at 11:20
  • \$\begingroup\$ After generating the possible rows and columns dynamically, this approach should work just fine in the general case. The row check makes sure all dashes occur in pairs, the column check does the same for bars. Since a valid row would have to contain an even amount of dashes and a valid column an even amount of bars, it would return nothing for 5x5. \$\endgroup\$ – Dennis Sep 20 '14 at 12:52
  • \$\begingroup\$ Interesting, the idea of generating and intersecting is clever. I hadn't considered a partial hardcode like this. \$\endgroup\$ – xnor Sep 21 '14 at 0:07
  • \$\begingroup\$ @xnor: Turns out that generating the rows is even shorter. \$\endgroup\$ – Dennis Sep 21 '14 at 21:44
4
\$\begingroup\$

C, 282 bytes ungolfed

i,j,p[4],q,t,a,b,c,d;
main(){
  char s[]="UTRQPJIHEDBA@";
  for(i=64*169;i--;){
    a=p[0]=s[i%13]*3,d=p[3]=s[i/13%13]*3,q=i/169;
    b=p[1]=p[0]&q;c=p[2]=p[3]&q;
    if((a|q)==255&(d|q)==255 & (b/3|b/3*2)==b & (c/3|c/3*2)==c)
      for(j=24;j--;)putchar(p[j/6]>>j%6&1?45:124),j%6||printf(j?"\n":" %d\n\n",t+=!j); 
  }
}

This works in a similar way to my answer to the previous question, with 1 representing - and 0 representing |. In fact the 13 valid combinations for n=6 in the previous question are encoded in s[], having had binary 11000000 added to them to bring them into a convenient ASCII range, then divided by 3.

A logical way to proceed is to place the vertical dominoes that straddle the centreline, then place the remaining vertical dominoes, and finally place the horizontal dominoes. That's basically how my code proceeds. The 13x13=169 possible tilings with no vertical dominoes crossing the centreline are listed first, then the different combinations of vertical dominoes crossing the centreline are explored.

q contains the pattern for vertical centre dominoes (all 64 combinations of 1's and 0's are allowed in principle.) a and d store the top and bottom rows (only those 13 combinations from the previous question are allowed, as they are the only ones that give complete horizontal dominoes.) b and c hold the calculated values for the centre rows (made by ANDing q with a and d) and the following rules are applied:

1: no vertical dominoes may overlap. a and d when ORed with q must give 11111111. (Remember due to the compression method, each domino in a and dis carrying an additional 11000000.)

2: rows b and c must hold complete horizontal dominoes. The code for checking this is (b/3|b/3*2)==b and is explained in my answer to the previous question.

output

in addition to a,b,c,d, the four rows are stored in an array p[] for printing via a loop. Currently each pattern is numbered. The numbering will be removed as part of the golfing process.

||||||
||||||
||||||
|||||| 1

||||||
||||||
||||--
||||-- 2

||||||
||||||
|||--|
|||--| 3

||||||
||||||
||--||
||--|| 4

||||||
||||||
||----
||---- 5

||||||
||||||
|--|||
|--||| 6

||||||
||||||
|--|--
|--|-- 7

||||||
||||||
|----|
|----| 8

||||||
||||||
--||||
--|||| 9

||||||
||||||
--||--
--||-- 10

||||||
||||||
--|--|
--|--| 11

||||||
||||||
----||
----|| 12

||||||
||||||
------
------ 13

||||--
||||--
||||||
|||||| 14

||||--
||||--
||||--
||||-- 15

||||--
||||--
|||--|
|||--| 16

||||--
||||--
||--||
||--|| 17

||||--
||||--
||----
||---- 18

||||--
||||--
|--|||
|--||| 19

||||--
||||--
|--|--
|--|-- 20

||||--
||||--
|----|
|----| 21

||||--
||||--
--||||
--|||| 22

||||--
||||--
--||--
--||-- 23

||||--
||||--
--|--|
--|--| 24

||||--
||||--
----||
----|| 25

||||--
||||--
------
------ 26

|||--|
|||--|
||||||
|||||| 27

|||--|
|||--|
||||--
||||-- 28

|||--|
|||--|
|||--|
|||--| 29

|||--|
|||--|
||--||
||--|| 30

|||--|
|||--|
||----
||---- 31

|||--|
|||--|
|--|||
|--||| 32

|||--|
|||--|
|--|--
|--|-- 33

|||--|
|||--|
|----|
|----| 34

|||--|
|||--|
--||||
--|||| 35

|||--|
|||--|
--||--
--||-- 36

|||--|
|||--|
--|--|
--|--| 37

|||--|
|||--|
----||
----|| 38

|||--|
|||--|
------
------ 39

||--||
||--||
||||||
|||||| 40

||--||
||--||
||||--
||||-- 41

||--||
||--||
|||--|
|||--| 42

||--||
||--||
||--||
||--|| 43

||--||
||--||
||----
||---- 44

||--||
||--||
|--|||
|--||| 45

||--||
||--||
|--|--
|--|-- 46

||--||
||--||
|----|
|----| 47

||--||
||--||
--||||
--|||| 48

||--||
||--||
--||--
--||-- 49

||--||
||--||
--|--|
--|--| 50

||--||
||--||
----||
----|| 51

||--||
||--||
------
------ 52

||----
||----
||||||
|||||| 53

||----
||----
||||--
||||-- 54

||----
||----
|||--|
|||--| 55

||----
||----
||--||
||--|| 56

||----
||----
||----
||---- 57

||----
||----
|--|||
|--||| 58

||----
||----
|--|--
|--|-- 59

||----
||----
|----|
|----| 60

||----
||----
--||||
--|||| 61

||----
||----
--||--
--||-- 62

||----
||----
--|--|
--|--| 63

||----
||----
----||
----|| 64

||----
||----
------
------ 65

|--|||
|--|||
||||||
|||||| 66

|--|||
|--|||
||||--
||||-- 67

|--|||
|--|||
|||--|
|||--| 68

|--|||
|--|||
||--||
||--|| 69

|--|||
|--|||
||----
||---- 70

|--|||
|--|||
|--|||
|--||| 71

|--|||
|--|||
|--|--
|--|-- 72

|--|||
|--|||
|----|
|----| 73

|--|||
|--|||
--||||
--|||| 74

|--|||
|--|||
--||--
--||-- 75

|--|||
|--|||
--|--|
--|--| 76

|--|||
|--|||
----||
----|| 77

|--|||
|--|||
------
------ 78

|--|--
|--|--
||||||
|||||| 79

|--|--
|--|--
||||--
||||-- 80

|--|--
|--|--
|||--|
|||--| 81

|--|--
|--|--
||--||
||--|| 82

|--|--
|--|--
||----
||---- 83

|--|--
|--|--
|--|||
|--||| 84

|--|--
|--|--
|--|--
|--|-- 85

|--|--
|--|--
|----|
|----| 86

|--|--
|--|--
--||||
--|||| 87

|--|--
|--|--
--||--
--||-- 88

|--|--
|--|--
--|--|
--|--| 89

|--|--
|--|--
----||
----|| 90

|--|--
|--|--
------
------ 91

|----|
|----|
||||||
|||||| 92

|----|
|----|
||||--
||||-- 93

|----|
|----|
|||--|
|||--| 94

|----|
|----|
||--||
||--|| 95

|----|
|----|
||----
||---- 96

|----|
|----|
|--|||
|--||| 97

|----|
|----|
|--|--
|--|-- 98

|----|
|----|
|----|
|----| 99

|----|
|----|
--||||
--|||| 100

|----|
|----|
--||--
--||-- 101

|----|
|----|
--|--|
--|--| 102

|----|
|----|
----||
----|| 103

|----|
|----|
------
------ 104

--||||
--||||
||||||
|||||| 105

--||||
--||||
||||--
||||-- 106

--||||
--||||
|||--|
|||--| 107

--||||
--||||
||--||
||--|| 108

--||||
--||||
||----
||---- 109

--||||
--||||
|--|||
|--||| 110

--||||
--||||
|--|--
|--|-- 111

--||||
--||||
|----|
|----| 112

--||||
--||||
--||||
--|||| 113

--||||
--||||
--||--
--||-- 114

--||||
--||||
--|--|
--|--| 115

--||||
--||||
----||
----|| 116

--||||
--||||
------
------ 117

--||--
--||--
||||||
|||||| 118

--||--
--||--
||||--
||||-- 119

--||--
--||--
|||--|
|||--| 120

--||--
--||--
||--||
||--|| 121

--||--
--||--
||----
||---- 122

--||--
--||--
|--|||
|--||| 123

--||--
--||--
|--|--
|--|-- 124

--||--
--||--
|----|
|----| 125

--||--
--||--
--||||
--|||| 126

--||--
--||--
--||--
--||-- 127

--||--
--||--
--|--|
--|--| 128

--||--
--||--
----||
----|| 129

--||--
--||--
------
------ 130

--|--|
--|--|
||||||
|||||| 131

--|--|
--|--|
||||--
||||-- 132

--|--|
--|--|
|||--|
|||--| 133

--|--|
--|--|
||--||
||--|| 134

--|--|
--|--|
||----
||---- 135

--|--|
--|--|
|--|||
|--||| 136

--|--|
--|--|
|--|--
|--|-- 137

--|--|
--|--|
|----|
|----| 138

--|--|
--|--|
--||||
--|||| 139

--|--|
--|--|
--||--
--||-- 140

--|--|
--|--|
--|--|
--|--| 141

--|--|
--|--|
----||
----|| 142

--|--|
--|--|
------
------ 143

----||
----||
||||||
|||||| 144

----||
----||
||||--
||||-- 145

----||
----||
|||--|
|||--| 146

----||
----||
||--||
||--|| 147

----||
----||
||----
||---- 148

----||
----||
|--|||
|--||| 149

----||
----||
|--|--
|--|-- 150

----||
----||
|----|
|----| 151

----||
----||
--||||
--|||| 152

----||
----||
--||--
--||-- 153

----||
----||
--|--|
--|--| 154

----||
----||
----||
----|| 155

----||
----||
------
------ 156

------
------
||||||
|||||| 157

------
------
||||--
||||-- 158

------
------
|||--|
|||--| 159

------
------
||--||
||--|| 160

------
------
||----
||---- 161

------
------
|--|||
|--||| 162

------
------
|--|--
|--|-- 163

------
------
|----|
|----| 164

------
------
--||||
--|||| 165

------
------
--||--
--||-- 166

------
------
--|--|
--|--| 167

------
------
----||
----|| 168

------
------
------
------ 169

||||--
||||||
||||||
||||-- 170

||||--
||||||
||--||
||---- 171

||||--
||||||
|--|||
|--|-- 172

||||--
||||||
--||||
--||-- 173

||||--
||||||
----||
------ 174

||----
||--||
||||||
||||-- 175

||----
||--||
||--||
||---- 176

||----
||--||
|--|||
|--|-- 177

||----
||--||
--||||
--||-- 178

||----
||--||
----||
------ 179

|--|--
|--|||
||||||
||||-- 180

|--|--
|--|||
||--||
||---- 181

|--|--
|--|||
|--|||
|--|-- 182

|--|--
|--|||
--||||
--||-- 183

|--|--
|--|||
----||
------ 184

--||--
--||||
||||||
||||-- 185

--||--
--||||
||--||
||---- 186

--||--
--||||
|--|||
|--|-- 187

--||--
--||||
--||||
--||-- 188

--||--
--||||
----||
------ 189

------
----||
||||||
||||-- 190

------
----||
||--||
||---- 191

------
----||
|--|||
|--|-- 192

------
----||
--||||
--||-- 193

------
----||
----||
------ 194

|||--|
||||||
||||||
|||--| 195

|||--|
||||||
|--|||
|----| 196

|||--|
||||||
--||||
--|--| 197

|----|
|--|||
||||||
|||--| 198

|----|
|--|||
|--|||
|----| 199

|----|
|--|||
--||||
--|--| 200

--|--|
--||||
||||||
|||--| 201

--|--|
--||||
|--|||
|----| 202

--|--|
--||||
--||||
--|--| 203

||----
|||--|
|||--|
||---- 204

||----
|||--|
--|--|
------ 205

------
--|--|
|||--|
||---- 206

------
--|--|
--|--|
------ 207

||--||
||||||
||||||
||--|| 208

||--||
||||||
||||--
||---- 209

||--||
||||||
--||||
----|| 210

||--||
||||||
--||--
------ 211

||----
||||--
||||||
||--|| 212

||----
||||--
||||--
||---- 213

||----
||||--
--||||
----|| 214

||----
||||--
--||--
------ 215

----||
--||||
||||||
||--|| 216

----||
--||||
||||--
||---- 217

----||
--||||
--||||
----|| 218

----||
--||||
--||--
------ 219

------
--||--
||||||
||--|| 220

------
--||--
||||--
||---- 221

------
--||--
--||||
----|| 222

------
--||--
--||--
------ 223

||----
||||||
||||||
||---- 224

||----
||||||
--||||
------ 225

------
--||||
||||||
||---- 226

------
--||||
--||||
------ 227

|----|
||--||
||--||
|----| 228

|--|||
||||||
||||||
|--||| 229

|--|||
||||||
||||--
|--|-- 230

|--|||
||||||
|||--|
|----| 231

|--|--
||||--
||||||
|--||| 232

|--|--
||||--
||||--
|--|-- 233

|--|--
||||--
|||--|
|----| 234

|----|
|||--|
||||||
|--||| 235

|----|
|||--|
||||--
|--|-- 236

|----|
|||--|
|||--|
|----| 237

|--|--
||||||
||||||
|--|-- 238

|----|
||||||
||||||
|----| 239

------
|----|
|----|
------ 240

----||
|--|||
|--|||
----|| 241

----||
|--|||
|--|--
------ 242

------
|--|--
|--|||
----|| 243

------
|--|--
|--|--
------ 244

------
|--|||
|--|||
------ 245

--||||
||||||
||||||
--|||| 246

--||||
||||||
||||--
--||-- 247

--||||
||||||
|||--|
--|--| 248

--||||
||||||
||--||
----|| 249

--||||
||||||
||----
------ 250

--||--
||||--
||||||
--|||| 251

--||--
||||--
||||--
--||-- 252

--||--
||||--
|||--|
--|--| 253

--||--
||||--
||--||
----|| 254

--||--
||||--
||----
------ 255

--|--|
|||--|
||||||
--|||| 256

--|--|
|||--|
||||--
--||-- 257

--|--|
|||--|
|||--|
--|--| 258

--|--|
|||--|
||--||
----|| 259

--|--|
|||--|
||----
------ 260

----||
||--||
||||||
--|||| 261

----||
||--||
||||--
--||-- 262

----||
||--||
|||--|
--|--| 263

----||
||--||
||--||
----|| 264

----||
||--||
||----
------ 265

------
||----
||||||
--|||| 266

------
||----
||||--
--||-- 267

------
||----
|||--|
--|--| 268

------
||----
||--||
----|| 269

------
||----
||----
------ 270

--||--
||||||
||||||
--||-- 271

--||--
||||||
||--||
------ 272

------
||--||
||||||
--||-- 273

------
||--||
||--||
------ 274

--|--|
||||||
||||||
--|--| 275

------
|||--|
|||--|
------ 276

----||
||||||
||||||
----|| 277

----||
||||||
||||--
------ 278

------
||||--
||||||
----|| 279

------
||||--
||||--
------ 280

------
||||||
||||||
------ 281
\$\endgroup\$
  • \$\begingroup\$ Very interesting and unique approach, as usual. The bit magic from this and your other answer is nothing short of amazing! \$\endgroup\$ – Dennis Sep 20 '14 at 12:56
2
\$\begingroup\$

C, 216 bytes

#define M:++B:++B:8;for(k=0
j,k,B;char*c,s[99];main(i){for(i<<=24;i--;B||puts(s)){for(B=k=0;j=i>>k++;)j&1?k%6?j&2?k++M;k^29;k+=6)j=~i>>(k-=k/24*23),j&1?k<18?j&64?k+=6
M,c=s;k<24;++k%6||(*c++=10))*c++=1<<k&i?45:'|';}}

Sadly it took over 200 bytes. My approach was to view the grid as 24 bits which can each be either part of a horizontal piece or part of a vertical piece. It generates all 1<<24 combinations and then goes down the rows and columns munching the dominos to see whether each one is valid.

\$\endgroup\$
  • \$\begingroup\$ How long does it take to run with 16 million or so combinations? \$\endgroup\$ – xnor Sep 21 '14 at 8:01
  • \$\begingroup\$ @xnor It was taking about 10 seconds, without optimizations enabled. \$\endgroup\$ – feersum Sep 21 '14 at 14:14
2
\$\begingroup\$

Python 2: 130 bytes

for i in range(4096):
 G=([0]*6+["\n"])*4;exec"b=i%2;j=G.index(0);G[j]=G[(j+7**b)%28]='-|'[b];i/=2;"*12
 if all(G):print"".join(G)

I use a different encoding of tilings than has been posted so far, one that is more efficient timewise in that it needs only 12 bits to represent a valid tiling, though in retrospect perhaps not the golfiest one.

If you "read" through the 4x6 grid from left to right, top to bottom, each domino you encounter in order is either vertical or horizontal. (Of course, you encounter each domino twice, but only the first encounter of the top or left corner matters). This gives a sequence of 12 bits.

For example, the tiling

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

corresponds to HVHVVVVHVHHH.

Conversely, each sequence of 12 corresponds to a unique tiling, created by repeatedly adding a tile of the specified orientation with it's top or right cell as the first unoccupied cell in reading order. Some, though, are not legal tilings because a domino is placed with its other half off the board or overlapping with an existing domino.

The code tries every possible sequence, represented by a 12-bit number 0 to 4095, reading off bits one at a time with %2 and /2. The board, initialized with zeroes for empty cells, is stored with rows concatenated into a single list. That way, it's easy to find the first zero element to place the domino. The other domino half is either one row or column down, and so found by adding 1 or 6 to the index. These two cells are filled with the proper character - or |. This list could have been a string except that Python strings are immutable.

Rather than checking for a collision, we place the dominoes allowing overlaps, and see at the end whether the board is filled by whether any zeroes remain (all). We actually make the board 4x7, filling the right row with \n for two reasons. The first is that the padding lets horizontal dominoes go off the end without cycling over to the left edge (dominoes that go off the bottom edge are wrapped around with %28, but that's fine because they overlap with the the first row which has been filled by then). The other reason is so that in a legal configuration, the newlines remain and cause the lines to be printed separately when the characters are joined.

\$\endgroup\$
  • \$\begingroup\$ Very interesting approach! Since this iterates through much less coverings than my algorithm, I expected it to be a lot faster. However, your code takes 1.14 s with CPython (2.66 s with PyPy) on my machine, while my CJam code takes only 0.35 s. I wonder why... \$\endgroup\$ – Dennis Sep 24 '14 at 3:54
  • \$\begingroup\$ @Dennis That is surprising. I was going to say that maybe printing dominates the running time, except removing printing doesn't make it faster. Maybe Python is really just that slow. Having written this, I had not expected a 2**24 algorithm to fit within the time limit. \$\endgroup\$ – xnor Sep 24 '14 at 4:02
  • \$\begingroup\$ Eliminating the print line was the first thing I tried. exec is the culprit. With a loop, it runs in 0.08 seconds. \$\endgroup\$ – Dennis Sep 24 '14 at 4:05
  • \$\begingroup\$ @Dennis Oh, nice find. So perhaps repeatedly calling the interpreter at runtime is eating up all of the time. Also, the loop time extrapolates to ~5 minutes for 2**24 tilings, so looping over these was probably viable, though I'd need to think about efficiency. \$\endgroup\$ – xnor Sep 24 '14 at 4:09
  • 1
    \$\begingroup\$ Longest 24 hours of my life. Let me know what you think. \$\endgroup\$ – Dennis May 18 '15 at 22:33

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.