3x3 Connected Components

Question

The Challenge

Consider the 3x3 king grid, as shown in the following ASCII graphic:

A--B--C
|\/|\/|
|/\|/\|
D--E--F
|\/|\/|
|/\|/\|
G--H--I

You are given as input a length-9 list of integers that represent a labeling of the nodes. For example, the input [0,1,1,2,1,0,5,5,1] represents the following labeling:

0--1--1
|\/|\/|
|/\|/\|
2--1--0
|\/|\/|
|/\|/\|
5--5--1

Your output is the set of integers in the input that form connected sets of nodes. More explicitly, the output should contain an integer n from the input if and only if the set of nodes with label n is connected. In this example, an acceptable output would be [1,2,5], since the two 0s are not connected. The lowest byte count wins.

Detailed rules

• You can choose a fixed ordering for the nodes in your input list, and you should state this in your answer. In the order EFBDHCAGI, the above labeling would be given as [1,0,1,2,5,1,0,5,1].
• You can write either a full program or a function. In the latter case, the output can be a set of integers if your language supports those.
• The output list may contain duplicates, but its length must not exceed 9.
• Standard loopholes are disallowed.

Test cases

These have single-digit numbers aligned to the grid; adjust them to your chosen order.

011
210 => 1 2 5
551
010
202 => 0 2
221
110
123 => 0 2 3
221
111
111 => 1
111
111
141 => 1 4
111

Answer 1

J, 54 bytes

#~3 :'0<*/,+/ .*/^:8~y#|:y#,/,"1/({0&,:)3 3$#:13'"1@e.

A function taking a list in the order ABCDEFGHI.

Given an adjacency matrix A of a graph of order n, the graph is connected if and only if all the entries of (A + I)ⁿ are nonzero, where I is the n×ばつn identity matrix.

We start with the (fixed) adjacency-plus-identity matrix of the ×ばつ3 king grid (in the order ABCDEFGHI,) namely:

1 1 0 1 1 0 0 0 0
1 1 1 1 1 1 0 0 0
0 1 1 0 1 1 0 0 0
1 1 0 1 1 0 1 1 0
1 1 1 1 1 1 1 1 1
0 1 1 0 1 1 0 1 1
0 0 0 1 1 0 1 1 0
0 0 0 1 1 1 1 1 1
0 0 0 0 1 1 0 1 1

. For each label l, we select the rows and columns corresponding to the nodes of label l. This gives us the adjacency-plus-identity matrix of the subgraph of l-labeled nodes. We then use this matrix to test if the subgraph is connected, as described above.

We construct the above matrix by noting that if we let

 0 0 0
Z = 0 0 0
 0 0 0

and

 1 1 0
O = 1 1 1
 0 1 1

, then the matrix can be seen as the ×ばつ3 block matrix

O O Z
O O O
Z O O

, which has the same pattern as O! O is produced by repeating the pattern 1 1 0 1 in a ×ばつ3 block.

• Zgarb: This is an amazing solution! On hindsight, adjacency matrices are probably the shortest way to do this, especially with a language like J.

Answer 2

CJam, (削除) 56 (削除ここまで) 67 bytes

q~4/~\@{a12ドル<-\(+}%)_)-{_(+{\(a@-\}}A?%+:+[$_(d+1$)c\+@]zLf|2f>:+|`

Order: CIGABFHDE.

Example input:

[1 1 5 0 1 0 5 2 1]

Output:

[1 2 5]

It firstly removes numbers in the corners which are the same as connected numbers on the sides. Then it removes numbers on the sides which are the same as the numbers on the next sides. Finally it removes all numbers occurred two or more times and add the center number.

Answer 3

CJam, 90 bytes

This is based on a iterative flood fill explained here and can be golfed a lot!

q~:Q{:IQ3/S*Sca5*+:T;G,G*{:AT=1$={[WXZ5 4_~_)_)]Af+Tf=AT='#a+&,g{TA'#t:T;}*}*}%;aT\/,3<},p

Requires the input in order of ABCDEFGH like:

[0 1 1 2 1 0 5 5 1]

and output is the connected nodes:

[1 1 2 1 5 5 1]

Brief Explanation

• First, I iterate over the input array for each label.
• In each iteration, I perform floodfill to figure out disconnected nodes.
• If the number of disconnected nodes is greater than 1, then that label is disconnected.
  • 1 because a label can have just 1 occurrence in the input array too.
• Then I simply filter out disconnected labels and print the array.

Full explanation to follow

Try it online here