实现拼字游戏解算器

Question

在我问任何事情之前,让大家知道这很有趣,我已经发布了我迄今为止所有的代码; 随着事情的修复/实施,会发布更多内容,对于冗长的帖子感到抱歉!

我在这里有两个问题,我将在下面发布我的所有代码.

1. 我似乎无法弄清楚为什么当输入12个字母和一些相同的字母时,我得到了几个重复,因为我的"接受"int是为了避免重复(大部分都有效);
2. 如果输入最多26个字母和一个nxn板(已经填写了一些字母),则输出适合有效点的所有可能的单词组合.关于如何进行此操作的任何建议(该板将是一个2维数组1个字符空间,每个1个字母)

现在它只是一个基于文本的程序,最多可接受26个字母,并输出200K字+字典中的所有有效单词:

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

下面的C程序要求将字典切成26个文件,其中包含每个文件中每个字母开头的所有单词(文件'a'等等中的所有单词...)perl将在下面发布.

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

文件拆分(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

关于你的Perl的一些想法.

没有理由进行大哈希初始化.您可以使用以下内容初始化:

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

但是根本没有理由进行初始化,当你说:Perl会为你自动生成散列引用:

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