Hintergrund

Ein Polyomino heißt L-konvex , wenn es möglich ist, über einen L-förmigen Pfad von einem Plättchen zu einem anderen zu gelangen, dh einen Pfad, der in die Hauptrichtung verläuft und die Richtung höchstens einmal ändert. Zum Beispiel das Polyomino von 1s in der Figur

0 0 1 1 1 0

1 1 1 1 0 0

1 1 0 0 0 0

ist nicht L-konvex, da beide L-förmigen Pfade von links unten 1nach rechts oben a 1enthalten 0:

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

Das Polyomino von 1s in dieser Figur ist jedoch L-konvex:

0 1 1 1 0 0

1 1 1 1 1 1

0 1 1 0 0 0

Eingang

Ihre Eingabe ist ein 2D-Array von Bits im ursprünglichen Format Ihrer Sprache oder eine durch Zeilenumbrüche getrennte Zeichenfolge, wenn unsere Sprache keine Arrays enthält. Es wird garantiert, um mindestens ein zu enthalten 1.

Ausgabe

Ihre Ausgabe soll ein wahrer Wert sein, wenn die Menge von 1 s ein L-konvexes Polyomino ist, und ein falscher Wert, wenn nicht. Diese Ausgaben müssen konsistent sein: Sie müssen für alle L-konvexen Eingaben den gleichen Wahrheitswert und für andere den gleichen falschen Wert ausgeben. Beachten Sie, dass eine getrennte Menge von 1s (die kein Polyomino ist) zu einer falschen Ausgabe führt.

Regeln und Wertung

Sie können entweder ein vollständiges Programm oder eine Funktion schreiben. Die niedrigste Byteanzahl gewinnt und Standardlücken sind nicht zulässig.

Testfälle

Diese Testfälle sollten auch funktionieren, wenn Sie die Arrays drehen oder spiegeln oder Zeilen von 0s zu beliebigen Rändern hinzufügen .

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

Schnecken , 45 24

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

Gleich nach der Veröffentlichung meiner ersten Lösung wurde mir klar, dass es einen viel besseren Weg gibt. Das ursprüngliche Programm bewegte sich um das Quadrat, das durch die Pfade zwischen zwei 1Sekun- den gebildet wurde, und prüfte auf das Vorhandensein einer 0 in jedem Seitenpaar. Es musste auch einen Sonderfall für gerade Strecken geben. Die neue Version beginnt mit dem Teleportieren von einem 1zum anderen und dem Testen, ob keine gerade oder L-förmige Bahn von 1s zum Start vorhanden ist.

Matlab, 182 Bytes

Idee: Für jeden wiederholen 1 in der Polyomino-Matrix:

• Erstelle eine neue Matrix nur mit der gegebenen 1 aber der restlichen Null.
• für jeden 1 in dieser neuen Matrix (wiederholen, bis sich nichts mehr ändert)
  • füge 1als Nachbarn in x-Richtung hinzu, wenn es 1als Nachbarn im Polynom gibt
• für jeden 1 in dieser neuen Matrix (wiederholen, bis sich nichts mehr ändert)
  • füge 1als Nachbarn in x-Richtung hinzu, wenn es 1als Nachbarn im Polynom gibt

Jetzt sollte 1in der neuen Matrix alles 1in der Polynom-Matrix abgedeckt sein, was vom angegebenen Startpunkt aus erreichbar ist, indem zuerst in x-Richtung und dann in y-Richtung gegangen wird. Jetzt können wir den gleichen Vorgang wiederholen, jedoch zuerst in y-Richtung und dann in x-Richtung. Jetzt sollte jede 1der Polyominomatrix einmal oder beide Male erreicht werden. Wenn nicht, dann haben wir eine Position in der Polynommatrix gefunden, die nicht von jeder anderen Position durch einen L-Pfad erreicht werden kann.

Golf gespielt:

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

Mit Kommentaren:

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

Skript für Testfälle:

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 Bytes

Ok, vielleicht wird es keine Preise für Kürze gewinnen, aber es verwendet einen neuartigen Ansatz. In der ungolfed Version erfahren Sie, wie es funktioniert.

Der Beweis für diese Methode findet sich in: Zelluläre Automaten und Diskrete Komplexe Systeme .

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 Bytes

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

Erläuterung:

Erstens ist das Array nicht L-konvex , wenn sich 0zwischen zwei 1s in derselben Zeile oder Spalte befindet, da wir die beiden 1s nicht verbinden können .

Nach dem Ausschließen dieses Falls können alle zwei 1s in derselben Zeile oder Spalte durch einen geraden Pfad verbunden werden. Wir können ein Diagramm erstellen, dessen Scheitelpunkte die Positionen von 1s im Array sind und dessen Kanten Paare von 1s in derselben Zeile oder Spalte sind. Dann ist das Array genau dann L-konvex, wenn der Durchmesser des Graphen kleiner als 3 ist.

JavaScript (ES6) 174

Wenn ich das Raster aus leeren oder gefüllten Zellen betrachte, überprüfe ich für jedes Paar gefüllter Zellen die horizontalen Pfade zur anderen Zellenspalte (es kann 1 geben, wenn sich die Zellen in derselben Zeile befinden, sonst 2) und die vertikalen Pfade zur andere Zellenreihe (es können auch 1 oder 2 sein). Wenn ich in beiden vertikalen Pfaden oder beiden horizontalen Pfaden eine leere Zelle finde, kann es keinen L-förmigen Pfad zwischen den Zellen geben.

(Es fiel mir schwer, diese Erklärung zu formulieren - ich hoffe, es war klar)

Testen Sie das folgende Snippet in einem beliebigen EcmaScript 6-kompatiblen Browser

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>