Фон

Полимин называется L-выпуклый , если это возможно путешествовать из любой плитки любой другой плитки с помощью L-образной траектории, то есть путь , который идет в кардинальных направлениях и меняет направление более одного раза. Например, полиомино 1с на рисунке

0 0 1 1 1 0

1 1 1 1 0 0

1 1 0 0 0 0

не является L-выпуклым, поскольку оба L-образных пути от нижнего левого 1до верхнего правого 1содержат 0:

0>0>1>1>1 0
^       ^
1 1 1 1 0 0
^       ^
1>1>0>0>0 0

Однако polyomino из 1s на этом рисунке является L-выпуклым:

0 1 1 1 0 0

1 1 1 1 1 1

0 1 1 0 0 0

вход

Ваш ввод представляет собой двумерный массив битов в собственном формате вашего языка или в виде строки с разделителями новой строки, если в нашем языке отсутствуют массивы. Он гарантированно содержит хотя бы один 1.

Выход

Ваш вывод должен быть истинным значением, если множество 1s является L-выпуклым polyomino, и ложным значением, если нет. Эти выходные данные должны быть согласованными: вы должны вывести одно и то же истинное значение для всех L-выпуклых входов и то же самое ложное значение для других. Обратите внимание, что несвязанный набор 1s (который не является polyomino) приводит к ложному выводу.

Правила и оценки

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

Тестовые случаи

Эти тесты также должны работать, если вы поворачиваете или отражаете массивы или добавляете строки 0s к любым границам.

False instances
01
10

111
101
111

1101
1111
1110

1100
1000
0011

01100
11110
01110
00110

011000
011110
001111

True instances
1

01
11

010
111
010

001
011
111

11100
11110
01100
01000

011000
011000
111100
111111
001000

Улитки , 45 24

&
!{\1t\1!{o\1,nf\1,!.!~

Сразу после публикации моего первоначального решения я понял, что есть гораздо лучший способ. Оригинальная программа путешествовала по квадрату, образованному путями между двумя 1s, проверяя наличие 0 в каждой паре сторон. Это также должно было иметь особый случай для прямых путей. Новая версия начинается с телепортации от одного 1к другому и проверки на отсутствие прямого или L-образного пути 1s назад к началу.

Matlab, 182 байта

Идея: Повторите для каждого 1в матрице полиомино:

• Создать новую матрицу только с заданным, 1но с остальным нулем.
• для каждого 1в этой новой матрице (повторять, пока ничего не меняется)
  • добавить в 1качестве соседей в направлении х, если 1в полиноме есть соседей
• для каждого 1в этой новой матрице (повторять, пока ничего не меняется)
  • добавить в 1качестве соседей в направлении х, если 1в полиноме есть соседей

Теперь 1в новой матрице необходимо охватить все 1полиномиоматрицы, которые достижимы из заданной начальной точки, сначала двигаясь в направлении x, а затем в направлении y. Теперь мы можем повторить тот же процесс, но сначала в направлении y, а затем в направлении x. Теперь каждая 1матрица полиомино должна быть достигнута одновременно или оба раза. Если нет, то мы нашли позицию в матрице полинома, которая не может быть достигнута из любой другой позиции с помощью L-path.

Golfed:

function r=f(a);[i,j,b]=find(a);N=nnz(i);r=1;for k=1:N;K=1:3;for l=1:2;c=b;b=a*0;b(i(k),j(k))=1;for z=1:2*N; b=conv2(b+0,K,'s')&a;if z==N;K=K';end;end;end;r=r*all(b(:)|c(:)>=a(:));end

С комментариями:

function r=codegolf_L_convex(a);
%a=[0,1;1,1];
[i,j,b]=find(a);%b just needs to be initialized, does not really mattter
N=nnz(i);%number of ones in the matrix
r=1;%return value
for k=1:N;%go throu all '1' in the matrix
    %expand that pixel in x dir:
    K=1:3;%convolution kernel (just three positive values needed)
    for l=1:2;%first horizontal->vertical then vertical->horizontal
        c=b;%backup for considering both runs
        b=a*0;
        b(i(k),j(k))=1; %set the seed
        for z=1:2*N;     
            b=conv2(b+0,K,'s')&a; %expand the seed horizontally (or vertically for the second half) but only within the polyomino
            if z==N;
                K=K'; %change horizontal/vertical 
            end;
        end;
    end;
    r=r*all(b(:)|c(:)>=a(:));%check whether we can really reach every point
end

Скрипт тестовых случаев:

disp('all false -------------');
a=[0,1;1,0];
f(a)
a=[1,1,1;1,0,1;1,1,1];
f(a)
a=[1,1,0,1;1,1,1,1;1,1,1,0];
f(a)
a=[1,1,0,0;1,0,0,0;0,0,1,1];
f(a)
a=[0,1,1,0,0;1,1,1,1,0;0,1,1,1,0;0,0,1,1,0];
f(a)
a=[0,1,1,0,0,0;0,1,1,1,1,0;0,0,1,1,1,1];
f(a)
 disp('all true +++++++++++++');
a=[1];
f(a)
a=[0,1;1,1];
f(a)
a=[0,1,0;1,1,1;0,1,0];
f(a)
a=[0,0,1;0,1,1;1,1,1];
f(a)
a=[1,1,1,0,0;1,1,1,1,0;0,1,1,0,0;0,1,0,0,0];
f(a)
a=[0,1,1,0,0,0;0,1,1,0,0,0;1,1,1,1,0,0;1,1,1,1,1,1;0,0,1,0,0,0];
f(a)

Javascript ES6, 290 байт

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

Доказательство этого метода можно найти в: Сотовые автоматы и дискретные комплексные системы .

L=a=>[1,0,1].every($=>(a=a[0].map((_,col)=>a.map(row=>row[col]))).map(r=>($?r.reverse():r).join``).every((r,i,b)=>r.replace(/^(0*)(1*)(0*)$|(.+)/,(_,s,m,o,e)=>(c=e)?'':!m||b[i-1]&&+b[i-1][s.length]?1:b.every((r,j)=>j<i||(c=c||!+r[l=s.length])?r.search(`0{${l}}.*0{${o.length}}`)+1:1)||'')))

Ungolfed:

function L(a) {
  /* Runs three times and ensure all pass validation
   * 1: horizontally reversed
   * 2: 90 degrees rotated
   * 3: original
   *
   *     | 1:  | 2:  | 3:
   * =====================
   * 001 | 100 | 111 | 001
   * 011 | 110 | 011 | 011
   * 111 | 111 | 001 | 111
   *
   * By finding maximal rectangles with corners on all NW and NE corners
   * (separately) of a HV-convex polyomino and ensuring it doesn't enter the
   * boundaries labelled ABCD for the rectangle X below:
   *
   *   A  |         |  B
   * -----===========-----
   *      |    X    |
   * -----===========-----
   *   C  |         |  D
   *
   * The first iteration tests the NE corners and horizontal convexity.
   * The second iteration test vertical convexity.
   * The third iteration tests the NW corners.
   *
   * If all pass then the polyomino is L-convex.
   */
  return [1,0,1].every(function($){
    return (a=a[0].map((_,col)=>{
      // Transpose rows with columns
      return a.map(row=>row[col])
    })).map(row=>{
      // Join rows as strings and on odd iterations reverse them
      return ($ ? row.reverse() : row).join``
    }).every(function(row, i, b) {
      if (i == 0) console.log(b.join('\n'));
      return row.replace(/^(0*)(1*)(0*)$|(.+)/, function(_, start, middle, end, invalid) {
        // Non H-convex polyomino (0 between 1s)
        if (invalid) return '';
        // Is not a NW corner (character above is 1)
        if (!middle || b[i-1] && +b[i-1][start.length]) return 1;
        c=1;
        return b.every(function(row, j) {
          // Above or below maximal rectangle from corner
          if (j < i || !(c=c&&+row[l=start.length])) {
            // Area before and after maximal rectangle doesn't contain 1
            return row.search(`0{${l}}.*0{${end.length}}`)+1
          }
          return 1;
        }) || '';
      });
    });
  });
}

Mathematica, 129 127 байтов

3>GraphDiameter@Graph[#,#<->#2&@@@Select[#~Tuples~2,!FreeQ[#-#2&@@#,0]&]]&@Position[#,1]&&{#,Thread@#}~FreeQ~{___,1,0..,1,___}&

Объяснение:

Во-первых, если 0между двумя 1s в одной строке или столбце есть массив, он не является L-выпуклым, потому что мы не можем соединить эти два 1s.

После исключения этого случая каждые две 1s в одной строке или столбце могут быть соединены прямым путем. Мы можем сгенерировать граф, вершинами которого являются позиции 1s в массиве, а ребрами являются пары 1s в одной строке или столбце. Тогда массив является L-выпуклым тогда и только тогда, когда диаметр графа меньше 3.

JavaScript (ES6) 174

Глядя на сетку пустых или заполненных ячеек, для любой пары заполненных ячеек я проверяю горизонтальные пути к столбцу другой ячейки (может быть 1, если ячейки находятся в одной строке, иначе или 2) и вертикальные пути к другой ряд ячеек (тоже может быть 1 или 2). Если я найду пустую ячейку в обоих вертикальных или обоих горизонтальных путях, то между ячейками не может быть L-образного пути.

(Я с трудом пытался выдвинуть это объяснение - надеюсь, было понятно)

Попробуйте запустить приведенный ниже фрагмент в любом браузере, совместимом с EcmaScript 6

F=p=>!p.some((n,y)=>n.some((q,x)=>q&&p.some((o,u)=>o.some((q,t)=>{for(f=0,i=y;q&i<=u;i++)f|=!p[i][x]|2*!p[i][t];if(f<3)for(f=0,j=x;q&j<=t;j++)f|=!n[j]|2*!o[j];return f>2}))))

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

tko = [
 [[0,1],[1,0]]
,[[1,1,1],[1,0,1],[1,1,1]]
,[[1,1,0,1],[1,1,1,1],[1,1,1,0]]
,[[1,1,0,0],[1,0,0,0],[0,0,1,1]]
,[[0,1,1,0,0],[1,1,1,1,0],[0,1,1,1,0],[0,0,1,1,0]]
,[[0,1,1,0,0,0],[0,1,1,1,1,0],[0,0,1,1,1,1]]
]
tko.forEach(t=>(console.log(t.join`\n`+`\nFalse? ${F(t)}\n`)));
tok = [
 [[1]]
,[[0,1],[1,1]]
,[[0,1,0],[1,1,1],[0,1,0]]
,[[0,0,1],[0,1,1],[1,1,1]]
,[[1,1,1,0,0],[1,1,1,1,0],[0,1,1,0,0],[0,1,0,0,0]]
,[[0,1,1,0,0,0],[0,1,1,0,0,0],[1,1,1,1,0,0],[1,1,1,1,1,1],[0,0,1,0,0,0]]
]  
tok.forEach(t=>(console.log(t.join`\n`+`\nTrue? ${F(t)}\n`)));

// LESS GOLFED

U=p=>
  !p.some((n,y)=>  
    n.some((q,x)=> 
      q && p.some((o,u)=>  
        o.some((q,t)=>{
          for(f=0,i=y; q&i<=u; i++)f|=!p[i][x]|2*!p[i][t]
          if (f<3)
            for(f=0,j=x; q&j<=t; j++)f|=!n[j]|2*!o[j]
          return f>2
        })
      )
    )
  )

<pre id=O></pre>