# The number of tilings of a grid

Setup: A block is any rectangular array of squares, specified by its dimensions $$\(w,h)\$$. A grid is any finite ordered list of blocks. For example, $$\\lambda = ((3,2),(3,1),(1,2))\$$ defines a grid.

Let $$\\lambda\$$ and $$\\mu\$$ be two grids with equal area.

A tiling of $$\\lambda\$$ by $$\\mu\$$ is any rearrangement of the squares of $$\\mu\$$ into the shape of $$\\lambda\$$ satisfying two properties:

1. horizontally adjacent squares of $$\\mu\$$ remain horizontally adjacent in $$\\lambda\$$, and
2. vertically adjacent squares of $$\\lambda\$$ come from vertically adjacent squares of $$\\mu\$$.

In other words, while rearranging one is allowed to make horizontal cuts to the blocks of $$\\mu\$$ but not vertical cuts, and one is allowed to place blocks into $$\\lambda\$$ side-by-side, but not on top of one another.

Two tilings of $$\\lambda\$$ by $$\\mu\$$ are considered equivalent if they can be rearranged into one another by any combination of either permuting squares within a column or reordering the columns of a block.

Problem: Write a function $$\T(\mu,\lambda)\$$ which computes the number of inequivalent tilings of a grid $$\\lambda\$$ by another grid $$\\mu\$$ of equal area.

Specifications: You may use any data type you would like to specify a grid.

Examples:

1. The grid $$\\lambda=((1,2),(1,2),(1,1),(2,1))\$$ admits a tiling by $$\\mu=((1,3),(1,2),(2,1))\$$ given by

There is exactly one other inequivalent tiling given by

(Since the two differently colored columns of height $$\2\$$ are not part of the same block, they cannot be permuted.)

1. The three displayed tilings of $$\\lambda=((3,1))\$$ by $$\\mu=((1,2),(1,1))\$$ are equivalent:

1. Let $$\\lambda\$$ be an arbitrary grid of area $$\n\$$ and let $$\\lambda[(w,h)]\$$ denote the number of blocks of $$\\lambda\$$ of dimension $$\w \times h\$$. Then $$\T(\lambda,\lambda) = \prod_{w,h\geq 1} \lambda[(w,h)]!\$$ and $$\T(\lambda,((n,1))) = 1\$$.

2. The matrix of values of $$\T(\mu,\lambda)\$$ for all pairs of grids of area $$\3\$$ (row is $$\\mu\$$, column is $$\\lambda\$$):

((1,3)) ((1,2),(1,1)) ((1,1),(1,1),(1,1)) ((2,1),(1,1)) ((3,1))
((1,3)) 1 1 1 1 1
((1,2),(1,1)) 0 1 3 2 1
((1,1),(1,1),(1,1)) 0 0 6 3 1
((2,1),(1,1)) 0 0 0 1 1
((3,1)) 0 0 0 0 1
• Welcome to Code Golf! This looks like a great challenge, although if you haven't already I'd recommend checking out the sandbox for future ones. Apr 10, 2021 at 3:05
• This is a well written and interesting challenge. However, it would be much appreciated to include some test cases where only $\lambda$, $\mu$ and the expected output are provided, so that the answers can be more easily tested. Apr 10, 2021 at 7:27
• Thanks for the suggestions. I've just added all possible values for grids of area 3.
– AWO
Apr 10, 2021 at 20:42
• You may want to provide a test case with at least one block of size $w>1$, $h>1$. Apr 11, 2021 at 7:12
• I've just generalized example 3 to include such test cases.
– AWO
Apr 11, 2021 at 13:41

• -2 bytes thanks to xnor, for suggesting a better partitioning function q.
• -8 bytes thanks to ovs, for suggesting [a!!i|i:_<-u] and removing an unnecessary map.
(a#b)c d=sum[1|g<-nub$(permutations(zipWith replicate b[0..]>>=id)>>=q)>>=mapM(q.sort),l g==l c,and[l x==h&&all(==x!!0)x&&sum[a!!i|i:_<-u]==w|(u,w,h)<-zip3 g c d,x<-u]] q=foldr(\h t->map([h]:)t++[(h:y):z|y:z<-t])[[]] l=length import Data.List  Try it online! A grid $$\\mu\$$ is represented as a pair $$\(W_\mu,H_\mu)\$$ where $$\W_\mu\$$, $$\H_\mu\$$ are lists containing, respectively, the widths and the heights of the blocks in $$\\mu\$$. The relevant function is (#), which takes as input four lists: a$$\=W_\mu\$$, b$$\=H_\mu\$$, c$$\=W_\lambda\$$, d$$\=H_\lambda\$$. It returns the integer $$\T(\mu,\lambda)\$$. • I noticed you have a function q that generates all partitions. You can use a slightly shorter version I had written from some previous challenge: q=foldr(\h t->map([h]:)t++[(h:y):z|y:z<-t])[[]]. – xnor Apr 11, 2021 at 3:25 • @xnor Nice, thanks! I should probably explain the code, so that you can suggest other amazing golfs ^^ Apr 11, 2021 at 10:00 • sum[a!!head i|i<-u] can be shortened to sum[a!!i|i:_<-u]. – ovs Apr 11, 2021 at 10:29 • nub$(permutations(zipWith replicate b[0..]>>=id)>>=q)>>=mapM(q.sort) saves 5 more bytes. (concatMap f \$ map g x == concatMap (f.g) x)