Juego de una carta ¿Problema?

Question

Recientemente, en una entrevista de trabajo me dieron el siguiente problema:

1. escribir un script capaz de ejecutar en la línea de comandos Python

2. Se debe tomar en dos palabras en la línea de comandos (o opcionalmente, si lo prefiere, puede consultar al usuario para que suministre las dos palabras a través de la consola).

3. Teniendo en cuenta estas dos palabras: a. Asegúrese de que tengan la misma longitud b. Asegúrese de que ambas palabras estén presentes en el diccionario de palabras válidas en el idioma inglés que descargó.

4. Si es así, calcule si puede alcanzar la segunda palabra del primero mediante una serie de pasos como sigue a. Puede cambiar una letra a la vez b. Cada vez que cambie una letra, la palabra resultante también debe existir en el diccionario c. No puede agregar o eliminar letras

5. Si las dos palabras son alcanzables, la secuencia de comandos debe imprimir la ruta que conduce como una ruta única y más corta de una palabra a la otra.

6. Puede/usr/share/dict/words para su diccionario de palabras.

Mi solución consistió en utilizar la primera búsqueda de amplitud para encontrar una ruta más corta entre dos palabras. Pero al parecer eso no era lo suficientemente bueno para hacer el trabajo :(

¿Quieres que chicos saben lo que pude haber hecho mal? Muchas gracias.

import collections 
import functools 
import re 

def time_func(func): 
    import time 

    def wrapper(*args, **kwargs): 
     start = time.time() 
     res = func(*args, **kwargs) 
     timed = time.time() - start 

     setattr(wrapper, 'time_taken', timed) 
     return res 

    functools.update_wrapper(wrapper, func) 
    return wrapper 

class OneLetterGame: 
    def __init__(self, dict_path): 
     self.dict_path = dict_path 
     self.words = set() 

    def run(self, start_word, end_word): 
     '''Runs the one letter game with the given start and end words. 
     ''' 
     assert len(start_word) == len(end_word), \ 
      'Start word and end word must of the same length.' 

     self.read_dict(len(start_word)) 

     path = self.shortest_path(start_word, end_word) 
     if not path: 
      print 'There is no path between %s and %s (took %.2f sec.)' % (
       start_word, end_word, find_shortest_path.time_taken) 
     else: 
      print 'The shortest path (found in %.2f sec.) is:\n=> %s' % (
       self.shortest_path.time_taken, ' -- '.join(path)) 

    def _bfs(self, start): 
     '''Implementation of breadth first search as a generator. 

     The portion of the graph to explore is given on demand using get_neighboors. 
     Care was taken so that a vertex/node is explored only once. 
     ''' 
     queue = collections.deque([(None, start)]) 
     inqueue = set([start]) 

     while queue: 
      parent, node = queue.popleft() 
      yield parent, node 

      new = set(self.get_neighbours(node)) - inqueue 
      inqueue = inqueue | new 
      queue.extend([(node, child) for child in new]) 

    @time_func 
    def shortest_path(self, start, end): 
     '''Returns the shortest path from start to end using bfs. 
     ''' 
     assert start in self.words, 'Start word not in dictionnary.' 
     assert end in self.words, 'End word not in dictionnary.' 

     paths = {None: []} 
     for parent, child in self._bfs(start): 
      paths[child] = paths[parent] + [child] 
      if child == end: 
       return paths[child] 
     return None 

    def get_neighbours(self, word): 
     '''Gets every word one letter away from the a given word. 

     We do not keep these words in memory because bfs accesses 
     a given vertex only once. 
     ''' 
     neighbours = [] 

     p_word = ['^' + word[0:i] + '\w' + word[i+1:] + '$' 
      for i, w in enumerate(word)] 
     p_word = '|'.join(p_word) 

     for w in self.words: 
      if w != word and re.match(p_word, w, re.I|re.U): 
       neighbours += [w] 
     return neighbours 

    def read_dict(self, size): 
     '''Loads every word of a specific size from the dictionnary into memory. 
     ''' 
     for l in open(self.dict_path): 
      l = l.decode('latin-1').strip().lower() 
      if len(l) == size: 
       self.words.add(l) 

if __name__ == '__main__': 
    import sys 
    if len(sys.argv) not in [3, 4]: 
     print 'Usage: python one_letter_game.py start_word end_word' 
    else: 
     g = OneLetterGame(dict_path = '/usr/share/dict/words') 
     try: 
      g.run(*sys.argv[1:]) 
     except AssertionError, e: 
      print e 

---

Gracias por todo el gran Creo que lo que realmente me atrapó es el hecho de que repetí TODAS las palabras en el diccionario cada vez para considerar posibles palabras vecinas. En vez de eso, podría haber usado un índice invertido como señalan Duncan y Matt Anderson. he ayudado también. Muchas gracias, ahora sé lo que he hecho mal.

aquí es el mismo código con índice invertido:

import collections 
import functools 
import re 

def time_func(func): 
    import time 

    def wrapper(*args, **kwargs): 
     start = time.time() 
     res = func(*args, **kwargs) 
     timed = time.time() - start 

     setattr(wrapper, 'time_taken', timed) 
     return res 

    functools.update_wrapper(wrapper, func) 
    return wrapper 

class OneLetterGame: 
    def __init__(self, dict_path): 
     self.dict_path = dict_path 
     self.words = {} 

    def run(self, start_word, end_word): 
     '''Runs the one letter game with the given start and end words. 
     ''' 
     assert len(start_word) == len(end_word), \ 
      'Start word and end word must of the same length.' 

     self.read_dict(len(start_word)) 

     path = self.shortest_path(start_word, end_word) 
     if not path: 
      print 'There is no path between %s and %s (took %.2f sec.)' % (
       start_word, end_word, self.shortest_path.time_taken) 
     else: 
      print 'The shortest path (found in %.2f sec.) is:\n=> %s' % (
       self.shortest_path.time_taken, ' -- '.join(path)) 

    def _bfs(self, start): 
     '''Implementation of breadth first search as a generator. 

     The portion of the graph to explore is given on demand using get_neighboors. 
     Care was taken so that a vertex/node is explored only once. 
     ''' 
     queue = collections.deque([(None, start)]) 
     inqueue = set([start]) 

     while queue: 
      parent, node = queue.popleft() 
      yield parent, node 

      new = set(self.get_neighbours(node)) - inqueue 
      inqueue = inqueue | new 
      queue.extend([(node, child) for child in new]) 

    @time_func 
    def shortest_path(self, start, end): 
     '''Returns the shortest path from start to end using bfs. 
     ''' 
     assert self.in_dictionnary(start), 'Start word not in dictionnary.' 
     assert self.in_dictionnary(end), 'End word not in dictionnary.' 

     paths = {None: []} 
     for parent, child in self._bfs(start): 
      paths[child] = paths[parent] + [child] 
      if child == end: 
       return paths[child] 
     return None 

    def in_dictionnary(self, word): 
     for s in self.get_steps(word): 
      if s in self.words: 
       return True 
     return False 

    def get_neighbours(self, word): 
     '''Gets every word one letter away from the a given word. 
     ''' 
     for step in self.get_steps(word): 
      for neighbour in self.words[step]: 
       yield neighbour 

    def get_steps(self, word): 
     return (word[0:i] + '*' + word[i+1:] 
      for i, w in enumerate(word)) 

    def read_dict(self, size): 
     '''Loads every word of a specific size from the dictionnary into an inverted index. 
     ''' 
     for w in open(self.dict_path): 
      w = w.decode('latin-1').strip().lower() 
      if len(w) != size: 
       continue 
      for step in self.get_steps(w): 
       if step not in self.words: 
        self.words[step] = [] 
       self.words[step].append(w) 

if __name__ == '__main__': 
    import sys 
    if len(sys.argv) not in [3, 4]: 
     print 'Usage: python one_letter_game.py start_word end_word' 
    else: 
     g = OneLetterGame(dict_path = '/usr/share/dict/words') 
     try: 
      g.run(*sys.argv[1:]) 
     except AssertionError, e: 
      print e 

y una comparación de tiempo: (. que se encuentra en 91.57 seg)

% pitón one_letter_game_old.py feliz hola El camino más corto es :
=> feliz - arpía - arpas - ciervos - detiene - salas - infiernos - hola

% pitón one_letter_game.py feliz hola El camino más corto (encontrado en.1,71 seg) es:
=> feliz - arpía - arpas - ciervos - detiene - salas - infiernos - hola

Answer 1

Yo no diría que su solución es equivocada, pero es un poco lento. Por dos razones.

1. primero en amplitud búsqueda va a visitar todos los caminos de longitud más corta de lo necesario, además de algunos-a-todos los caminos de longitud necesarios, antes de que se le puede dar una respuesta. La mejor primera búsqueda (A *) omitirá la mayoría de las rutas irrelevantes.

2. Está comprobando cada palabra en el diccionario para la candidatura como vecino cada vez que busca vecinos. Como sugiere Duncan, puede construir una estructura de datos para buscar esencialmente a los vecinos en lugar de buscarlos.

Aquí hay otra solución a su problema:

import collections 
import heapq 
import time 

def distance(start, end): 
    steps = 0 
    for pos in range(len(start)): 
     if start[pos] != end[pos]: 
      steps += 1 
    return steps 


class SearchHeap(object): 
    def __init__(self): 
     self.on_heap = set() 
     self.heap = [] 

    def push(self, distance, word, path): 
     if word in self.on_heap: 
      return 
     self.on_heap.add(word) 
     heapq.heappush(self.heap, ((distance, len(path)), word, path)) 

    def __len__(self): 
     return len(self.heap) 

    def pop(self): 
     return heapq.heappop(self.heap) 


class OneLetterGame(object): 
    _word_data = None 

    def __init__(self, dict_path): 
     self.dict_path = dict_path 

    def run(self, start_word, end_word): 
     start_time = time.time() 
     self._word_data = collections.defaultdict(list) 
     if len(start_word) != len(end_word): 
      print 'words of different length; no path' 
      return 

     found_start, found_end = self._load_words(start_word, end_word) 
     if not found_start: 
      print 'start word %r not found in dictionary' % start_word 
      return 
     if not found_end: 
      print 'end word %r not found in dictionary' % end_word 
      return 

     search_start_time = time.time() 
     path = self._shortest_path(start_word, end_word) 
     search_time = time.time() - search_start_time 
     print 'search time was %.4f seconds' % search_time 

     if path: 
      print path 
     else: 
      print 'no path found from %r to %r' % (start_word, end_word) 

     run_time = time.time() - start_time 
     print 'total run time was %.4f seconds' % run_time 

    def _load_words(self, start_word, end_word): 
     found_start, found_end = False, False 
     length = len(start_word) 
     with open(self.dict_path) as words: 
      for word in words: 
       word = word.strip() 
       if len(word) == length: 
        if start_word == word: found_start = True 
        if end_word == word: found_end = True 
        for bucket in self._buckets_for(word): 
         self._word_data[bucket].append(word) 
     return found_start, found_end 

    def _shortest_path(self, start_word, end_word): 
     heap = SearchHeap() 
     heap.push(distance(start_word, end_word), start_word, (start_word,)) 
     while len(heap): 
      dist, word, path = heap.pop() 
      if word == end_word: 
       return path 
      for neighbor in self._neighbors_of(word): 
       heap.push(
        distance(neighbor, end_word), 
        neighbor, 
        path + (neighbor,)) 
     return() 

    def _buckets_for(self, word): 
     buckets = [] 
     for pos in range(len(word)): 
      front, back = word[:pos], word[pos+1:] 
      buckets.append(front+'*'+back) 
     return buckets 

    def _neighbors_of(self, word): 
     for bucket in self._buckets_for(word): 
      for word in self._word_data[bucket]: 
       yield word 

if __name__ == '__main__': 
    import sys 
    if len(sys.argv) not in [3, 4]: 
     print 'Usage: python one_letter_game.py start_word end_word' 
    else: 
     matt = OneLetterGame(dict_path = '/usr/share/dict/words') 
     matt.run(*sys.argv[1:]) 

Y, una comparación de tiempo:

% python /tmp/one_letter_alex.py canoe happy 
The shortest path (found in 51.98 sec.) is: 
=> canoe -- canon -- caxon -- taxon -- taxor -- taxer -- taper -- paper -- papey -- pappy -- happy 

% python /tmp/one_letter_matt.py canoe happy 
search time was 0.0020 seconds 
('canoe', 'canon', 'caxon', 'taxon', 'taxor', 'taxer', 'taper', 'paper', 'papey', 'pappy', 'happy') 
total run time was 0.2416 seconds 

Answer 2

Tal vez se espera que el * Una búsqueda con la distancia de edición como la estimación?

Answer 3

Tal vez se olvidó de agregar el shebang? > - |

O tal vez simplemente no les gustó su estilo de codificación ... Por ejemplo, no habría hecho una clase para un problema tan simple, es sobre-diseñar la solución (aunque no soy tan exigente con basar la decisión de contratación solo en eso, por supuesto).

Answer 4

Tal vez no quería trabajar en una compañía de idiotas así para empezar. Personalmente, no creo en las revisiones de código. Creo que si haces un buen trabajo revisando el portafolio y las referencias pasadas, no hay necesidad de eso en las pruebas de código spot. Las empresas con políticas estrictas como estas son las que nunca lo hacen, ya que todo lo que emplean es un código de seguimiento nerds que están pensando código 24/7. Solo mis 2 centavos.

Answer 5

Estoy de acuerdo en que sería extraño esperar que su respuesta a esta prueba de programación sea la única razón por la que eligieron a otra persona, pero en realidad hay problemas con su código. Realiza una búsqueda lineal a través del diccionario para cada paso de la ruta o cada ruta potencial. Eso podría tomar mucho tiempo para un gran diccionario y muchos caminos potenciales. También es bastante obvio que no lo probaste a fondo, ya que falla cuando no hay camino.

Si estuviera codificando esto crearía un diccionario al cargar las palabras que eliminarían la búsqueda lineal al permitirle seleccionar las siguientes palabras bastante bien directamente. Este código no es la solución completa, pero debe indicar a qué me refiero:

words = {} 

def get_keys(word): 
    """Generate keys from a word by replacing each letter in turn by an asterisk""" 
    for i in range(len(word)): 
     yield word[:i]+'*'+word[i+1:] 

def get_steps(word): 
    """Find the set of all words that can link to the given word.""" 
    steps = [] 
    for key in get_keys(word): 
     steps.extend(words[key]) 
    steps = set(steps) - set([word]) 
    return steps 

# Load the dictionary 
for word in ('start', 'stare', 'spare', 'spore'): 
    for key in get_keys(word): 
     if key not in words: 
      words[key] = [] 
     words[key].append(word) 

print(words) 
print(get_steps('stare'))