Group binary shapes together

Question

Consider the following binary matrix:

$$\begin{matrix} 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 1 \end{matrix}$$

The (1-indexed) co-ordinates of the \1ドル\$s here are \$(1,1), (1,3), (2,1), (3, 2), (3, 3)\$. We can also notice that there are three "shapes" of \1ドル\$s in the matrix, made of orthogonally connected \1ドル\$s:

$$\begin{matrix} \color{red}{1} & 0 & \color{cyan}{1} \\ \color{red}{1} & 0 & 0 \\ 0 & \color{blue}{1} & \color{blue}{1} \end{matrix}$$

We can then group the coordinates into those shapes: \$((1, 1), (2, 1)), ((3, 2), (3, 3)), ((1,3))\$.

Given a non-empty list of coordinates, group them into the shapes that can be found in the binary matrix represented by those coordinates. You may take the input as any reasonable format for a list of pairs, including complex numbers. You may also choose to use 0 or 1 indexing.

You may also instead choose to take the binary matrix as input, rather than the coordinates. In this case, the output should still be the groups.

The output may be any format where the groups (lists of pairs) are clearly recognisable, as are the pairs themselves. One example may be newline delimited lists of complex numbers. You may also output the groups as lists of indices (0 or 1 indexed, your choice) from the original input (so the example would be [[1,3], [4,5], [2]])

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

Test cases

^{I've used (a, b) for the output to try to show some distinction}

input ->
output
lines
[[1, 2], [2, 1], [2, 3], [3, 2]] ->
[(1, 2)]
[(2, 1)]
[(2, 3)]
[(3, 2)]
[[1, 1], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2], [3, 3]] ->
[(1, 1), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2), (3, 3)]
[[1, 1], [1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2], [3, 3]] ->
[(1, 1), (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2), (3, 3)]
[[1, 3], [1, 4], [3, 1], [3, 2], [5, 2]] ->
[(1, 3), (1, 4)]
[(3, 1), (3, 2)]
[(5, 2)]
[[1, 3], [3, 1], [3, 2], [4, 2], [5, 2], [5, 3]] ->
[(1, 3)]
[(3, 1), (3, 2), (4, 2), (5, 2), (5, 3)]
[[2, 2]] ->
[(2, 2)]
[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [2, 4], [3, 1], [4, 1], [4, 3], [4, 4], [4, 5], [5, 1], [5, 4], [5, 5], [6, 4], [6, 5]] ->
[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 4)]
[(3, 1), (4, 1), (5, 1)]
[(4, 3), (4, 4), (4, 5), (5, 4), (5, 5), (6, 4), (6, 5)]
[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [2, 1], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [4, 5], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6]] ->
[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 1), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (4, 5), (5, 1), (5, 2), (5, 3), (5, 4), (5, 5), (5, 6)]
[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [2, 5], [3, 1], [3, 4], [4, 1], [4, 2], [4, 4], [4, 5], [4, 6], [5, 1], [5, 4], [5, 5], [6, 1], [6, 4], [6, 5]] ->
[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 5)]
[(3, 1), (4, 1), (4, 2), (5, 1), (6, 1)]
[(3, 4), (4, 4), (4, 5), (4, 6), (5, 4), (5, 5), (6, 4), (6, 5)]

And this is a visualisation of the matrices themselves

• tsh: May I assume the coordinates given in input is sorted?
• caird coinheringaahing: @tsh You may assume that the input will be in a consistent order of your choosing, such as sorted
• Aaroneous Miller: Related

Answer 1

APL (Dyalog Unicode), 18 bytes

Full program. Takes input as list of complex numbers. Returns list of lists of indices into the input.

⍸ ̈↓∪∨.∧⍣≡⍨1≥|∘.-⍨⎕

Try it online!

⎕ prompt for evaluated input via stdin

∘.-⍨ differences between all pairs of indices

| absolute value

1≥ Boolean matrix indicating where no more than 1 (points have 0 distance from themselves)

∨.∧⍣≡⍨ transitive closure

∪ unique rows

↓ split into list of lists

⍸ ̈ indices where true in each

Answer 2

J, 24 bytes

</.~[:+./ .*^:_~1>:|@-/~

Try it online!

Very similar approach to Adam's APL answer, though arrived at independently. Input as complex numbers:

• |@-/~ Table of absolute differences.
• 1>: Is it elementwise less than or equal to 1? Returns a 0-1 matrix representing direct neighbors.
• [:+./ .*^:_ Do a matrix multiply replacing sum with boolean OR until a fixed point. The rows now represent connected groups.
• </.~ Use those groups to group the original input.

• caird coinheringaahing: I'd be interested to know why the space is necessary- it's a rare sight in J in my experience
• Jonah: The dot is a common way to "inflect" built in verbs... you'll notice even in this example there is /. and +.. You can think of them like accents over letters in natural language. But in the case you're asking about the dot is a conjunction joining +./ and *. The space is needed so that it won't attach to the /. in parsing.

Answer 3

Jelly, 9 bytes

ạþ`Ịæ*LṠĠ

Try it online!

How it works

ạþ`Ịæ*LṠĠ Monadic link. Input: list of coordinates in complex
ạþ` Table of absolute differences
 Ị <= 1
 æ*L Raise the matrix to the power equal to length
 Ṡ Sign (mat[i][j] == 1 if a path exists between i and j)
 Ġ Group indices by identical rows of the matrix

Answer 4

Wolfram Language (Mathematica), 61 bytes

Xor@@List/@#//.a_⊻b_/;Min@DistanceMatrix[a,b]==1:>a~Join~b&

Try it online!

Returns an Xor of coordinate lists, unless there is only one group, in which case just a single coordinate lists is returned (since Xor[something]==something). Repeatedly concatenates adjacent groups. Runtime balloons quickly.

Also 61 bytes

Thread[Sign@MatrixExp@Ramp[1.1-DistanceMatrix@#]->#]~Merge~D&

Try it online!

Returns an association with coordinate lists as its values. Same approach as several other answers: build an adjacency matrix by zeroing entries of a distance matrix that are greater than 1, take the closure, group.

---

Alternate approach with a built-in that performs most of the task: 63 bytes

ConnectedComponents@Subgraph[##&@@Table[#->#+I^i,{i,4}]&/@#,#]&

Try it online! Input a list of complex numbers. Returns a list of complex number lists. With ConnectedComponents, all that remains is building the adjacency graph.

• 2012rcampion: I would suggest MorphologicalComponents but it needs CornerNeighbors->False and ends up being too long... otherwise it would be perfect for the task.
• att: @2012rcampion yep, I tried variations on that but could only get it down to 75 bytes.

Answer 5

Charcoal, (削除) 91 (削除ここまで) 81 bytes

≔E2⊕⌈Eθ§λιηE§η1⭆§η0c/o¬Noθ⟦λι⟧≔2ζF⊟ηFΣη«Jκι¿¬c/oKK«¤c/oζ≦⊕ζ»»F...2ζ⊞υ⌕AKAc/oι⎚IEυEι⟦%λΣη÷λΣη

Try it online! Link is to verbose version of code. Output is a triple-spaced list of double-spaced list of pairs of coordinates, each on their own line. Explanation:

≔E2⊕⌈Eθ§λιη

Find the size of the matrix.

E§η1⭆§η0c/o¬Noθ⟦λι⟧

Create an area of that size on the canvas with holes at all of the points provided.

≔2ζ

Start tracking the next shape.

F⊟ηFΣη«

Loop through the matrix.

Jκι¿¬c/oKK«

If there is a hole at this position, then...

¤c/oζ≦⊕ζ»»

... fill it in and increment the shape tracker.

F...2ζ

Loop through the found shapes.

⊞υ⌕AKAc/oι

Get the flattened list of coordinates of each shape.

⎚IEυEι⟦%λΣη÷λΣη

Clear the canvas and convert the coordinates back to pairs.

Answer 6

JavaScript, 103 bytes

a=>new Set(a.map(p=>a[r=a.reduce(b=>a.filter(q=>b.some(([x,y])=>(x-=q[0])*x+(y-=q[1])*y<2)),[p])]??=r))

f=
a=>new Set(a.map(p=>a[r=a.reduce(b=>a.filter(q=>b.some(([x,y])=>(x-=q[0])*x+(y-=q[1])*y<2)),[p])]??=r))
console.log(JSON.stringify([...f([[1, 2], [2, 1], [2, 3], [3, 2]])]));
console.log(JSON.stringify([...f([[1, 1], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2], [3, 3]])]));
console.log(JSON.stringify([...f([[1, 1], [1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2], [3, 3]])]));
console.log(JSON.stringify([...f([[1, 3], [1, 4], [3, 1], [3, 2], [5, 2]])]));
console.log(JSON.stringify([...f([[1, 3], [3, 1], [3, 2], [4, 2], [5, 2], [5, 3]])]));
console.log(JSON.stringify([...f([[2, 2]])]));
console.log(JSON.stringify([...f([[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [2, 4], [3, 1], [4, 1], [4, 3], [4, 4], [4, 5], [5, 1], [5, 4], [5, 5], [6, 4], [6, 5]])]));
console.log(JSON.stringify([...f([[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [2, 1], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [4, 5], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6]])]));
console.log(JSON.stringify([...f([[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [2, 5], [3, 1], [3, 4], [4, 1], [4, 2], [4, 4], [4, 5], [4, 6], [5, 1], [5, 4], [5, 5], [6, 1], [6, 4], [6, 5]])]));

Input Array<[number, number]>. Output Set<Array<[number, number]>>.

18 bytes are used to remove duplicate groups, maybe someone may find out a better way to golf it down.

---

Python 2, 100 bytes

lambda a:set(tuple(reduce(lambda b,_:[P for P in a if any(abs(P-Q)<=1for Q in b)],a,[p]))for p in a)

Try it online!

Input List[complex]. Output Set[Tuple[complex, ...]].

Try to port above JavaScript codes to Python results 100 bytes.