É L-convexo?

14

fundo

Um poliomino é chamado L-convexo , se for possível viajar de qualquer ladrilho para outro ladrilho por um caminho em forma de L, ou seja, um caminho que segue as direções cardinais e muda de direção no máximo uma vez. Por exemplo, o poliomino de 1s na figura

0 0 1 1 1 0

1 1 1 1 0 0

1 1 0 0 0 0

não é L-convexo, pois os dois caminhos em forma de L do canto inferior esquerdo 1para o canto superior direito 1contêm um 0:

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

No entanto, o poliomino de 1s nesta figura é L-convexo:

0 1 1 1 0 0

1 1 1 1 1 1

0 1 1 0 0 0

Entrada

Sua entrada é uma matriz 2D de bits no formato nativo do seu idioma ou como uma string delimitada por nova linha, se o nosso idioma não tiver matrizes. É garantido que contenha pelo menos um 1.

Resultado

Sua saída deve ser um valor verdadeiro se o conjunto de 1s for um poliomaino L-convexo e um valor falso se não. Essas saídas devem ser consistentes: você deve gerar o mesmo valor verdadeiro para todas as entradas L-convexas e o mesmo valor falso para outras. Observe que um conjunto desconectado de 1s (que não é um poliomino) resulta em uma saída falsa.

Regras e Pontuação

Você pode escrever um programa completo ou uma função. A contagem de bytes mais baixa vence e as brechas padrão não são permitidas.

Casos de teste

Esses casos de teste também devem funcionar se você girar ou refletir as matrizes ou adicionar linhas de 0s a qualquer borda.

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
Zgarb
fonte
Muito bom desafio, eu gostei =)
flawr
Sobre input: é permitida uma string delimitada por nova linha , se o nosso idioma não possui matrizes ?
edc65
@ edc65 (desculpe, estou fora da rede por alguns dias.) Claro, isso também é permitido, mas está mal formulado da minha parte.
Zgarb 13/10/2015

Respostas:

6

Caracóis , 45 24

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

Logo após postar minha solução inicial, percebi que havia uma maneira muito melhor. O programa original percorreu o quadrado formado pelos caminhos entre dois 1s, testando a presença de um 0 em cada par de lados. Ele também precisava ter um caso especial para caminhos de linha reta. A nova versão começa se teletransportando de um 1para o outro e testando a ausência de um caminho reto ou em forma de L de 1s de volta ao início.

feersum
fonte
AMD!! Existe um intérprete on-line onde possamos brincar com isso?
flawr
1
@ flawr Você pode compilá-lo da fonte com o código fonte aqui .
Alex A.
6

Matlab, 182 bytes

Idéia: Repita para cada um 1na matriz polyomino:

  • Crie uma nova matriz apenas com o dado, 1mas o restante zero.
  • para cada 1nesta nova matriz (repita até que nada mude mais)
    • adicione 1como vizinhos na direção x se houver 1como vizinhos no polinômio
  • para cada 1nesta nova matriz (repita até que nada mude mais)
    • adicione 1como vizinhos na direção x se houver 1como vizinhos no polinômio

Agora, 1na nova matriz, deve abranger todos 1os elementos da polinômio-matriz que são alcançáveis ​​a partir do ponto de partida especificado, primeiro indo na direção x e depois na direção y. Agora podemos repetir o mesmo processo, mas primeiro indo na direção y e depois na direção x. Agora todas 1as matrizes polyomino devem ser alcançadas ao mesmo tempo ou nos dois momentos. Caso contrário, encontramos uma posição na matriz polynomio que não pode ser alcançada de todas as outras posições por um L-path.

Golfe:

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

Com comentários:

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

Script de casos de teste:

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)
flawr
fonte
2

Javascript ES6, 290 bytes

Ok, talvez não ganhe nenhum prêmio por concisão, mas usa uma abordagem inovadora. Veja a versão ungolfed para saber como funciona.

A prova desse método pode ser encontrada em: Autômatos celulares e sistemas complexos discretos .

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;
        }) || '';
      });
    });
  });
}
George Reith
fonte
1
Ha, esse artigo é onde eu me inspirei para este desafio!
Zgarb 9/10/2015
@ Zgarb O artigo foi ótimo e um dos poucos que pude achar que fazia sentido para alguém que não é matematicamente orientado.
George Reith
2

Mathematica, 129 127 bytes

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

Explicação:

Primeiro, se houver 0entre dois 1s na mesma linha ou coluna, a matriz não é L-convexa, porque não podemos conectar os dois 1s.

Após excluir este caso, a cada dois 1s na mesma linha ou coluna pode ser conectada por um caminho reto. Podemos gerar um gráfico, cujos vértices são as posições de 1s na matriz e as arestas são pares de 1s na mesma linha ou coluna. Então a matriz é L-convexa se e somente se o diâmetro do gráfico for menor que 3.

alefalpha
fonte
1
Você pode dar uma explicação de como isso funciona? Não vou upvote jargão ninguém poderia entender =)
flawr
Como isso reconhece a primeira e a quarta instâncias falsas (as desconectadas)?
Zgarb
1
@Zgarb Se o gráfico estiver desconectado, seu diâmetro será infinito.
Alephalpha # 9/15
2

JavaScript (ES6) 174

Observando a grade de células vazias ou preenchidas, para qualquer par de células preenchidas, verifico os caminhos horizontais para a outra coluna da célula (pode haver 1 se as células estiverem na mesma linha, mais ou 2) e os caminhos verticais para o outra linha da célula (também pode haver 1 ou 2). Se eu encontrar uma célula vazia nos caminhos verticais ou horizontais, não poderá haver um caminho em forma de L entre as células.

(Foi difícil tentar explicar essa explicação - espero ter ficado claro)

Teste a execução do trecho abaixo em qualquer navegador compatível com 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>

edc65
fonte