У моих детей есть алфавитный коврик для игры, примерно такой:

После нескольких месяцев, когда плитки коврика были расположены в случайном порядке, я устала и разместила все плитки коврика, сгруппированные по секциям в соответствии с их фоновыми цветами. Итак, если буквы представляют цвет фона, я получил коврик, как это:

AABBCDDDE
ABBCCCDEE
ABCCCCDDE
AACCCDDEE
AAAACCCCE
AAAAAACCC

Таким образом, для цветов A, B, C, D и E всегда есть возможность соединить все плитки с одинаковым фоновым цветом в мате по горизонтали или по вертикали. Это то, что я называю матом, правильно сгруппированным по цветам . Вы можете увидеть группы для предыдущего примера в следующих таблицах:

AA
A
A
AA
AAAA
AAAAAA

  BB
 BB
 B

    C
   CCC
  CCCC
  CCC
    CCCC
      CCC

     DDD
      D
      DD
     DD

        E
       EE
        E
       EE
        E

Кроме того, существует только одна группа для каждого цвета, поэтому это будет недопустимо:

ABA
ABA

Потому что плитки цвета А не сгруппированы только в одну группу. Это также не будет действительным, потому что плитки не соединяются ни горизонтально, ни вертикально:

AB
BA

Соревнование

Учитывая двумерный массив символов в печатаемом диапазоне ASCII (не обязательно должен быть квадратным, если размер обоих измерений равен или больше 1), проверьте, представляет ли массив коврик, правильно сгруппированный по цветам (каждый отдельный символ в массиве представляет свой цвет). Входные данные могут быть в любом приемлемом формате, если они представляют собой двумерный массив символов (двумерный массив символов, массив строк одинаковой длины и т. Д.), А выходные данные должны представлять собой пару истинных и ложных значений (0 / 1, 't' / 'f', true / false, независимо от того, что что-то возвращено и возвращаемые значения согласованы для всех входных данных).

Это код-гольф, поэтому может быть самая короткая программа / функция / метод / лямбда для каждого языка!

Примеры

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

Мой коврик правильно сгруппирован по цветам

(Я все еще должен исправить эти границы ...)

MATL , 16 15 байт

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

Ввод - это двумерный массив символов (строки разделены ;). Выход0 если ввод квалифицируется или 1иным образом.

Попробуйте онлайн!Или проверьте все тестовые случаи .

объяснение

Код обязательно проверяет, имеет ли каждый символ на входе только один подключенный компонент, учитывая 4-связность (то есть отсутствие диагоналей).

Повторные символы обрабатываются многократно (что гораздо сложнее, чем дедупликация).

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 байт

Редактировать: Исправлено для правильного подсчета байтов. Также можно играть в гольф дальше

93+:10pv  +93p01+1g01_  v@.1<
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

Отпечатки 1 как правдивые, 0 как фальси

Попробуйте онлайн

Вот визуализация пути, по которому идет указатель

Примечание: это для старой версии

Как это устроено

Вот какой-то быстрый и грязный псевдокод

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

В основном, после сохранения ввода, он проходит через все это, проверяя каждый пробел. Когда он находит пробел с символом в нем, он добавляет координаты в стек. Затем он рекурсивно проверяет пробелы вокруг него для того же символа, устанавливая для каждого пробела значение 0. Когда он исчерпал раздел этого символа, он проверяет, имел ли этот символ раздел. Если это так, верните 0. Если нет, добавьте его в массив символов. Как только он прошел всю сетку без дубликатов, он возвращает 1.

Для людей, знакомых с Befunge, вот раздельная версия кода

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 байт

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

cопределяет глагол , который говорит вам , если матрица из единиц и нулей с onnected. Он рассматривает одиночные как особый случай истины. В противном случае он берет ортогональный счетчик соседей каждой ячейки, затем знак этого счетчика, а затем умножает его на исходную матрицу: если это произведение равно исходной матрице, то оно связно.

Подсчет соседей достигается путем сдвига во всех 4 направлениях, а затем суммирования. Сдвиг в 4 направлениях достигается с помощью функции « x-arg by a table» rotate / shift|.

Наконец, сам ответ достигается путем создания матрицы единиц / нулей для каждого уникального ~. элемента входных данных, а затем обеспечения связи всех этих матриц. Это глагол во второй строке.

Попробуйте онлайн!

JavaScript (ES6), 114 байт

Принимает ввод в виде массива строк. Возвращает 0или 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)

Контрольные примеры

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"
]))

Отформатировано и прокомментировано

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 байт

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

Попробуйте онлайн!

Вводит в виде 2D списка символов: например {{"A","B"},{"C","D"}},.

Характер\[Transpose] .

Как это устроено

Для каждого символа cна входе, берет Subgraphиз GridGraphодного и того же , Dimensionsкак на входе , который соответствует каждому , Positionв котором cпроисходит, и проверяет , является ли это ConnectedGraphQ.

Python 2 , 247 байт

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

Попробуйте онлайн!

JavaScript (ES6), 181 байт

(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 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
`)));