Thực hiện một bộ giải scrabble

Question

trước khi tôi hỏi bất cứ điều gì, chỉ cần cho mọi người biết rằng đây là cho vui và tôi đã đăng tất cả mã của tôi mà tôi có cho đến nay; sẽ đăng bài nhiều hơn khi mọi thứ được cố định/triển khai), xin lỗi vì bài đăng dài!

Tôi có hai câu hỏi ở đây và tôi sẽ đăng tất cả mã của tôi bên dưới.

1. Tôi không thể tìm ra lý do tại sao khi nhập hơn 12 chữ cái với một số chữ cái giống nhau, tôi nhận được nhiều bản sao như int 'được chấp nhận' của tôi được đặt ra để tránh trùng lặp (hoạt động cho hầu hết các phần);
2. cho đầu vào tối đa 26 chữ cái và bảng nxn (có một số chữ cái đã điền sẵn), xuất tất cả các từ có thể phù hợp với các điểm hợp lệ. Bất kỳ lời khuyên nào về cách thực hiện điều này (bảng sẽ là một mảng 2 byte 1 byte trong mỗi chữ cái 1)

Ngay bây giờ Đây chỉ là chương trình dựa trên văn bản chấp nhận tối đa 26 chữ cái và đầu ra tất cả các từ có giá trị từ 200K từ + từ điển được đăng ở đây:

http://www.calvin.edu/~rpruim/scrabble/ospd3.txt

chương trình C dưới đây đòi hỏi sự từ điển để được cắt thành 26 file chứa tất cả các từ bắt đầu bằng mỗi chữ cái trong mỗi tập tin (tất cả một từ nào trong tệp 'a' vv ...) perl được đăng dưới đây để làm như vậy.

Lời Finder (c):

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

#define NUM_CHARS 26 
#define MAX_WORD_LEN 20 
#define WORDS_PER_LINE 12 

/* Character link structure */ 
typedef struct char_link 
{ 
    struct char_link **cl; /* All of this links possible next characters */ 
    short eow;    /* END OF WORD (means this is the last letter of a valid word */ 
} CHARLINK; 
/* Global found word count, used for printing '\n' char. */ 
unsigned short gwc = 0; 
CHARLINK * _init_link(CHARLINK **link) 
{ 
    short i; 
    (*link)->cl = (CHARLINK **) malloc(NUM_CHARS * sizeof(CHARLINK *)); 
    for (i = 0; i < NUM_CHARS; i++) 
     (*link)->cl[i] = NULL; 
    (*link)->eow = 0; 
    return (*link); 
} 

void _build_char_link(CHARLINK *link) 
{ 
    FILE *fp; 
    char *ptr, file[2]; 
    CHARLINK *current_link = NULL; 
    char line_buffer[MAX_WORD_LEN]; 
    unsigned short size = 0; 
    static short letter_index = 0; 
    int current_letter = 0; 

    sprintf(file, "%c", letter_index + 'a'); 
    current_link = _init_link(&link); 

    if (fp = fopen(file, "r")) 
    { 
     while (fgets(line_buffer, MAX_WORD_LEN, fp) > 0) 
     { 
      /* Skip letter_index */ 
      ptr = line_buffer + 1; 

      while(*ptr && (*ptr != '\n' && *ptr != '\r')) 
      { 
       current_letter = (int)(*ptr - 'a'); 

       /* Create and jump to new link */ 
       if (!current_link->cl[current_letter]) 
       { 
        current_link->cl[current_letter] = (CHARLINK *) malloc (sizeof(CHARLINK)); 
        current_link = _init_link(&current_link->cl[current_letter]); 
       } 
       /* Jump to existing link */ 
       else 
        current_link = current_link->cl[current_letter]; 

       ptr++; 
      } 

      current_link->eow = 1; 
      /* Reset our current_link pointer to the letter_index link */ 
      current_link = link; 
     } 
     fclose(fp); 
    } 
    else 
     printf("Warning: Couldn't import words for letter: %s\n", file); 

    letter_index++; 
} 

void _draw_tree(CHARLINK *link, short letter, short depth) 
{ 
    short i, tmp; 

    if (!depth) 
    { 
     printf("Data for letter %c\n", letter + 'a'); 
     printf("%c\n", letter + 'a'); 
    } 

    for (i = 0; i < NUM_CHARS; i++) 
    { 
     if (link->cl[i]) 
     { 
      tmp = depth; 
      while (tmp-- >= 0) 
       printf("\t"); 
      printf("%c(%d)\n", i + 'a', link->cl[i]->eow); 
      _draw_tree(link->cl[i], letter, depth + 1); 
     } 
    } 
} 

void _get_possible_words(CHARLINK *link, char *prefix, char *letters, unsigned int input_len, unsigned int depth) 
{ 
    short i, len, j; 
    unsigned int attempted = 0x00000000; 

    if (link->eow) 
    { 
     printf("\t%s", prefix); 
     if (++gwc == WORDS_PER_LINE) 
     { 
      printf("\n"); 
      gwc = 0; 
     } 
    } 

    len = strlen(prefix); 
    for (i = 0; i < input_len; i++) 
    { 
     if (letters[i]) 
     { 
      j = (1 << (letters[i] - 'a')); 
      if (!(j & attempted) && link->cl[letters[i] - 'a']) 
      { 
       prefix[len] = letters[i]; 
       letters[i] = '\0'; 
       _get_possible_words(link->cl[prefix[len] - 'a'], prefix, letters, input_len, depth + 1); 
       letters[i] = prefix[len]; 
       prefix[len] = '\0'; 
      } 
      attempted |= j; 
     } 
    } 
} 

int main(int argc, char *argv[]) 
{ 
    short i; 
    /* 26 link structures for a-z */ 
    CHARLINK root_nodes[NUM_CHARS]; 
    printf("Building structures "); 
    for (i = 0; i < NUM_CHARS; i++) 
    { 
     _build_char_link(&root_nodes[i]); 
     printf(". "); 
    } 
    printf("Done!\n"); 
    /* Debug, what do our trees look like? */ 
    //for (i = 0; i < NUM_CHARS; i++) 
    // _draw_tree(&root_nodes[i], i, 0); 

    for(;;) 
    { 
     short input_len = 0; 
     unsigned int j = 0, attempted = 0x00000000; 
     char input[26] = {0}; 
     char letters[26] = {0}; 
     char prefix[26] = {0}; 
     printf("Enter letters ('0' to exit): "); 
     gets(input); /* Yay buffer overflow */ 
     if (input[0] == '0') break; 
     sprintf(letters, "%s", input); 
     input_len = strlen(input); 
     for (i = 0; i < input_len; i++) 
     { 
      j = (1 << (input[i] - 'a')); 
      if (!(j & attempted)) 
      { 
       prefix[0] = input[i]; 
       letters[i] = '\0'; 
       _get_possible_words(&root_nodes[prefix[0] - 'a'], prefix, letters, input_len, 1); 
       letters[i] = input[i]; 
       attempted |= j; 
      } 
     } 
     printf("\n"); 
    } 

    return 255; 
} 

file được chia nhỏ (perl):

#!/usr/bin/perl 
open(FH, "< words.txt"); 
my %w = map { $_ => {} } 'a'..'z'; 
while (<FH>) 
{ 
    s/\s+$//; 
    $w{lc $1}->{lc $_} = 1 if /^(\w)/; 
} 

foreach my $l (keys %w) 
{ 
    open (OUT, "> $l"); 
    foreach my $a (keys %{$w{$l}}) 
    { 
     print OUT "$a\n"; 
    } 
    close OUT; 

} 

Answer 1

Chỉ cần một vài suy nghĩ về Perl của bạn.

Không có lý do gì để khởi chạy băm lớn. Bạn có thể khởi tạo trong một dòng với điều này:

my %w = map { $_ => {} } 'a'..'z'; 

Nhưng có thực sự là không có lý do gì để init ở tất cả, Perl sẽ autovivify các refs băm cho bạn khi bạn nói:

$w{$1}{$_} = 1 if /^(\w)/; 

Nhưng bạn có một lỗi, nếu một từ bắt đầu bằng một lá thư của thủ đô, nó sẽ đi vào sai phím. Nếu bạn muốn nắm bắt các loại lỗi này, bạn có thể sử dụng Hash :: Util's lock_keys để ngăn các khóa mới được thêm vào băm của bạn. Để khắc phục lỗi, hãy bình thường hóa các từ của bạn bằng cách sử dụng lc hoặc uc để buộc đúng trường hợp.

Bạn có một số vấn đề về phong cách khác với Perl của mình. Ngoài ra, kể từ khi bạn đang làm việc với (có lẽ) các tập tin lớn, tại sao giữ tất cả các từ trong bộ nhớ?

#!/usr/bin/perl 
use strict; 
use warnings; 

use IO::Handle; 

open my $fh, '<', $wordlist_path 
    or die "Error opening word list '$wordlist' - $!\n"; 

# Open a handle for each target file.  
my %handle = map { 
    open my $fh, '>', $_ 
     or die "Error opening sublist $_ - $!\n"; 
    $_ => $fh; 
} 'a'..'z'; 

while(my $word = <$fh>) { 

    $word = clean_word($word); 

    my $first_letter = substr $word, 0, 1; 

    $handle{$first_letter}->print("$word\n"); 
} 

sub clean_word { 
    my $word = shift; 

    chomp $word; 
    $word = lc $word; 

    $word =~ s/^\s*//; 
    $word =~ s/\s*$//; 

    return $word; 
}