9
\$\begingroup\$

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
Improve this question
\$\endgroup\$
0

3 Answers 3

Reset to default
4
\$\begingroup\$

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)n are nonzero, where I is the n×n identity matrix.

We start with the (fixed) adjacency-plus-identity matrix of the 3×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×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×3 block.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ This is an amazing solution! On hindsight, adjacency matrices are probably the shortest way to do this, especially with a language like J. \$\endgroup\$ Commented Dec 27, 2014 at 17:16
3
\$\begingroup\$

CJam, 56 67 bytes

q~4/~\@{a1$2<-\(+}%)_)-{_(+{\(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.

Improve this answer
\$\endgroup\$
0
2
\$\begingroup\$

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

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.