c - 实现拼字游戏求解器

Question

在我问任何问题之前，只是让大家知道这是为了好玩，我已经发布了我目前所有的代码；随着事情的修复/实现，将发布更多内容)，对于冗长的帖子感到抱歉!

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

1. 我似乎无法弄清楚为什么当输入 12 个以上的字母和一些相同的字母时，我得到了几个重复项，因为我的“接受”int 已经到位以避免重复(大部分情况下有效)；
2. 给定最多 26 个字母的输入和一个 nxn 板(已经填充了一些字母)，输出适合有效位置的所有可能的单词组合。关于如何解决这个问题的任何建议(板将是一个二维数组，每个数组中有 1 个字符空间，代表 1 个字母)

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

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

下面的 C 程序要求将字典分成 26 个文件，其中包含每个文件中以每个字母开头的所有单词(文件 'a' 中的所有单词等...)perl 在下面发布以执行此操作。

找词器(三):

#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 来防止新的 key 被添加到你的哈希中。要修复此错误，请使用 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;
}