17
\$\begingroup\$

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 , 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
\$\endgroup\$
7
  • 2
    \$\begingroup\$ Nice use of the table for the test cases, so each matrix can be copied individually \$\endgroup\$
    – Luis Mendo
    Jun 10 at 22:18
  • 5
    \$\begingroup\$ @LuisMendo That was Adám's brilliant idea, definitely going to reuse it for later [matrix] challenges :) \$\endgroup\$ Jun 10 at 22:20
  • \$\begingroup\$ Can input be taken as lists of coordinates of the 1 positions? \$\endgroup\$
    – Jonah
    Jun 11 at 1:53
  • \$\begingroup\$ Also what a great name for a PL \$\endgroup\$
    – Jonah
    Jun 11 at 1:53
  • 1
    \$\begingroup\$ @Jonah Yeah, I think that's an acceptable method of input, so long as the indexing the coordinates use is consistent (i.e. it all uses 1 indexing or zero indexing, rather than mixing and matching) \$\endgroup\$ Jun 11 at 1:55
8
\$\begingroup\$

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?
\$\endgroup\$
8
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ 42 bytes. Now I can go to bed \$\endgroup\$
    – Luis Mendo
    Jun 10 at 23:18
  • \$\begingroup\$ <insert 44 joke here> \$\endgroup\$ Jun 10 at 23:32
6
\$\begingroup\$

J, 41 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.
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Nice! [:~. -> &~. for 40, so you'll have exactly half the bytes of my answer. :-) \$\endgroup\$
    – xash
    Jun 11 at 15:02
  • \$\begingroup\$ Ah, nice observation, thanks. \$\endgroup\$
    – Jonah
    Jun 11 at 16:55
5
\$\begingroup\$

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?
\$\endgroup\$
3
  • 2
    \$\begingroup\$ -1 byte \$\endgroup\$ Jun 11 at 0:47
  • 1
    \$\begingroup\$ -1 byte I had a very similar approach but was 1 byte longer, even with the golf I’ve just given you. \$\endgroup\$ Jun 11 at 20:06
  • \$\begingroup\$ @NickKennedy Ah, that's clever - thanks. \$\endgroup\$
    – hyper-neutrino
    Jun 11 at 20:08
4
\$\begingroup\$

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!

\$\endgroup\$
9
  • 1
    \$\begingroup\$ I have to say, I'm surprised at how short this is. I expected, from the length of the J and MATL answers, that JS would clock in around 200 ish bytes. Definitely +1 \$\endgroup\$ Jun 11 at 0:05
  • \$\begingroup\$ change q=[], v&&q.push(...) to v?[(h=...)(x,y)]:[] then flat(2) would save bytes \$\endgroup\$
    – tsh
    Jun 11 at 2:31
  • \$\begingroup\$ Move condition out [-1,0,1,2].map(d=>(m[Y=y+d%2]||0)[X=x+~-d%2]?d+h(X,Y):h,m[y][x]=0) (m[y]||0)[x]?[-1,m[y][x]=0,1,2].map(d=>d+h(x+~-d%2,y+d%2)):h would help some bytes. Also, you can save more bytes by switch to ES2021 use m[y]?.[x] replace (m[y]||0)[x] \$\endgroup\$
    – tsh
    Jun 11 at 2:37
  • \$\begingroup\$ 149: a=>b=>(g=m=>m.map((r,Y)=>r.map((v,X)=>v?[(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)):h)(X,Y)]:[])).flat(2).sort()+h)(a)==g(b) And Im not sure if this 147: 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)+3)]:[])(X,Y))).flat(2).sort()+4)(a)==g(b) works \$\endgroup\$
    – tsh
    Jun 11 at 8:07
  • \$\begingroup\$ Based on tsh's 147, 146: a=>b=>(g=m=>m.map((r,Y)=>r.map((v,X)=>(h=(x,y,w=m[y])=>w&&w[x]?[[2,3,4,5].map(d=>d+h(x+d--%2,y+d%2),w[x]=0)]:[])(X,Y))).flat(2).sort()+4)(a)==g(b) by eliminating the +3 from the equation. \$\endgroup\$
    – emanresu A
    Jun 11 at 8:48
2
\$\begingroup\$

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).

\$\endgroup\$
2
  • \$\begingroup\$ This is great. You could also similarly save 12 using pryr::f: try it (not counting the f= in the TIO link)... \$\endgroup\$ Jun 18 at 8:36
  • \$\begingroup\$ @DominicvanEssen: yep I'm aware of pryr::f, but I always prefer to stick with base R ;) \$\endgroup\$
    – digEmAll
    Jun 18 at 16:31
1
\$\begingroup\$

Charcoal, 151 120 bytes

F²«≔⟦⟧θWS«≔⊕Lκη≔⁺θI⪪⁺κ0¹θ»Fη⊞θ⁰≔⟦⟧ζWΣθ«≔⟦⌕θ¹⟧εF嫧≔θλ⁰F⁺λ⟦η¹±¹±η⟧¿§θμ⊞εμ»⊞ζEε⟦⁻﹪λη﹪⌊εη÷⁻λ⌊εη⟧»≔⟦⟧θW⁻ζθF№ζ⌊κ⊞θ⌊κ⊞υθ»⁼⊟υ⊟υ

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

F²«

Process two matrices.

≔⟦⟧θWS«

Start reading the matrix into a flat array.

≔⊕Lκη

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

≔⁺θI⪪⁺κ0¹θ

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

»Fη⊞θ⁰

Append a safety margin to the bottom of the array.

≔⟦⟧ζ

Start collecting the tiles.

WΣθ«

Repeat until all tiles have been found.

≔⟦⌕θ¹⟧εFε«

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

§≔θλ⁰

Mark this cell has having been collected.

F⁺λ⟦η¹±¹±η⟧

Check all orthogonally adjacent cells.

¿§θμ⊞εμ

If this cell is a 1 then collect this cell.

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

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.)

»≔⟦⟧θW⁻ζθF№ζ⌊κ⊞θ⌊κ

Sort the list of normalised tiles.

⊞υθ

Save the sorted list.

»⁼⊟υ⊟υ

Compare the two lists of normalised tiles.

\$\endgroup\$

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.