Recibiendo palabras (Parte 2)

Ahora que podemos recibir las palabras entradas por el jugador, el computador debe revisar si la palabra se puede construir con las letras disponibles. ¡Este tipo de cálculos son la razón de existir de los computadores!
Para averiguar si una palabra se encuentra, tenemos que revisar primero si la primera letra está disponible. Además, debemos tratar de formar la palabra a partir de cada aparición de la letra, es decir debemos repetir el proceso para cada vez que la letra se encuentre. Para esto se escribí la función start_positions, que busca entre los dados las ubicaciones de la letra, y entrega la lista de coordenadas en las que se encuentra. Entrega una lista vacía si la letra no se encuentra.

def start_positions(letter):
 positions = []
    for row in range(4):
     for column in range(4):
         if dice[facedie[row][column]][face[row][column]] == letter:
             positions.append([row, column])
    return positions

Para mejorar un poco la interacción, modifico el ciclo principal para que muestre los dados después de cada intento. Este es un execelente ejemplo de lo que sucede en un proceso de desarrollo, al necesitar afinar la interacción a partir de la evaluación del uso real. Además, como la función word_is_valid ahora entregará la lista de coordenadas de la palabra formada, entonces para saber si la palabra fue encontrada, tenemos que revisar el último elemento de la lista.

while True:
 print_face()
 word = raw_input(">")
 word = word.upper() #todo en mayusculas
 if word == "X":
     print "Adiós"
     break
 elif len(word) < 3:
     print "Demasiado Corta"
 else:
     word_chain = word_is_valid(word)
     if word_chain[-1] != False:
         print "Válida", word_chain
     else:
         print "Inválida"

Ahora si, pasemos a la pulpa...
El proceso de encontrar la palabra consiste en a partir de la primera letra, buscar la siguiente en las casillas adyacentes, teniendo en cuenta de no buscar en casillas que no existen y sobretodo teniendo en cuenta no usar letras que ya han sido usadas. Si entre las adyacentes encontramos la siguiente letra, pasamos a esta y repetimos el mismo proceso de buscar en las adyacentes hasta que se han acabado las letras de la palabra. Si las letras se acaban y hemos logrado encontrarlas todas en línea, quiere decir que la palabra existe. Si alguna letra no la encontramos, debemos ir hacia atrás para buscar otras posibilidades. Este tipo de procesos son ideales para ser modelados en código por medio de recursión. la recursión es el proceso de llamar la función desde ella misma, hasta que alguna condición permita terminar la cadena. La función find_word es una función recursiva, que se llama a si misma mientras la palabra tenga letras. Cuando la llamamos, no le entrego la palabra completa, sino el pedazo de la palabra que falta por encontrar. De esta forma, si se han acabado las letras, sabremos que la palabra fue encontrada.
Para buscar en las casillas adyacentes, uso la matriz matrix que guarda las coordenadas relativas a la casilla. Recorro cada una de ellas en un ciclo (cada elemento es la variable transform), y en este ciclo, si la letra es encontrada, llamo recursivamente find_word.

def find_word(word, row, column, used):
 matrix = [[-1, -1], [-1,0], [-1, 1],
           [0, -1],         [0,1],
           [1, -1], [1, 0], [1,1] ]
 if word == "":
     return []    #fin de la palabra-cerrar recursion
 letter = get_letter(word,0)
 if letter == "Qu":
     new_word = word[2:]
 else:
     new_word = word[1:]
 for transform in matrix:
     new_row = row + transform[0]
     new_column = column + transform[1]
     if  new_row < 0 or new_column < 0 or \
             new_row > 3 or new_column > 3 or \
             used[new_row][new_column] == 1:
         pass
     elif dice[facedie[new_row][new_column]][face[new_row][new_column]] == letter:
         used_copy = used
         used_copy[new_row][new_column] = 1
         return [[new_row, new_column]] + \
             find_word(new_word, new_row, new_column, used_copy)
 return [False]

Ya se puede ver en esta función un problema que surge de la existencia de la letra "Qu". En los dados , puede salir la letra "Qu" que debe contarse como una sola letra a pesar de contener dos letras. Esto implica que en todas las palabras que se entren la palabra es inválida si hay una "q" a la que no le sigue un "u", y además que cuando aparezca "qu" debemos tratarla como una sola letra.
Finalmente, hay que hacer algunas adiciones a la función word_is_valid para que busque la primera letra de la palabra, y a partir de esta inicie la recursion con la función find_word.

def word_is_valid(word):
  letter = get_letter(word,0)
  if letter == "":
      return [False]
  elif letter == "Qu":
      new_word = word[2:]
  else:
      new_word = word[1:]
  for position in start_positions(letter):
      used = [[0,0,0,0], [0,0,0,0], [0,0,0,0], [0,0,0,0]]
      used[position[0]][position[1]] = 1
      used_copy = used
      word_chain = [[position[0],position[1]]] + \
              find_word(new_word, position[0], position[1], used_copy)
      if word_chain[-1] != False:
          return word_chain
  return [False]

Y listo por ahora... En la próxima empezaremos a crear la interfaz visual para nuestro programa (además de buscar un pequeño error que hace que algunas veces no se detecte la palabra correctamente....)
Como siempre aquí está el código:

import random

dice = [ ["T", "O", "E", "S", "S", "I"],
       ["A", "S", "P", "F", "F", "K"],
       ["N", "U", "I", "H", "M", "Qu"],
       ["O", "B", "J", "O", "A", "B"],
       ["L", "N", "H", "N", "R", "Z"],
       ["A", "H", "S", "P", "C", "O"],
       ["R", "Y", "V", "D", "E", "L"],
       ["I", "O", "T", "M", "U", "C"],
       ["L", "R", "E", "I", "X", "D"],
       ["T", "E", "R", "W", "H", "V"],
       ["T", "S", "T", "I", "Y", "D"],
       ["W", "N", "G", "E", "E", "H"],
       ["E", "R", "T", "T", "Y", "L"],
       ["O", "W", "T", "O", "A", "T"],
       ["A", "E", "A", "N", "E", "G"],
       ["E", "I", "U", "N", "E", "S"] ]

face = [ [0,0,0,0], [0,0,0,0], [0,0,0,0], [0,0,0,0] ]
facedie = [ [0,0,0,0], [0,0,0,0], [0,0,0,0], [0,0,0,0] ]

def new_dice_set():
  available_dice = range(16)
  for row in range(4):
      for column in range(4):
          facedie[row][column] = random.randint(0,len(available_dice) - 1)
          available_dice.pop(facedie[row][column])

def new_shuffled_group():
  for row in range(4):
      for column in range(4):
          face[row][column] = random.randint(0,5)

def print_face():
  for row in range(4):
      for column in range(4):
          print dice[facedie[row][column]][face[row][column]], " ",
      print ""

def get_letter(word, index):
  internal_index = 0
  real_index = 0
  if word == "":
      return ""
  while internal_index < index:
      letter = word[real_index]
      if letter == "Q":
          real_index = real_index + 1
          if real_index < len(word):
              letter = word[real_index]
          elif letter != "U":
              return ""
      real_index = real_index + 1
      internal_index = internal_index + 1
  result = word[real_index]
  if result == "Q":
      real_index = real_index + 1
      if real_index < len(word):
          result = result + "u"
  return result

def start_positions(letter):
  positions = []
  for row in range(4):
      for column in range(4):
          if dice[facedie[row][column]][face[row][column]] == letter:
              positions.append([row, column])
  return positions

def find_word(word, row, column, used):
  matrix = [[-1, -1], [-1,0], [-1, 1],
            [0, -1],         [0,1],
            [1, -1], [1, 0], [1,1] ]
  if word == "":
      return []    #fin de la palabra-cerrar recursion
  letter = get_letter(word,0)
  if letter == "Qu":
      new_word = word[2:]
  else:
      new_word = word[1:]
  for transform in matrix:
      new_row = row + transform[0]
      new_column = column + transform[1]
      if  new_row < 0 or new_column < 0 or \
              new_row > 3 or new_column > 3 or \
              used[new_row][new_column] == 1:
          pass
      elif dice[facedie[new_row][new_column]][face[new_row][new_column]] == letter:
          used_copy = used
          used_copy[new_row][new_column] = 1
          return [[new_row, new_column]] + \
              find_word(new_word, new_row, new_column, used_copy)
  return [False]

def word_is_valid(word):
  letter = get_letter(word,0)
  if letter == "":
      return [False]
  elif letter == "Qu":
      new_word = word[2:]
  else:
      new_word = word[1:]
  for position in start_positions(letter):
      used = [[0,0,0,0], [0,0,0,0], [0,0,0,0], [0,0,0,0]]
      used[position[0]][position[1]] = 1
      used_copy = used
      word_chain = [[position[0],position[1]]] + \
              find_word(new_word, position[0], position[1], used_copy)
      if word_chain[-1] != False:
          return word_chain
  return [False]

new_shuffled_group()
new_dice_set()

while True:
  print_face()
  word = raw_input(">")
  word = word.upper() #todo en mayusculas
  if word == "X":
      print "Adiós"
      break
  elif len(word) < 3:
      print "Demasiado Corta"
  else:
      word_chain = word_is_valid(word)
      if word_chain[-1] != False:
          print "Válida", word_chain
      else:
          print "Inválida"

Imágenes

• sergis blog: http://www.flickr.com/photos/srgblog/2772659768/
• brew books http://www.flickr.com/photos/brewbooks/3318600273/
• Quinn-S: http://www.flickr.com/photos/q-shan/3205236312/