14
\$\begingroup\$

Background

A polyomino is called L-convex, if it's possible to travel from any tile to any other tile by an L-shaped path, that is, a path that goes in the cardinal directions and changes direction at most once. For example, the polyomino of 1s in the figure

0 0 1 1 1 0

1 1 1 1 0 0

1 1 0 0 0 0

is not L-convex, since both L-shaped paths from the bottom left 1 to the top right 1 contain a 0:

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

However, the polyomino of 1s in this figure is L-convex:

0 1 1 1 0 0

1 1 1 1 1 1

0 1 1 0 0 0

Input

Your input is a 2D array of bits in the native format of your language, or as a newline-delimited string if our language lacks arrays. It is guaranteed to contain at least one 1.

Output

Your output shall be a truthy value if the set of 1s is an L-convex polyomino, and a falsy value if not. These outputs must be consistent: you must output the same truthy value for all L-convex inputs, and the same falsy value for others. Note that a disconnected set of 1s (which is not a polyomino) results in a falsy output.

Rules and Scoring

You can write either a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.

Test Cases

These test cases should work also if you rotate or reflect the arrays, or add rows of 0s to any borders.

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
\$\endgroup\$
  • \$\begingroup\$ Very nice challenge, I enjoyed it=) \$\endgroup\$ – flawr Oct 7 '15 at 18:35
  • \$\begingroup\$ About input: it a newline-delimited string allowed, if our language does not lack arrays ? \$\endgroup\$ – edc65 Oct 11 '15 at 11:32
  • \$\begingroup\$ @edc65 (Sorry, been off the grid for a couple of days.) Sure, that's allowed too, it's just badly worded on my part. \$\endgroup\$ – Zgarb Oct 13 '15 at 15:32
6
\$\begingroup\$

Snails, 45 24

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

Right after posting my initial solution, I realized there was a much better way. The original program traveled around the square formed by the paths between two 1s, testing for the presence of a 0 in each pair of sides. It also had to have a special case for straight line paths. The new version starts by teleporting from one 1 to the other, and testing for the absence of a straight or L-shaped path of 1s back to the start.

\$\endgroup\$
  • \$\begingroup\$ OMG!! Is there an online interpreter where we could play around with this? \$\endgroup\$ – flawr Oct 8 '15 at 8:43
  • 1
    \$\begingroup\$ @flawr You can build it from source with the source code here. \$\endgroup\$ – Alex A. Oct 8 '15 at 23:41
6
\$\begingroup\$

Matlab, 182 bytes

Idea: Repeat for every 1 in the polyomino matrix:

  • Create new matrix with only the given 1 but the rest zero.
  • for every 1 in this new matrix (repeat until nothing changes anymore)
    • add 1 as neighbours in x direction if there are 1 as neighbours in the polynomio
  • for every 1 in this new matrix (repeat until nothing changes anymore)
    • add 1 as neighbours in x direction if there are 1 as neighbours in the polynomio

Now 1 in the new matrix should cover all 1 in the polynomio-matrix that are reachable from the given starting point by first going in x-direction and then in y-direction. Now we can repeat the same process but with first going into y-direction and then in x-direction. Now every 1 of the polyomino matrix should be reached at once or both times. If not, then we have found a position in the polynomio matrix that cannot be reached from every other position by an 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

With comments:

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

Test cases script:

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)
\$\endgroup\$
2
\$\begingroup\$

Javascript ES6, 290 bytes

Ok, maybe it won't win any awards for brevity, but it does use a novel approach. See the ungolfed version for how it works.

Proof for this method can be found in: Cellular Automata and Discrete Complex Systems.

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;
        }) || '';
      });
    });
  });
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Ha, that article is where I got the inspiration for this challenge! \$\endgroup\$ – Zgarb Oct 9 '15 at 0:06
  • \$\begingroup\$ @Zgarb The article was great and one of the few I could find that made sense to someone who isn't mathematically orientated. \$\endgroup\$ – George Reith Oct 9 '15 at 0:36
2
\$\begingroup\$

Mathematica, 129 127 bytes

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

Explanation:

First, if there is a 0 between two 1s on the same row or column, the array is not L-convex, because we can't connect the two 1s.

After excluding this case, every two 1s on the same row or column can be connected by a straight path. We can generate a graph, whose vertices are the positions of 1s in the array, and edges are pairs of 1s on the same row or column. Then the array is L-convex if and only if the diameter of the graph is less than 3.

\$\endgroup\$
  • 1
    \$\begingroup\$ Can you give an explanation how this works? I am not gonna upvote gibberish nobody could possibly understand=) \$\endgroup\$ – flawr Oct 8 '15 at 8:54
  • \$\begingroup\$ How does this recognize the first and fourth false instances (the disconnected ones)? \$\endgroup\$ – Zgarb Oct 8 '15 at 18:12
  • 1
    \$\begingroup\$ @Zgarb If the graph is disconnected, its diameter is infinity. \$\endgroup\$ – alephalpha Oct 9 '15 at 2:58
2
\$\begingroup\$

JavaScript (ES6) 174

Looking at the grid of empty or filled cells, for any pair of filled cells I check the horizontal paths to the other cell column (there can be 1 if the cells are on the same row, else or 2) and the vertical paths to the other cell row (there can be 1 or 2 too). If I find an empty cell in both vertical paths or both horizontal paths, then there can not be an L shaped path between the cells.

(I had a hard time trying to put up this explanation - I hope to have been clear)

Test running the snippet below in any EcmaScript 6 compliant 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>

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.