Wyzwanie

Rozważ siatkę króla 3x3, jak pokazano na poniższej grafice ASCII:

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

Otrzymujesz jako dane wejściowe listę liczb całkowitych o długości 9, które reprezentują etykietowanie węzłów. Na przykład dane wejściowe [0,1,1,2,1,0,5,5,1]reprezentują następujące etykietowanie:

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

Twój wynik jest zbiorem liczb całkowitych na wejściu, które tworzą połączone zestawy węzłów. Mówiąc dokładniej, wynik powinien zawierać liczbę całkowitą nz wejścia, tylko wtedy, gdy zestaw węzłów z etykietą njest podłączony. W tym przykładzie akceptowalne wyjście byłoby [1,2,5], ponieważ dwa 0s nie są połączone. Wygrywa najniższa liczba bajtów.

Szczegółowe zasady

• Możesz wybrać ustaloną kolejność dla węzłów na liście danych wejściowych, co należy podać w odpowiedzi. W zamówieniu EFBDHCAGI powyższe oznakowanie będzie podane jako [1,0,1,2,5,1,0,5,1].
• Możesz napisać pełny program lub funkcję. W tym drugim przypadku wynikiem może być zestaw liczb całkowitych, jeśli Twój język je obsługuje.
• Lista wyjściowa może zawierać duplikaty, ale jej długość nie może przekraczać 9.
• Standardowe luki są niedozwolone.

Przypadki testowe

Mają one jednocyfrowe liczby wyrównane do siatki; dostosuj je do wybranego zamówienia.

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 bajty

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

Funkcja przyjmująca listę w kolejności ABCDEFGHI.

Biorąc pod uwagę macierz przylegania A wykresu rzędu n , wykres jest łączony wtedy i tylko wtedy, gdy wszystkie wpisy ( A + I ) ⁿ są niezerowe, gdzie I jest macierzą tożsamości n × n .

Zaczynamy od (stałej) macierzy przylegania i tożsamości z siatki króla 3 × 3 (w kolejności ABCDEFGHI), a mianowicie:

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

. Dla każdej etykiety lwybieramy wiersze i kolumny odpowiadające węzłom etykiety l. To daje nam macierz przylegania plus tożsamość podgrupy loznaczonych węzłów. Następnie używamy tej macierzy do sprawdzenia, czy podgraph jest podłączony, jak opisano powyżej.

Konstruujemy powyższą macierz, zwracając uwagę, że jeśli pozwolimy

    0 0 0
Z = 0 0 0
    0 0 0

i

    1 1 0
O = 1 1 1
    0 1 1

, wówczas macierz może być postrzegana jako macierz blokowa 3 × 3

O O Z
O O O
Z O O

, który ma taki sam wzór jak O! Opowstaje przez powtórzenie wzoru 1 1 0 1w bloku 3 × 3.

CJam, 56 67 bajtów

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

Zamówienie: CIGABFHDE.

Przykładowe dane wejściowe:

[1 1 5 0 1 0 5 2 1]

Wynik:

[1 2 5]

Najpierw usuwa cyfry w rogach, które są takie same jak połączone cyfry po bokach. Następnie usuwa liczby po bokach, które są takie same jak liczby po następnych stronach. Wreszcie usuwa wszystkie liczby występujące dwa lub więcej razy i dodaje numer środkowy.

CJam, 90 bajtów

Jest to oparte na iteracyjnym Wypełnienie wyjaśnione tutaj i może być grałem dużo!

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

Wymaga wprowadzenia danych w następującej kolejności ABCDEFGH:

[0 1 1 2 1 0 5 5 1]

a dane wyjściowe to połączone węzły:

[1 1 2 1 5 5 1]

Krótkie wyjaśnienie

• Najpierw iteruję tablicę wejściową dla każdej etykiety.
• W każdej iteracji wykonuję wypełnienie zalewowe, aby znaleźć rozłączone węzły.
• Jeśli liczba rozłączonych węzłów jest większa niż 1, wówczas ta etykieta jest odłączana.
  • 1, ponieważ etykieta może mieć tylko 1 wystąpienie w tablicy wejściowej.
• Następnie po prostu odfiltrowuję odłączone etykiety i drukuję tablicę.

Pełne wyjaśnienie do naśladowania

Wypróbuj online tutaj