Tp Eda
Páginas: 17 (4082 palabras)
Publicado: 30 de mayo de 2012
-Informe de Trabajo Práctico-
Índice
Introduccion al problema 3
El scrabble - La variante propuesta 3
Primeros pasos 4
Seccion I - La Estructura 4
Decision y analisis 4
Nuestra Imprelementacion 5
Clase Word y Clase Rack. 6
Clase Board 7
Seccion II – El Algoritmo 8
IdeaBasica 8
Etapa I – Cargando y creando la estructura 9
Etapa II – Iterando y ubicando palabras en el tablero 10
Seccion III – Parser – Visual Mode - MaxTime 13
Seccion IV – Futuros Cambios 14
Seccion V – Conclusiones 15
Introducción al problema
El Scrabble
Scrabble es un juego de mesa en el cual cada jugadorintenta ganar más puntos mediante la construcción de palabras sobre un tablero de 15x15 casillas. Las palabras pueden formarse horizontalmente o verticalmente y se pueden cruzar siempre y cuando aparezcan en el diccionario o lista palabras validas.
El juego se realiza entre 2 o 4 jugadores, sobre un tablero (Ver Figura 1), en el que cada jugador coloca sus fichas. Cada jugador recibe un númeroespecífico de fichas (Letras). Las letras se encuentran numeradas con su respectivo valor, obteniéndose por cada palabra formada una puntuación que depende tanto del valor de las letras empleadas como de la posición de dichas letras dentro del tablero.
[pic][pic]
Fig. 1. Ejemplo de Tablero - Scrabble
La variante propuesta
El problema propuesto es la auto-resolución del juego Scrabblepara un solo jugador, que a partir de un conjunto de letras y un diccionario de posibles palabras, encuentre la distribución de las mismas en el tablero que maximiza el puntaje total obtenido.
Se tiene inicialmente una grilla de 15 x 15 vacía. Y se cuenta además con una lista de letras disponibles. En cada movimiento se debe formar una palabra nueva en la grilla. Las palabras deben tener comomínimo 2 letras y como máximo 7.
La palabra inicial se ubica de manera tal de que alguna letra que la conforma se encuentre en el casillero central. Se pueden repetir palabras, al momento de ubicarlas, a lo largo del juego.
Cada letra tiene un puntaje asociado, según la siguiente tabla
[pic]
Fig. 2. Tabla de valores de las letras
PrimerosPasos
Con unas 3 semanas para el desarrollo del Algoritmo en su totalidad, la organización para la confección del Trabajo Práctico se dividió en dos etapas.
La primer etapa fue la de decidir que estructura soporte utilizar para almacenar las palabras del diccionario de la manera en que sean accedidas de la manera más eficiente a fin de optimizar el uso a la hora de aplicar el algoritmo deubicación.
Consistió en una semana de investigación, análisis del Paper “The World Fastest Scrabble Program”[1], brainstorming, en la que ninguna idea ubicar las ideas del Diccionario, por más impensada que sea, fue ignorada, discusión con otros grupos.
Todas las ideas surgidas fueron debidamente apuntadas en un cuaderno, y luego analizadas en función de sus pros y contras, obteniendodiferencias en la complejidad espacial.
La segunda etapa se centró en el desarrollo mismo del algoritmo, independizando éste ultimo de la estructura soporte utilizada, la correcta ubicación de las palabras optimizando el puntaje, y la validación de todas las palabras formadas en base a sus aledaños, término que de ahora en adelante se denominara CrossCheck.
Sección I - La estructuraDecisión y Análisis
En un primer paso, fuimos tentados a implementar un árbol de prefijos Trie[2], el cual era generado
a partir del diccionario de entrada, y en el que en sus nodos hoja (En una primer implementación) guardaba si se formaba una palabra hasta ese momento por dicha rama, (Con el seteo de una Variable booleana, isEndOfWord = true). En sus aristas contenía la letra que se agregaba...
Índice
Introduccion al problema 3
El scrabble - La variante propuesta 3
Primeros pasos 4
Seccion I - La Estructura 4
Decision y analisis 4
Nuestra Imprelementacion 5
Clase Word y Clase Rack. 6
Clase Board 7
Seccion II – El Algoritmo 8
IdeaBasica 8
Etapa I – Cargando y creando la estructura 9
Etapa II – Iterando y ubicando palabras en el tablero 10
Seccion III – Parser – Visual Mode - MaxTime 13
Seccion IV – Futuros Cambios 14
Seccion V – Conclusiones 15
Introducción al problema
El Scrabble
Scrabble es un juego de mesa en el cual cada jugadorintenta ganar más puntos mediante la construcción de palabras sobre un tablero de 15x15 casillas. Las palabras pueden formarse horizontalmente o verticalmente y se pueden cruzar siempre y cuando aparezcan en el diccionario o lista palabras validas.
El juego se realiza entre 2 o 4 jugadores, sobre un tablero (Ver Figura 1), en el que cada jugador coloca sus fichas. Cada jugador recibe un númeroespecífico de fichas (Letras). Las letras se encuentran numeradas con su respectivo valor, obteniéndose por cada palabra formada una puntuación que depende tanto del valor de las letras empleadas como de la posición de dichas letras dentro del tablero.
[pic][pic]
Fig. 1. Ejemplo de Tablero - Scrabble
La variante propuesta
El problema propuesto es la auto-resolución del juego Scrabblepara un solo jugador, que a partir de un conjunto de letras y un diccionario de posibles palabras, encuentre la distribución de las mismas en el tablero que maximiza el puntaje total obtenido.
Se tiene inicialmente una grilla de 15 x 15 vacía. Y se cuenta además con una lista de letras disponibles. En cada movimiento se debe formar una palabra nueva en la grilla. Las palabras deben tener comomínimo 2 letras y como máximo 7.
La palabra inicial se ubica de manera tal de que alguna letra que la conforma se encuentre en el casillero central. Se pueden repetir palabras, al momento de ubicarlas, a lo largo del juego.
Cada letra tiene un puntaje asociado, según la siguiente tabla
[pic]
Fig. 2. Tabla de valores de las letras
PrimerosPasos
Con unas 3 semanas para el desarrollo del Algoritmo en su totalidad, la organización para la confección del Trabajo Práctico se dividió en dos etapas.
La primer etapa fue la de decidir que estructura soporte utilizar para almacenar las palabras del diccionario de la manera en que sean accedidas de la manera más eficiente a fin de optimizar el uso a la hora de aplicar el algoritmo deubicación.
Consistió en una semana de investigación, análisis del Paper “The World Fastest Scrabble Program”[1], brainstorming, en la que ninguna idea ubicar las ideas del Diccionario, por más impensada que sea, fue ignorada, discusión con otros grupos.
Todas las ideas surgidas fueron debidamente apuntadas en un cuaderno, y luego analizadas en función de sus pros y contras, obteniendodiferencias en la complejidad espacial.
La segunda etapa se centró en el desarrollo mismo del algoritmo, independizando éste ultimo de la estructura soporte utilizada, la correcta ubicación de las palabras optimizando el puntaje, y la validación de todas las palabras formadas en base a sus aledaños, término que de ahora en adelante se denominara CrossCheck.
Sección I - La estructuraDecisión y Análisis
En un primer paso, fuimos tentados a implementar un árbol de prefijos Trie[2], el cual era generado
a partir del diccionario de entrada, y en el que en sus nodos hoja (En una primer implementación) guardaba si se formaba una palabra hasta ese momento por dicha rama, (Con el seteo de una Variable booleana, isEndOfWord = true). En sus aristas contenía la letra que se agregaba...
Leer documento completo
Regístrate para leer el documento completo.