Напишите программу или функцию, которая принимает прямоугольную сетку текста, где каждая ячейка представляет собой Aили B. Все Aячейки образуют односвязную форму, то есть все они будут ортогонально соединены без отверстий (соседние по диагонали буквы не считаются связанными). Точно так же все Bклетки будут образовывать другую, просто связанную форму. Сетка всегда будет содержать хотя бы один Aи хотя бы один B.

Представьте , сетка на самом деле два Блочные-образные части тонкого пластика, в лице Aи Bчастями. Если бы он лежал на столе ровно, можно ли было бы раздвинуть две части, оставив обе на столе полностью плоскими?

Печать или вернуть truthy значение , если два Aи Bформы могут быть разделены , как это просто потянув их друг от друга. Если нет, напечатайте или верните ложное значение.

Например, вход

AAA
ABB
AAA

Это правда, потому что BBраздел может быть сдвинут вправо, отделяя его от A:

AAA
A    BB
AAA

Тем не менее, вход

AAAA
ABBA
ABAA

ложно, потому что нет способа раздвинуть части Aи Bчасти без их наложения.

Самый короткий код в байтах побеждает. При желании вы можете использовать любые два окружных печатных символа ASCII вместо Aи B.

Правдивые примеры (разделенные пустыми строками)

BBB
BAA
BBB

BA

A
B

AB
AB

AAA
BBB

AAAAB
ABBBB

ABBA
ABBA
AAAA

AAAAAABBBBBBBBB
AABBBBBBBBBBBBB
AAAAAAAAAABBBBB
AABBBBBBBBBBBBB
AAAAAAAAAAAAAAB

AAAAAAAAAAAA
ABABABABABAB
BBBBBBBBBBBB

BAAAAABB
BBAAABBB
BBBABBBB
BBBABBBB
BBBABBBB
BBBBBBBB
BBBBBBBB

AAA
BAA
AAA

Ложные Примеры

BBBB
BAAB
BABB

BBBB
BAAB
AABB

BBBBBBB
BBBBBAB
AAAAAAB
BBBBBBB

BAAA
BABA
BBBA
AABA
AAAA

AAAAAAA
ABBBBBA
AAAAABA
BBBBBBA

BAAAAABB
BBAAABBB
BBBABBBB
BBBABBBB
BBBAABBB
BBBBBBBB
BBBBBBBB

AAA
ABA
BBA
ABA
AAA

Улитки, 14

o(t\B+~)+!(t\B

Если головоломка может быть раздвинута, она печатает область ввода. В противном случае он печатает 0.

Для более крупных примеров это немного медленно, так как требуется факториал времени в области сетки.

         ,, the program will print the number of starting cells matching this pattern
o        ,, pick a cardinal direction
(
    t    ,, teleport to any cell on the grid
    \B+  ,, match "B" 1 or more times, moving in the direction set by 'o'.
         ,, when a cell is matched, it gets slimed and can't be matched again.
    ~    ,, match an out-of-bounds cell
)+       ,, do parenthesized instructions 1 or more times
!(       ,, the following must not match:
    t\B  ,, teleport to some cell and match 'B'

CJam, 33 32 20 19 17 байт

Пересмотренная версия с широкой поддержкой @ Sp3000 и @ MartinBüttner:

qN/_z]{:e`z,3<}/|

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

взносы

• @ Sp3000 предложил критическое упрощение моего оригинального алгоритма.
• @ MartinBüttner применил свои безумные навыки игры в гольф к пересмотренному подходу, что почти наверняка привело к более короткому коду, чем я мог бы придумать даже после рассмотрения упрощения.

Алгоритм и Доказательство

Далее объясняются критерии для головоломки, раздвигающейся горизонтально. Вертикальный регистр может быть определен путем просмотра столбцов вместо строк или транспонирования матрицы символов и повторного просмотра строк.

Я буду использовать термин «растянуть» для максимальной последовательности тех же букв. Например, следующие строки имеют 1, 2 и 3 растяжения соответственно:

AAAAAAAA
BBBAAAAA
AABBBAAA

Я также буду использовать термин «заблокированный» для строки / головоломки, которые не могут раздвинуться.

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

Следующее может не квалифицироваться как строгое математическое доказательство, но я считаю, что оно дает убедительное объяснение, почему это так.

Легко видеть, что головоломка блокируется, если она имеет ряды более 2-х отрезков. Глядя на ряд с 3-мя участками:

BBBAAB

Понятно, что это препятствует раздвижению головоломки, потому что Aнатяжение заблокировано между Bотрезками. Это означает, что ряд заблокирован, что, в свою очередь, блокирует всю головоломку.

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

• Строки с одним растяжением не способствуют блокировке головоломки, так как они могут скользить в любом направлении без каких-либо столкновений.
• Если все строки с 2-мя участками имеют одинаковый порядок Aи B, головоломка явно не блокируется. В этом случае все Aячейки остаются от всех Bячеек или наоборот, и при раздвижении двух частей нет столкновений.

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

.......
AAABBBB
.......
BBAAAAA
.......

Теперь в спецификации говорится, что Aи Bячейка, и ячейка просто связаны во всех действительных головоломках. Чтобы Aсвязать ячейки в частичной головоломке, представленной выше, у нас есть два варианта:

1. Мы зациклились на одном из отрезков B, например:

   ..AAAAAA
   AAABBBBA
   .......A
   BBAAAAAA
   ........
   

   Чтобы сделать это, мы неизбежно расширяем один из рядов на 3 отрезка, так что это никогда не даст нам правильную головоломку, где все ряды имеют максимум 2 отрезка.

2. Мы соединяем их по прямому пути:

   .......
   AAABBBB
   ..A....
   BBAAAAA
   .......
   

   Эти Aклетки теперь просто соединены, и до сих пор нет строки с более чем 2 -х участков. Тем не менее, Bклетки также должны быть просто связаны. Прямой путь теперь заблокирован соединенными Aячейками, и единственный способ соединить Bячейки - это обхватить один из участков Aячейки. Это возвращает нас к случаю 1, где мы не можем сделать это, не создавая ряды из 3 отрезков.

Для подсчета растяжений в реализации используется оператор CJam RLE.

Объяснение кода

qN/     Get input and split at newlines.
_z      Make a transposed copy.
]       Wrap the original and transposed puzzle in an array so that we can
        loop over the two.
{       Start of loop over original and transposed puzzle.
  :e`     Apply RLE to all rows.
  z,      Transpose the matrix with the RLE rows, and take the element count of the
          result. Or in other words, take the column count. This will be the length
          of the longest row after RLE.
  3<      Check the length for less than 3.
}/      End of loop over original and transposed puzzle.
|       Or the results of the two.

JavaScript (ES6), 108 107 98 91 82 байта

a=>!(T=[],R=/AB+A|BA+B/).test([...a].map((c,i)=>T[i%-~a.search`
`]+=c))|!R.test(a)

Живая демоверсия . Проверено в Firefox. Принимает ввод в виде строки с разделителями новой строки.

Редактирование:

• Сохранено 1 байт путем перехода \nна буквальный перевод строки.
• Сэкономили 9 байт, выполнив тест RegExp непосредственно на многострочную строку вместо преобразования в массив.
• Удалил еще 9 байтов, используя массивы для разделения строки, двигаясь! в gфункцию и вызывая RegExp непосредственно в массиве вместо использования find.
• Продолжил арт-последовательность, сохранив еще 9 байтов. Сделал модуль индекса вместо того, чтобы разбивать массив по новым строкам перед выполнением транспонирования.

Как это работает

Предыдущая версия:

a=>(T=[],a.split`
`.map(s=>s.split``.map((c,i)=>T[i]+=c)),!T.find(g=s=>/AB+A|BA+B/.test(s)))|!g(a)

1. Возьмите ввод aи разбейте его по символам новой строки на массив строк.
2. Транспонировать aи хранить его в T. Используйте, mapчтобы перебрать каждый элемент a, разбить строку на массив символов и использовать mapснова, чтобы добавить iсимвол th в строку к iстроке th T. Поскольку каждый элемент Tнеинициализирован, он будет выглядеть примерно так "undefinedAAABBA", но это не имеет значения.
3. Создайте функцию тестирования на основе RegExp g, соответствующую шаблону /AB+A|BA+B/. Если это совпадает, кусочки блокируются в заданном направлении, потому что тогда есть набор Bs, зажатый между двумя или более As или наоборот.
4. Используйте функцию тестирования gдля проверки всех элементов блока aи его транспонирования Tна соответствие find. Если оба совпадают, то кусочки блокируются в обоих направлениях, поэтому выведите ложное значение, в противном случае - истинное.

Javascript (ES6), 118

slidey=
// code
a=>!a.match(R=/AB+A|BA+B/)||!(a=a.split`
`.map(b=>b.split``))[0].map((_,c)=>a.map(d=>d[c])).some(e=>e.join``.match(R))

// IO
var S =document.getElementById('S');
S.onkeyup = _=> document.getElementById('P').innerText = slidey(S.value);

document.getElementById('P').innerText = slidey(S.value);

<textarea id='S'>BAAAAABB
BBAAABBB
BBBABBBB
BBBABBBB
BBBABBBB
BBBBBBBB
BBBBBBBB</textarea>
<p id='P'></p>

Объяснение:

a=> !/* check string horizontally */ || !/* check string vertically by transposing it and
                                            running the same horizontal check */

a=> !a.match(R=/AB+A|BA+B/) || !/* ... */
// check for lines containing something like BAAAAAB or ABBBBBBBA
// this is the only way something can get blocked horizontally
// eg AAAAAAA
//    AAABAAA <<< note the B in the middle of As here
//    AAABBBB <<< blocked from being pulled out horizontally
//    AAAAAAA

a=> /* ... */ ||!( a = a.split('\n').map(b=> b.split('')) ) // split a into 2D array
    [0].map((_,c)=>a.map(d=>d[c])) // transpose it
    .some(e=>e.join``.match(R)) // run the check again using `some` to go line by line
                                // which is shorter than .join().match() outside

a=> !/* returns null if no horizontal obstacles and an array if there are */
    || !/* same thing */
// negate both to cast to a boolean (false if obstacles, true if not)
// an input can only be unslidable if both directions are blocked
// so (no obstacles vertically? || no obstacles horizontally?) gives the answer

JavaScript (ES6) 72 74

Редактирование 2 байта , сохраненные THx @NotthatCharles

У меня есть интуитивное понимание того, что если одна часть может скользить лишь долю шага, то это бесплатно. Текущие тесты подтверждают это.

Поэтому я проверяю только один шаг в каждом направлении.

Используемые символы: 1 и 0 на
2 байта больше, чтобы использовать любые 2 печатных символа, таких как A и B

Протестируйте приведенный ниже фрагмент в браузере, совместимом с EcmaScript 6 (с поддержкой оператора распространения - IE Firefox)

f=s=>[w=~s.search`
`,-w,-1,1].some(o=>![...s].some((x,p)=>x+s[p+o]==10))

// 4 bytes more- for any symbol, not just 1 and 0 (for instance A and B):
g=s=>[w=~s.search`
`,-w,-1,1].some(o=>![...s].some((x,p)=>x+s[p+o]=='AB'))

//TEST
console.log=x=>O.innerHTML+=x+'\n'

testOk = [
 '111\n100\n111',
 '10',
 '0\n1',
 '01\n01',
 '000\n111',
 '00001\n01111',
 '0110\n0110\n0000',
 '000000111111111\n001111111111111\n000000000011111\n001111111111111\n000000000000001',
 '000000000000\n010101010101\n111111111111',
 '10000011\n11000111\n11101111\n11101111\n11101111\n11111111\n11111111',
 '000\n100\n000'
]

testKo = [
 '1111\n1001\n1011',
 '1111\n1001\n0011',
 '1111111\n1111101\n0000001\n1111111',
 '1000\n1010\n1110\n0010\n0000',
 '0000000\n0111110\n0000010\n1111110',
 '10000011\n11000111\n11101111\n11101111\n11100111\n11111111\n11111111',
 '000\n010\n110\n010\n000'
]

console.log('Expecting true')
testOk.forEach(t=>console.log(t+'\n'+f(t)+'\n'))
console.log('Expecting false')
testKo.forEach(t=>console.log(t+'\n'+f(t)+'\n'))

<pre id=O></pre>

Mathematica 100 69 байт

Благодаря огромному сохранению 31 байта, благодаря @Martin Buttner,

g=Max[Length/@Split/@#]<3&;g[c=Characters@StringSplit@#]||g@Thread@c&

Форматирует ввод как матрицу символов; это также делает транспонирование матрицы. Если либо матрица, либо ее транспонирование имеет не более 2 прогонов в ряду, головоломка может скользить.

{a,a,b,b,b} имеет 2 серии писем.

{a,a,b,a,a} имеет 3 серии писем.

{a,a,b,a,a,a,b,b,b,b,b,b,b,b} имеет 4 серии писем.

Дьялог АПЛ, 22 байта

(∨/{∧/2>+/2≠/⍵}¨)⊂∘⍉,⊂

Попробуй это здесь. Эта функция принимает двумерный массив символов и возвращает1 для скользящих и 0не скользящих экземпляров . Алгоритм аналогичен большинству других ответов: проверьте матрицу и транспонируйте ее, чтобы ни одна строка не содержала более одной соседней пары разных букв. Для входной матрицы 4x3

AAAA
ABBB
AAAB

функция может быть вызвана как

f ← (∨/{∧/2>+/2≠/⍵}¨)⊂∘⍉,⊂
f 4 3 ⍴ 'AAAAABBBAAAB'

что приводит к 1.

объяснение

⊂∘⍉,⊂   The matrix and its transpose.
{...}¨   For each of them:
  2≠/⍵   On each row, replace each adjacent pair with 1 if they differ, with 0 otherwise
  2>+/    Take the sum on each row and check that it's less than 2
  ∧/     AND over all rows
∨/      OR over the resulting two values

JavaScript (ES6), 94 байта

x=>!(y=/AB+A|BA+B/).test(x)|(z=[],x.split`
`.map(b=>b.split``.map((c,i)=>z[i]+=c)),!y.test(z))

Альтернативный метод того же размера:

x=>(t=s=>!/AB+A|BA+B/.test(s),z=[],x.split`
`.map(b=>b.split``.map((c,i)=>z[i]+=c)),t(x)|t(z))

Это возвращает 1для правдивого ввода и0 для ложного. Я начал работать над этим, прежде чем другие ответы были опубликованы. Я также первоначально пытался использовать массивы ES7, но это оказалось примерно на 10 символов длиннее, чем этот метод.

Попробуйте это:

a=x=>!(y=/AB+A|BA+B/).test(x)|(z=[],x.split`
`.map(b=>b.split``.map((c,i)=>z[i]+=c)),!y.test(z))

P.onclick=_=>Q.innerHTML='Result: '+a(O.value)

<textarea id=O cols="20" rows="8">AAAAAABBBBBBBBB
AABBBBBBBBBBBBB
AAAAAAAAAABBBBB
AABBBBBBBBBBBBB
AAAAAAAAAAAAAAB</textarea>
<button id=P>Test</button>
<p id=Q>Result: </p>

Предложения приветствуются!