HackerRank Conway's Game of Life Algorithms

Question

I have recently finished solving the interesting HackerRank problem titled "Conway's Game Of Life." The problem statement is as follows:

Game of Life is a cellular automaton game devised by the British Mathematician John Horton Conway. The original game is a zero player game. The evolution of it depends entirely on its input.

Game of life takes place on a 2D grid. Each cell in the grid will be in one of the two possible states,

ALIVE DEAD The birth or death of the cells is based on the following rules.

A cell switches from DEAD to ALIVE if its surrounded exactly by 3 living cells. A cell remains alive if its surrounded by 2 or 3 living cells. A cell switches from being ALIVE to DEAD if its surrounded by more than 3 living cells because of over population. A cell switches from being ALIVE to DEAD if its surrounded by less than 2 cells because of under population. Each cell is surrounded by 8 cells, 4 on its sides and 4 on its corners. Cells at the extreme corners have only 3 neighbors and the cells at the extreme right, left, top and bottom of the board have 5 neighboring cells. The rules mentioned above applies for these cells as well.

This version of Game of Life takes place of a 29x29 grid, the top left cell is (0,0) and the bottom right cell is (28,28). It’s indexed as (row,column) like arrays in Computer Science. Two players play against each other. What differs this game from the original is that a cell has 2 states when its ALIVE. The two states being

WHITE BLACK The first rule differs.

When a cell switches from being DEAD to ALIVE, it assumes the color of the majority of the 3 cells. Since 3 is odd, majority always exists. Rest of the rules follow the original version of the game. Initially, all the cells are in DEAD state. The first player plays WHITE and the second player plays BLACK. Each player take turns to switch one DEAD cell to ALIVE state. The ALIVE cell takes the color assigned to the player. This goes on till each player has placed 40 cells of their respective colors on the grid. The game then starts. The alive cells of the maximum color at the end of 500 life cycles wins the game!

Input Format

The 1st player is represented by the character w (ascii value 119) and the 2nd player is represented by the character b (ascii value 98). First line of the input represents the character of the player. 29 lines follow. Each line has 29 characters without any spaces between them. Alive cells are represented by their respective characters and the dead cells are represented by - (ascii value 45).

Output

Output is 2 single spaced integers which indicates the position the cell which needs to be switched from DEAD to ALIVE.

There is a sample input and sample output, along with more details, at the official problem site here: https://www.hackerrank.com/challenges/conway

I was wondering what algorithms other hackers used. I'm right now right around the bottom of the list - any other perspective would be extremely useful.

Answer 1

The two player version of Conway’s Game of Life is extremely interesting, and so far I have developed and submitted one solid algorithm to HackerRank (attaining me a score of 41.656).

The program I wrote attempts to set up diagonals across the board to act as obstacles and prevent opponents from deploying their regular strategies, all the while providing me with more space to reproduce and spread out across the board.

Below is my implementation (in Python):

#!/usr/bin/python
# Conway's game of life - set up diagonals across the board
BOARD_SIZE = 28;

#get the next move, 
def nextMove(player, board):
    b = [] #append to b
    for s in board:
        b.append(list(s))
    
    #check up left (rows) 
    for r in range(0, BOARD_SIZE, 2):
        if (b[BOARD_SIZE - r][BOARD_SIZE] == "-"):
            return BOARD_SIZE - r, BOARD_SIZE
        else:
            row, col= diagUL(b, BOARD_SIZE - r, BOARD_SIZE)
            if (row!= -1):
                return row, col
    
    #check up left (cols)
    for c in range(0, BOARD_SIZE, 2):
        if (b[BOARD_SIZE][BOARD_SIZE - c] == "-"):
            return BOARD_SIZE, BOARD_SIZE - c
        else:
            row, col= diagUL(b, BOARD_SIZE, BOARD_SIZE - c)
            if (row!= -1):
                return row, col
    
    #check up right (rows) 
    for r in range(0, BOARD_SIZE, 2):
        if (b[r][BOARD_SIZE] == "-"):
            return r, BOARD_SIZE
        else:
            row, col= diagUR(b, r, BOARD_SIZE)
            if (row!= -1):
                return row, col
    
    #check up right (cols)
    for c in range(0, BOARD_SIZE, 2):
        if (b[0][BOARD_SIZE - c] == "-"):
            return 0, BOARD_SIZE - c
        else:
            row, col= diagUR(b, 0, BOARD_SIZE - c)
            if (row!= -1):
                return row, col

#gets the diagonals (up right and up left) 
def diagUL(bd, r, c):
    if (r == 0 or c == 0):
        return -1, -1
    elif (bd[r - 1][c - 1] == "-"):
        return r - 1, c - 1
    else:
        return diagUL(bd, r - 1, c - 1)

def diagUR(bd, r, c):
    if (r == BOARD_SIZE or c == 0):
        return -1, -1
    elif (bd[r + 1][c - 1] == "-"):
        return r + 1, c - 1
    else:
        return diagUL(bd, x + 1, y - 1)

#i/o
player = raw_input()
board = []
for row in xrange(0, 29):
    board.append(raw_input())
a,b = nextMove(player, board)
print a,b