Este es un juego de palabras de un conjunto de tarjetas de actividades para niños. Debajo de las reglas hay un código para encontrar el mejor triplete usando / usr / share / dict / words. Pensé que era un problema de optimización interesante, y me pregunto si las personas pueden encontrar mejoras.
Reglas
- Elija una letra de cada uno de los conjuntos a continuación.
- Elija una palabra usando las letras elegidas (y cualquier otra).
- Anota la palabra.
- Cada letra del conjunto elegido obtiene el número que se muestra con el conjunto (repeticiones incluidas).
AEIOU
cuenta 0- Todas las otras letras son -2
- Repita los pasos 1-3 anteriores (sin reutilizar letras en el paso 1) dos veces más.
- El puntaje final es la suma de los puntajes de tres palabras.
Conjuntos
(conjunto 1 puntajes 1 punto, conjunto 2 puntajes 2 puntos, etc.)
- LTN
- RDS
- GBM
- CHP
- FWV
- YKJ
- QXZ
Código:
from itertools import permutations
import numpy as np
points = {'LTN' : 1,
'RDS' : 2,
'GBM' : 3,
'CHP' : 4,
'FWV' : 5,
'YKJ' : 6,
'QXZ' : 7}
def tonum(word):
word_array = np.zeros(26, dtype=np.int)
for l in word:
word_array[ord(l) - ord('A')] += 1
return word_array.reshape((26, 1))
def to_score_array(letters):
score_array = np.zeros(26, dtype=np.int) - 2
for v in 'AEIOU':
score_array[ord(v) - ord('A')] = 0
for idx, l in enumerate(letters):
score_array[ord(l) - ord('A')] = idx + 1
return np.matrix(score_array.reshape(1, 26))
def find_best_words():
wlist = [l.strip().upper() for l in open('/usr/share/dict/words') if l[0].lower() == l[0]]
wlist = [l for l in wlist if len(l) > 4]
orig = [l for l in wlist]
for rep in 'AEIOU':
wlist = [l.replace(rep, '') for l in wlist]
wlist = np.hstack([tonum(w) for w in wlist])
best = 0
ct = 0
bestwords = ()
for c1 in ['LTN']:
for c2 in permutations('RDS'):
for c3 in permutations('GBM'):
for c4 in permutations('CHP'):
for c5 in permutations('FWV'):
for c6 in permutations('YJK'):
for c7 in permutations('QZX'):
vals = [to_score_array(''.join(s)) for s in zip(c1, c2, c3, c4, c5, c6, c7)]
ct += 1
print ct, 6**6
scores1 = (vals[0] * wlist).A.flatten()
scores2 = (vals[1] * wlist).A.flatten()
scores3 = (vals[2] * wlist).A.flatten()
m1 = max(scores1)
m2 = max(scores2)
m3 = max(scores3)
if m1 + m2 + m3 > best:
print orig[scores1.argmax()], orig[scores2.argmax()], orig[scores3.argmax()], m1 + m2 + m3
best = m1 + m2 + m3
bestwords = (orig[scores1.argmax()], orig[scores2.argmax()], orig[scores3.argmax()])
return bestwords, best
if __name__ == '__main__':
import timeit
print timeit.timeit('print find_best_words()', 'from __main__ import find_best_words', number=1)
La versión matricial es la que se me ocurrió después de escribir una en Python puro (usando diccionarios y calificando cada palabra independientemente), y otra en numpy pero usando indexación en lugar de multiplicación de matriz.
La siguiente optimización sería eliminar las vocales de la puntuación por completo (y usar una ord()
función modificada ), pero me pregunto si hay enfoques aún más rápidos.
EDITAR : código timeit.timeit agregado
EDITAR : estoy agregando una recompensa, que daré a la mejora que más me guste (o posiblemente múltiples respuestas, pero tendré que acumular más reputación si ese es el caso).
Respuestas:
Utilizando la idea de Keith de calcular previamente la mejor puntuación posible para cada palabra, logré reducir el tiempo de ejecución a aproximadamente 0.7 segundos en mi computadora (usando una lista de 75,288 palabras).
El truco consiste en pasar por las combinaciones de palabras que se jugarán en lugar de todas las combinaciones de letras elegidas. Podemos ignorar todas menos algunas combinaciones de palabras (203 usando mi lista de palabras) porque no pueden obtener una puntuación más alta de la que ya hemos encontrado. Casi todo el tiempo de ejecución se dedica a precalificar las puntuaciones de palabras.
Python 2.7:
Esto devuelve la solución
['KNICKKNACK', 'RAZZMATAZZ', 'POLYSYLLABLES']
con un puntaje de 95. Con las palabras de la solución de Keith agregadas a la lista de palabras, obtengo el mismo resultado que él. Con la "xilopirografía" de youis agregada, obtengo['XYLOPYROGRAPHY', 'KNICKKNACKS', 'RAZZMATAZZ']
un puntaje de 105.fuente
He aquí una idea: puede evitar revisar muchas palabras al notar que la mayoría de las palabras tienen puntajes horribles. Digamos que has encontrado un juego de puntuación bastante bueno que te da 50 puntos. Entonces cualquier jugada con más de 50 puntos debe tener una palabra de al menos ceil (51/3) = 17 puntos. Por lo tanto, cualquier palabra que no pueda generar 17 puntos puede ser ignorada.
Aquí hay un código que hace lo anterior. Calculamos el mejor puntaje posible para cada palabra en el diccionario y lo almacenamos en una matriz indexada por puntaje. Luego usamos esa matriz para verificar solo las palabras que tienen el puntaje mínimo requerido.
El puntaje mínimo llega rápidamente a 100, lo que significa que solo necesitamos considerar más de 33 puntos de palabras, que es una fracción muy pequeña del total total (mi
/usr/share/dict/words
tiene 208662 palabras válidas, de las cuales solo 1723 son 33+ puntos = 0.8%). Se ejecuta en aproximadamente media hora en mi máquina y genera:fuente