Solucionado Board Boggle en Ruby -- algorithm campo con ruby camp codereview Relacionados El problema

Boggle board solver in Ruby


4
vote

problema

Español

El siguiente es mi intento de crear un solucionador de placa de boggle en Ruby. No es especialmente rápido. Me encantaría tener información sobre cómo se puede acelerar la solución, o si se puede aplicar un algoritmo diferente que sea más rápido.

La solución corresponde a mi respuesta en una pregunta relacionada en el sitio de intercambio de pila de matemáticas: https: //math.stacarkexchange. COM / A / 2908479/30919

  addCSRF3  
Original en ingles

The following is my attempt at creating a Boggle board solver in Ruby. It's not especially fast. I would love to have input on how the solution can either be sped up, or whether a different algorithm might be applied that is faster.

The solution corresponds to my answer on a related question on the Math Stack Exchange site: https://math.stackexchange.com/a/2908479/30919

require 'set' # List of words in a file, imported into sorted set for quick lookup: WORDS = SortedSet.new(open('wordlist.txt').readlines.map(&:chomp)) # Possible directions from a space and their x/y deltas: DIRS = { n: [0, -1], ne: [1, -1], e: [1, 0], se: [1, 1], s: [0, 1], sw: [-1, 1], w: [-1, 0], nw: [-1, -1] }.freeze  # Note on "Qu" -- "Qu" should require special handling in the  # Sample board we want to solve; we could create a random board with # the known configuration of the cubes.  # For 'Qu' on the Boggle board, only 'Q' is entered in @board, because the traversion routine # has special handling for 'Q' by adding a 'U' each time @board = [   %w[ N P E R ],   %w[ P L R O ],   %w[ I U N T ],   %w[ J E G V ]   ]  # This method determines the next position based on the currend position # and direction. If the position is out of bounds, it returns nil def next_pos(position, direction)   npos = [     position[0] + DIRS[direction][0],     position[1] + DIRS[direction][1]   ]   return nil if (npos[0] < 0) || (npos[1] < 0) ||                 (npos[0] > 3) || (npos[1] > 3)   npos end  @stack = [] # Stack containing the positions traversed # NB: **The letters have their own stack due to the special handling of "Qu"** @letters = [] # Corresponding letters from the positions in stack @found_words = SortedSet.new # Words found  def traverse(cpos)      # Nested method that handles popping of stack with special 'Qu' handling (because it's used more than once)     def pop_stack         @stack.pop         @letters.pop         # Special handling for "Qu":         @letters.pop if @letters.last == "Q"             end    #The longest words in my list are 15 letters - omit this check if you have more   return if @stack.length == 15     # Push current position and letters collected so far on the respective stacks   @stack << cpos   @letters << @board[cpos[0]][cpos[1]]   # Special handling for Qu:   @letters << "U" if @letters.last == "Q"    # From 2 letters onwards, check whether this path is worth pursuing   if @stack.length >= 2     unless WORDS.grep(/^#{@letters.join}/).any?       pop_stack       return     end   end    # From 3 letters onwards, check if the word is in the dictionary   if @stack.length >= 3     word = @letters.join     if WORDS.include?(word)       @found_words << word     end   end    # Try each direction in succession from the current position   DIRS.keys.each do |dir|     npos = next_pos(cpos, dir) # Calculate next pos from current pos     next unless npos # Check it is not out of bounds     # Check whether the new position had been visited in current stack     visited = false     @stack.reverse_each do |pos|       if pos == npos         visited = true         break        end     end     next if visited # Skip the new position if it had been visited     traverse(npos) # Start looking from next position   end    # Take the last position/letter off the stack before returning   pop_stack  end  # Traverse from every square on the board 4.times.map do |x|   4.times.map do |y|     traverse([x, y])   end end  puts @found_words.sort 
     

Lista de respuestas

2
 
vote

No puedo comentar sobre el estilo de Ruby, pero hay un par de puntos algorítmicos que no necesitan conocimientos de rubí para identificar.


    if @stack.length >= 2     unless WORDS.grep(/^#{@letters.join}/).any?       pop_stack       return     end   end   

Aunque ha preprocesado la lista de palabras en una estructura de datos ordenada con una búsqueda de tiempo logarítmica, 9988776655544332 parece ser un método de Enumerable y no puedo ver ninguna indicación Que hay casos especiales. En otras palabras, este es (peor caso) haciendo una exploración lineal de toda la lista de palabras. Debe haber una mejora de la velocidad masiva ya sea explotando la interfaz SortedSet o (más probable) al preprocesar la lista de palabras en un trie . Este último da la ventaja de que puede pasar el nodo actual en la pila y no debe ejecutar toda la ruta desde la raíz cada vez.


      # Check whether the new position had been visited in current stack     visited = false     @stack.reverse_each do |pos|       if pos == npos         visited = true         break        end     end   

de nuevo, esto está haciendo un escaneo lineal para algo que no necesita ser tan lento. La forma de OO sería usar un 9988776665544336 , que debe tener cheques FAST 99887776655544337 . El enfoque de optimización sobre todo sería usar un entero como una mascar de bits. Cualquiera de los dos enfoques requiere un mantenimiento mínimo en la pila.

 

I can't comment on Ruby style, but there are a couple of algorithmic points which don't need Ruby knowledge to identify.


  if @stack.length >= 2     unless WORDS.grep(/^#{@letters.join}/).any?       pop_stack       return     end   end 

Although you've preprocessed the wordlist into a sorted data structure with logarithmic time lookup, grep seems to be a method from Enumerable and I can't see any indication that there are special cases. In other words, this is (worst case) doing a linear scan of the entire wordlist. There should be a massive speed improvement either by exploiting the SortedSet interface or (more likely) by preprocessing the wordlist into a trie. The latter gives the advantage that you can pass the current node down the stack and not have to run the entire route from the root every time.


    # Check whether the new position had been visited in current stack     visited = false     @stack.reverse_each do |pos|       if pos == npos         visited = true         break        end     end 

Again, this is doing a linear scan for something which doesn't need to be so slow. The OO way would be to use a Set, which ought to have fast member? checks. The optimisation-over-all approach would be to use an integer as a bitmask. Either approach requires minimal maintenance on the stack.

 
 
   
   
2
 
vote

Prácticas generales

  • variables globales

    Tiene un guión largo, con un gran código de código libre que interactúa de manera poco clara. Tiene algunas variables, como @board , @stack1 , y @found_words , que esencialmente actúan como variables globales.

    Consideraría WORDS (o wordlist.txt ) y 9988777665544335 Para ser las entradas, pero no se definen entre sí. Ya que estará lidiando con muchas "palabras" en el código, le sugiero que lo llame el "vocabulario" que se aclare sobre lo que quiere decir.

    @found_words contiene las salidas después de ejecutar el script. Dado que es un SortedSet , sus entradas siempre están alfabetizadas, pero llama 9988777665544338 en él de todos modos.

    Sería mejor hacer claro el flujo de información. Además, las variables globales deben ser alcanzadas como variables de instancia, por lo que definiría una clase. En mi solución sugerida a continuación, consulte la última línea, que da una descripción general de cómo se adapta al código:

      Boggle.new(vocabulary, board).search { |word| puts word }   
  • backtracking

    Su código realiza retroceder, usando @stack0 para almacenar el estado del travess. Considere utilizar la recursión, lo que simplificaría un poco el código. La profundidad máxima de la recursión es de 16, por lo que no tendrá que preocuparse por el desbordamiento de la pila.

    su @stack1 y @stack2 son un tipo de redundante. Teniendo en cuenta que podría reconstruir @stack3 de la pila con un soltero, no me molestaría en mantener un seguimiento de ambos.

  • coordenadas

    El manejo de los pares de coordenadas es un poco de dolor. Si puede representar cada posición como un entero único en lugar de un par de enteros, entonces el código sería un poco más simple.

  • edificio de ruta

    En lugar de definir una función @stack4 que puede devolver @stack5 , Defina una función @stack6 que devuelve todas las posiciones vecinas válidas. La persona que llama puede simplemente iterar los resultados, y no tendrá que lidiar con el caso 99887766655443317 .

    Su bucle que realiza la prueba @stack8 es solo una operación de diferencia establecida. En mi solución a continuación, es solo 99887766555443319 .

  • Apertura de archivos

    Evite llamar @found_words0 sin cerrar el asa del archivo. La mejor manera de hacerlo es llamar @found_words1 con un bloque, en cuyo caso la manija del archivo se cerrará automáticamente al salir del bloque.

Eficiencia

La forma más sencilla de proporcionar la ilusión de desempeño es generar resultados a medida que los encuentra, en lugar de todos a la vez al final. En la solución sugerida a continuación, el método 998877665554433222 realiza un bloque de devolución de llamada que maneja cada resultado. (Por supuesto, podría adaptar la devolución de llamada para recopilar todos los resultados e imprimirlos en orden alfabético, si se requirió la clasificación).

La la mayoría de las personas que consumen mucho tiempo del código es @found_words3 , porque implica una prueba de regex para cada palabra en el vocabulario. Una ligera mejora sería @found_words4 , que evita usar un regex, y también permite el cortocircuito cuando se encuentra una coincidencia.

Desafortunadamente, la clase 99887766555443325 carece de un método , que podría lograr la prueba de manera eficiente. En ese sentido, el uso de un @found_words7 para almacenar el vocabulario no es mejor que usar un @found_words8 . (Java's @found_words9 , en contraste, admite una WORDS0 Operación. Puede probar que el conjunto de cola no está vacío, y que su primera entrada es un prefijo). Para hacer su boggle El solver eficiente, por lo tanto, requiere una mejor estructura de datos para el vocabulario. Recomiendo un trie para este propósito. Pasarás más tiempo construyendo el Trie al cargar el vocabulario, pero la búsqueda de boggle será muy rápida.

Solución sugerida

  WORDS1  
 

General practices

  • Global variables

    You have a long script, with a lot of free-floating code that interacts in unclear ways. You have some variables, such as @board, @stack, and @found_words, that essentially act as global variables.

    I would consider WORDS (or wordlist.txt) and @board to be the inputs, but they aren't defined next to each other. Since you'll be dealing with a lot of "words" in the code, I suggest calling it the "vocabulary" to be clear about what you mean.

    @found_words contains the outputs after running the script. Since it's a SortedSet, its entries are always alphabetized, but you call @found_words.sort on it anyway.

    It would be better to make the flow of information clear. Also, the global variables should be scoped as instance variables, so I would define a class. In my suggested solution below, see the last line, which gives an overview of how the code fits together:

    Boggle.new(vocabulary, board).search { |word| puts word } 
  • Backtracking

    Your code performs backtracking, using @stack to store the state of the traversal. Consider using recursion instead, which would simplify the code a bit. The maximum recursion depth is 16, so you wouldn't have to worry about the stack overflowing.

    Your @stack and @letters are kind of redundant. Considering that you could reconstruct @letters from the stack using a one-liner, I wouldn't bother keeping track of both.

  • Coordinates

    Handling coordinate pairs is a bit of a pain. If you could represent each position as a single integer instead of a pair of integers, then the code would be a bit simpler.

  • Path building

    Instead of defining a next_pos function that may return nil, define a neighbors function that returns all valid neighboring positions. The caller can just iterate over the results, and won't have to deal with the nil case.

    Your loop that performs the visited test is just a set difference operation. In my solution below, it's just neighbors(path.last) - path.

  • Opening files

    Avoid calling open without closing the file handle. The best way to do that is to call open with a block, in which case the file handle will be automatically closed when exiting the block.

Efficiency

The simplest way to provide the illusion of performance is to output results as you find them, rather than all at once at the end. In the suggested solution below, the traverse method takes a callback block that handles each result. (You could, of course, adapt the callback to gather all of the results and print them in alphabetical order, if sorting was required.)

The most time-consuming part of the code is WORDS.grep(/^#{@letters.join}/).any?, because it involves a regex test for every word in the vocabulary. One slight improvement would be WORDS.any? { |w| w.start_with? prefix }, which avoid using a regex, and also allows short-circuiting when a match is found.

Unfortunately, Ruby's SortedSet class lacks a #contains_prefix? method, which could accomplish the test efficiently. In that sense, using a SortedSet to store the vocabulary is no better than using a Set. (Java's SortedSet, in contrast, supports a .tailSet() operation. You could test that the tail set is non-empty, and that its first entry is a prefix.) To make your Boggle solver efficient, therefore, requires a better data structure for the vocabulary. I recommend a trie for this purpose. You'll spend more time building the trie when loading the vocabulary, but the Boggle search will be very fast.

Suggested solution

require 'set'  class Boggle   # Boggle searcher.   #   # The vocabulary is a set of all valid words, in uppercase.   #   # The board is a 4x4 array of characters, or an array of   # four 4-character strings, or a string of 16 characters, all   # uppercase.  'Q' represents 'Qu'.   def initialize(vocabulary, board)     @vocabulary = vocabulary     @board = board.flatten.join     raise ArgumentError.new('Invalid board size') unless @board.length == 16   end    # Search the board, yielding each word that is found.   def search      # :yields: word     seen_words = Set.new     16.times do |pos|       traverse([pos]) { |word| yield word if seen_words.add? word }     end   end  private   # Neighboring positions of a given index on a linearized 4x4 board   def neighbors(pos)     left  = (pos % 4 == 0) ? pos : pos - 1     right = (pos % 4 == 3) ? pos : pos + 1     Set[       left - 4, pos - 4, right + 4,       left,              right,       left + 4, pos + 4, right + 4,     ].delete_if { |p| p < 0 || p >= 16 }   end    def traverse(path, &block)     word = path.map { |pos| @board[pos] == 'Q' ? 'QU' : @board[pos] }.join     block.call(word) if word.length >= 3 && @vocabulary.include?(word)      (neighbors(path.last) - path).each do |pos|       traverse(path + [pos], &block)     end if @vocabulary.any? { |v| v.start_with? word }   end end   vocabulary = open('wordlist.txt') do |f|   Set.new(f.readlines.map { |line| line.chomp.upcase }) end  board = [   'NPER',   'PLRO',   'IUNT',   'JEGV', ]  Boggle.new(vocabulary, board).search { |word| puts word } 
 
 
   
   

Relacionados problema

5  Implementación de rubíes del algoritmo SoundEx  ( Ruby implementation of soundex algorithm ) 
Soy nuevo en RUBY. Normalmente el código Sling en C #. ¿Qué podría hacer para hacer esta clase de SoofEx simple más Rubyesque? SELECT1 La salida es: S...

4  Convertidor de temperatura que parece violar SRP  ( Temperature converter that seems to violate srp ) 
He escrito esta clase para dos propósitos (creo que solo este hecho muestra que este código viola srp < / a>): convertir el peso de una unidad a otra y para ...

1  Cómo reducir el número de "Si las declaraciones" jerárquicas "[CERRADO]  ( How to reduce number of hierarchical if statements ) 
cerrado . Esta pregunta necesita detalles o claridad . Actualmente no está aceptando respuestas. ...

2  Estructura de ruta para múltiples asociaciones en rieles  ( Route structure for multiple associations in rails ) 
Estoy haciendo un sitio en este momento (primer sitio de Rails, aprendiendo como código) y me preocupa que estoy complicando las rutas. Mis asociaciones se ...

6  Solución de codewars a "ascensor simple"  ( Codewars solution to simple elevator ) 
Soy nuevo en la programación (menos de un año), y me gustaría mejorar. Resolví un problema en las claquinas y copié tanto mi solución como la solución venci...

4  Implementación de rubíes del juego de la vida de Conway  ( Ruby implementation of conways game of life ) 
Estoy empezando con Ruby y decidí hacer dos implementaciones diferentes del juego de la vida de Conway. En este primero, no estoy usando cells como una clas...

11  Proyecto de proxy de Ruby Koans  ( Ruby koans proxy project ) 
Acabo de terminar el Ruby Koans y uno de los últimos proyectos fue crear una clase de proxy que envía métodos a otra clase. Me preguntaba si cambiarías algo d...

4  Repetidor para bloques de rubí  ( Repeater for blocks of ruby ) 
He escrito un módulo para repetir bloques de código, generalmente para cubrir los problemas relacionados con el eventual consistencia y los elementos de la pa...

3  Elementos de la matriz de clon al multiplicar por un escalar  ( Clone array elements when multiplying by a scalar ) 
Estoy construyendo una matriz de cuerdas para formar la representación "vacía" de un rompecabezas en el que sobrescribiré caracteres individuales según sea ne...

2  PEQUEÑO: configuración regional  ( Small setting locale ) 
Soy nuevo en rieles / Ruby y me gustaría obtener comentarios sobre mi pequeño 99887766655443312 que puede detectar el idioma del visitante. Estoy especialme...




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