Foto cortesía:jimray
Hemos visto en un artículo anterior de introducción a awk que awk puede ser una herramienta eficaz para todo, desde pequeñas frases ingeniosas hasta algunas aplicaciones interesantes. Ciertamente, hay lenguajes más complejos a nuestra disposición si la situación lo requiere; me vienen a la mente perl y python. Es mejor dejar las aplicaciones que requieren soporte de red, acceso a bases de datos, interfaces de usuario, datos binarios o soporte y complejidad de bibliotecas más extensos a otros lenguajes con mejor soporte en estas áreas.
Sin embargo, awk es un excelente lenguaje para probar algoritmos y aplicaciones con cierta complejidad , especialmente donde el problema se puede dividir en partes que se pueden transmitir como parte de una canalización. Es una herramienta ideal para aumentar las características de la programación de shell, ya que es omnipresente; se encuentra de alguna forma en casi todos los sistemas Unix/Linux/BSD. Muchos problemas relacionados con texto, líneas de registro o tablas de símbolos se resuelven fácilmente o, al menos, se crean prototipos con awk junto con otras herramientas que se encuentran en los sistemas Unix/Linux.
Si bien awk se presta bien para operar ingresando una línea a la vez, procesando y luego enviando algo de salida para cada línea, también se puede usar en una aplicación de estilo de procesamiento por lotes más tradicional donde lee toda la entrada, procesa y luego envía el salida procesada en adelante.
Otro solucionador de rompecabezas de Sudoku:YASPS para Awk
La aplicación que elegí usar como ejemplo es "otro solucionador de sudoku". Debo confesar desde el principio que nunca me he sentado a resolver uno de estos acertijos yo mismo, sino que esbocé esto durante unos días mientras viajaba en un tren y miraba a otras personas trabajar en ellos. Creo que fue mucho más divertido que hacer cualquiera de los rompecabezas...
Descargar el programa YASPS para Awk:solve.awk
El formato de entrada que he elegido es fácil de analizar en awk y es bastante tradicional en el entorno Unix. Las líneas en blanco y las que comienzan con un carácter almohadilla (#) se ignoran, lo que facilita la inserción de comentarios. Se pueden usar espacios adicionales entre columnas para mejorar la legibilidad. Un ejemplo se muestra en la siguiente figura:
------------------------------------------------------------------------------- # I forget where I got this.. # this is one of the hardest ones I've found for this algorithm, although # after transposing the matrix it can be solved in a fraction of the time 2 0 0 6 7 0 0 0 0 0 0 6 0 0 0 2 0 1 4 0 0 0 0 0 8 0 0 5 0 0 0 0 9 3 0 0 0 3 0 0 0 0 0 5 0 0 0 2 8 0 0 0 0 7 0 0 1 0 0 0 0 0 4 7 0 8 0 0 0 6 0 0 0 0 0 0 5 3 0 0 8 -------------------------------------------------------------------------------
Casi no hay verificación de errores en este programa, pero sería fácil agregarlo al frente o como parte de un script de envoltura. Lo dejaré como ejercicio para el lector.
Este programa utiliza un algoritmo de seguimiento recursivo de profundidad primero muy simple con eliminación directa y continua de entradas no válidas. Es posible que Awk no tenga el poder expresivo para representar datos complejos que tienen Perl u otros lenguajes, pero con cuidado, se pueden usar muchos problemas y conjuntos de datos de tamaño moderado. Es posible que este algoritmo no sea el mejor, pero ciertamente es lo suficientemente rápido para la mayoría de los problemas y es fácil de implementar.
Con cualquier problema, representar los datos de manera efectiva hace que la tarea de diseñar un programa sea mucho más fácil. He representado el estado completo del puzzle en una matriz llamada “maestra”. Esto apenas se usa para mucho, excepto para mantener un registro de qué está dónde y para hacer el resultado final.
Las principales variables de caballo de batalla son otras tres matrices. Intuitivamente, sabemos por el método recursivo de prueba y error que hemos elegido que necesitaremos verificar la validez de los números de prueba con bastante frecuencia. Para acelerar ese proceso, mantenemos matrices asociativas para almacenar el estado actual de las filas, columnas y cada región (que, aunque no es técnicamente correcto, llamaremos "cuadrante"). Estas son las matrices R, C y Q. (Tenga en cuenta que awk distingue entre mayúsculas y minúsculas).
A veces, ayuda cuando se intenta factorizar cálculos comunes de bucles for anidados o llamadas a funciones recursivas para calcular previamente los valores que se usan con frecuencia. Intenté esto con la matriz "regmap" que almacenaría un número de cuadrante dados los valores de fila y columna, pero encontré que el ahorro de tiempo en este caso era ambiguo. Lo dejé comentado, pero su kilometraje puede variar y la técnica suele ser muy útil.
Los algoritmos recursivos a menudo se diseñan mejor y, por lo tanto, se describen de manera descendente. La función principal de este programa se llama "buscar()" y se llama desde el patrón "FIN" después de que los datos del problema se hayan leído en las matrices.
En un nivel alto, search() comienza con los parámetros de fila y columna proporcionados y busca el siguiente espacio vacío para verificar. Si no los hay, el problema se ha solucionado y vuelve con la solución. Si hay un espacio vacío (representado por cero), prueba los números disponibles (con la función inuse(), para los números que no están en uso en esa fila, columna o cuadrante) insertando un número en las matrices usando mark() y llamando sí mismo recursivamente. Si la función de búsqueda recursiva () devuelve un cero, significa que ha fallado, por lo que se llama nuevamente a la función de marcar () para desmarcar el número de prueba. Luego se repite hasta que se agotan las posibilidades o la llamada de búsqueda () devuelve el éxito.
La belleza de muchos algoritmos recursivos es la elegancia inherente y la simplicidad de las soluciones. Si bien a veces no son los algoritmos más rápidos, a menudo son "lo suficientemente rápidos" y más fáciles de diseñar. Este programa resuelve la mayoría de los acertijos en menos de unos segundos. Una cosa que noté mientras probaba este programa en diferentes acertijos es que si un problema tomaba más tiempo para resolverse (en decenas de segundos), simplemente transponiendo la matriz a menudo daría la misma solución en una fracción de segundo. Con las CPU multinúcleo de hoy en día, esto sugiere una posibilidad para acelerarlo:escriba un script contenedor que inicie varias instancias del programa con diferentes transposiciones de la matriz. Se muestra un ejemplo con el rompecabezas anterior que se muestra arriba y la versión transpuesta en la siguiente figura donde el problema transpuesto se resolvió cuatro veces más rápido.
------------------------------------------------------------------------------- marion:~/sudoku$ time awk -f solve.awk THE-HARDEST-SO-FAR.dat # Searches=134214 2 8 3 6 7 1 9 4 5 9 7 6 5 4 8 2 3 1 4 1 5 3 9 2 8 7 6 5 6 7 4 1 9 3 8 2 8 3 4 2 6 7 1 5 9 1 9 2 8 3 5 4 6 7 3 2 1 7 8 6 5 9 4 7 5 8 9 2 4 6 1 3 6 4 9 1 5 3 7 2 8 real 0m10.009s user 0m9.889s sys 0m0.024s marion:~/sudoku$ time awk -f solve.awk /tmp/transposed.dat # Searches=32253 8 3 4 7 9 2 6 1 5 2 1 9 6 5 8 7 3 4 7 6 5 4 1 3 8 2 9 3 4 6 5 7 9 2 8 1 5 2 8 3 6 1 9 4 7 1 9 7 8 2 4 3 5 6 9 8 1 2 4 7 5 6 3 4 5 2 9 3 6 1 7 8 6 7 3 1 8 5 4 9 2 real 0m2.487s user 0m2.456s sys 0m0.008s -------------------------------------------------------------------------------
Cuando se requiere algo aún más rápido, a menudo se puede lograr traduciendo el algoritmo a otro idioma con una representación más directa de los conjuntos de datos. Una vez hice una traducción de este programa a C con un giro interesante en la indexación de datos. Esta versión probablemente ejecuta algunos órdenes de magnitud más rápido, en gran parte debido a la forma en que se representan los datos. Probablemente publicaremos "Otro solucionador de rompecabezas de Sudoku usando C" como otro artículo más adelante.
Creo que awk merece un lugar en la caja de herramientas de todos. Su simplicidad en relación con otros idiomas quizás se vea como una debilidad, pero yo la veo como una de sus fortalezas. El idioma puede aprenderse en una tarde y usarse sin recurrir a libros de consulta para resolver muchos problemas del día a día. Lo uso de forma regular directamente desde la línea de comandos, hasta implementar cosas como compiladores para DSL (lenguajes específicos del dominio).
Libros Awk recomendados
- El lenguaje de programación AWK de Alfred V. Aho, Brian W. Kernighan y Peter J. Weinberger. El libro original de los autores del lenguaje tiene algunos ejemplos excelentes de programas moderadamente complejos y sigue siendo mi libro favorito sobre awk. Publicado por Addison-Wesley, 1988. ISBN 020107981X.
- Más perlas de programación:Confesiones de un programador por Jon Bentley, AT&T Bell Labs, Murray Hill, NJ. Otro libro para usar awk como herramienta de creación de prototipos para algoritmos se puede encontrar en More Pearls. Excelente lectura. Año de publicación:1988. ISBN:0201118890