Moje dzieci mają matę alfabetyczną do zabawy, coś takiego:

Po miesiącach z losowo rozmieszczonymi kafelkami maty, zmęczyłem się i umieściłem wszystkie kafelki maty pogrupowane w sekcje zgodnie z ich kolorami tła. Więc jeśli litery reprezentują kolor tła, mam matę taką:

AABBCDDDE
ABBCCCDEE
ABCCCCDDE
AACCCDDEE
AAAACCCCE
AAAAAACCC

Tak więc dla kolorów A, B, C, D i E zawsze istnieje sposób na połączenie wszystkich płytek z tym samym kolorem tła, poziomo lub pionowo, w macie. Tak nazywam matę odpowiednio pogrupowaną według kolorów . Grupy z poprzedniego przykładu możesz zobaczyć w następujących tabelach:

AA
A
A
AA
AAAA
AAAAAA

  BB
 BB
 B

    C
   CCC
  CCCC
  CCC
    CCCC
      CCC

     DDD
      D
      DD
     DD

        E
       EE
        E
       EE
        E

Ponadto dla każdego koloru istnieje tylko jedna grupa, więc nie będzie to poprawne:

ABA
ABA

Ponieważ kafelki w kolorze A nie są pogrupowane w jednej grupie. Nie byłoby to również ważne, ponieważ kafelki nie łączą się poziomo ani pionowo:

AB
BA

Wyzwanie

Biorąc pod uwagę dwuwymiarową tablicę znaków w zakresie do wydruku ASCII (nie musi być kwadratowy, o ile rozmiar obu wymiarów jest równy lub większy niż 1), sprawdź, czy tablica reprezentuje matę odpowiednio pogrupowaną według kolorów (każdy inny znak w tablicy reprezentuje inny kolor). Dane wejściowe mogą być w dowolnym rozsądnym formacie, o ile reprezentują dwuwymiarową tablicę znaków (tablica znaków 2D, tablica ciągów o tej samej długości itd.), A dane wyjściowe muszą być parą wartości prawdziwych i falsey (0 / 1, „t” / „f”, prawda / fałsz, niezależnie od tego, o ile coś jest zwracane, a zwracane wartości są spójne we wszystkich danych wejściowych).

To jest golf golfowy, więc może wygrać najkrótszy program / funkcja / metoda / lambda dla każdego języka!

Przykłady

A    truthy

AB
AB   truthy

AB
BA   falsey

ABCDE    truthy

ABCDC    falsey

**::dd22
***:d222
*:::::22    truthy

$$$%%%&&
$$%%&&&&
&&$$$%&&    falsey

AABBCDDDE
ABBCCCDEE
ABCCCCDDE
AACCCDDEE
AAAACCCCE
AAAAAACCC   truthy

AABB
ABBA
AAAA    truthy

AAAB
AAAA
AAAA    truthy

Moja mata odpowiednio pogrupowana według kolorów

(Nadal muszę naprawić te granice ...)

MATL , 16 15 bajtów

1e"G@=4&1ZI1>vzg

Dane wejściowe to tablica znaków 2D (z wierszami oddzielonymi ;). Dane wyjściowe mają miejsce, 0jeśli dane wejściowe się kwalifikują lub w 1inny sposób.

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie

Kod zasadniczo sprawdza, czy każdy znak na wejściu ma tylko jeden podłączony komponent, biorąc pod uwagę łączność 4 (to znaczy bez przekątnych).

Powtarzane znaki są przetwarzane wielokrotnie (co jest bardziej golfowe niż deduplikacja).

1e       % Implicit input. Reshape into a row vector of chars
"        % For each char
  G      %   Push input again
  @      %   Push current char
  =      %   Equal (element-wise)? Gives a matrix of zeros and ones, where one
         %   represents the presence of the current char
  4      %   Push 4. This will indicate 4-connectivity
  &1ZI   %   Matrix with labels of connected componnents. Inputs are a number (4)
         %   to indicate connectivity, and a binary matrix. The output is a matrix
         %   the same size as the input where each connected componnent of ones
         %   in the input is replaced by a different integer starting at 1
  1>     %   Greater than 1 (element-wise)? The result is a matrix. If the result 
         %   is true for some entry the input doesn't qualify
  v      %   Concatenate vertically with results from previous iterations
  z      %   Number of nonzero/true values
  g      %   Logical. Converts nonzero to true
         % Implicit end. Implicit display. False / true are displayed as 0 / 1

Befunge-93, 317 bajtów

Edycja: Naprawiono dla właściwej liczby bajtów. Można również zagrać w golfa dalej

93+:10pv  +93p01+1g01_  [email protected]<
gp00g1+>00p~1+:93+`!#^_1-00g10
50p93+:vv_v#!:gg03:p02:<>40p#
!`g01: <>\ 1+:vvp05:+<@^p03_^#
v93$_v# !- g00<4v04g<^1<vp06:<
>+\!\>\ 3v> 40v0>g-v^<.g>:70vp
07_v#:<^ >#+0# g#\<  10\v4gg<^
!#v _$^  g03p <\ v1_#:^5>0g  -
   <    ^ g02p1< >-:#^_^#:g05
-1<   ^p\g06\0\+1:\g06\-1:\g06:\+1g06:g07

Drukuje 1 jako prawdę, 0 jako falsey

Wypróbuj online

Oto wizualizacja ścieżki kursora

Uwaga: dotyczy starej wersji

Jak to działa

Oto szybki i brudny pseudokod

a = 2Darray() # from 12,12 down and to the right
arrayLocation = 12
x = arrayLocation #stored at 0,0
y = arrayLocation #stored at 1,0
i = input()       #stored in the stack
while (i != 0):
    if (i == 10):
        y++
        x = init
    else
        a[x][y] = i
        x++
    i = input

new.x = init    #stored at 2,0
new.y = init    #stored at 3,0

currentChar = 0    #stored at 4,0
chars = array()    #stored at 1,1 onwards
charnum = 0        #stored 5,0
ToCheck = array()  #stored in the stack

current.x = null   #stored at 6,0
current.y = null   #stored at 7,0

while (new.y < y):
    if (a[new] != 0)
        currentChar = a[new]
        toCheck[] = new
        while (toCheck)
            current = toCheck.pop()
            if (a[current] == currentChar)
                toCheck.append(adjacent(current))
                a[current] = 0
        foreach (chars as char)
            if (char == currentChar)
                return 0
        charNum++
        chars[charNum] = char
    new.x++
    if (new.x > x)
        new.x = init
        new.y++

return 1

Zasadniczo po zapisaniu danych wejściowych przechodzi przez całość, sprawdzając każdą przestrzeń. Kiedy znajdzie spację z postacią, dodaje współrzędne do stosu. Następnie sprawdza rekurencyjnie otaczające go spacje, ustawiając każdą spację na 0. Po wyczerpaniu sekcji tej postaci sprawdza, czy ta postać ma już sekcję. Jeśli tak, zwróć 0. Jeśli nie, dodaj go do tablicy znaków. Po przejściu przez całą siatkę bez duplikatów zwraca 1.

Dla osób zaznajomionych z Befunge, oto rozłożona wersja kodu

96+:10p    v    +69p01+1g01_v
`+96:+1~p00<+1g00pg01g00-1_^#
v                           <
>40p50p96+:v                ^
v    @.1<  >
>:10g `#^_30p:20p:30gg:#v_$>1+:00g-!#v_0   >30g+
v                       <  ^         >$96+1^
>40p30gv                   ^
       >:!#v_70p:60p:70gg40 g-!#v_$>
           v               ^     > ^
1:\g06\+1:g 07\g07\-1:\g07\ +1: <^p\g06\0\-
v          <               ^
>50gv   >5\g1+:50p40g\1p20g^
    >:!#^_:1g40g-!#v_1-
                   >0.@

J, 66 bajtów

c=.1=+/@,+.]-:]*[:*@+/((,|."1)0,.1 _1)&(|.!.0)
[:*/[:c"2[="_ 0~.@,

cdefiniuje czasownik, który informuje, czy macierz zer i jedynek jest c onnected. Traktuje singletony jako szczególny przypadek prawdy. W przeciwnym razie pobierana jest liczba sąsiadów ortogonalnych każdej komórki, następnie znak tej liczby, a następnie mnoży to przez pierwotną macierz: jeśli ten produkt jest równy oryginalnej macierzy, to jest połączony.

Liczbę sąsiadów uzyskuje się poprzez przesunięcie we wszystkich 4 kierunkach, a następnie zsumowanie. Przesunięcie w 4 kierunkach uzyskuje się za pomocą „x -arg can by table” obrotu / shift|.

Wreszcie sama odpowiedź uzyskana przez utworzenie macierzy zer / jedynek dla każdego unikalnego elementu ~. elementu danych wejściowych, a następnie upewnienie się, że wszystkie te macierze są połączone. To jest czasownik w drugiej linii.

Wypróbuj online!

JavaScript (ES6), 114 bajtów

Pobiera dane wejściowe jako tablicę ciągów. Zwraca 0lub 1.

a=>(C={},F=x=>!C[c=a[y][x]]|(g=v=>(a[y+v]||[])[x]==c)(-1)|g(1)|g(0,x--)|g(0,x+=2)?a[y+=!c]?F(C[c]=c?x:0):1:0)(y=0)

Przypadki testowe

let f =

a=>(C={},F=x=>!C[c=a[y][x]]|(g=v=>(a[y+v]||[])[x]==c)(-1)|g(1)|g(0,x--)|g(0,x+=2)?a[y+=!c]?F(C[c]=c?x:0):1:0)(y=0)

console.log(f([ // 1
  "A"
]))

console.log(f([ // 1
  "AB",
  "AB"
]))

console.log(f([ // 0
  "AB",
  "BA"
]))

console.log(f([ // 1
  "ABCDE"
]))

console.log(f([ // 0
  "ABCDC"
]))

console.log(f([ // 1
  "**::dd22",
  "***:d222",
  "*:::::22"
]))

console.log(f([ // 0
  "$$$%%%&&",
  "$$%%&&&&",
  "&&$$$%&&"
]))

console.log(f([ // 1
  "AABBCDDDE",
  "ABBCCCDEE",
  "ABCCCCDDE",
  "AACCCDDEE",
  "AAAACCCCE",
  "AAAAAACCC"
]))

console.log(f([ // 1
  "AABB",
  "ABBA",
  "AAAA"
]))

console.log(f([ // 1
  "AAAB",
  "AAAA",
  "AAAA"
]))

Sformatowane i skomentowane

a => (                            // given an array of strings a
  C = {},                         // C = object holding encountered characters
  F = x =>                        // F = recursive function taking x:
    !C[c = a[y][x]]               //   c = current character; is it a new one?
    | (g = v =>                   //   g = helper function taking v
        (a[y + v] || [])[x] == c  //       and testing whether a[y + v][x] == c
      )(-1)                       //   test a[y - 1][x]
    | g(1)                        //   test a[y + 1][x]
    | g(0, x--)                   //   test a[y][x - 1]
    | g(0, x += 2) ?              //   test a[y][x + 1]; if at least one test passes:
      a[y += !c] ?                //     increment y if c is undefined; if a[y] exists:
        F(C[c] = c ? x : 0)       //       update C, update x and do a recursive call
      :                           //     else:
        1                         //       all characters have been processed -> success
    :                             //   else:
      0                           //     invalid character detected -> failure
)(y = 0)                          // initial call to F, starting with x = y = 0

Wolfram Language (Mathematica) , 96 bajtów

And@@(ConnectedGraphQ@Subgraph[GridGraph@Dimensions[t],Tr/@Position[c,#]]&/@(c=Join@@(t=#)))&

Wypróbuj online!

Pobiera dane wejściowe jako listę znaków 2D: na przykład {{"A","B"},{"C","D"}} .

Znak jest\[Transpose] .

Jak to działa

Dla każdego znaku cw wejściu, bierze Subgraphz GridGraphtego samego Dimensionsjako wejście co odpowiada każdy Position, w którym cwystępuje, i sprawdza, czy jest to ConnectedGraphQ.

Python 2 , 247 bajtów

def f(a):
 b=map(list,a.split('\n'));l=len(b[0])
 for c in set(a):i=a.find(c);g(b,i/l,i%l,c)
 print all(set(l)<={0}for l in b)
def g(a,i,j,c):
 if len(a)>i>-1<j<len(a[0])and a[i][j]==c:
	for x,y in(0,1),(0,-1),(1,0),(-1,0):g(a,i+x,j+y,c);a[i][j]=0

Wypróbuj online!

JavaScript (ES6), 181 bajtów

(d,o={})=>{f=(i,j,c,l=d[i])=>{if(c&&l&&l[j]==c){l[j]='';f(i-1,j,c);f(i+1,j,c);f(i,j-1,c);f(i,j+1,c);o[c]=1}};d.map((e,i)=>e.map((c,j)=>o[c]||f(i,j,c)));return!d.some(e=>e.join(''))}

Za każdym razem, gdy zostanie znaleziona nowa płytka koloru, wypełnij połączone pustymi ciągami. Jeśli mata jest odpowiednio pogrupowana według kolorów, wszystkie płytki powinny być wypełnione pustymi sznurkami.

Kod testowy

const t =
(d,o={})=>{f=(i,j,c,l=d[i])=>{if(c&&l&&l[j]==c){l[j]='';f(i-1,j,c);f(i+1,j,c);f(i,j-1,c);f(i,j+1,c);o[c]=1}};d.map((e,i)=>e.map((c,j)=>o[c]||f(i,j,c)));return!d.some(e=>e.join(''))}
;

const mat = s=>s.split('\n').filter(l=>l).map(l=>l.split(''));
console.log('true?', t(mat(`
A
`)));
console.log('true?', t(mat(`
AB
AB
`)));
console.log('false?', t(mat(`
AB
BA
`)));
console.log('true?', t(mat(`
ABCDE
`)));
console.log('false?', t(mat(`
ABCDC
`)));
console.log('true?', t(mat(`
**::dd22
***:d222
*:::::22
`)));
console.log('false?', t(mat(`
$$$%%%&&
$$%%&&&&
&&$$$%&&
`)));
console.log('true?', t(mat(`
AABBCDDDE
ABBCCCDEE
ABCCCCDDE
AACCCDDEE
AAAACCCCE
AAAAAACCC
`)));
console.log('true?', t(mat(`
AABB
ABBA
AAAA
`)));
console.log('true?', t(mat(`
AAAB
AAAA
AAAA
`)));