| Bytes | Lang | Time | Link |
|---|---|---|---|
| 018 | Jelly | 240902T181156Z | Unrelate |
| 476 | Python3 | 240829T174034Z | Ajax1234 |
| 158 | R | 210617T114752Z | digEmAll |
| 030 | Jelly | 210611T004546Z | hyper-ne |
| 120 | Charcoal | 210613T170344Z | Neil |
| 4140 | J | 210611T064922Z | Jonah |
| 145 | JavaScript ES10 | 210611T000031Z | Arnauld |
| 039 | MATL | 210610T230807Z | Luis Men |
| 080 | J | 210610T224914Z | xash |
Jelly, 35 34 24 26 24 20 19 18 bytes
ạSỊɗþæ*LT€ị¹_Ɲ€Ṣ)E
-1 and inspiration for another -1 thanks to emanresu A
Input as a list of lists of pairs of coordinates, sorted.
)E Test the coordinate lists for equality under:
þ Table
ạ absolute difference in each coordinate
SỊɗ sums to <= 1?
ạSỊɗþ This creates a refreshingly vanilla adjacency matrix.
æ*L Matrix power to the number of coordinates.
T€ Convert each row to truthy indices
ị¹ and index those back into the list of coordinates.
æ*LT€ị Each row is now a (duplicate) connected tile.
€ For each row,
_Ɲ take the coordinate-wise differences of adjacent pairs.
Ṣ Sort the rows.
A little embarrassed it took me on the order of 8 hours to come up with this, but at least I got this edit history out of it.
Python3, 476 bytes
lambda a,b:sorted(G(a))==sorted(G(b))
T=lambda x,y:[[j*i,k*I]for j,k in[[x,y],[y,x]]for i in[-1,1]for I in[-1,1]]
E=enumerate
K=lambda d:sorted([(a-min(a for a,_ in d),b-min(b for _,b in d))for a,b in d])
def G(b):
d={(x,y):v for x,r in E(b)for y,v in E(r)if v}
q=[*d]
while q:
Q=[q.pop(0)];s=[*Q]
for x,y in Q:
for X,Y in[(1,0),(-1,0),(0,-1),(0,1)]:
if(w:=(x+X,y+Y))in q and d[w]==d[(x,y)]:s+=[w];Q+=[w];q=[*{*q}-{w}]
yield from map(K,zip(*[T(*I)for I in s]))
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
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).
Jelly, 30 bytes
+þ2ŒRBU¤ẎQfðƬṪṢ
W祀`Q1ị_Ɗ€Ṣ)E
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?
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.
J, 41 40 bytes
-:&([:/:~]-/~@#~&~.[:+./ .*^:_~1>:|@-/~)
-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
- Create an adjacency matrix of the points, using "distance <= 1" as the criterion for "adjacent".
- 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.
- Use these as masks to pick out the actual points of each group.
- 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.
- Sort these tables.
- Check if the final two results are the same.
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)
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
J, 80 bytes
-:&(1/:~@}.(#:i.)@$<@(-"1<./)/.~&(,/)[(*[:>./(0,(,-)=0 1)|.!.0])^:_[*i.@$)&(0,])
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 points0 0, 0 1, 0 2,. 1 0, ……/.~&(,/)flatten both lists and group the coordinates by the indices<@(-"1<./)normalize each group to0 0:1/:~@}.drop the first group (the 0s) and sort the rest-:&are the results for both inputs equal?