Resolviendo el #TuentiChallenge4: Challenge 5 – Tribblemaker

Hola de nuevo. Con este problema, completamos la primera cuarta parte del evento. En esta ocasión, nos pedían simular el Juego de La Vida una cierta cantidad de veces y determinar si en algún momento la simulación entraba en un ciclo. La pista para descubrir que se trataba de dicho juego estaba en el nombre del creador John Conway. Google a la primera se encargaba del resto :)

Una anécdota curiosa sobre John y su juego es que al principio “lo odiaba”

Análisis del problema

El planteamiento era sencillo. Nos daban la descripción de un tablero inicial y teníamos que ir evolucionándolo hasta encontrar un bucle y nos aseguraban que habría uno antes de 100 iteraciones.

Para solucionar este problema no había un algoritmo de libro ni tampoco era necesaria una estrategia sofisticada. Seguir los pasos del planteamiento era suficiente: ir evolucionando el tablero hasta encontrar un estado repetido.

Análisis alternativo

En vista de que el planteamiento aseguraba que habría un ciclo en las primeras 100 generaciones, hubo compañeros que primero las precalcularon todas y luego buscaron entre ellas dónde estaba el ciclo. Dada las condiciones del problema, era una solución válida.

Otro análisis que encontré entre las soluciones (y este sí me gustó bastante) fue el de aprovechar la estructura del tablero (8×8 en donde hay o no hay vida) para representarlo como un entero de 64bits. La idea de los compañeros fue la de usar esa representación para comparar rápidamente si dos generaciones eran iguales.

Me gustaría agregar un granito de arena a esa optimización. Más que utilizarla únicamente como clave del tablero (ellos de todas formas usaban una matriz para trabajar y era solo al final que la transformaban a un entero), hubiese sido interesante calcular las generaciones directamente sobre un entero de 64bits, utilizando operadores a nivel de bits para contar los vecinos. Digo yo, ya puestos a optimizar a bajo nivel, hacerlo a lo grande :)

Solución enviada

En mi solución, decidí representar el tablero de manera similar a como lo proponía el problema. Usando carácteres. Solo que en mi caso los leí todos en una lista unidimensional en vez de hacerlo en una matriz. Lo hice pensando en que sería más fácil para Python comparar de ese manera.

g0 = []
for row in range(8): g0 += list(raw_input()) 
 
generations = [g0] # generations computed so far
first_gen = -1 # first generation in the loop
period = 0 # loop duration
next_gen = g0
cur_gen = 0
while period == 0: # no loop found
  next_gen = compute_step(next_gen)
  cur_gen += 1
  try:
    first_gen = generations.index(next_gen)
    period = cur_gen-first_gen # loop found
  except ValueError: pass
  generations.append(next_gen)
print first_gen, period

En la línea 10 calculo la próxima generación (código que les mostraré en un momento) mientras que entre las líneas 12 y 15 verifico que la generación calculada no exista antes. El método index lanza un excepción si no encuentra un elemento. Por lo tanto, si la generación no está repetida, el código no llegará a la línea 18 (no se actualizará “period”) y el bucle “while” continuará su rumbo.

Para avanzar una generación, implementé el siguiente código:

SIZE = 8 # board dimension
LIVE_CELL = 'X'
DEAD_CELL = '-'
def compute_neighbors(start_state, position):
  row = position / SIZE
  column = position % SIZE
  
  num_neighbors = 0

  if column > 0: num_neighbors += int(start_state[position-1] == LIVE_CELL) # previous column
  if column < SIZE-1: num_neighbors += int(start_state[position+1] == LIVE_CELL) # next column

  if row > 0: # previous row 
    num_neighbors += int(start_state[position-SIZE] == LIVE_CELL)
    if column > 0: num_neighbors += int(start_state[position-SIZE-1] == LIVE_CELL)
    if column < SIZE-1: num_neighbors += int(start_state[position-SIZE+1] == LIVE_CELL)

  if row < SIZE-1: # next row
    num_neighbors += int(start_state[position+SIZE] == LIVE_CELL)
    if column > 0: num_neighbors += int(start_state[position+SIZE-1] == LIVE_CELL)
    if column < SIZE-1: num_neighbors += int(start_state[position+SIZE+1] == LIVE_CELL)

  return num_neighbors

def compute_step(start_state):
  end_state = list(start_state) # make a copy of start_state
  for (position, cell) in enumerate(start_state):
    num_neighbors = compute_neighbors(start_state, position)
    if cell == DEAD_CELL and num_neighbors == 3: 
      end_state[position] = LIVE_CELL # new cell borned by reproduction
    elif cell == LIVE_CELL and not num_neighbors in [2,3]: 
      end_state[position] = DEAD_CELL # died for underpopulation or overcrowding
  return end_state

El método compute_neighbors que devuelve el número de vecinos de una casilla tiene un montón de condicionales pero son solo validaciones para las filas y columnas de los bordes.

Entra las soluciones de los compañeros, las que más me gustaron fueron la de Leo Antoli que también es en Python y, aunque no optimiza con un entero de 64bits, sí lo hace con un bitarray y tiene un código muy legible y la solución de Pedro Osorio, que sí utiliza el entero de 64bits, aunque no me gusta cómo obtiene el número. Yo lo hubiese hecho con desplazamientos de bits a la izquierda en vez de multiplicaciones.

Y tú ¿cómo lo resolviste?

2 thoughts on “Resolviendo el #TuentiChallenge4: Challenge 5 – Tribblemaker