도전:
0과 1의 행렬 (또는 2 차원 배열)이 주어지면 Conway의 삶의 게임이 안정적인 상태에 도달하는 데 걸리는 단계 수 또는 1에 도달하지 않으면 -1을 출력합니다. 안정 상태는 각 단계에서 셀이 켜지거나 꺼지지 않는 상태입니다. 게임은 상단과 하단이 연결되고 측면이 연결되어있는 주어진 매트릭스에서 실행되어야합니다. (즉, 4×3 매트릭스가 주어지면 4×3 토러스에서 실행되어야 함) 입력 매트릭스는 15×15보다 크지 않습니다.
참고 : 매트릭스가 안정적인 상태에서 시작되면 출력은 0이어야합니다.
견본:
입력:
[[0,0,0],
[0,1,1],
[0,1,0]]
산출:
2
프로세스 : (표시 할 필요는 없습니다)
[[0,0,0],
[0,1,1],
[0,1,0]]
[[1,1,1],
[1,1,1],
[1,1,1]]
[[0,0,0],
[0,0,0],
[0,0,0]]
입력:
[[0,0,1,1],
[0,1,1,1],
[0,1,0,0],
[0,1,1,1]]
산출:
2
방법:
[[0,0,1,1],
[0,1,1,1],
[0,1,0,0],
[0,1,1,1]]
[[0,0,0,0],
[0,1,0,1],
[0,0,0,0],
[0,1,0,1]]
[[0,0,0,0],
[0,0,0,0],
[0,0,0,0],
[0,0,0,0]]
입력:
[[0,1,0,0],
[0,1,0,0],
[0,1,0,0],
[0,0,0,0]]
산출:
-1
방법:
[[0,1,0,0],
[0,1,0,0],
[0,1,0,0],
[0,0,0,0]]
[[0,0,0,0],
[1,1,1,0],
[0,0,0,0],
[0,0,0,0]]
[[0,1,0,0],
[0,1,0,0],
[0,1,0,0],
[0,0,0,0]]
영원히 반복
입력:
[[0,0,0,0],
[0,0,0,1],
[0,1,1,1],
[0,0,1,0]]
산출:
4
방법:
[[0,0,0,0],
[0,0,0,1],
[0,1,1,1],
[0,0,1,0]]
[[0,0,0,0],
[1,0,0,1],
[1,1,0,1],
[0,1,1,1]]
[[0,1,0,0],
[0,1,1,1],
[0,0,0,0],
[0,1,0,1]]
[[0,1,0,1],
[1,1,1,0],
[0,1,0,1],
[1,0,1,0]]
[[0,0,0,0],
[0,0,0,0],
[0,0,0,0],
[0,0,0,0]]
입력:
[[0,0,0,0],
[0,1,1,0],
[0,1,1,0],
[0,0,0,0]]
산출:
0
방법:
시작 상태는 안정적입니다.
인생 게임의 규칙
꺼져있는 셀 (0)이 정확히 세 개의 켜진 셀 (1) 옆에 있으면 켜집니다. 그렇지 않으면 꺼져 있습니다. 켜져있는 셀이 사각형에서 2 또는 3 옆에 있으면 켜집니다. 그렇지 않으면 꺼집니다.
답변
매쓰, 130 129 바이트
#&@@FirstPosition[Partition[CellularAutomaton[{224,{2,{{2,2,2},{2,1,2},{2,2,2}}},{1,1}},#,2^Length[Join@@#]],2,1],{x_,x_},0,1]-1&
4×4 이상의 입력을 시도하지 않는 것이 좋습니다. 영원히 많은 메모리가 필요하기 때문입니다.
설명
이것은 단순히 삶의 게임 시뮬레이션 2 N의 단계 N이 입력 세포의 수입니다. 이를 통해 시스템이 안정적인 상태에 도달하면 도달 한 것입니다. 이후 시뮬레이션 된 이력에서 연속적인 동일한 상태의 첫 번째 쌍을 찾습니다.
코드를 살펴 봅시다 :
2^Length[Join@@#]
2D리스트를 평탄화하는 데 사용 되므로 2 N을 계산 Join@@
합니다.
CellularAutomaton[{224,{2,{{2,2,2},{2,1,2},{2,2,2}}},{1,1}},#,...]
이것은 2 N 세대 동안의 게임 게임을 시뮬레이션합니다 . 3×3 매트릭스는 전체 2D 오토 마톤의 주변을 지정하며 224
표준 Game of Life의 규칙 번호입니다. Mathematica.SE 에서이 숫자를 계산하는 방법에 대해 썼습니다 .
Partition[...,2,1]
이것은 모든 연속 (중복) 세대 쌍을 가져옵니다.
FirstPosition[...,{x_,x_},0,1]
이것은 동일한 세대의 첫 번째 쌍을 찾으며, 기본값이 0
없으면 기본값으로 검색을 깊이로 제한합니다 1
. 그러한 쌍 을 찾으면 결과는 목록으로 반환됩니다. 그래서 우리는 다음을 사용합니다.
#&@@...
해당 목록에서 첫 번째 요소를 추출하려면 ( 0
원자 값 인 기본값 은 이에 영향을받지 않음)
...-1
마지막으로 우리는 도전에 0
기반 인덱스와 -1
실패를 기대하기 때문에 하나를 뺍니다 .
답변
루아, 531 509 488 487 464 424 405 404 바이트
대량 제출을 원하는 사람은 누구입니까? \영형/
편집 : 그것을 향상 시켰지만 더 이상 골프를하는 법을 모르므로 설명이 추가됩니다 🙂
@ KennyLau 의 도움으로 ~ 60 바이트를 절약했습니다.
인라인 된 16 진 변환을 방지하기 위해 이름 a
을 변경 하여 1 바이트 이상 더 작은 소형 골프Y
function f(m)c={}t=table.concat::z::c[#c+1]={}p=c[#c]Y={}for i=1,#m do k=m[i]p[#p+1]=t(k)Y[i]={}for j=1,#k
do v=m[i%#m+1]l=j%#k+1w=m[(i-2)%#m+1]h=(j-2)%#k+1Y[i][j]=v[l]+k[l]+w[l]+v[h]+v[j]+w[h]+w[j]+k[h]end
end s=''for i=1,#m do k=m[i]for j=1,k do
x=Y[i][j]k[j]=k[j]>0 and((x<2or x>3)and 0or 1)or (x==3 and 1or 0)end
s=s..t(k)end for i=1,#c do
if(s==t(c[i]))then return#c>i and-1or i-1
end end goto z end
언 골프
function f(m) -- takes a 2D array of 0 and 1s as input
c={} -- intialise c -> contains a copy of each generation
t=table.concat -- shorthand for the concatenating function
::z:: -- label z, used to do an infinite loop
c[#c+1]={} -- initialise the first copy
p=c[#c] -- initialise a pointer to this copy
a={} -- initialise the 2D array of adjacency
for i=1,#m -- iterate over the lines of m
do
k=m[i] -- shorthand for the current line
p[#p+1]=t(k]) -- saves the current line of m as a string
a[i]={} -- initialise the array of adjacency for the current line
for j=1,#k -- iterate over each row of m
do
-- the following statements are used to wraps at borders
v=m[i%#m+1] -- wrap bottom to top
l=j%#k+1 -- wrap right to left
w=m[(i-2)%#m+1] -- wrap top to bottom
h=(j-2)%#k+1 -- wrap left to right
a[i][j]= v[l] -- living cells are 1 and deads are 0
+k[l] -- just add the values of adjacent cells
+w[l] -- to know the number of alive adjacent cells
+v[h]
+v[j]
+w[h]
+w[j]
+k[h]
end
end
s='' -- s will be the representation of the current generation
for i=1,#m -- iterate over each line
do
k=m[i] -- shorthand for the current line
for j=1,#k -- iterate over each row
do
x=a[i][j] -- shorthand for the number of adjacent to the current cell
-- the next line change the state of the current cell
k[j]=k[j]>0 -- if it is alive
and((x<2 -- and it has less than 2 adjacent
or x>3) -- or more than 3 adjacent
and 0 -- kill it
or 1) -- else let it alive
or -- if it is dead
(x==3 -- and it has 3 adjacent
and 1 -- give life to it
or 0) -- else let it dead
end
s=s..t(k) -- save the representation of the current line
end
for i=1,#c -- iterate over all the generation done until now
do
if(s==t(c[i])) -- if the representation of the current generation
then -- is equal to one we saved
return#c>i -- check if it is the latest generation
and-1 -- if it isn't, it means we are in a loop -> return -1
or i-1 -- if it is, we did 2 generations without changing
-- -> return the number of generation
end
end
goto z -- if we reach that point, loop back to the label z
end
테스트 사례
다음은 몇 가지 테스트 사례입니다
function f(m)c={}t=table.concat::z::c[#c+1]={}p=c[#c]a={}for i=1,#m do k=m[i]p[#p+1]=t(k)a[i]={}for j=1,#k
do v=m[i%#m+1]l=j%#k+1w=m[(i-2)%#m+1]h=(j-2)%#k+1
a[i][j]=v[l]+k[l]+w[l]+v[h]+v[j]+w[h]+w[j]+k[h]end
end s=''for i=1,#m do k=m[i]for j=1,k do
x=a[i][j]k[j]=k[j]>0 and((x<2or x>3)and 0or 1)or (x==3 and 1or 0)end
s=s..t(k)end for i=1,#c do
if(s==t(c[i]))then return#c>i and-1or i-1
end end goto z end
print(f({{0,0,0},{0,1,1},{0,1,0}}))
print(f({{0,1,0,0},{0,1,0,0},{0,1,0,0},{0,0,0,0}}))
-- 53 generation, 15x15, takes 50-100 ms on a bad laptop
print(f({{0,0,0,0,1,1,0,1,0,0,0,0,1,0,0},
{0,1,1,0,1,1,1,1,1,1,1,0,0,0,0},
{0,1,1,1,0,1,0,1,0,0,0,0,1,0,0},
{0,0,1,0,1,1,1,0,0,1,1,1,0,1,1},
{1,1,0,0,1,1,1,0,1,1,0,0,0,1,0},
{0,0,0,0,1,1,0,1,0,0,0,0,1,0,0},
{0,1,1,0,1,1,1,1,1,1,1,0,0,0,0},
{0,1,1,1,0,1,0,1,0,0,0,0,1,0,0},
{0,0,1,0,1,1,1,0,0,1,1,1,0,1,1},
{1,1,0,0,1,1,1,0,1,1,0,0,0,1,0},
{0,0,1,0,1,1,1,0,0,1,1,1,0,1,1},
{1,1,0,0,1,1,1,0,1,1,0,0,0,1,0},
{0,0,0,0,1,1,0,1,0,0,0,0,1,0,0},
{0,0,0,0,1,1,0,1,0,0,0,0,1,0,0},
{0,1,1,0,1,1,1,1,1,1,1,0,0,0,0}}))
-- Glider on a 15x14 board
-- 840 distinct generation
-- loop afterward -> return -1
-- takes ~4-5 seconds on the same bad laptop
print(f({{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,1,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,1,0,0,0,0,0,0,0,0,0},
{0,0,0,1,1,1,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}}))
답변
젤리, 26 25 바이트
ṙ-r1¤SZµ⁺_|=3
ÇÐĿ-LiṪÇ$$?
온라인으로 사용해보십시오! 또는 모든 테스트 사례를 확인하십시오 .
더 큰 테스트 사례 ( @Katenkyo의 답변에서 ) : 15 × 15 안정 | 15 × 14 글라이더
작동 원리
ṙ-r1¤SZµ⁺_|=3 Helper link. Argument: G (grid)
This link computes the next state of G.
¤ Evaluate the three links to the left as a niladic chain.
- Yield -1.
1 Yield 1.
r Range; yield [-1, 0, 1].
ṛ Rotate the rows of G -1, 0 and 1 units up.
S Compute the sum of the three resulting grids.
Essentially, this adds the rows directly above and below each given
row to that row.
Z Zip; transpose rows and columns.
µ Convert the preceding chain into a link and begin a new chain.
⁺ Apply the preceding chain once more.
This zips back and adds the surrounding columns to each column.
_ Subtract G from the result.
Each cell now contains the number of lit cells that surround it.
| That the bitwise OR of the result and G.
Notably, 3|0 = 3|1 = 2|1 = 3.
=3 Compare each resulting number with 3.
ÇÐĿ-LiṪÇ$$? Main link. Argument: G (grid)
ÇÐL Repeatedly apply the helper link until the results are no longer
unique. Collect all unique results in a list.
$ Evaluate the two links to the left as a monadic chain:
$ Evaluate the two links to the left as a monadic chain:
Ṫ Pop the last element of the list of grids.
Ç Apply the helper link to get the next iteration.
i Get the index of the grid to the right (the first non-unique one)
in the popped list of grids. This yields 0 iff the popped list
doesn't contain that grid, i.e., the grid reached a stable state.
? If the index is non-zero:
- Return -1.
L Else, return the length of the popped list of grids.
답변
펄 154 151 144 140 137 133 129 바이트
에 +3 포함 -ap0
공백으로 구분 된 숫자 그룹의 행으로 입력으로 실행
life.pl <<< "0000 0001 0111 0010"
입력이 즉시 안정적인 경우에만 필요합니다. 다른 모든 경우에는 별도의 숫자 줄로 더 편리하게 제공 할 수도 있습니다.
life.pl
0000
0001
0111
0010
^D
그러나 이런 식으로 입력하면 즉시 안정적인 구성을 위해 0 대신 1이됩니다.
life.pl
:
#!/usr/bin/perl -ap0
map{@f=map$F[$_%@F]x3,$i-1..++$i;s%.%"0+($&+33)=~grep\$_,map{(//g)[@--1..@+]}\@f"%eeg}@Q=@F;$_=/@Q/?keys%n:$n{$_="@Q"}--||redo
이 중 거의 Mathematica를 꺾고 …
상수를 변수로 사용할 수있는 이전 펄 버전에서만이 126 바이트 솔루션이 작동합니다.
#!/usr/bin/perl -p0a
map{@f=map$F[$_++%@F]x2,-1..1;s%.%"0+($&+33)=~grep\$_,map{(//g)[@--1..@+]}\@f"%eeg}@Q=@F;$_=/@Q/?keys%n:$n{$_="@Q"}--||redo
적어도 2 개의 행이있는 경우이 123 바이트 솔루션은 모든 perl 버전에서 작동합니다.
#!/usr/bin/perl -p0a
@F=@F[-$#F..!s%.%"0+($&+33)=~grep\$_,map{(//g,//g)[@--1..@+]}\@F[-1..1]"%eeg]for@Q=@F;$_=/@Q/?keys%n:$n{$_="@Q"}--||redo
답변
루비, 207 바이트
->a{r=[];(r<<a;a=(0...a.size).map{|i|(0...a[i].size).map{|j|n=0;(-1..1).map{|u|(-1..1).map{|v|n+=a[(i+u)%a.size][(j+v)%a[i].size]}};[n==3,n>2&&n<5][a[i][j]]?1:0}})while(!r.index(a));(a==r[-1])?r.index(a):-1}
나는 각 보드의 역사를 유지하므로 보드를 얻으면 두 가지 중 하나가 발생하기 전에 본 적이 있습니다. 먼저 우리는 안정적인 입장을 찾았을 수 있으며,이 경우 우리 역사상 가장 분개 할 것입니다. 다른 가능성은 루프가 있다는 것입니다.
답변
줄리아, 92 88 바이트
f(x,r...)=x∈r?(r[k=end]==x)k-1:f(sum(i->circshift(x,[i÷3,i%3]-1),0:8)-x|x.==3,r...,x)
확인
julia> f(x,r...)=x∈r?(r[k=end]==x)k-1:f(sum(i->circshift(x,[i÷3,i%3]-1),0:8)-x|x.==3,r...,x)
f (generic function with 1 method)
julia> f([0 0 0;0 1 1;0 1 0])
2
julia> f([0 0 1 1;0 1 1 1;0 1 0 0;0 1 1 1])
2
julia> f([0 1 0 0;0 1 0 0;0 1 0 0;0 0 0 0])
-1
julia> f([0 0 0 0;0 0 0 1;0 1 1 1;0 0 1 0])
4
julia> f([0 0 0 0;0 1 1 0;0 1 1 0;0 0 0 0])
0
julia> f([0 0 0 0 1 1 0 1 0 0 0 0 1 0 0;0 1 1 0 1 1 1 1 1 1 1 0 0 0 0;0 1 1 1 0 1 0 1 0 0 0 0 1 0 0;0 0 1 0 1 1 1 0 0 1 1 1 0 1 1;1 1 0 0 1 1 1 0 1 1 0 0 0 1 0;0 0 0 0 1 1 0 1 0 0 0 0 1 0 0;0 1 1 0 1 1 1 1 1 1 1 0 0 0 0;0 1 1 1 0 1 0 1 0 0 0 0 1 0 0;0 0 1 0 1 1 1 0 0 1 1 1 0 1 1;1 1 0 0 1 1 1 0 1 1 0 0 0 1 0;0 0 1 0 1 1 1 0 0 1 1 1 0 1 1;1 1 0 0 1 1 1 0 1 1 0 0 0 1 0;0 0 0 0 1 1 0 1 0 0 0 0 1 0 0;0 0 0 0 1 1 0 1 0 0 0 0 1 0 0;0 1 1 0 1 1 1 1 1 1 1 0 0 0 0])
53
julia> f([0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;0 0 0 0 1 0 0 0 0 0 0 0 0 0 0;0 0 0 0 0 1 0 0 0 0 0 0 0 0 0;0 0 0 1 1 1 0 0 0 0 0 0 0 0 0;0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;0 0 0 0 0 0 0 0 0 0 0 0 0 0 0])
-1