c# – 我的迭代正在永远.寻找更好的方法

前端之家收集整理的这篇文章主要介绍了c# – 我的迭代正在永远.寻找更好的方法前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
给定一组16个字母和一个英文字文件,需要找到一个解决方案,其中这16个字母可以放入4×4网格中,以便可以在每行和每列下读取有效字.

我目前的解决方

1)获取可以用这些字母(anagram generator)制作的所有可能的4个字母单词的列表,并将它们分配给数组.

2)循环遍历每个单词,在每一行中尝试它,同时检查每个单词的正确数量是否被使用.

3)检查anagram数组中是否存在每列中创建的单词.

逻辑工作,但它已经运行了一个多小时,我在400字节的字谜词200.有什么建议?

namespace GridWords
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] words = new string[] { "zoon","zonk","zone","zona","zoea","zobo","zero","zerk","zeal","zack","rore","roon","rook","rood","rone","role","roke","roed","rode","rock","roch","robe","roar","roan","road","rhea","rend","redo","reck","rear","rean","real","reak","read","raze","rare","rank","rand","rana","rale","rake","rade","rack","rach","race","raca","orzo","orra","orle","ordo","orca","oral","orad","ooze","oner","once","oleo","olea","olde","okra","okeh","ohed","odor","odea","odal","odah","oche","obol","oboe","nork","noob","nook","nolo","nole","noel","node","nock","nerk","nerd","neck","near","neal","naze","nark","nare","nard","narc","nala","nada","nach","nabk","nabe","lorn","lore","lord","loor","loon","look","lone","loke","lode","loco","lock","loch","loca","lobo","lobe","loan","load","leno","lend","lehr","lech","lear","lean","leak","lead","lazo","laze","larn","lark","lare","lard","lank","lane","land","lana","lakh","lake","laer","lade","lack","lace","krab","kore","kora","kond","kolo","kola","kohl","koel","kobo","koan","knob","knar","khor","khan","kern","kerb","keno","kbar","karn","kara","kaon","kane","kana","kale","kaed","kade","horn","hore","hora","hoon","hook","hood","honk","hone","hond","holk","hole","hold","hoke","hoer","hoed","hock","hobo","hoar","hero","hern","herl","herd","herb","hend","helo","held","heck","hear","heal","head","haze","haro","harn","harl","hark","hare","hard","hank","hand","halo","hale","hake","haka","haen","haed","hade","hack","haar","eorl","eoan","enol","elan","ecod","echo","ecad","ebon","earn","earl","eard","each","dzho","drek","drab","doze","dorr","dork","dore","door","dool","dook","doob","done","dona","dole","doer","doen","doek","dock","doab","dhal","dhak","dern","deco","deck","dear","dean","deal","daze","darn","darl","dark","dare","darb","dank","dale","dahl","dace","daal","czar","cred","cran","crab","coze","corn","cork","core","cord","coon","cool","cook","conk","cone","cond","cole","cold","cola","coke","coho","coed","code","coda","coal","clon","clod","clan","clad","chon","chez","cher","char","chao","chal","chad","cero","carr","carn","carl","cark","care","card","carb","cane","calo","calk","cake","cade","caba","broo","brod","brer","bren","bred","bran","brae","brad","bozo","born","bork","bore","bord","bora","boor","boon","bool","book","booh","bonk","bone","bond","bona","bolo","bole","bold","bola","boko","boke","boho","bode","bock","boar","boak","bloc","bled","blah","blae","blad","bhel","berk","bend","beck","bear","bean","beak","bead","barn","bark","bare","bard","bank","bane","band","banc","balk","bale","bald","bake","bael","bade","back","bach","baal","azon","azan","arna","arle","ared","area","arco","arch","arba","arar","arak","anoa","ankh","ance","anal","aloe","alod","alec","albe","alba","alar","alan","alae","aked","ahed","aero","aeon","adze","acre","acne","ache","acer","aced","able","abed","abac" };
            char[] letters = new char[] { 'a','a','b','c','d','e','h','k','l','n','o','r','z' };
            for (int z = 0; z < words.Length; z++)
            {
                Console.WriteLine(z);
                for (int y = 0; y < words.Length; y++)
                {
                    bool letterCountCorrect0 = true;
                    char[] wordLetters0 = words[z].tocharArray().Concat(words[y].tocharArray()).ToArray();
                    for (int a = 0; a < wordLetters0.Length; a++)
                    {
                        if (countInstances(wordLetters0,wordLetters0[a]) != countInstances(letters,wordLetters0[a]))
                        {
                            letterCountCorrect0 = false;
                            break;
                        }
                    }
                    if (y != z && letterCountCorrect0)
                    {
                        for (int x = 0; x < words.Length; x++)
                        {
                            bool letterCountCorrect1 = true;
                            char[] wordLetters1 = words[z].tocharArray().Concat(words[y].tocharArray()).Concat(words[x].tocharArray()).ToArray();
                            for (int a = 0; a < wordLetters0.Length; a++)
                            {
                                if (countInstances(wordLetters0,wordLetters0[a]))
                                {
                                    letterCountCorrect1 = false;
                                    break;
                                }
                            }
                            if (x != y && x != z && letterCountCorrect1)
                            {
                                for (int w = 0; w < words.Length; w++)
                                {
                                    bool letterCountCorrect2 = true;
                                    char[] wordLetters2 = words[z].tocharArray().Concat(words[y].tocharArray()).Concat(words[x].tocharArray()).Concat(words[w].tocharArray()).ToArray();
                                    for (int a = 0; a < wordLetters0.Length; a++)
                                    {
                                        if (countInstances(wordLetters0,wordLetters0[a]))
                                        {
                                            letterCountCorrect2 = false;
                                            break;
                                        }
                                    }
                                    if (w != x && w != y && w != z && letterCountCorrect2)
                                    {
                                        char[] row1 = words[z].tocharArray();
                                        char[] row2 = words[y].tocharArray();
                                        char[] row3 = words[x].tocharArray();
                                        char[] row4 = words[w].tocharArray();
                                        char[] wordLetterArray = row1.Concat(row2).Concat(row3).Concat(row4).ToArray();
                                        Array.Sort(wordLetterArray);
                                        if (wordLetterArray == letters)
                                        {
                                            string col1 = new string(new char[] { row1[0],row2[0],row3[0],row4[0] });
                                            if (col1 != words[z] && col1 != words[y] && col1 != words[x] && col1 != words[w])
                                            {
                                                string col2 = new string(new char[] { row1[1],row2[1],row3[1],row4[1] });
                                                if (col2 != words[z] && col2 != words[y] && col2 != words[x] && col2 != words[w])
                                                {
                                                    string col3 = new string(new char[] { row1[2],row2[2],row3[2],row4[2] });
                                                    if (col3 != words[z] && col3 != words[y] && col3 != words[x] && col3 != words[w])
                                                    {
                                                        string col4 = new string(new char[] { row1[3],row2[3],row3[3],row4[3] });
                                                        if (col4 != words[z] && col4 != words[y] && col4 != words[x] && col4 != words[w])
                                                        {
                                                            if (words.Contains<String>(col1.ToLower()) && words.Contains<String>(col2.ToLower()) && words.Contains<String>(col3.ToLower()) && words.Contains<String>(col4.ToLower()))
                                                            {
                                                                Console.WriteLine(new string(row1) + " " + new string(row2) + " " + new string(row3) + " " + new string(row4));
                                                                //Console.WriteLine(col1.ToString() + " " + col2.ToString() + " " + col3.ToString() + " " + col4.ToString());
                                                            }
                                                        }
                                                    }
                                                }

                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

        private static int countInstances(char[] arrToSearch,char charToFind)
        {
            int count = 0;
            for (int x = 0; x < arrToSearch.Length; x++)
            {
                if (arrToSearch[x] == charToFind)
                {
                    count++;
                }
            }
            return count;
        }
    }
}

这是一个例子,按要求:

给定字母“N,O,O和T”找到一个解决方案,其中这些字母适合2×2网格,以便在横向和向下阅读时,可以创建英文单词.答案是:

T O
O N

除了这个问题是4×4网格.

更新:谢谢你的帮助,但我是个白痴.我没有修复我的复制/粘贴变量(我想,这可以追溯到那个建议我重构的人).此外,我比较数组的方式是错误的.修正了这些问题,并针对已知的工作单词列表,像魅力一样工作.再次对着我的原始数据,花了13秒.没有结果.再次感谢你的帮助.

更新2:由于我没有足够的代表回答我自己的问题,这是我的工作代码(…代码删除…请参阅下面的dasblinklight的答案)

更新3:请参阅下面的dasblinkenlight的答案.更优雅,更少的循环.谢谢!

解决方法

您不需要嵌套七个级别,您只需要五个:四个循环来尝试所有适合16个字母集的单词组合,以及一个额外的循环来检查选择所暗示的四个垂直组合横向的话.

您需要一种有效的方法来管理您当前使用的字母集.处理它的一种方法是创建一个计数器数组,如下所示:

static readonly int[] Counts = new int[256];
static void Add(string s) {
    foreach (var c in s) {
        Counts[c]++;
    }
}
static bool Sub(string s) {
    var res = true;
    foreach (var c in s) {
        res &= --Counts[c] >= 0;
    }
    if (!res) {
        Add(s);
    }
    return res;
}

Sub(string)尝试从计数中“减去”该单词,如果成功则返回true.添加(字符串)将单词添加回计数.

现在您可以编写代码的四向嵌套框架,如下所示:

foreach (var w0 in Words) {
    if (!Sub(w0)) continue;
    foreach (var w1 in Words) {
        if (!Sub(w1)) continue;
        foreach (var w2 in Words) {
            if (!Sub(w2)) continue;
            foreach (var w3 in Words) {
                if (!Sub(w3)) continue;
                // Check if the w0..w3 combination yields four valid words
                // when you read it vertically,and restore the state
                Add(w3);
            }
            Add(w2);
        }
        Add(w1);
    }
    Add(w0);
}

垂直单词的检查会添加第五个和最后一个嵌套级别.我将单词转换为哈希集以加快检查:

var allExist = true;
for (var i = 0; allExist && i != 4; i++) {
    vert[0] = w0[i];
    vert[1] = w1[i];
    vert[2] = w2[i];
    vert[3] = w3[i];
    allExist = Words.Contains(new string(vert));
}
if (allExist) {
    found = true;
    Console.WriteLine(w0);
    Console.WriteLine(w1);
    Console.WriteLine(w2);
    Console.WriteLine(w3);
    Console.WriteLine();
}

您可以找到this program on the pastebin.它可以在我的计算机上完成几分钟而无需生成解决方案.我确认它找到了存在的解决方案(但是当您注释掉单词和字母并取消注释最后两行时,程序会找到有效组合及其转置图像).

猜你在找的C#相关文章