아무 것도 묻기 전에 스크래블 솔버

Question

을 구현합니다. 이제는 재미 있기 때문에 내가 지금까지 가지고있는 모든 코드를 게시했습니다. 모든 것이 고정/구현됨에 따라 더 게시 될 것입니다.), 긴 게시물을 유감스럽게 생각합니다!

여기에 두 가지 질문이 있습니다. 아래에서 모든 코드를 게시합니다.

1. 12 문자를 같은 글자로 입력 할 때 왜 중복되는 것을 피하기 위해 '받아 들인'int가 여러 곳에 들어 있는지 알 수 없습니다.);
2. 최대 26 자의 입력과 nxn 보드 (이미 일부 문자가 채워져 있음)는 유효한 지점에 맞는 모든 가능한 단어 조합을 출력합니다. 이것에 관해서 어떤 충고 (이사회는 각각 1 글자에 대해 2 차원 어레이 1 문자 공간이됩니다)

지금 바로 26 글자까지 출력 할 수있는 텍스트 기반 프로그램입니다 200K 단어 + 사전에서 유효한 모든 단어는 여기에 게시 :

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

아래의 C 프로그램은 각 파일의 각 문자 (파일의 모든 단어로 시작하는 모든 단어를 포함하는 26 개의 파일로 분리 할 수있는 사전이 필요 'a'등 ...) perl은 아래에 게시되어 있습니다.

말씀 파인더 (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; 
} 

파일 분할 (펄) : 펄에

#!/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

그냥 몇 가지 생각.

큰 해시 초기화가 필요하지 않습니다. 이 하나 개의 라인에서 초기화 할 수 있습니다 :

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

을하지만 당신이 말할 때 펄 당신을위한 해시 심판을 autovivify 것, 모든 init를 이유 정말 없다 :

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

은 그러나 당신은이 오류, 한 단어가 국회 의사당 편지로 시작하면 틀린 키로 들어갑니다. 이러한 종류의 오류를 잡으려면 Hash :: Util의 lock_keys을 사용하여 새 키가 해시에 추가되지 않도록 할 수 있습니다. 버그를 수정하려면 lc 또는 uc을 사용하여 단어를 정규화하여 대소 문자를 올바르게 입력하십시오.

Perl에는 다른 문체 문제가 있습니다. 또한 대용량 파일 (아마도)로 작업하고 있기 때문에 모든 단어를 메모리에 저장해야하는 이유는 무엇입니까?

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