string - test - trucos scrabble

Scrabble azulejo comprobación

Question

Para el control de fichas en scrabble, se crean cuatro cuadrículas de letras de 5x5 que totalizan 100 fichas. Me gustaría hacer uno donde las 40 palabras horizontales y verticales sean válidas. El conjunto de fichas disponibles contiene:

• 12 x E
• 9 x A, I
• 8 x O
• 6 x N, R, T
• 4 x D, L, S, U
• 3 x G
• 2 x B, C, F, H, M, P, V, W, Y, mosaico en blanco (comodín)
• 1 x K, J, Q, X, Z

El diccionario de palabras válidas está disponible here (700 KB). Hay aproximadamente 12,000 palabras válidas de 5 letras.

Aquí hay un ejemplo donde las 20 palabras horizontales son válidas:

Z O W I E|P I N O T
Y O G I N|O C t A D   <= blank being used as ''t''
X E B E C|N A L E D
W A I T E|M E R L E
V I N E R|L U T E A
---------+---------
U S N E A|K N O S P
T A V E R|J O L E D
S O F T A|I A M B I
R I D G Y|H A I T h   <= blank being used as ''h''
Q U R S H|G R O U F

Me gustaría crear uno donde todos los verticales también sean válidos. ¿Puedes ayudarme a resolver esto? No es tarea. Es una pregunta con la que un amigo me pidió ayuda.

Answer 1

Aquí hay muchos 5x5 precalculados. Se deja como ejercicio al lector para encontrar 4 compatibles :-)

http://www.gtoal.com/wordgames/wordsquare/all5

Answer 2

Así es como probaría esto. Primero construye un árbol de prefijo.

Elija una palabra y colóquela horizontalmente en la parte superior. Elija una palabra y colóquela verticalmente. Alternarlos hasta opciones agotadas. Al alternar, comienzas a corregir las primeras letras y elimina muchas palabras que no coinciden. Si realmente encuentras ese cuadrado, verifica si se pueden hacer con esas piezas.

Para cuadrados de 5x5: después de pensar un poco, no puede ser peor que O (12000! / 11990!) Para palabras de texto aleatorias. Pero pensándolo un poco más. Cada vez que arreglas una carta (en texto normal), eliminas aproximadamente el 90% (una suposición optimista) de tus palabras. Esto significa que después de tres iteraciones tienes 12 palabras. Entonces la velocidad real sería

O(n * n/10 * n/10 * n/100 * n/100 * n/1000 * n/1000 ...
which for 12000 elements acts something like n^4 algorithm

que no es tan malo

Probablemente alguien pueda hacer un mejor análisis del problema. Pero la búsqueda de palabras aún debe converger bastante rápido.

Puede haber más eliminaciones al abusar de las letras poco frecuentes. Básicamente encuentra todas las palabras que tienen letras poco frecuentes. Intenta hacer una posición correspondiente para cada letra. Construya un conjunto de letras válidas para cada posición.

Por ejemplo, supongamos que tenemos cuatro palabras con la letra Q en él.

 AQFED, ZQABE, EDQDE, ELQUO

 this means there are two valid positionings of those:

 xZxxx
 AQFED
 xAxxx   ---> this limits our search for words that contain [ABDEFZ] as the second letter
 xBxxx
 xExxx

 same for the other

 EDQDE   ---> this limits our search for words that contain [EDLU] as the third letter
 ELQUO

 all appropriate words are in union of those two conditions

Entonces, básicamente, si tenemos varias palabras que contienen una letra X infrecuente en la palabra S en la posición N, significa que otras palabras que están en esa matriz deben tener una letra que también está en S en la posición n.

Fórmula:

• Encuentra todas las palabras que contienen la letra X infrecuente en la posición 1 (próxima iteración 2, 3 ...)
• Haz un conjunto A de las letras en esas palabras
• Guarde solo las palabras del diccionario que tienen letra del conjunto A en posición 1
• Intenta encajarlos en la matriz (con el primer método)
• Repita con la posición 2

Answer 3

Edición final: ¡Resuelto! Aquí hay una solución.

GNAWN|jOULE
RACHE|EUROS
IDIOT|STEAN
PINOT|TRAvE
TRIPY|SOLES
-----+-----
HOWFF|ZEBRA
AGILE|EQUID
CIVIL|BUXOM
EVENT|RIOJA
KEDGY|ADMAN

Aquí hay una foto de ella construida con mi conjunto de scrabble. http://twitpic.com/3wn7iu

Este fue fácil de encontrar una vez que tuve el enfoque correcto, así que apuesto a que podría encontrar muchos más de esta manera. Vea a continuación la metodología.

Construya un árbol de prefijo del diccionario de 5 letras para cada fila y columna. Recíprocamente, una ubicación de mosaico dada es válida si forma prefijos válidos para su columna y fila, y si el mosaico está disponible, y si la colocación de la siguiente tesela es válida. El caso base es que es válido si no queda espacio para colocar.

Probablemente tenga sentido encontrar todas las placas válidas de 5x5, como dijo Glenn, y ver si se pueden combinar cuatro de ellas. Recordar a una profundidad de 100 no suena como diversión.

Editar: Aquí está la versión 2 de mi código para esto.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef union node node;
union node {
    node* child[26];
    char string[6];
};

typedef struct snap snap;
struct snap {
    node* rows[5];
    node* cols[5];
    char tiles[27];
    snap* next;
};

node* root;
node* vtrie[5];
node* htrie[5];
snap* head;

char bag[27] = {9,2,2,4,12,2,3,2,9,1,1,4,2,6,8,2,1,6,4,6,4,2,2,1,2,1,2};
const char full_bag[27] = {9,2,2,4,12,2,3,2,9,1,1,4,2,6,8,2,1,6,4,6,4,2,2,1,2,1,2};
const char order[26] = {16,23,9,25,21,22,5,10,1,6,7,12,15,2,24,3,20,13,19,11,8,17,14,0,18,4};

void insert(char* string){
    node* place = root;
    int i;
    for(i=0;i<5;i++){
        if(place->child[string[i] - ''A''] == NULL){
            int j;
            place->child[string[i] - ''A''] = malloc(sizeof(node));
            for(j=0;j<26;j++){
                place->child[string[i] - ''A'']->child[j] = NULL;
            }
        }
        place = place->child[string[i] - ''A''];
    }
    memcpy(place->string, string, 6);
}

void check_four(){
    snap *a, *b, *c, *d;
    char two_total[27];
    char three_total[27];
    int i;
    bool match;
    a = head;
    for(b = a->next; b != NULL; b = b->next){
        for(i=0;i<27; i++)
            two_total[i] = a->tiles[i] + b->tiles[i];
        for(c = b->next; c != NULL; c = c->next){
            for(i=0;i<27; i++)
                three_total[i] = two_total[i] + c->tiles[i];
            for(d = c->next; d != NULL; d = d->next){
                match = true;
                for(i=0; i<27; i++){
                    if(three_total[i] + d->tiles[i] != full_bag[i]){
                        match = false;
                        break;
                    }
                }
                if(match){
                    printf("/nBoard Found!/n/n");
                    for(i=0;i<5;i++){
                        printf("%s/n", a->rows[i]->string);
                    }
                    printf("/n");
                    for(i=0;i<5;i++){
                        printf("%s/n", b->rows[i]->string);
                    }
                    printf("/n");
                    for(i=0;i<5;i++){
                        printf("%s/n", c->rows[i]->string);
                    }
                    printf("/n");
                    for(i=0;i<5;i++){
                        printf("%s/n", d->rows[i]->string);
                    }
                    exit(0);
                }
            }
        }
    }
}

void snapshot(){
    snap* shot = malloc(sizeof(snap));
    int i;
    for(i=0;i<5;i++){
        printf("%s/n", htrie[i]->string);
        shot->rows[i] = htrie[i];
        shot->cols[i] = vtrie[i];
    }
    printf("/n");
    for(i=0;i<27;i++){
        shot->tiles[i] = full_bag[i] - bag[i];
    }
    bool transpose = false;
    snap* place = head;
    while(place != NULL && !transpose){
        transpose = true;
        for(i=0;i<5;i++){
            if(shot->rows[i] != place->cols[i]){
                transpose = false;
                break;
            }
        }
        place = place->next;
    }
    if(transpose){
        free(shot);
    }
    else {
        shot->next = head;
        head = shot;
        check_four();

    }
}

void pick(x, y){
    if(y==5){
        snapshot();
        return;
    }
    int i, tile,nextx, nexty, nextz;
    node* oldv = vtrie[x];
    node* oldh = htrie[y];
    if(x+1==5){
        nexty = y+1;
        nextx = 0;
    } else {
        nextx = x+1;
        nexty = y;
    }
    for(i=0;i<26;i++){
        if(vtrie[x]->child[order[i]]!=NULL &&
           htrie[y]->child[order[i]]!=NULL &&
           (tile = bag[i] ? i : bag[26] ? 26 : -1) + 1) {
                vtrie[x] = vtrie[x]->child[order[i]];
                htrie[y] = htrie[y]->child[order[i]];
                bag[tile]--;

                pick(nextx, nexty);

                vtrie[x] = oldv;
                htrie[y] = oldh;
                bag[tile]++;
           }
    }
}

int main(int argc, char** argv){
    root = malloc(sizeof(node));
    FILE* wordlist = fopen("sowpods5letters.txt", "r");
    head = NULL;
    int i;
    for(i=0;i<26;i++){
        root->child[i] = NULL;
    }
    for(i=0;i<5;i++){
        vtrie[i] = root;
        htrie[i] = root;
    }

    char* string = malloc(sizeof(char)*6);
    while(fscanf(wordlist, "%s", string) != EOF){
        insert(string);
    }
    free(string);
    fclose(wordlist);
    pick(0,0);

    return 0;
}

Esto prueba primero las letras poco frecuentes, que ya no estoy seguro de que sea una buena idea. Comienza a empantanarse antes de que salga de las tablas comenzando con x. Después de ver cuántos bloques de 5x5 había, modifiqué el código para enumerar todos los bloques válidos de 5x5. Ahora tengo un archivo de texto de 150 MB con todas las 4,430,974 soluciones de 5x5.

También lo probé con solo recurrir a través de las 100 fichas completas, y eso todavía está en ejecución.

Edición 2: Aquí está la lista de todos los bloques válidos de 5x5 que generé. http://web.cs.sunyit.edu/~levyt/solutions.rar

Editar 3: Hmm, parece que hubo un error en el seguimiento del uso de mosaicos, porque acabo de encontrar un bloque en mi archivo de salida que usa 5 Zs.

COSTE
ORCIN
SCUZZ
TIZZY
ENZYM

Edición 4: Aquí está el producto final.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef union node node;
union node {
    node* child[26];
    char string[6];
};

node* root;
node* vtrie[5];
node* htrie[5];
int score;
int max_score;

char block_1[27] = {4,2,0,2, 2,0,0,0,2,1,0,0,2,1,2,0,1,2,0,0,2,0,0,1,0,1,0};//ZEBRA EQUID BUXOM RIOJA ADMAN
char block_2[27] = {1,0,1,1, 4,2,2,1,3,0,1,2,0,1,1,0,0,0,0,1,0,2,1,0,1,0,0};//HOWFF AGILE CIVIL EVENT KEDGY
char block_3[27] = {2,0,1,1, 1,0,1,1,4,0,0,0,0,3,2,2,0,2,0,3,0,0,1,0,1,0,0};//GNAWN RACHE IDIOT PINOT TRIPY
                                                                            //JOULE EUROS STEAN TRAVE SOLES
char bag[27] =     {9,2,2,4,12,2,3,2,9,1,1,4,2,6,8,2,1,6,4,6,4,2,2,1,2,1,2};
const char full_bag[27] = {9,2,2,4,12,2,3,2,9,1,1,4,2,6,8,2,1,6,4,6,4,2,2,1,2,1,2};
const char order[26] = {16,23,9,25,21,22,5,10,1,6,7,12,15,2,24,3,20,13,19,11,8,17,14,0,18,4};
const int value[27] = {244,862,678,564,226,1309,844,765,363,4656,909,414,691,463,333,687,11998,329,218,423,536,1944,1244,4673,639,3363,0};

void insert(char* string){
    node* place = root;
    int i;
    for(i=0;i<5;i++){
        if(place->child[string[i] - ''A''] == NULL){
            int j;
            place->child[string[i] - ''A''] = malloc(sizeof(node));
            for(j=0;j<26;j++){
                place->child[string[i] - ''A'']->child[j] = NULL;
            }
        }
        place = place->child[string[i] - ''A''];
    }
    memcpy(place->string, string, 6);
}

void snapshot(){
    static int count = 0;
    int i;
    for(i=0;i<5;i++){
        printf("%s/n", htrie[i]->string);
    }
    for(i=0;i<27;i++){
            printf("%c%d ", ''A''+i, bag[i]);
    }
    printf("/n");
    if(++count>=1000){
        exit(0);
    }
}


void pick(x, y){
    if(y==5){
        if(score>max_score){
            snapshot();
            max_score = score;
        }
        return;
    }
    int i, tile,nextx, nexty;
    node* oldv = vtrie[x];
    node* oldh = htrie[y];
    if(x+1==5){
        nextx = 0;
        nexty = y+1;
    } else {
        nextx = x+1;
        nexty = y;
    }
    for(i=0;i<26;i++){
        if(vtrie[x]->child[order[i]]!=NULL &&
           htrie[y]->child[order[i]]!=NULL &&
           (tile = bag[order[i]] ? order[i] : bag[26] ? 26 : -1) + 1) {
                vtrie[x] = vtrie[x]->child[order[i]];
                htrie[y] = htrie[y]->child[order[i]];
                bag[tile]--;
                score+=value[tile];

                pick(nextx, nexty);

                vtrie[x] = oldv;
                htrie[y] = oldh;
                bag[tile]++;
                score-=value[tile];
           }
    }
}

int main(int argc, char** argv){
    root = malloc(sizeof(node));
    FILE* wordlist = fopen("sowpods5letters.txt", "r");
    score = 0;
    max_score = 0;
    int i;
    for(i=0;i<26;i++){
        root->child[i] = NULL;
    }
    for(i=0;i<5;i++){
        vtrie[i] = root;
        htrie[i] = root;
    }
    for(i=0;i<27;i++){
        bag[i] = bag[i] - block_1[i];
        bag[i] = bag[i] - block_2[i];
        bag[i] = bag[i] - block_3[i];

        printf("%c%d ", ''A''+i, bag[i]);
    }

    char* string = malloc(sizeof(char)*6);
    while(fscanf(wordlist, "%s", string) != EOF){
        insert(string);
    }
    free(string);
    fclose(wordlist);
    pick(0,0);

    return 0;
}

Después de descubrir cuántos bloques había (casi 2 mil millones y aún contando), cambié a tratar de encontrar ciertos tipos de bloques, en particular los difíciles de construir con letras poco comunes. Mi esperanza era que si terminaba con un conjunto bastante benigno de cartas yendo al último bloque, el vasto espacio de bloques válidos probablemente tendría uno para ese conjunto de letras.

Le asigné a cada tesela un valor inversamente proporcional al número de 5 letras en las que aparece. Luego, cuando encontré un bloque válido, resumía los valores del mosaico, y si el puntaje era el mejor que había visto hasta ahora, imprimía fuera del bloque.

Para el primer bloque eliminé las fichas en blanco, pensando que el último bloque necesitaría más esa flexibilidad. Después de dejar que se ejecutara hasta que no había visto un bloque mejor aparecer durante algún tiempo, seleccioné el mejor bloque y quité las fichas de la bolsa, y ejecuté el programa nuevamente, obteniendo el segundo bloque. Repetí esto para el 3er bloque. Luego, para el último bloque, agregué los espacios en blanco y usé el primer bloque válido que encontró.

Answer 4

Estoy empezando con algo más simple.

Aquí hay algunos resultados hasta ahora:

   3736 2x2 solutions
8812672 3x3 solutions

The 1000th 4x4 solution is
   A A H S
   A C A I
   L A I R
   S I R E

The 1000th 5x5 solution is
   A A H E D
   A B U N A
   H U R S T
   E N S U E
   D A T E D

The 1000th 2x4x4 solution is
   A A H S | A A H S
   A B A C | A B A C
   H A I R | L E K U
   S C R Y | S T E D
   --------+--------
   D E E D | D E E M
   E I N E | I N T I
   E N O L | O V E R
   T E L T | L Y N E

Tenga en cuenta que transponer una "A" y un espacio en blanco que se está utilizando como una "A" debe considerarse la misma solución. Pero la transposición de las filas con las columnas se debe considerar como una solución diferente. Espero que tenga sentido.

Answer 5

Me acercaría al problema (ingenuamente, para estar seguro) tomando una opinión pesimista. Intentaría probar que no había una solución de 5x5, y por lo tanto, ciertamente no cuatro soluciones de 5x5. Para probar que no había una solución 5x5, intentaría construir una desde todas las posibilidades. Si mi conjetura fallara y pudiera construir una solución de 5x5, entonces, tendría una forma de construir soluciones 5x5 y trataría de construir todas las soluciones (independientes) de 5x5. Si hubiera al menos 4, entonces determinaría si alguna combinación cumple con las restricciones de conteo de letras.

[Editar] El conjunto nulo ha determinado que hay "4,430,974 soluciones 5x5". ¿Son estos válidos? Quiero decir que tenemos una limitación en la cantidad de letras que podemos usar. Esta limitación se puede expresar como un vector de límite BV = [9, 2, 2, 4, ...] correspondiente a los límites de A, B, C, etc. (Verá este vector en el código del Conjunto nulo). Una solución de 5x5 es válida si cada término de su vector de conteo de letras es menor que el término correspondiente en BV. Sería fácil verificar si una solución de 5x5 es válida tal como fue creada. Quizás el número 4,430,974 se puede reducir, por ejemplo, N.

De todos modos, podemos expresar el problema de la siguiente manera: encuentre cuatro vectores de conteo de letras entre los N cuya suma es igual a BV. Hay (N, 4) posibles sumas ("N elige 4"). Con N igual a 4 millones, esto todavía está en el orden de 10 ^ 25 --- no es un número alentador. Quizás podría buscar cuatro cuyos primeros términos sumen un total de 9, y si es así, verificar que los segundos términos suman un total de 2, etc.

Me gustaría destacar que después de elegir 4 de N, los cálculos son independientes, por lo que si tiene una máquina de múltiples núcleos puede hacer que esto funcione más rápido con una solución paralela.

[Editar2] Paralelizar probablemente no haría mucha diferencia, sin embargo. En este punto, podría tener una visión optimista: ciertamente hay más soluciones 5x5 de lo que esperaba, por lo que puede haber más soluciones finales de lo esperado. Tal vez no tenga que llegar muy lejos en el 10 ^ 25 para golpear a uno.