SORU
31 Ocak 2011, PAZARTESİ

Scrabble çini kontrol

Scrabble çini kontrol etmek için, mektuplar 100 çini olmak üzere toplam dört 5x5 ızgaraları olun. Tüm yatay ve dikey 40 sözlerinin geçerli olduğu bir yapmak istiyorum. İçerir: mevcut kiremit ayarlayın

  • 12 x E
  • 9 x, ben
  • 8 x Ç
  • 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, boş karo (joker)
  • 1 x K, J, Q, X, Z

Geçerli kelimeler sözlüğü mevcuttur here (700KB). Geçerli 5 harf yaklaşık 12.000 kelime vardır.

İşte tüm 20 yatay sözlerinin geçerli olduğu bir örnek:

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

Tüm dikey olanları da geçerli olduğu yerlerde bir tane oluşturmak istiyorum. Bana bu çözmeye yardımcı olabilir misiniz? Ödev değil. Bir arkadaşım benden yardım istedi bir soru.

CEVAP
31 Ocak 2011, PAZARTESİ

Son Düzenleme:Çözüldü!İşte bir çözüm.

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

İşte bir fotoğraf scrabble benim set ile inşa edilmiştir. http://twitpic.com/3wn7iu

Bu çok daha fazla olur bence çok doğru bir yaklaşım vardı, bir kez bulmak için kolay bir yol oldu. Metodoloji için aşağıya bakınız.

Her satır ve sütun için 5 harfli kelime sözlükten önek bir ağaç oluşturabilirsiniz. Özyinelemeli olarak, belirli bir kiremit yerleştirme eğer sütun ve satır için geçerli bir önek oluşturur, ve eğer kiremit varsa, ve eğer bir sonraki çini yerleştirme geçerli ise geçerlidir. Temel durum varsa karo yere bırakılırsa orada geçerli olmasıdır.

Muhtemelen sense sadece tüm geçerli 5x5 masası Glenn dediği gibi, bulmak ve onları herhangi bir dört kombine edilebilir olmadığını görmek için yapar. 100 derinliğe kadar Recursing eğlenceli gibi gelmedi.

Edit: bu benim kod Burada sürüm 2.

#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;
}

Bu artık iyi bir fikir olduğundan emin olduğum nadir harfleri önce çalışır. Tahtaları x ile başlayan dışarı kılmadan batağa saplanmış başlar. Ne kadar çok olduklarını gördükten sonra, tüm geçerli 5x5 blok liste için kodu değiştirdim. Ben şimdi 150 MB bir metin 4,430,974 5x5 tüm çözümleri ile dosya var.

Ben de tam 100 döşemeler arasında recursing ile çalıştı ve hala çalışıyor.

Edit 2: Burada oluşturulan tüm geçerli 5x5 blok liste. http://web.cs.sunyit.edu/~levyt/solutions.rar

Edit 3: Hmm, ben sadece 5 Zs kullanan çıkış dosyamda bir blok buldum çünkü karo kullanımını izleme bir hata var gibi görünüyor.

COSTE
ORCIN
SCUZZ
TIZZY
ENZYM

Edit 4: İşte son ürünü.

#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;
}

Kaç bölüm olduğunu öğrendikten sonra (yaklaşık 2 milyar ve devam ediyor hala), blok bazı türleri, özellikle zor olanlar nadir harfleri kullanarak inşa etmek bulmaya geçtim. Umudum eğer harfleri ile son bloğu için iyi yeterli bir set ile sona erdi eğer, geçerli blok geniş alan muhtemelen harfler kümesi için bir olurdu oldu.

Her karo göründüğü 5 harfli kelimeler sayısı ters orantılı bir değer atanmış. Geçerli bir blok buldum zaman sonra, çini değerlerini toplamak istiyorum, ve eğer skor henüz gördüğüm en iyi olsa blok yazdırmak istiyorum.

Birinci blok için boş kiremit, son blok esneklik en çok ihtiyacı olacağını düşünerek çıkardım. Sonra izin bitene kadar kaldım görülmeyen bir blok daha iyi görünmesi için biraz zaman, seçtiğim en iyi blok ve kaldırılan fayans ondan çanta, ve koştu programını yeniden, ikinci blok. 3 blok için bunu tekrarladım. Son blok için daha sonra boşlukları ve bulunan ilk geçerli bloğu tekrar kullanılan ekledim.

Bunu Paylaş:
  • Google+
  • E-Posta
Etiketler:
DizeStringAlgoritmaAlgorithmVeri YapılarıData-structures

AYNI ETİKETTEKİ VİDEOLAR

YORUMLAR

SPONSOR VİDEO

Rastgele Yazarlar

  • michellefeng's channel

    michellefeng

    26 Kasım 2006
  • Phandroid

    Phandroid

    26 Ocak 2009
  • WePlayWeWatch

    WePlayWeWatc

    3 Temmuz 2013

İLGİLİ SORU / CEVAPLAR

İLGİLİ BAĞLANTILAR