[pyar] Pregunta sobre algoritmo para procesar palabras en un juego

[Angel Java Lopez]

Hola gente!

Juan, gracias por compartir la idea, no conocia Boggle, jeje... soy un
raton de biblioteca ;-)

Bueno, primera idea, SI TENES LA LISTA DE PALABRAS, haria algo parecido a
lo que se hace con expresiones regulares: ir visitando una palabra o un
arbol.

Primero, visitar cada palabra. En seudo codigo, no sabria como escribirlo
en Python "puro"

def search (visited, word, current, position)
    if word.length >= current
        return visited
    for cell in position.neighbourgs
        if cell.content != word[current]
            continue
        if visited.contains(cell)
            continue
        newvisited = visited + cell
        result = search(newvisited, word, current+1, cell)
        if result
            return result

    return null

Eso para cada palabra, empezando con todas las celdas que tengan la primer
letra de la palabra

visited: lista de celdas ya visitadas
word: palabra a buscar
position: numero de letra que se esta procesando
position: celda donde ya se encontro la letra que se esta procesando

Luego, en vez de interpretarla, compilar todo esto (doy mas detalles si
hacen falta)

Luego, optimizar: hacer como en otros algoritmos, en vez de buscar "papa",
"papita", "pepa", "pipa", buscar la "p", y si se encuentra, buscar la
segunda letra de TODAS las palabras que empiezan con "p", y asi. Se podria
formar un arbol tipo

[ "p" ["a" ["p" ["a" [....] "i" [....] ...

Quedaria entonces:

- Visitar cada celda
- Dada la letra de la celda, esta en algun lado el arbol de las palabras
que empiezan con esa letra.

Lo bueno del arbol, es que cada celda se visita una vez, y se van buscando
TODAS sus posibles palabras.

Lo malo es que hay que armar el arbol ;-) de la primera forma, es mas
facil, lo intentaria como primer algoritmo, con TDD ;-) y luego pasaria al
segundo

Hasta se podria compilar esta busqueda (como muchas veces se hace con las
expresiones regulares)

Nos leemos!

Angel "Java" Lopez
http://www.ajlopez.com
http://twitter.com/ajlopez


2013/1/7 Juan Rodríguez Monti <juanrodriguezmonti en gmail.com>

> Buenas lista,
> Cómo va?.
>
> Hace unos días, tenia ganas de jugar al Boggle[0]. Como no tenia a mano
> ninguno, me escribí un mezclador de dados de boggle. En realidad no escribí
> el juego, sólo programé lo que seria el tablero y una lógica que permite
> "mezclar" los dados. Cada dado tiene 6 letras posibles, y bueno lo que hace
> es ir eligiendo las letras y armar - de forma aleatoria - la distribución
> de los dados en el tablero. Tiene un botoncito que dice mezclar y el
> tablero armado. Es una UX sencilla. Esa parte fué fácil y rápida y anda
> perfecto.
>
> El tema es que, después de haber jugado un rato, me puse a pensar en que
> estaría bueno implementar el juego completo. Y allí me encontré el motivo
> de esta consulta que es el siguiente.
>
> ¿ Qué algoritmo puedo usar, o cual es la mejor manera de resolver esto,
> para encontrar palabras en este tablero usando como base de referncia un
> listado de palabras ?.
>
> El tablero es así:
>
> ANSMD
> EOOES
> OEOED
> OPOSE
> LSLSP
>
> Son 5 filas, formadas por 5 dados cada una.
>
> Las restricciones son: Que no es posible usar un mismo dado más de una vez
> ( en realidad sí se puede usar si es principio y final, pero no la
> compliquemos más y supongamos que no se puede ) y que las letras que se
> usan deben ser contiguas, es decir: deben tocarse. Después es posible ir
> hacia arriba, abajo, derecha izquierda, diagonal, etc. Cualquier dibujo es
> posible.
>
> Lo que yo quiero saber es cómo podría implementarse la lógica para buscar
> palabras allí adentro, con la posibilidad de subir, bajar, y moverse para
> todos lados en el tablero al formar las palabras. El algoritmo también debe
> tener una velocidad aceptable que permita jugar, también.
>
> En realidad lo que me pareció más interesante es pensar la manera de
> resolver esto. Independientemente del juego, me interesó mucho ver qué
> lógica y qué algoritmo puede resolver esta situación de la mejor manera
> posible.
>
> Las palabras las voy a sacar de un archivo de texto que tiene las
> palabras, formado con aspell.
>
> Si algun día armo el juego completo, lo liberaré y será otro lindo
> proyecto nacido en PyAr. Por cierto, es un juego muy divertido que lo
> recomiendo si no lo conocen.
>
> Abrazo,
> Juan
>
> [0] http://en.wikipedia.org/wiki/Boggle
> --
> Juan Rodríguez Monti
>
> Blog: http://www.juanrodriguezmonti.com.ar
> Twitter: @jrodriguezmonti
>
> _______________________________________________
> pyar mailing list pyar en python.org.ar
> http://listas.python.org.ar/listinfo/pyar
>
> PyAr - Python Argentina - Sitio web: http://www.python.org.ar/
>
> La lista de PyAr esta Hosteada en USLA - Usuarios de Software Libre de
> Argentina - http://www.usla.org.ar
>
------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: <http://listas.python.org.ar/pipermail/pyar/attachments/20130107/919ab0ab/attachment.html>