El enfoque de BFS del desafío de SmartWordloy -- python campo con performance campo con breadth-first-search campo con memory-optimization camp codereview Relacionados El problema

The BFS approach to the SmartWordToy challenge


2
vote

problema

Español

Actualmente estoy trabajando en la solución de la SmartWordToy TOPCODER problema :

La compañía de juguetes "¡No puedo creer que funcione!" te ha contratado para ayudar desarrollar juguetes educativos. El proyecto actual es un juguete de palabras que Muestra cuatro letras en todo momento. Debajo de cada letra hay dos botones que causan que la letra anterior se cambie a la letra anterior o siguiente en orden alfabético. Entonces, con un solo clic de un botón la letra 'C' se puede cambiar a un 'B' o un 'D'. El alfabeto es circular, por lo que para Ejemplo Una 'A' puede convertirse en un 'Z' o un 'B' con un solo clic.

Para probar el juguete, le gustaría saber si una palabra puede ser alcanzado desde alguna palabra inicial, dada una o más restricciones. A La restricción define un conjunto de palabras prohibidas que nunca pueden ser mostrado por el juguete. Cada restricción está formateada como "x x x x", donde cada x es una cadena de letras minúsculas. Una palabra está definida por un restricción si la letra ith de la palabra está contenida en la X x de la altitud Por ejemplo, la restricción "LF A TC E" define la Las palabras "tarde", "destino", "encaje" y "cara".

Se le dará un inicio de cadena, un acabado de cadena y una cadena [] prohibir. Calcule y devuelva el número mínimo de presiones de botón. Requerido para que el juguete muestre la palabra Finalizar si el juguete fue originalmente mostrando la palabra comienzo. Recuerda, el juguete nunca debe mostrar un prohibido. palabra. Si es imposible que el juguete muestre la palabra deseada, return -1.

  Definition  Class:    SmartWordToy Method:   minPresses Parameters:   String, String, String[] Returns:  int Method signature: int minPresses(String start, String finish, String[] forbid) (be sure your method is public)   

y tratando de implementar el enfoque de BFS Mantener la cola de palabras para analizar mientras realiza un seguimiento de las palabras "visitadas" y "prohibidas".

Aquí está mi implementación actual:

  from collections import deque from itertools import product   def get_combinations(word):     """Get a next and previous word variation for every character."""     for index, char in enumerate(word):         next_char = chr(ord(char) + 1)         prev_char = chr(ord(char) - 1)          # make it a cycle         if char == 'a':             prev_char = 'z'         if char == 'z':             next_char = 'a'          yield word[:index] + next_char + word[index + 1:]         yield word[:index] + prev_char + word[index + 1:]   class SmartWordToy:     def minPresses(self, start, finish, forbid):         # if we've got the solution with no presses         if start == finish:             return 0          forbidden = set(["".join(variation)                          for item in forbid                          for variation in product(*item.split())])          # if finish is forbidden, it is never reachable         if finish in forbidden:             return -1          visited = set()          # double-ended queue for the BFS approach         queue = deque([(start, 0)])          while queue:             # take the next element from queue             word, presses = queue.popleft()              # mark word as visited             visited.add(word)              # make two changes for every character and check if we reached finish             for item in get_combinations(word):                 if item == finish:                     return presses + 1                  # put a word variation to queue if not already visited and not forbidden                 if item not in forbidden and item not in visited:                     queue.append((item, presses + 1))          # we've got no match         return -1   

Funciona en múltiples entradas de muestra, como:

  (0  

Pero, si la "distancia de edición" (el 99887776655443311 contador) se está volviendo más grande, como por ejemplo, en la siguiente entrada:

  (2  

El programa comienza rápidamente a comer mucha memoria (1 GB en solo unos segundos en mi máquina) y supera el límite de tiempo permitido también. Y, este no es ni siquiera es el peor de los casos.

¿Cómo recomendaría mejorar mi enfoque actual y hacer un seguimiento de las palabras visitadas de una manera más eficiente? Apreciará cualquier otro comentario.

Original en ingles

I'm currently working on solving the SmartWordToy TopCoder problem:

The toy company "I Can't Believe It Works!" has hired you to help develop educational toys. The current project is a word toy that displays four letters at all times. Below each letter are two buttons that cause the letter above to change to the previous or next letter in alphabetical order. So, with one click of a button the letter 'c' can be changed to a 'b' or a 'd'. The alphabet is circular, so for example an 'a' can become a 'z' or a 'b' with one click.

In order to test the toy, you would like to know if a word can be reached from some starting word, given one or more constraints. A constraint defines a set of forbidden words that can never be displayed by the toy. Each constraint is formatted like "X X X X", where each X is a string of lowercase letters. A word is defined by a constraint if the ith letter of the word is contained in the ith X of the contraint. For example, the constraint "lf a tc e" defines the words "late", "fate", "lace" and "face".

You will be given a String start, a String finish, and a String[] forbid. Calculate and return the minimum number of button presses required for the toy to show the word finish if the toy was originally showing the word start. Remember, the toy must never show a forbidden word. If it is impossible for the toy to ever show the desired word, return -1.

Definition  Class:    SmartWordToy Method:   minPresses Parameters:   String, String, String[] Returns:  int Method signature: int minPresses(String start, String finish, String[] forbid) (be sure your method is public) 

and trying to implement the BFS approach maintaining the queue of words to analyze while keeping track of "visited" and "forbidden" words.

Here is my current implementation:

from collections import deque from itertools import product   def get_combinations(word):     """Get a next and previous word variation for every character."""     for index, char in enumerate(word):         next_char = chr(ord(char) + 1)         prev_char = chr(ord(char) - 1)          # make it a cycle         if char == 'a':             prev_char = 'z'         if char == 'z':             next_char = 'a'          yield word[:index] + next_char + word[index + 1:]         yield word[:index] + prev_char + word[index + 1:]   class SmartWordToy:     def minPresses(self, start, finish, forbid):         # if we've got the solution with no presses         if start == finish:             return 0          forbidden = set(["".join(variation)                          for item in forbid                          for variation in product(*item.split())])          # if finish is forbidden, it is never reachable         if finish in forbidden:             return -1          visited = set()          # double-ended queue for the BFS approach         queue = deque([(start, 0)])          while queue:             # take the next element from queue             word, presses = queue.popleft()              # mark word as visited             visited.add(word)              # make two changes for every character and check if we reached finish             for item in get_combinations(word):                 if item == finish:                     return presses + 1                  # put a word variation to queue if not already visited and not forbidden                 if item not in forbidden and item not in visited:                     queue.append((item, presses + 1))          # we've got no match         return -1 

It works on multiple sample inputs, like:

print(SmartWordToy().minPresses("aaaa", "gzzb", {}))  # prints 9 print(SmartWordToy().minPresses("aaaa", "zaaz", {"z z a a"}))  # prints 2 print(SmartWordToy().minPresses("aaaa", "zzzz", {"z z z z"}))  # prints -1 print(SmartWordToy().minPresses("aaaa", "aaaa", {}))  # prints 0 

But, if the "edit distance" (the presses counter) is becoming larger, like for example on the following input:

SmartWordToy().minPresses("aaaa", "aagg", {}) 

The program quickly starts to eat a lot of memory (1GB in just a few seconds on my machine) and exceeds the allowed time limit as well. And, this is not even a worst case.

How would you recommend to improve my current approach and keep track of visited words in a more efficient manner? Will appreciate any other feedback.

           

Lista de respuestas

1
 
vote
vote
La mejor respuesta
 

Está marcando un vértice según lo visitado mientras lo saca de la cola y no mientras lo empuja. Por lo tanto, puede haber una gran cantidad de copias del mismo vértice en la cola, empeorando la complejidad del espacio y el tiempo.

La solución es marcar un vértice según lo visitado mientras lo presiona en la cola.

 

You are marking a vertex as visited while taking it out of the queue and not while pushing it. Hence there can be a large number of copies of the same vertex in the queue, worsening the space and time complexity.

The solution is to mark a vertex as visited while pushing it in the queue.

 
 
   
   

Relacionados problema

4  Reducción del uso de la memoria para FIZZBUZZZ IN R  ( Reducing memory usage for fizzbuzz in r ) 
He estado intentando toda la noche para que mi Fuzzbuzz use por debajo de 20 MB de RAM, pero parece que no puedo obtenerlo mucho más pequeño que esto. Inde...

4  Tirar los datos de la API, permitió la memoria agotada  ( Pulling data from api allowed memory exhausted ) 
Estoy trabajando en un proyecto donde tire los datos (JSON) de una API. Me gustaría manipular estos datos y almacenar esto como información útil en mi DB (MyS...

8  Calculando la longitud mínima promedio de números aleatorios de 0 - 1 que se suma a más de 1  ( Calculating the average minimum length of random numbers from 0 1 that adds up ) 
Mi profesor de informática nos dio una tarea para calcular el promedio después de mil millones de pruebas. Su asignación exacta fue esta: Considere gener...

1  Solicitarios de raspado y ahorro a MySQL  ( Scraping websites and saving to mysql ) 
Tengo la siguiente pieza de código que raspa los sitios web y guarda la información de regreso a MySQL. En este momento está consumiendo toda la memoria en ...

0  Cálculo de la ruta más corta posible entre dos nodos dados  ( Calculating shortest possible route between two given nodes ) 
Recientemente me encontré con este problema : Héroes en películas indias son capaces de hazañas superhumanas. Por ejemplo, Pueden saltar entre edificios...

2  Creación de archivos mensuales de un archivo anual  ( Creating monthly files from an annual file ) 
Estoy interesado en aprender una forma más sucinta (o mejor desempeño) de escribir el siguiente código de trabajo. Simplemente lo descubrí, pero es bastante d...

-1  Lista vinculada más simple en C ++?  ( Simplest linked list in c ) 
Mi contexto fue básicamente para obtener la implementación de mi lista vinculada en C ++ revisado, ya que lo escribí desde cero y quería hacerlo lo más simple...

3  Libro de trabajo _Open Copy-Pega Hoja de referencia (30k + líneas) de otro libro de trabajo solo en cambio  ( Workbook open copy paste reference sheet 30klines from other workbook on cha ) 
Trabajando en la búsqueda de una manera de reducir el tamaño de la fórmula de la célula y el uso de la memoria de mi libro de personal de Excel, se me ocurrió...

3  Cálculo del número de hojas ilegadas  ( Calculating number of unharmed leaves ) 
Recientemente me encontré con este problema que le pide que imprima el Número de hojas no comidas por las orugas: Como todos conocemos a las orugas, aman...

1  Encontrar el palíndromo más largo de la cadena dada  ( Finding the longest palindrome from the given string ) 
Recientemente me encontré con este problema que me instruye a encontrar el Subcanera más larga que es un palíndromo: Como todos sabemos, un palíndromo es...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos