배경
폴리오 미노는 호출 L-볼록 가있는 L 자 형상의 경로, 기수의 방향으로 진행 한 번에 가장 방향을 변경하는 다른 경로에 의해 타일에 대한 타일에서 이동하는 것이 가능하면. 예를 들어, 1
그림에서 s 의 polyomino
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
그러나이 1
그림에서 s 의 polyomino 는 L- 볼록한 모양입니다.
0 1 1 1 0 0
1 1 1 1 1 1
0 1 1 0 0 0
입력
입력 내용은 사용자 언어의 기본 형식으로 된 2D 비트 배열이거나 언어에 배열이없는 경우 줄 바꿈으로 구분 된 문자열입니다. 적어도 하나는 포함되어 있어야 1
합니다.
산출
1
s 세트 가 L- 볼록 폴리오 미노이면 출력값이 진실 값이되고 그렇지 않으면 거짓 값이됩니다. 이러한 출력은 일관성이 있어야합니다. 모든 L- 볼록 입력에 대해 동일한 값을, 다른 값에 대해 동일한 값을 출력해야합니다. 연결이 끊긴 1
s 세트 (polyomino가 아님)는 잘못된 출력을 초래합니다.
규칙과 채점
전체 프로그램이나 함수를 작성할 수 있습니다. 가장 낮은 바이트 수가 이기고 표준 허점 은 허용되지 않습니다.
테스트 사례
이 테스트 사례는 배열을 회전하거나 반영하거나 0
s 행을 테두리에 추가하는 경우에도 작동 합니다.
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,!.!~
초기 솔루션을 게시 한 직후 훨씬 더 좋은 방법이 있음을 깨달았습니다. 원래 프로그램은 두 1
쌍 사이의 경로에 의해 형성된 사각형 주위를 이동 하여 각 쌍의 쌍에 0이 있는지 테스트합니다. 또한 직선 경로에 대한 특별한 경우가 있어야했습니다. 새로운 버전은 1
서로간에 순간 이동 하고 직선 또는 L 자형 경로가 없는지 테스트합니다 1
.
답변
Matlab, 182 바이트
아이디어 : 1
polyomino matrix에서 반복합니다 :
- 주어진 값만 사용
1
하고 나머지는 0 인 새 행렬을 만듭니다 . 1
이 새로운 매트릭스의 모든 것 (더 이상 아무것도 변하지 않을 때까지 반복)- 폴리 노미오에 이웃이있는
1
경우 x 방향으로 이웃으로 추가1
- 폴리 노미오에 이웃이있는
1
이 새로운 매트릭스의 모든 것 (더 이상 아무것도 변하지 않을 때까지 반복)- 폴리 노미오에 이웃이있는
1
경우 x 방향으로 이웃으로 추가1
- 폴리 노미오에 이웃이있는
이제 1
새로운 행렬 1
에서 먼저 x 방향으로 이동 한 다음 y 방향으로 이동하여 주어진 시작점에서 도달 할 수있는 다항식 행렬의 모든 항목 을 포함 해야합니다 . 이제 동일한 프로세스를 반복 할 수 있지만 먼저 y 방향으로 이동 한 다음 x 방향으로 이동합니다. 이제 모든 1
polyomino matrix에 한 번 또는 두 번에 도달해야합니다. 그렇지 않은 경우 폴리 노미오 행렬에서 L
-path 를 통해 다른 모든 위치에서 도달 할 수없는 위치를 찾았습니다 .
골프 :
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)
답변
자바 스크립트 ES6, 290 바이트
좋아, 어쩌면 그것은 간결한 상을 수상하지는 않지만 새로운 접근법을 사용합니다. 작동 방법은 ungolfed 버전을 참조하십시오.
이 방법에 대한 증거는 Cellular Automata 및 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)||'')))
언 골프 드 :
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, 129127 바이트
3>GraphDiameter@Graph[#,#<->#2&@@@Select[#~Tuples~2,!FreeQ[#-#2&@@#,0]&]]&@Position[#,1]&&{#,Thread@#}~FreeQ~{___,1,0..,1,___}&
설명:
첫째, 같은 행이나 열에 0
두 개의 사이 가 있으면 두 개의 1
연결을 할 수 없기 때문에 배열은 L 볼록하지 않습니다 1
.
이 경우를 제외 1
하면 동일한 행 또는 열에있는 두 개의 모든 경로를 직선 경로로 연결할 수 있습니다. 정점은 1
배열에서 s 의 위치 이고 모서리는 1
같은 행 또는 열 에서 s의 쌍인 그래프를 생성 할 수 있습니다 . 그런 다음 그래프 의 지름 이 3보다 작은 경우에만 배열이 L- 볼록합니다 .
답변
자바 스크립트 (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>