a terribly hacktastic implementation of Conway’s Game of Life

I had to take a Ruby training course as part of my job recently. The instructor asked us to write Conway’s Game of Life without any conditional statements–so no “if”, no “unless”, no ternary statements, etc.

Once upon a time I would have thought she was on crack and a mean vicious lady and refused to play along, but I’ve grown up a little bit, and to my surprise, I was the only one in the class to come up with a solution.

This isn’t the full implementation, but the core of the game is calculating the state a cell will be in on the next tick. Here it is:

=begin
  The general gist is that you iterate through all the neighbors, gather the liveness states
  of each of them, and convert the array of liveness states to a string. E.g. the array of 
  states [true, false, true] would end up becoming "true_true_false" (since we sort the array).

  Ruby has the ability to pass the name of a function to a method called "send." This is useful
  if your method calls are so dynamic you have no idea what you're going to be calling, as 
  we are in this case. So we write one method for each condition: one live neighbor, two live 
  neighbors, three, etc. Using the set of states, we generate the correct method to invoke without
  ever having to resort to the use of conditional statements.

  The cases, taken from http://coderetreat.org/gol:
    Any live cell with fewer than two live neighbours dies, as if caused by underpopulation.
    Any live cell with more than three live neighbours dies, as if by overcrowding.
    Any live cell with two or three live neighbours lives on to the next generation.
    Any dead cell with exactly three live neighbours becomes a live cell.

  The one case I haven't handled is the case where two dead cells is not brought back to life, 
  but you could handle it using the strategy I've outlined.
=end

def true_true_false_false_false_false_false_false(board, cell)
  board[cell] = true
end

def true_false_false_false_false_false_false_false(board, cell)
  board[cell] = false
end

# The overcrowding case.
def true_true_true_true_false_false_false_false(board, cell)
  board[cell] = false
end

# I won't write all of them because that's boring.

def check_neighbor_status(board, cell)
  neighbors = []
  neighbors += [-1, 0, 1].map { |x| [cell[0] + x, cell[1] + 1] }
  neighbors += [-1, 0, 1].map { |x| [cell[0] + x, cell[1] - 1] }
  neighbors << [cell[0] - 1, cell[1]]
  neighbors << [cell[0] + 1, cell[1]]
  neighbors.uniq!
  # produces something like: 
  #   ['alive', 'alive', 'dead'...]
  neighbors.map { |n| board[n].to_s }.sort.reverse.join("_")
end

board = {}

board[[1,1]] = false
board[[0,1]] = false
board[[0,0]] = false
board[[2,0]] = false
board[[0,2]] = true
board[[1,0]] = false
board[[1,2]] = false
board[[2,2]] = false
board[[2,1]] = true


puts "Starting value of cell: #{board[[1,1]].inspect}"
# Generating the method name by checking the state of the neighbors.
method = check_neighbor_status(board, [1, 1])
# Using Ruby's metaprogramming abilities to invoke this method.
send(method.to_sym, board, [1, 1])

# Et voila, the state changed!
puts board[[1,1]].inspect

I was talking to a fellow dancer at an alternative blues event, of all places, and he pointed out that using a hash where the strings were the keys and the methods were values would have worked. Excellent point. The key insight is that you can use hashing to approximate conditional behavior.

Mainly, I’m posting this because did I mention I was the only person to get the solution, out of a room of about twenty professional computery types, and one of those people was my superhumanly competent coworker Lisa and I even surprised the instructor, and I *cannot* stop gloating?

I only look like a bad person, because I speak the truth. If you were me, you wouldn’t be able to stop gloating either.

Advertisements