I've been working on a problem (full problem at the bottom) and as a result I've generated some binary matrices with a peculiar pattern. Here is the pattern for $n=29$ (the largest $n$ before my image editor craps out). A black pixel represents a $1$ and a white pizel represents a $0$.
These matrices are generated with the following method.
Given $n$ as input:
First we generate all the collection, $C$, of lists consisting of $2$ and $3$ that sum to $n$ (in dictionary order). For example if $n$ is $8$ then our collection is $[[2,2,2,2],[2,3,3],[3,2,3],[3,3,2]]$.
Or matrix $M(n)$ is then defined as
$$ M(n)_{i,j} = \begin{cases}0 & \exists x,y\in\mathbb{N}: \sum(\mathrm{take}(x)(C_i)) = \sum(\mathrm{take}(y)(C_j))\\1 & \mathrm{otherwise}\end{cases} $$
Here is some Haskell code that generates these matrices:
rowsOf (-1) = [[]]
rowsOf 0 = [[]] : rowsOf (-1)
rowsOf 1 = [] : rowsOf 0
rowsOf n
| l <- rowsOf $ n-1 = ((map (3:) $ l!!2) ++ (map (2:) $ l!!1)) : l
partialSums = init.tail.scanl(+)0
adjacencyMatrix n = do
a <- rows
pure $ do
b <- rows
pure $ if all (`notElem` partialSums a) $ partialSums b
then 1
else 0
where
rows = head $ rowsOf n
From here my question is is this a known pattern? It is rather reminiscent of the Serpinski gasket. Is there a faster way to generate these matrices other than the brute force method shown above?
Original Problem
I saw this challenge on code-golf (based on a now deleted SO question) a little while ago and I have been working on a solution to it using an transformation matrix approach.
The question is as follows:
Given a width $M$ and a height $N$, write a program that outputs how many unique ways an $M\times N$ rectangle can be filled by $2\times 1$ and $3\times 1$ tiles given these constraints.
- All tiles stay within their row (ie they are all horizontal).
- Between every two adjacent rows tiles should not be aligned, except on the two ends.
In this problem the each row and column represents a way to fill a single size $M$ row. And an element indicates whether those two rows can be places next to each other in the final project without violating rule 2. If I had such a matrix I could use it as a transition matrix and find the desired result very quickly with matrix composition.
