But, Is It Art?

Question

But Is It Art? is an esolang created by ais523, where one step is break the program into orthogonally connected "tiles":

A BBBB
A B  B
AA CC
A CC

Each separate letter shows a different tile. Interestingly, programs in But Is It Art? only rely on the orientations of the tiles themselves, not their placement. This means that the above program is functionally equivalent to

 CC    A
CC     A
  BBBB AA
  B  B A

But this isn't equivalent to

BBB  A
B B AA
 CC  A
  CC A

Or to

DDD A
DDD AA
 CC ABBBB
CC  AB  B

---

You are to take two binary rectangular matrices, \$A\$ and \$B\$. Each matrix will have zero or more "tiles" consisting of 1s that are orthogonally connected to zero or more other 1s. You should then output 2 distinctive consistent values that indicate whether the tiles in \$A\$ and \$B\$ are equivalent per But Is It Art?'s definition of equivalent grids.

For example,

A =         B =
0000111000  11000011
0110010010  10011100
0100011110  00101001
1011000001  10101111
1000000000

Are equivalent. If you can't see it, try replacing the 1s with letters, similar to above, to form groups of differently lettered tiles:

A =         B =
0000AAA000  BB0000DD
0BB00A00A0  B00AAA00
0B000AAAA0  00C0A00A
C0DD00000E  E0C0AAAA
C000000000

You can assume that the matrices will always be rectangular and will only ever contain 1 and 0. They will never be empty, but are not guaranteed to contain a 1, or to be the same dimensions.

You may take these matrices as newline separated strings, with a non-digit, non-newline separator between them; 2D nested arrays; a string representation of a matrix; or any reasonable representation of a binary matrix. You may take input as 2 lists of integers converted from binary, representing the rows (so the example A above would be [56, 402, 286, 705, 512])

This is code-golf, so the shortest code in bytes wins

Test cases

A	B	result
1101110 1010010 0101110 1100000 1010100 0010101 1000101 1001110 0000110 1101011	1111100101 0111000111 0011111101 1010000010 1101010111 0111001010 1000111100 1100001010 1101001000	false
0110111 0011010 0101101 1111010 0101001 0000011 0100111 0000010 1101011	110000101 000000000 011011101 101101011 010110111 111101010 010100011	true
11111 01100 00100 10101 10010 01101 10010 10001 00110	11111011011 01100000100 10101010010 10101001001	true
010010 011111 110001 010001 010111 101101 110001 111111	000000 000000 000000 000000 000000 000000 000000 000000	false
10 01	1 0 1	true
1111111110 0111111101 1000010000 0010001110 0110011011 0100100010 0100011001	1111111110 0111111101 1000010000 0010001110 0110011011 0100100010 0100011001	true
1000 0010 0110	1000 1010 0001	false

Answer 1

J, 80 bytes

-:&(1/:~@}.(#:i.)@$<@(-"1<./)/.~&(,/)[(*[:>./(0,(,-)=0 1)|.!.0])^:_[*i.@$)&(0,])

Try it online!

Rather straight-forward approach.

• &(0,]) prepend a 0-line, so the first "tile" found is always the 0s
• [*i.@$ every 1 gets a unique index

0 0  0
3 4  0
0 0  8
9 0 11

• [(*[:>./(0,(,-)=0 1)|.!.0])^:_ shift the board into the 4 directions, and reduce to the highest index. So each group tile will have the same index, e.g.:

0 0  0
4 4  0
0 0 11
9 0 11

• (#:i.)@$ the coordinates of all the points 0 0, 0 1, 0 2,. 1 0, …
• …/.~&(,/) flatten both lists and group the coordinates by the indices
• <@(-"1<./) normalize each group to 0 0:
• 1/:~@}. drop the first group (the 0s) and sort the rest
• -:& are the results for both inputs equal?

Answer 2

MATL, 44 43 42 39 bytes

,i4&1ZIXKXz!"K@=&fJ*+!t1)-]N@-$XhoXS]X=

Inputs: two matrices (numerical 2D arrays), using ; as row seperator.

Output: 0 for falsy, 1 for truthy.

Try it online! Or verify all test cases.

How it works

,           % Do twice
  i         %   Input: matrix
  4&1ZI     %   Label connected components formed by the value 1, using 4-connectivity.
            %   In the n-th component, 1 is replaced n
  XK        %   Copy this label matrix into clipboard K
  Xz!       %   Nonzeros as a row vector. Gives a vector containing the values 1, 2,
            %   ..., N, where N is the number of connected components and each value
            %   is repeated as many times as the size of that component
  "         %   For each n in that vector. Because of the above mentioned repetitions,
            %   several iterations will give the same result. This is inefficient but
            %   harmless
    K       %     Push label matrix
    @=&f    %     Push row and column indices of occurrences of n, as column vectors
    J*+!    %     Multiply by imaginary unit, add, transpose: combines the two column
            %     vectors into a complex row vector which describes the connected
            %     component with label n
    t1)-    %     Subtract first entry from the vector. This has the effect of
            %     normalizing the *position* of each connected component
  ]         %   End
  N         %   Push current number of elements in the stack
  @-        %   Subtract 0 in the first iteration, or 1 in the second. The result is
            %   the number of components of the latest input (in the second iteration
            %   the bottom of the stack contains a result from the previous input)
  $Xh       %   Take that many elements from the stack and combine them into a cell
            %   array. This cell array contains all row vectors of the components of
            %   the latest input. Each component is repeated as many times as the
            %   size of that component
  o         %   Convert into a matrix, right-padding with zeros if needed
  XS        %   Sort rows (atomically). This has the effect of normalizing the
            %   *order* of the components
]           % End
X=          % Are the two result matrices equal? Implicit display

Answer 3

J, ⁴¹ 40 bytes

-:&([:/:~]-/~@#~&~.[:+./ .*^:_~1>:|@-/~)

Try it online!

^{-1 thanks to xash}

This J approach was different enough that I thought it deserved its own answer.

We take input as lists of complex numbers representing the coordinates of the ones.

the idea

1. Create an adjacency matrix of the points, using "distance <= 1" as the criterion for "adjacent".
2. Matrix multiply by itself until a fixed point. The rows now represent the groups. Rows with the same signature of ones are items in the same group, so we take the unique of the rows.
3. Use these as masks to pick out the actual points of each group.
4. For each of these, create a "subtraction table" of every group element with every other one. This will give a unique signature for the spatial pattern of the group, which is independent of its placement within the grid.
5. Sort these tables.
6. Check if the final two results are the same.

Answer 4

Jelly, 30 bytes

+þ2ŒRBU¤ẎQfðƬṪṢ
W祀`Q1ị_Ɗ€Ṣ)E

Try it online!

Accepts input as a list of (1-indexed) coordinates (though it doesn't really matter).

-2 bytes thanks to caird coinheringaahing
-1 byte thanks to Nick Kennedy

This is one of the most fun challenges I've done in Jelly in a while. Thanks for the challenge :)

+þ2ŒRBU¤ẎQfðƬṪṢ    Helper link; given a list containing coordinates
                   ^ on the left and the list of filled coordinates
                   ^ on the right, breadth-first fill from those
                   ^ coordinates (initially accepts a singleton list
                   ^ with the starting coordinate)
+þ                 Outer product table on addition between each coordinate and
  2ŒRBU¤           (As a nilad)
  2ŒR              [-2, -1, 0, 1, 2]
     B             Binary; [[-1, 0], [-1], [0], [1], [1, 0]]
     U             Vectorizing reverse; [[0, -1], [-1], [0], [1], [0, 1]]
                   We now have the neighbors of each starting point
        Ẏ          Tighten / flatten once, since outer product table gives a 2D list
         Q         Remove duplicates
          f        Filter to only keep cells that are part of the whole grid itself
           ðƬ      Take that entire previous part and keep running it until
                   ^ the results are no longer unique (i.e. we have filled
                   ^ the whole block) (keeps intermediate values)
             Ṫ     Keep the last of these
              Ṣ    And sort it
W祀`Q1ị_Ɗ€Ṣ)E     Main Link; accepts a list of two matrices
            )      For each of the matrices
    `              With this list as the left and right arguments
   €               For each coordinate
Wç¥                Wrap the coordinate into a singleton list and call the helper
                   ^ link on that with the list of coordinates on the right
     Q             Remove any duplicates
         Ɗ€        For each shape
      1ị           Get the first coordinate
        _          Subtract each coordinate
           Ṣ        Sort it
             E     Are the two results equal?

Answer 5

JavaScript (ES10),  160  145 bytes

Saved 15 bytes thanks to @tsh

Expects two binary matrices as (a)(b). Returns a Boolean value.

a=>b=>(g=m=>m.map((r,Y)=>r.map((v,X)=>(h=(x,y,w=m[y])=>w&&w[x]?[[-1,w[x]=0,1,2].map(d=>d+h(x+d%2,y+--d%2))]:[])(X,Y))).flat(2).sort()+3)(a)==g(b)

Try it online!

Answer 6

R, 158 bytes

function(a,b,`+`=function(m,`?`=toString,x=seq(l=nrow(m))){for(i in x)x[K]=min(x[K<-as.matrix(dist(m))[i,]<=1]);?sort(by(m,x,function(d)?Map(rank,d)))})+a==+b

Try it online!

A function taking two matrices having two columns x,y with the coordinates of 1's and returning TRUE/FALSE.
The order of the coordinates must be the same in the two matrices (e.g. both sorted by column then row).

Explanation:

function(a,b){                 # matrices a and b
  G=function(m){               # define function G taking a matrix m (same format as a,b)
    x=seq(l=nrow(m))           # init x = 1...nrow of m
    for(i in x){               # for i in 1...nrow of m
      D=as.matrix(dist(m))[i,] #  compute D=euclidean distance of row i of m from all the other rows
      x[D<=1]=min(x[D<=1])     #  replace all vals of x where D<=1 with the min value of x where D<=1
    }                          # (now x contains an equal value for each group of connected tiles)
    B=by(m,x,function(d){      # for each group of connected tiles d (a sub-matrix of m)
      R=Map(rank,d))           #  compute the rank of each vector of coordinates x and y
      toString(R)              #  concat the result into one string
    }                          # (now B = list of string for each group of tiles)
    toString(sort(B))          # sort B and concat into one string
  }                            #
  G(a)==G(b)                   # if G(a) == G(b) then they have the same connected tiles pattern
}                              #

Note:

we use function() keyword 3 times, with the new syntax \() of R 4.1.0+ we can save 21 bytes, but unfortunately is not on TIO (yet).

Answer 7

Charcoal, 151 120 bytes

Ｆ²«≔⟦⟧θＷＳ«≔⊕Ｌκη≔⁺θＩ⪪⁺κ0¹θ»Ｆη⊞θ⁰≔⟦⟧ζＷΣθ«≔⟦⌕θ¹⟧εＦ嫧≔θλ⁰Ｆ⁺λ⟦η¹±¹±η⟧¿§θμ⊞εμ»⊞ζＥε⟦⁻﹪λη﹪⌊εη÷⁻λ⌊εη⟧»≔⟦⟧θＷ⁻ζθＦ№ζ⌊κ⊞θ⌊κ⊞υθ»⁼⊟υ⊟υ

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for equivalent, nothing if not. Explanation:

Ｆ²«

Process two matrices.

≔⟦⟧θＷＳ«

Start reading the matrix into a flat array.

≔⊕Ｌκη

Keep track of the width of the matrix, including a safety margin.

≔⁺θＩ⪪⁺κ0¹θ

Append the current row to the array, including a safety margin.

»Ｆη⊞θ⁰

Append a safety margin to the bottom of the array.

≔⟦⟧ζ

Start collecting the tiles.

ＷΣθ«

Repeat until all tiles have been found.

≔⟦⌕θ¹⟧εＦε«

Start a breadth-first search for the tile that includes the top leftmost 1.

§≔θλ⁰

Mark this cell has having been collected.

Ｆ⁺λ⟦η¹±¹±η⟧

Check all orthogonally adjacent cells.

¿§θμ⊞εμ

If this cell is a 1 then collect this cell.

»⊞ζＥε⟦⁻﹪λη﹪⌊εη÷⁻λ⌊εη⟧

Convert the position of all of the elements of this tile back to coordinates, then subtract the coordinates of the first element of the tile, and save the result to the list of normalised tiles. (Note that the subtraction is consistently off by one for cells to the left of the first cell, but because it's consistent, it won't affect the comparison between tiles.)

»≔⟦⟧θＷ⁻ζθＦ№ζ⌊κ⊞θ⌊κ

Sort the list of normalised tiles.

⊞υθ

Save the sorted list.

»⁼⊟υ⊟υ

Compare the two lists of normalised tiles.