6
\$\begingroup\$

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 , 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

\$\endgroup\$
3
  • \$\begingroup\$ May I assume the coordinates given in input is sorted? \$\endgroup\$
    – tsh
    Jul 27 at 2:28
  • \$\begingroup\$ @tsh You may assume that the input will be in a consistent order of your choosing, such as sorted \$\endgroup\$ Jul 27 at 2:39
  • \$\begingroup\$ Related \$\endgroup\$ Jul 27 at 4:41
7
\$\begingroup\$

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

\$\endgroup\$
5
\$\begingroup\$

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.
\$\endgroup\$
2
  • \$\begingroup\$ I'd be interested to know why the space is necessary- it's a rare sight in J in my experience \$\endgroup\$ Jul 26 at 23:31
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Jonah
    Jul 26 at 23:34
5
\$\begingroup\$

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

Charcoal, 91 81 bytes

≔E²⊕⌈Eθ§λιηE§η¹⭆§η⁰℅¬№θ⟦λι⟧≔²ζF⊟ηFΣη«Jκι¿¬℅KK«¤℅ζ≦⊕ζ»»F…²ζ⊞υ⌕AKA℅ι⎚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:

≔E²⊕⌈Eθ§λιη

Find the size of the matrix.

E§η¹⭆§η⁰℅¬№θ⟦λι⟧

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

≔²ζ

Start tracking the next shape.

F⊟ηFΣη«

Loop through the matrix.

Jκι¿¬℅KK«

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

¤℅ζ≦⊕ζ»»

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

F…²ζ

Loop through the found shapes.

⊞υ⌕AKA℅ι

Get the flattened list of coordinates of each shape.

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

Clear the canvas and convert the coordinates back to pairs.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ I would suggest MorphologicalComponents but it needs CornerNeighbors->False and ends up being too long... otherwise it would be perfect for the task. \$\endgroup\$ Jul 27 at 14:49
  • \$\begingroup\$ @2012rcampion yep, I tried variations on that but could only get it down to 75 bytes. \$\endgroup\$
    – att
    Jul 27 at 18:22
1
\$\begingroup\$

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.

\$\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.