El código Python más rápido para encontrar un conjunto de palabras ganadoras en este juego

14

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

  1. Elija una letra de cada uno de los conjuntos a continuación.
  2. Elija una palabra usando las letras elegidas (y cualquier otra).
  3. 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
  4. Repita los pasos 1-3 anteriores (sin reutilizar letras en el paso 1) dos veces más.
  5. El puntaje final es la suma de los puntajes de tres palabras.

Conjuntos

(conjunto 1 puntajes 1 punto, conjunto 2 puntajes 2 puntos, etc.)

  1. LTN
  2. RDS
  3. GBM
  4. CHP
  5. FWV
  6. YKJ
  7. 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).

tu
fuente
3
Por cierto, escribí el código para darle a mi hijo de ocho años tres palabras para memorizar cuando jugaba contra su madre. Ahora sé lo que significa xilopirografía.
2
Esta es una pregunta divertida. Creo que podría aumentar la probabilidad de obtener respuestas si proporciona lo siguiente: (1) Un enlace a una lista de palabras en línea para que todos trabajen con el mismo conjunto de datos. (2) Pon tu solución en una sola función. (3) Ejecute esa función usando el módulo time-it para mostrar los tiempos. (4) Asegúrese de colocar la carga de datos del diccionario fuera de la función para que no estemos probando la velocidad del disco. Entonces, las personas pueden usar el código existente como marco para comparar sus soluciones.
Reescribiré para usar timeit, pero para realizar comparaciones justas tendría que usar mi propia máquina (lo cual me complace hacer para las personas que publican soluciones). Una lista de palabras debería estar disponible en la mayoría de los sistemas, pero si no, hay varias aquí: wordlist.sourceforge.net
1
Se pueden obtener comparaciones justas si cada usuario mide el tiempo de su solución y cualquier otra solución publicada contra la suya en su propia máquina. Habrá algunas diferencias entre plataformas, pero en general este método funciona.
1
Hm, en ese caso, me pregunto si este es el sitio correcto. Creo que SO habría sido la mejor opción.
Joey

Respuestas:

3

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:

import collections
import itertools


WORDS_SOURCE = '../word lists/wordsinf.txt'

WORDS_PER_ROUND = 3
LETTER_GROUP_STRS = ['LTN', 'RDS', 'GBM', 'CHP', 'FWV', 'YKJ', 'QXZ']
LETTER_GROUPS = [list(group) for group in LETTER_GROUP_STRS]
GROUP_POINTS = [(group, i+1) for i, group in enumerate(LETTER_GROUPS)]
POINTS_IF_NOT_CHOSEN = -2


def best_word_score(word):
    """Return the best possible score for a given word."""

    word_score = 0

    # Score the letters that are in groups, chosing the best letter for each
    # group of letters.
    total_not_chosen = 0
    for group, points_if_chosen in GROUP_POINTS:
        letter_counts_sum = 0
        max_letter_count = 0
        for letter in group:
            if letter in word:
                count = word.count(letter)
                letter_counts_sum += count
                if count > max_letter_count:
                    max_letter_count = count
        if letter_counts_sum:
            word_score += points_if_chosen * max_letter_count
            total_not_chosen += letter_counts_sum - max_letter_count
    word_score += POINTS_IF_NOT_CHOSEN * total_not_chosen

    return word_score

def best_total_score(words):
    """Return the best score possible for a given list of words.

    It is fine if the number of words provided is not WORDS_PER_ROUND. Only the
    words provided are scored."""

    num_words = len(words)
    total_score = 0

    # Score the letters that are in groups, chosing the best permutation of
    # letters for each group of letters.
    total_not_chosen = 0
    for group, points_if_chosen in GROUP_POINTS:
        letter_counts = []
        # Structure:  letter_counts[word_index][letter] = count
        letter_counts_sum = 0
        for word in words:
            this_word_letter_counts = {}
            for letter in group:
                count = word.count(letter)
                this_word_letter_counts[letter] = count
                letter_counts_sum += count
            letter_counts.append(this_word_letter_counts)

        max_chosen = None
        for letters in itertools.permutations(group, num_words):
            num_chosen = 0
            for word_index, letter in enumerate(letters):
                num_chosen += letter_counts[word_index][letter]
            if num_chosen > max_chosen:
                max_chosen = num_chosen

        total_score += points_if_chosen * max_chosen
        total_not_chosen += letter_counts_sum - max_chosen
    total_score += POINTS_IF_NOT_CHOSEN * total_not_chosen

    return total_score


def get_words():
    """Return the list of valid words."""
    with open(WORDS_SOURCE, 'r') as source:
        return [line.rstrip().upper() for line in source]

def get_words_by_score():
    """Return a dictionary mapping each score to a list of words.

    The key is the best possible score for each word in the corresponding
    list."""

    words = get_words()
    words_by_score = collections.defaultdict(list)
    for word in words:
        words_by_score[best_word_score(word)].append(word)
    return words_by_score


def get_winning_words():
    """Return a list of words for an optimal play."""

    # A word's position is a tuple of its score's index and the index of the
    # word within the list of words with this score.
    # 
    # word played: A word in the context of a combination of words to be played
    # word chosen: A word in the context of the list it was picked from

    words_by_score = get_words_by_score()
    num_word_scores = len(words_by_score)
    word_scores = sorted(words_by_score, reverse=True)
    words_by_position = []
    # Structure:  words_by_position[score_index][word_index] = word
    num_words_for_scores = []
    for score in word_scores:
        words = words_by_score[score]
        words_by_position.append(words)
        num_words_for_scores.append(len(words))

    # Go through the combinations of words in lexicographic order by word
    # position to find the best combination.
    best_score = None
    positions = [(0, 0)] * WORDS_PER_ROUND
    words = [words_by_position[0][0]] * WORDS_PER_ROUND
    scores_before_words = []
    for i in xrange(WORDS_PER_ROUND):
        scores_before_words.append(best_total_score(words[:i]))
    while True:
        # Keep track of the best possible combination of words so far.
        score = best_total_score(words)
        if score > best_score:
            best_score = score
            best_words = words[:]

        # Go to the next combination of words that could get a new best score.
        for word_played_index in reversed(xrange(WORDS_PER_ROUND)):
            # Go to the next valid word position.
            score_index, word_chosen_index = positions[word_played_index]
            word_chosen_index += 1
            if word_chosen_index == num_words_for_scores[score_index]:
                score_index += 1
                if score_index == num_word_scores:
                    continue
                word_chosen_index = 0

            # Check whether the new combination of words could possibly get a
            # new best score.
            num_words_changed = WORDS_PER_ROUND - word_played_index
            score_before_this_word = scores_before_words[word_played_index]
            further_points_limit = word_scores[score_index] * num_words_changed
            score_limit = score_before_this_word + further_points_limit
            if score_limit <= best_score:
                continue

            # Update to the new combination of words.
            position = score_index, word_chosen_index
            positions[word_played_index:] = [position] * num_words_changed
            word = words_by_position[score_index][word_chosen_index]
            words[word_played_index:] = [word] * num_words_changed
            for i in xrange(word_played_index+1, WORDS_PER_ROUND):
                scores_before_words[i] = best_total_score(words[:i])
            break
        else:
            # None of the remaining combinations of words can get a new best
            # score.
            break

    return best_words


def main():
    winning_words = get_winning_words()
    print winning_words
    print best_total_score(winning_words)

if __name__ == '__main__':
    main()

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.

flornquake
fuente
5

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.

from itertools import permutations
import time

S={'A':0,'E':0,'I':0,'O':0,'U':0,
   'L':1,'T':1,'N':1,
   'R':2,'D':2,'S':2,
   'G':3,'B':3,'M':3,
   'C':4,'H':4,'P':4,
   'F':5,'W':5,'V':5,
   'Y':6,'K':6,'J':6,
   'Q':7,'X':7,'Z':7,
   }

def best_word(min, s):
    global score_to_words
    best_score = 0
    best_word = ''
    for i in xrange(min, 100):
        for w in score_to_words[i]:
            score = (-2*len(w)+2*(w.count('A')+w.count('E')+w.count('I')+w.count('O')+w.count('U')) +
                      3*w.count(s[0])+4*w.count(s[1])+5*w.count(s[2])+6*w.count(s[3])+7*w.count(s[4])+
                      8*w.count(s[5])+9*w.count(s[6]))
            if score > best_score:
                best_score = score
                best_word = w
    return (best_score, best_word)

def load_words():
    global score_to_words
    wlist = [l.strip().upper() for l in open('/usr/share/dict/words') if l[0].lower() == l[0]]
    score_to_words = [[] for i in xrange(100)]
    for w in wlist: score_to_words[sum(S[c] for c in w)].append(w)
    for i in xrange(100):
        if score_to_words[i]: print i, len(score_to_words[i])

def find_best_words():
    load_words()
    best = 0
    bestwords = ()
    for c1 in permutations('LTN'):
        for c2 in permutations('RDS'):
            for c3 in permutations('GBM'):
            print time.ctime(),c1,c2,c3
                for c4 in permutations('CHP'):
                    for c5 in permutations('FWV'):
                        for c6 in permutations('YJK'):
                            for c7 in permutations('QZX'):
                                sets = zip(c1, c2, c3, c4, c5, c6, c7)
                                (s1, w1) = best_word((best + 3) / 3, sets[0])
                                (s2, w2) = best_word((best - s1 + 2) / 2, sets[1])
                                (s3, w3) = best_word(best - s1 - s2 + 1, sets[2])
                                score = s1 + s2 + s3
                                if score > best:
                                    best = score
                                    bestwords = (w1, w2, w3)
                                    print score, w1, w2, w3
    return bestwords, best


if __name__ == '__main__':
    import timeit
    print timeit.timeit('print find_best_words()', 'from __main__ import find_best_words', number=1)

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/wordstiene 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:

(('MAXILLOPREMAXILLARY', 'KNICKKNACKED', 'ZIGZAGWISE'), 101)
Keith Randall
fuente
Agradable. Agregaré eso a la solución matricial (eliminando palabras ya que su puntaje es demasiado bajo), pero esto es significativamente mejor que cualquiera de las soluciones puras de Python que se me ocurrió.
eres
1
No estoy seguro de haber visto tantos anidados para bucles antes.
Peter Olson
1
La combinación de su idea con la puntuación de matriz (y un límite superior más ajustado en la mejor puntuación posible) reduce el tiempo a aproximadamente 80 segundos en mi máquina (de aproximadamente una hora). código aquí
eres
Una buena parte de ese tiempo está en la precomputación de los mejores puntajes posibles, que podrían hacerse mucho más rápido.
eres