El reto

Considere la cuadrícula real de 3x3, como se muestra en el siguiente gráfico ASCII:

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

Se le da como entrada una lista de enteros de longitud 9 que representa un etiquetado de los nodos. Por ejemplo, la entrada [0,1,1,2,1,0,5,5,1]representa el siguiente etiquetado:

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

Su salida es el conjunto de enteros en la entrada que forman conjuntos de nodos conectados. Más explícitamente, la salida debe contener un número entero nde la entrada si y solo si el conjunto de nodos con etiqueta nestá conectado. En este ejemplo, una salida aceptable sería [1,2,5], ya que los dos 0s no están conectados. El conteo de bytes más bajo gana.

Reglas detalladas

• Puede elegir un orden fijo para los nodos en su lista de entrada, y debe indicarlo en su respuesta. En el orden EFBDHCAGI, el etiquetado anterior se daría como [1,0,1,2,5,1,0,5,1].
• Puede escribir un programa completo o una función. En el último caso, la salida puede ser un conjunto de enteros si su idioma los admite.
• La lista de salida puede contener duplicados, pero su longitud no debe exceder de 9.
• Las lagunas estándar no están permitidas.

Casos de prueba

Estos tienen números de un solo dígito alineados a la cuadrícula; ajústelos a su orden elegido.

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

J, 54 bytes

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

Una función que toma una lista en el orden ABCDEFGHI.

Dada una matriz de adyacencia A de una gráfica de orden n , la gráfica está conectada si y solo si todas las entradas de ( A + I ) ⁿ son distintas de cero, donde I es la matriz de identidad n × n .

Comenzamos con la matriz (fija) de adyacencia más identidad de la cuadrícula real de 3 × 3 (en el orden ABCDEFGHI), a saber:

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

. Para cada etiqueta l, seleccionamos las filas y columnas correspondientes a los nodos de la etiqueta l. Esto nos da la matriz de adyacencia más identidad del subgrafo de lnodos etiquetados. Luego usamos esta matriz para probar si el subgrafo está conectado, como se describió anteriormente.

Construimos la matriz anterior al notar que si dejamos

    0 0 0
Z = 0 0 0
    0 0 0

y

    1 1 0
O = 1 1 1
    0 1 1

, entonces la matriz se puede ver como la matriz de bloques 3 × 3

O O Z
O O O
Z O O

, que tiene el mismo patrón que O! Ose produce repitiendo el patrón 1 1 0 1en un bloque 3 × 3.

CJam, 56 67 bytes

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

Orden: CIGABFHDE.

Entrada de ejemplo:

[1 1 5 0 1 0 5 2 1]

Salida:

[1 2 5]

En primer lugar, elimina los números en las esquinas que son los mismos que los números conectados en los lados. Luego, elimina los números en los lados que son iguales a los números en los siguientes lados. Finalmente, elimina todos los números ocurridos dos o más veces y agrega el número central.

CJam, 90 bytes

¡Esto se basa en un relleno de inundación iterativo explicado aquí y se puede jugar mucho al golf!

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

Requiere la entrada en orden de me ABCDEFGHgusta:

[0 1 1 2 1 0 5 5 1]

y la salida es los nodos conectados:

[1 1 2 1 5 5 1]

Breve explicacion

• Primero, itero sobre la matriz de entrada para cada etiqueta.
• En cada iteración, realizo un relleno para descubrir nodos desconectados.
• Si el número de nodos desconectados es mayor que 1, entonces esa etiqueta se desconecta.
  • 1 porque una etiqueta también puede tener solo 1 aparición en la matriz de entrada.
• Luego, simplemente filtro las etiquetas desconectadas e imprimo la matriz.

Explicación completa a seguir

Pruébalo en línea aquí