7
\$\begingroup\$

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

enter image description here

There is exactly one other inequivalent tiling given by

enter image description here

(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:

enter image description here

  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
\$\endgroup\$
5
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Apr 10, 2021 at 3:05
  • 6
    \$\begingroup\$ 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. \$\endgroup\$
    – Arnauld
    Apr 10, 2021 at 7:27
  • 1
    \$\begingroup\$ Thanks for the suggestions. I've just added all possible values for grids of area 3. \$\endgroup\$
    – AWO
    Apr 10, 2021 at 20:42
  • 1
    \$\begingroup\$ You may want to provide a test case with at least one block of size \$w>1\$, \$h>1\$. \$\endgroup\$
    – Arnauld
    Apr 11, 2021 at 7:12
  • \$\begingroup\$ I've just generalized example 3 to include such test cases. \$\endgroup\$
    – AWO
    Apr 11, 2021 at 13:41

1 Answer 1

5
\$\begingroup\$

Haskell, 255247 242 bytes

  • -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)\$.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ 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])[[]]. \$\endgroup\$
    – xnor
    Apr 11, 2021 at 3:25
  • \$\begingroup\$ @xnor Nice, thanks! I should probably explain the code, so that you can suggest other amazing golfs ^^ \$\endgroup\$
    – Delfad0r
    Apr 11, 2021 at 10:00
  • 1
    \$\begingroup\$ sum[a!!head i|i<-u] can be shortened to sum[a!!i|i:_<-u]. \$\endgroup\$
    – ovs
    Apr 11, 2021 at 10:29
  • 1
    \$\begingroup\$ nub$(permutations(zipWith replicate b[0..]>>=id)>>=q)>>=mapM(q.sort) saves 5 more bytes. (concatMap f $ map g x == concatMap (f.g) x) \$\endgroup\$
    – ovs
    Apr 11, 2021 at 11:00
  • \$\begingroup\$ @Delfad0r Wow, impressive! I'd be very interested in reading an explanation of the code. \$\endgroup\$
    – AWO
    Apr 11, 2021 at 23: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.