콘웨이의 생명 게임(Conway's game of life)은 영국의 수학자 존 호튼 콘웨이가 고안해낸 세포 자동자 게임이다. 바둑판처럼 정사각형의 여러 칸으로 나뉘어진 공간에서 한 칸에 한 마리씩 있는 세포들의 삶과 죽음이 펼쳐지는 게임이라 할 수 있다. 규칙은 단순하지만 만들어 낼 수 있는 패턴이 무수히 많아서 관심을 끈 게임이기도 하며, 컴퓨터 과학에서도 다루고 있는 게임이다.
----- 규칙 ------
다음 세대로 넘어갈 때 세포들의 생사가 결정되는데, 인접한 8개의 칸을 기준으로 하며 그 기준은 다음과 같다.
어떤 칸과 인접한 8칸 중 정확히 3칸에 세포가 살아 있다면 해당 칸의 세포는 그 다음 세대에 살 수 있다. (계속 살아 있거나 죽은 상태에서 살아난다.)
어떤 칸과 인접한 8칸 중 정확히 2칸에 세포가 살아 있다면 해당 칸의 세포는 살아 있는 상태 혹은 죽은 상태를 계속 유지한다.
그 이외의 경우[1] 해당 칸의 세포는 다음 세대에 고립돼 죽거나 혹은 주위가 너무 복잡해져서 죽는다. (계속 죽어 있거나 이미 살아 있는 상태라면 죽는다.)
우리의 목표는 다음과 같다.
1.총 격자의 크기 n x n 에서 n 을 입력 받는다.
2.살아있는 세포는 1, 죽은세포는 0으로 표시한다.
3.초기값(처음에 살아있는 세포의 위치)를 (x,y) 형태로 입력받는다. 이때 특정 숫자 혹은 숫자쌍이나 단어를 입력할때까지 계속 입력받는다.(입력종료) (또는 파일로 불러와도 된다.)
3.시행횟수(세대 수)를 입력하고 n세대가 지난 후의 결과를 n*n행렬이나 배열 형태로 반환한다.
12개의 풀이가 있습니다.
n = int(input('격자 크기 : '))
board = []
for i in range(n):
x = []
for j in range(n):
x.append(0)
board.append(x)
a = input('처음에 살아있을 세포 위치 (x y) (끝내기:0)\n')
while a!='0':
x, y = map(int, a.split())
board[x][y] = 1
a = input()
def nextgene(b):
change = []
for i in range(n):
for j in range(n):
cells = []
for x in range(max(i-1, 0), min(i+2, n)):
for y in range(max(j-1, 0), min(j+2, n)):
cells.append(b[x][y])
c = cells.count(1)
if c==3:
change.append((i, j, 1))
elif c==2:
pass
else:
change.append((i, j, 0))
for x in change:
b[x[0]][x[1]] = x[2]
return b
for i in range(int(input("몇 세대 까지? : "))):
for i in board:
print(''.join(map(str, i)))
print()
board = nextgene(board)
for i in board:
print(''.join(map(str,i)))
시간 복잡도는 test * n * n * 8 이 되겠네요. 규칙 따라가면서 짜봤습니다.
val num = scala.io.StdIn.readInt() // 격자 크기
val board = Array.ofDim[Int](num, num) // n*n 격자
import scala.util.control.Breaks._
breakable {
while(true){
val Array(a, b) = scala.io.StdIn.readLine().split(" ").map(_.toInt) // 살아있는 세포 위치
if(a == -1 && b == -1) break()
board(a)(b) = 1
}
}
val t = scala.io.StdIn.readInt() // 시행횟수
def cntAlive(idx1: Int, idx2: Int):Boolean = { // 살아있는 세포 인지 파악
if(idx1 < 0 || idx1 >= num || idx2 < 0 || idx2 >= num || board(idx1)(idx2) == 0) false
else true
}
val direction = List((0,1),(1,0),(-1,0),(0,-1),(1,-1),(-1,1),(1,1),(-1,-1)) // 8 가지 방향
for(i <- 1 to t){
for(j <- 0 until num; k <- 0 until num){
var cnt = 0 //살아있는 세포 수 세기
for((a, b) <- direction){
if(cntAlive(j + a, k + b)) cnt += 1
}
cnt match {
case 2 => board(j)(k)
case 3 => board(j)(k) = 1
case _ => board(j)(k) = 0
}
}
}
board.map(_.toList).toList.foreach(println)
따로 주석이 필요 없게끔 코드를 작성했습니다.
import java.util.NoSuchElementException;
import java.util.Scanner;
import java.util.StringTokenizer;
public class ConwaysGameOfLife {
private int generation = 0;
private Cell cell = null;
private ConwaysGameOfLife() {}
private static void print(String out) {
System.out.print(out);
}
private static void println(String out) {
System.out.println(out);
}
private static String readLine() {
Scanner scanner = new Scanner(System.in);
try {
return scanner.nextLine();
} catch (NoSuchElementException | IllegalStateException e) {
e.printStackTrace();
}
return "";
}
public static void main(String[] args) {
ConwaysGameOfLife game = new ConwaysGameOfLife();
game.getInput();
game.play();
game.showResult();
}
private void getInput() {
inputSizeofSquare();
inputCellAlive();
inputGeneration();
}
private void inputSizeofSquare() {
print("input size of square (X => X * X): ");
String input = readLine();
int size = 0;
try {
size = Integer.valueOf(input);
} catch (NumberFormatException e) {
e.printStackTrace();
}
setCellSize(size);
}
private void inputCellAlive() {
while (true) {
print("[type \"enough\" to stop] input alive cell (x,y): ");
String input = readLine();
if (input.equals("enough")) {
break;
}
StringTokenizer tokenizer = new StringTokenizer(input, ",");
int x, y;
try {
x = Integer.valueOf(tokenizer.nextToken());
y = Integer.valueOf(tokenizer.nextToken());
} catch (NumberFormatException | NoSuchElementException e) {
e.printStackTrace();
x = 0;
y = 0;
continue;
}
cell.setAlive(x, y);
}
}
private void inputGeneration() {
print("Nth Generation: ");
String input = readLine();
try {
setGeneration(Integer.valueOf(input));
} catch (NumberFormatException e) {
e.printStackTrace();
}
}
private void play() {
for (int i = 0; i < generation; i++) {
cell.step();
}
}
private void showResult() {
cell.draw();
}
private void setCellSize(int cellSize) {
cell = new Cell(cellSize);
}
private void setGeneration(int generation) {
this.generation = generation;
}
class Cell {
private final int cellSize;
private final boolean[][] cell;
Cell(int x) {
cellSize = x;
cell = new boolean[x][x];
for (boolean[] b : cell) {
for (boolean c : b) {
c = false;
}
}
}
boolean isAlive(int x, int y) {
return cell[x][y];
}
void setAlive(int x, int y) {
cell[x][y] = true;
}
private int countAdjacentCellsAlive(int x, int y) {
int count = 0;
for (int i = x - 1; i <= x + 1; i++) {
if (i < 0 || i >= cellSize) {
continue;
}
for (int j = y - 1; j <= y + 1; j++) {
if (j < 0 || j >= cellSize) {
continue;
}
if (i == x && j == y) {
continue;
}
if (cell[i][j]) {
count++;
}
}
}
return count;
}
private void step() {
for (int i = 0; i < cellSize; i++) {
for (int j = 0; j < cellSize; j++) {
int count = countAdjacentCellsAlive(i, j);
if (count == 3) {
cell[i][j] = true;
} else if (count != 2) {
cell[i][j] = false;
}
}
}
}
void draw() {
println("show result...");
for (int i = 0; i < cellSize; i++) {
println("");
for (int j = 0; j < cellSize; j++) {
if (cell[i][j]) {
print("[ O ]");
} else {
print("[ X ]");
}
}
println("");
}
}
}
}
입력 및 결과 입니다.
input size of square (X => X * X): 6 [type "enough" to stop] input alive cell (x,y): 0,0 [type "enough" to stop] input alive cell (x,y): 0,4 [type "enough" to stop] input alive cell (x,y): 0,5 [type "enough" to stop] input alive cell (x,y): 1,0 [type "enough" to stop] input alive cell (x,y): 1,3 [type "enough" to stop] input alive cell (x,y): 1,4 [type "enough" to stop] input alive cell (x,y): 1,5 [type "enough" to stop] input alive cell (x,y): 2,2 [type "enough" to stop] input alive cell (x,y): 2,4 [type "enough" to stop] input alive cell (x,y): 3,0 [type "enough" to stop] input alive cell (x,y): 3,1 [type "enough" to stop] input alive cell (x,y): 3,2 [type "enough" to stop] input alive cell (x,y): 3,4 [type "enough" to stop] input alive cell (x,y): 3,5 [type "enough" to stop] input alive cell (x,y): 4,4 [type "enough" to stop] input alive cell (x,y): 4,2 [type "enough" to stop] input alive cell (x,y): 4,1 [type "enough" to stop] input alive cell (x,y): 5,1 [type "enough" to stop] input alive cell (x,y): 5,3 [type "enough" to stop] input alive cell (x,y): 5,5 [type "enough" to stop] input alive cell (x,y): enough Nth Generation: 4 show result...
[ X ][ X ][ X ][ X ][ X ][ X ]
[ X ][ X ][ O ][ X ][ O ][ O ]
[ X ][ X ][ O ][ X ][ X ][ O ]
[ X ][ O ][ O ][ X ][ O ][ O ]
[ O ][ X ][ X ][ X ][ X ][ X ]
[ X ][ O ][ O ][ O ][ O ][ X ]
Ruby
require 'matrix'
def play_life_game
# initialize grid
live, dead, n = 1, 0, gets.to_i
grid, idxes = Matrix.zero(n), (0...n).map {|row| [row].product [*0...n] }
alive_cells = File.readlines("input.dat").map {|ln| ln.split.map(&:to_i) }
alive_cells.each {|pos| col,row = pos; grid.send(:[]=, row, col, live) }
# make generations
cnt = ->g,r,c { g.minor(r-(r<=>0)..r+1, c-(c<=>0)..c+1).sum - g[r,c] }
nxt = ->g,r,c,lives=cnt[g,r,c] { lives == 3 ? live : (lives == 2 ? g[r,c] : dead) }
make = ->prev,_ { Matrix[*idxes.map {|row| row.map {|idx| nxt[prev, *idx]}}] }
puts gets.to_i.times.reduce(grid, &make).to_a.map(&:join)
end
Input file
1 0
2 1
0 2
1 2
2 2
Test
# glider pattern
$stdin = StringIO.new("4\n0\n") # generation 0 time
expect { play_life_game }.to output( "0100\n" +
"0010\n" +
"1110\n" +
"0000\n" ).to_stdout
$stdin = StringIO.new("4\n4\n") # generation 4 times
expect { play_life_game }.to output( "0000\n" +
"0010\n" +
"0001\n" +
"0111\n" ).to_stdout
__author__ = 'SANG WOOK KIM'
class conway_game():
import numpy as np
def __init__(self, n = 6, x = 2):
self.n = n # size of map
self.x = x # number of generation
def mapping(self, input_loc):
map = np.zeros((self.n,self.n), dtype = int)
for loc in input_loc:
x,y = loc
try:
map[int(x)][int(y)] = 1
except:
pass
return map
def generation(self, map):
live_cell = []
#n = self.n
for x in range(1,self.n-1):
for y in range(1, self.n-1):
criterion = map[x][y]
number_one = 0
for i in range(x-1, x+2):
for j in range(y-1, y+2):
if map[i][j] == 1 and (i, j) != (x, y):
number_one += 1
if number_one == 3 :
live_cell.append((x,y))
elif number_one == 2 and criterion == 1 :
live_cell.append((x,y))
return live_cell
def ask_input(self):
input_loc = []
while (True):
loc = input("세포가 살아있는 곳의 좌표를 입력해주세요 <break 입력 시 입력 종료> >>> ")
if loc == 'break':
break
input_loc.append((loc[0], loc[-1]))
return input_loc
def forward(self):
for time in range(self.x):
if time == 0:
input_loc = self.ask_input()
map = self.mapping(input_loc)
print(map)
input_loc = self.generation(map)
print(input_loc)
map = self.mapping(input_loc)
print('\n***final result***\n')
print(map)
return map
conway = conway_game(n = 6, x = 2)
result = conway.forward()
import numpy as np
import random
def summ_around(row,col,board):
ans=0
moving = [[-1,-1],[0,-1],[1,-1], # 왼쪽열 세로로 3개
[-1,0],[1,0], # 해당열 위아래 2개
[-1,1],[0,1],[1,1]] # 오른쪽열 세로로 3개
for step in moving:
t1 = row +step[0]
t2 = col +step[1]
if t1<0 or t2<0 or t1>= board.shape[0] or t2>= board.shape[1]:
continue
ans += board[t1,t2]
return(ans)
def solution(n)
copy = board.copy()
for _ in range(n):
for i in range(n):
for j in range(n):
t1=summ_around(i,j,copy) # 근처 8개의 합을 구하기
if t1 ==3:
copy[i,j]=1
elif t1==2:
continue
else:
copy[i,j]=0
return(copy)
print('n을 입력하세요')
k = input()
n= int(k)
board = np.zeros(n*n).reshape([n,n])
while True:
print('x좌표값을 입력하세요');x= int(input())
print('y좌표값을 입력하세요');y= int(input())
if x<0 or y<0 or x>= board.shape[0] or y>= board.shape[1]:
break
board[x,y]=1
solution(n)
def conway_init(con,init):
arr = [[0 for j in range(con)] for i in range(con)]
for i in init:
arr[i[0]][i[1]] = 1
return arr
def conway_nearlife(board,x,y):
return sum(board[x+i][y+j] for i in range(-1,2)
for j in range(-1,2) if x+i >= 0 and x+i < len(board) and y+j >=0 and y+j < len(board[0]))-board[x][y]
def conway_gen(mat, count):
new = []
for i in range(len(mat)): new.append(mat[i][:])
for i in range(len(mat)):
for j in range(len(mat[0])):
nearlife = conway_nearlife(mat,i,j)
if nearlife == 3: new[i][j] = 1
elif nearlife == 2: pass
else: new[i][j] = 0
if count == 1: return new
count -= 1
return conway_gen(new, count)
if __name__=="__main__":
init_coord = set()
n = int(input('격자 크기: '))
while 1:
coord = input(('초기값을 (x,y)형태로 입력(입력종료는 엔터): '))
if coord == '': break
if isinstance(eval(coord), tuple):
if eval(coord)[0] < n and eval(coord)[1] < n and len(eval(coord)) == 2:
init_coord.add(eval(coord))
print('\n초기값: {}\n'.format(init_coord))
g = int(input('세대수: '))
x = conway_init(n,init_coord)
print('\n0세대')
for i in range(n):
for j in range(n):
print('{} '.format(x[i][j]),end='')
print('')
result = conway_gen(x,g)
print('\n{}세대'.format(g))
for i in range(n):
for j in range(n):
print('{} '.format(result[i][j]),end='')
print('')
def parse(raw_data):
data = [int(x) for x in raw_data.split()]
N = data.pop(0)
arr = [[0 for y in range(N)] for x in range(N)]
x, y = data.pop(0), data.pop(0)
while x >= 0: # (-1, -1) 전까지
arr[x][y] = 1
x, y = data.pop(0), data.pop(0)
return N, arr, data[0]
def cells_around(N, board, x, y):
offset = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
return sum([board[x + dx][y + dy] for (dx, dy) in offset if x + dx in range(N) and y + dy in range(N)])
def next_gen(N, cur):
next = [[0 for y in range(N)] for x in range(N)]
for i in range(N):
for j in range(N):
cells = cells_around(N, cur, i, j)
if cells is 3:
next[i][j] = 1
elif cells is 2:
next[i][j] = cur[i][j]
return next
N, board, G = parse(raw_data)
for i in range(G):
board = next_gen(N, board)
print(i + 1,'th generation:')
for row in board:
print(row)
print()
size = int(input("격자의 크기 ")) # 격자의 크기 입력
def make_square(square_size):
square = []
for p in range(square_size): # 크기가 n*n 인 격자 생성
in_list = []
for q in range(square_size):
in_list.append(0)
square.append(in_list)
return square
def enter_cell(cell_list): # 살아있는 세포의 위치 입력
print("세포의 위치를 입력합니다. 그만하려면 end를 입력")
while 1:
location = input("x,y로 좌표 입력. 최대값은 %d : " % (size)).split(',')
print(location)
if len(location) == 2:
cell_list[int(location[0]) - 1][int(location[1]) - 1] = 1
else:
break
def check_cell(x, y, cell_list): # x,y cell주변의 세포 값 확인 함수 return으로 cell의 개수 리턴
cell_count = 0
pm = [-1, 0, 1]
for r in pm:
for c in pm:
if x+r < 0 or y+c < 0 or x+r >= size or y+c >= size: # x,y의 값을 변화시켰을때 범위를 넘어가는 경우를 방지
continue
elif r == 0 and c == 0:
continue
else:
if cell_list[x+r][y+c]:
cell_count += 1
return cell_count
def next_generation(count, cell_list): # 시행횟수 count입력 받음
while count > 0:
temp = make_square(size)
for a in range(size):
for b in range(size):
if check_cell(a, b, cell_list) == 2:
temp[a][b] = cell_list[a][b]
elif check_cell(a, b, cell_list) == 3:
temp[a][b] = 1
else:
temp[a][b] = 0
cell_list = temp
count -= 1
return cell_list
cell = make_square(size)
enter_cell(cell)
try_count = int(input("시행 횟수(세대 수)? "))
cell = next_generation(try_count, cell)
for c in cell:
print(c)
import random
import copy
direc = ((-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1))
def display(L):
for line in L:
print(' '.join(map(str, line)))
def conway(L, k):
for _ in range(k):
T = [[0 for i in range(n)] for j in range(n)]
for x in range(n):
for y in range(n):
c = 0
for dx, dy in direc:
nx = x + dx
ny = y + dy
if 0 <= nx < n and 0 <= ny < n and L[nx][ny] == 1:
c += 1
if c == 3:
T[x][y] = 1
elif c == 2:
T[x][y] = L[x][y]
else:
T[x][y] = 0
display(L)
n = 7
L = [[int(random.random() < 0.4) for i in range(n)] for j in range(n)]
display(L)
파이썬 3입니다
인접한 세포의 수를 세는 함수를 정의한 다음에 시행했습니다.
n, N = tuple(map(int, input('한 변의 길이와 시행 횟수 입력 (공백으로 구분):').split())) # 격자 한변의 길이, 총 시행 횟수
sqr = [[0 for _ in range(n)] for _ in range(n)] # n * n의 격자 생성
print('처음에 살아있는 세포의 위치 입력 ((x, y) 또는 x, y 형태)')
while True: # 0이나 빈칸이 입력될 때 까지 (x, y)의 좌표를 받는다
temp = input()
if temp == '0' or temp == '':
break
alive = tuple(map(int, temp.strip('()').split(',')))
sqr[alive[0]][alive[1]] = 1
def adj(grid, i0, j0): # 인접한 1의 개수를 세는 함수
count = 0
for di in (-1, 0, 1):
if i0 + di not in range(n):
continue
for dj in (-1, 0, 1):
if j0 + dj not in range(n):
continue
elif di == 0 and dj == 0:
continue
count += grid[i0 + di][j0 + dj]
return count
# 규칙
print('######## 초기 상태 ########')
for k in range(n):
for m in range(n):
print(sqr[k][m], end=' ')
print()
print()
for i in range(N):
print('######## {} 번째 시행 ########'.format(i + 1))
temp = [[0 for _ in range(n)] for _ in range(n)]
for k in range(n):
for m in range(n):
temp[k][m] = int(adj(sqr, k, m) == 3) + sqr[k][m] * (adj(sqr, k, m) == 2)
print(temp[k][m], end=' ')
print()
print()
sqr = temp.copy()
'''
Conway's game of life
'''
def printspace(space):
for i in range(1, len(space)-1):
for j in range(1, len(space)):
if space[i][j] == 1:
print('■', end=' ')
else:
print('□', end=' ')
print()
size = int(input('input size of space: '))
space = [[0 for i in range(size+2)] for i in range(size+2)]
while True:
try:
x, y = map(lambda x: int(x.strip()), input('input position of alive cell: ').split())
space[y][x] = 1
printspace(space)
except:
break
gen = int(input('input number of generation: '))
for i in range(gen):
for y in range(1, size+1):
for x in range(1, size+1):
neighbor = sum(space[y-1][x-1:x+2]) + sum(space[y+1][x-1:x+2]) + space[y][x-1] + space[y][x+1]
if neighbor == 3:
space[y][x] = 1
elif neighbor == 2:
pass
else:
space[y][x] = 0
print(f'after {i+1}th generation')
printspace(space)