18
\$\begingroup\$

Challenge

Given a matrix of digits (0-9), find the smallest (in terms of area) rectangular matrix of digits where one or more copies of itself, possibly rotated, can tile the original matrix. Reflection is not allowed (think of a collection of tiles on a wall or floor).

Input can be taken in any reasonable ways to represent a matrix of integers or characters. Output format should be consistent with the input, but output in any orientation (out of four possible rotations) is allowed.

If there are multiple possible tiles of same area, you may output one or all of them. It is guaranteed to be solvable for any possible input, since the entire input matrix is always an option if no smaller tiles can cover it.

Standard rules apply. The shortest code in bytes wins.

Test cases

Input:
0 1 2 3 4
5 6 7 8 9
0 1 2 3 4
5 6 7 8 9
0 1 2 3 4
5 6 7 8 9
Output:
0 1 2 3 4
5 6 7 8 9
------------------
Input:
1 1 1
1 1 1
1 1 1
Output:
1
------------------
Input:
1 2 3
4 5 6
7 8 9
Output:
1 2 3
4 5 6
7 8 9
------------------
Input:
1 2 3 4 1
4 5 6 5 2
6 5 4 6 3
3 2 1 3 6
1 2 3 2 5
4 5 6 1 4
Output:
1 2 3
4 5 6
------------------
Input:
0 0 0 0
0 1 0 1
0 0 0 0
0 0 0 0
1 0 1 0
0 0 0 0
Valid Output 1:
0 0 0 0 1 0
Valid Output 2:
0 1 0
0 0 0
Invalid Output (because it is an L-shape, not a rectangular matrix):
0 1 0 0 0
0
------------------
Input: (a hard case, suggested by Arnauld)
1 2 1 2 1 1
1 1 2 1 2 2
2 1 1 2 1 2
1 2 2 1 2 1
2 1 2 1 2 2
Output:
1 2
\$\endgroup\$
6
  • \$\begingroup\$ Suggested test case. My initial version was failing on that one because of a too weak tile insertion test. \$\endgroup\$
    – Arnauld
    Commented Jul 1, 2020 at 17:23
  • \$\begingroup\$ @Arnauld Thanks, added. It indeed looks hard. \$\endgroup\$
    – Bubbler
    Commented Jul 1, 2020 at 23:24
  • \$\begingroup\$ Are rotations of the tile allowed? \$\endgroup\$
    – user9207
    Commented Jul 2, 2020 at 6:33
  • 1
    \$\begingroup\$ @Anush "rectangular matrix of digits where one or more copies of itself, possibly rotated, can tile the original matrix..." and "output in any orientation (out of four possible rotations) is allowed." \$\endgroup\$
    – Bubbler
    Commented Jul 2, 2020 at 7:00
  • \$\begingroup\$ Are non-deterministic programs allowed? \$\endgroup\$ Commented Jul 3, 2020 at 8:36

4 Answers 4

5
\$\begingroup\$

JavaScript (ES6),  354 352 345  342 bytes

I/O: matrix of integers.

This is quite long but pretty fast -- at least with those test cases.

m=>m[b=P='map']((r,h)=>r[P]((_,w)=>(M=m.slice(~h)[P](r=>r.slice(~w)),a=~w*~h,g=(x,y,F)=>a>b|q.some((r,Y)=>r.some((v,X)=>~v?v^m[Y][X]:![x=X,y=Y]))?0:1/y?[...P+0][P](z=>(F=k=>!M[P]((r,Y)=>r[P]((v,X)=>k^1?q[y-Y][x-X]=v|k:(z|=~(q[y-X]||0)[x-Y],T[X]=T[X]||[])[Y]=v),T=[]))(1)&T.reverse(M=T)|z||g(F())|F(-1)):(o=M,b=a))(q=m[P](r=>r[P](_=>-1)))))&&o

Try it online!

How?

Whatever the tiling is, it is guaranteed that each corner of the matrix is also a corner of the tile that we're looking for. The two outer map() loops extract each possible tile \$M\$ from the bottom-right side of the input matrix \$m\$ and compute its area \$a\$.

m.map((r, h) =>           // for each row r[] at position h in m[]:
  r.map((_, w) =>         //   for each value at position w in r[]:
    (                     //
      M =                 //     build M[]:
        m.slice(~h)       //       keep the last h + 1 rows of m[]
        .map(r =>         //       for each of them:
          r.slice(~w)     //         keep the last w + 1 columns
        ),                //
      a = ~w * ~h,        //     area = (w + 1) * (h + 1)
      ...                 //     attempt to do a tiling with M
    )                     //
  )                       //   end of map()
)                         // end of map()

We build a matrix \$q\$ with the same dimensions as \$m\$, initially filled with \$-1\$.

q = m.map(r => r.map(_ => -1))

At each iteration of the recursive function \$g\$, we look for the position \$(x,y)\$ of the last cell in \$q\$ still set to \$-1\$, going from left to right and from top to bottom.

By definition, this cell has either a cell already set or a border on its right, and ditto below it. So it must be the bottom-right corner of a new tile, such as the cell marked with an 'x' below:

matrix

Simultaneously, we test whether there's a cell in \$q\$ whose value is not \$-1\$ and is different from the value in \$m\$ at the same position. If such a tile is found, we abort the recursion.

q.some((r, Y) =>          // for each row r[] at position Y in q[]:
  r.some((v, X) =>        //   for each value v at position X in r[]:
    ~v ?                  //     if v is not equal to -1:
      v ^ m[Y][X]         //       abort if v is not equal to M[Y][X]
    :                     //     else:
      ![x = X, y = Y]     //       set (x, y) = (X, Y)
  )                       //   end of some()
)                         // end of some()

If all cells of \$q\$ are matching the cells of \$m\$ and the area of \$M\$ is less than (or equal to) the best area found so far, we update the output \$o\$ to \$M\$.

Otherwise, we invoke the following code 4 times:

F(1) & T.reverse(M = T) | z || g(F()) | F(-1)

The behavior of the helper function \$F\$ depends on the parameter \$k\$:

  • If \$k=1\$, it computes the transpose \$T\$ of \$M\$ and checks whether all cells in \$q\$ between \$(x-w,y-h)\$ and \$(x,y)\$ are set to \$-1\$. The result of this test is saved in \$z\$.
  • If \$k\$ is undefined, it copies the content of \$M\$ to \$q\$ at \$(x-w,y-h)\$.
  • If \$k=-1\$, it cancels the previous operation by restoring all updated values to \$-1\$.

It is defined as follows:

F = k =>                  // k = parameter
  !M.map((r, Y) =>        // for each row r[] at position Y in M[]:
    r.map((v, X) =>       //   for each value v at position X in r[]:
      k ^ 1 ?             //     if k is not equal to 1:
        q[y - Y][x - X] = //       set q[y - Y][x - X]
          v | k           //       to v if k is undefined, or -1 if k = -1
      :                   //     else:
        ( z |=            //       update z:
            ~( q[y - X]   //         read q at (x - Y, y - X)
              || 0        //
            )[x - Y],     //         set z if it's not equal to -1
          T[X] =          //       compute T by writing v at the
            T[X] || []    //       relevant position
        )[Y] = v          //
    ),                    //   end of inner map()
    T = []                //   initialize T to an empty array
  )                       // end of outer map()

Therefore, the code block mentioned above can be interpreted as follows:

F(1)                      // compute the transpose T[] of M[] and test whether
&                         // M[] can be copied at (x-w, y-h) in q[]
T.reverse(M = T)          // reverse T[] and assign it to M[], which means
|                         // that M[] has been rotated 90° counterclockwise
z ||                      // if z = 0:
  g(F()) |                //   copy M[] to q[] and do a recursive call
  F(-1)                   //   restore q[] to its previous state
\$\endgroup\$
4
\$\begingroup\$

J, 195 bytes

A bit long, but blazing fast! There should be some micro-optimizations still left, but I believe there could be an overall better strategy, maybe one without boxes.

((]>@{.@\:[:>./@(*i.@#)[:(#*0*/@,@:=])&>]([:(~.@#~0,@:=(_&e.&,+0+/@,@:>])"2)[:,/|:@|.^:(<4)@[(-~%2*/@,@:>[+&*-~)/@,:"2/(|.~*{.@#&(,/)(#:i.)@$)"2@])&.>^:(<_)<@,:@[)[:(/:*/@:$&>)[:,/<@|:\@|:\)&.:>:

Try it online!

How it works

&.:>:

Add 1 to the matrix, so we can use 0 as a special value.

[:,/<@|:\@|:\

Get all possible tiles that contain the upper left digit.

[:(/:*/@:$&>)

Sort them according to their dimension.

](…)&.>^:(<_)<@,:@[

Use the initial matrix as seed, and execute – with the possible tiles on the left side – until the result does not change, while storing the results:

(|.~*{.@#&(,/)(#:i.)@$)"2@]

Shift the matrices so the first non-zero digit is in the upper left.

|:@|.^:(<4)@[

On the left side, rotate all the tiles.

(-~%2*/@,@:>[+&*-~)/@,:"2/

For each tile and each matrix, pad the tile and matrix to the same size (/@,:"2). The final result will be the subtraction, but we'll do some checks here by setting faulty results to infinity. With this we later don't have to keep track which tile produced which result. We add the signum of the tile and the matrix, then everything should be 1 (or 0, if the rotated tile stuck out and we added some 0 with padding. But it these cases, as every tile is >0, we'll have some negative numbers there.) We divide the subtraction by this check and it's either the original number or infinity.

(_&e.&,+0+/@,@:>])"2

We check if there is infinity in a matrix or a value below 0.

[:(~.@#~0,@:=(…)

And filter these out. The ~. is not necessary, but it reduces duplicates and speeds things quite a lot in the 1 1 1,1 1 1,1 1 1 cases.

[:(#*0*/@,@:=])&>

After the function's result does not change anymore, we have a matrix where each column represents a tile, and each row contains the possible placements for N tiles. We're interested in placements that result in a matrix filled with 0, so we check for them. We now have something like

0 0 0 0 0 0 0 0 0  0 tiles
0 0 0 0 0 0 0 0 1  1 tiles (the right-most tile is the whole matrix)
0 0 1 0 0 0 1 0 0  2 tiles

[:>./@(*i.@#)

We multiple each row with its index and reduce them, so we get for example 0 0 2 0 0 0 2 0 1.

 >@{.@\:

Using this as an index we sort the tiles, take the first one, unpack it and with the decrement we have the final tile.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I never thought writing a single tacit function in J that long. Great job! \$\endgroup\$
    – Bubbler
    Commented Jul 3, 2020 at 2:34
2
\$\begingroup\$

APL (Dyalog Unicode), 189 173 bytes

{{A[⍵]⍴⍨⊃⌽⍵}{{⊃⍵[⊃⍋⍴¨⍵]},↑⍵[⍸(~0∊∊)¨⍵]}{⊃((×/⍵)÷⍨⍴,A){⍺≤1:⊂¨↓⍵⋄R←⍵∇⍨⍺-1⋄,{0<≢R:⍵[⍸{((⊢≡∪)⊃,/⍵)∧((1≡⊃∘⍴∘∪)¨↓{A[⍵]}¨⍵)}¨⍵]⋄⍬}R∘.(,∘⊂)↓⍵}⊃⍪/{(,⍳1-⍵-⍴A)∘.+,¯1+⍳⍵}¨⍵(⌽⍵)}¨,⍳⍴A←⍵}

Try it online!

Slow when there are few distinct values in the grid (can't eliminate possibilities quickly).

Enumerates all possible rectangles (not many), then tries adding one at a time, checking for overlap and equal elements.

Explanation

⍳⍴A←⍵    ⍝ Set A to be the given matrix, and generate all dimensions of smaller rectangles
¨,       ⍝ For each smaller dimension (e.g. 5 4):
¨⍵(⌽⍵)     ⍝ Apply the following for both the dimension and its transpose:
  {(,⍳1-⍵-⍴A)∘.+,¯1+⍳⍵}  ⍝ Get all possible vectors of the indices of each cell in each possible translated submatrix
  
  ((×/⍵)÷⍨⍴,A)     ⍝ The number of these matrices needed to get the right area to tile the grid
  {⍺≤1:...∇⍺-1⋄⍬}  ⍝ Repeat that many times, starting with ⍬ (empty vector):
    R←⍵∇⍨⍺-1       ⍝ Take R to be the result of the previous step
    R∘.(,∘⊂)↓⍵}⊃⍪/ ⍝ Add to R all possible existing submatrix sequences
    ⍵[⍸...]        ⍝ Filter for those that:
     ((⊢≡∪)⊃,/⍵)   ⍝ Have no overlapping tiles and
     ((1≡⊃∘⍴∘∪)¨↓{A[⍵]}¨⍵)  ⍝ Consist of the same sequence of entries
  {⊃⍵[⊃⍋⍴¨⍵]}  ⍝ Get the first possibility, sorted by area
{A[⍵]⍴⍨⊃⌽⍵}  ⍝ Get the corresponding elements from the original matrix, and correct the shape
\$\endgroup\$
1
  • \$\begingroup\$ If you haven't already, check out The APL Orchard, a chat room dedicated for APL-family languages. \$\endgroup\$
    – Bubbler
    Commented Jul 1, 2020 at 23:28
0
\$\begingroup\$

Python, 253 bytes

from math import*
R=range
def C(b):
 d={}
 for i in b:
  for j in i:d[j]=d.get(j,0)+1
 return d
def f(b):
 d=C(b)
 K={i:int(d[i]/gcd(*d.values()))for i in d}
 for x in R(len(b)):
  for y in R(len(b[0])):
   if C(T:=[j[:y+1]for j in b[:x+1]])==K:return T

Attempt This Online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.