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

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

我目前的解决方案

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

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

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

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

  1. namespace GridWords
  2. {
  3.     class Program
  4.     {
  5.         static void Main(string[] args)
  6.         {
  7.             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" };
  8.             char[] letters = new char[] { 'a','a','b','c','d','e','h','k','l','n','o','r','z' };
  9.             for (int z = 0; z < words.Length; z++)
  10.             {
  11.                 Console.WriteLine(z);
  12.                 for (int y = 0; y < words.Length; y++)
  13.                 {
  14.                     bool letterCountCorrect0 = true;
  15.                     char[] wordLetters0 = words[z].tocharArray().Concat(words[y].tocharArray()).ToArray();
  16.                     for (int a = 0; a < wordLetters0.Length; a++)
  17.                     {
  18.                         if (countInstances(wordLetters0,wordLetters0[a]) != countInstances(letters,wordLetters0[a]))
  19.                         {
  20.                             letterCountCorrect0 = false;
  21.                             break;
  22.                         }
  23.                     }
  24.                     if (y != z && letterCountCorrect0)
  25.                     {
  26.                         for (int x = 0; x < words.Length; x++)
  27.                         {
  28.                             bool letterCountCorrect1 = true;
  29.                             char[] wordLetters1 = words[z].tocharArray().Concat(words[y].tocharArray()).Concat(words[x].tocharArray()).ToArray();
  30.                             for (int a = 0; a < wordLetters0.Length; a++)
  31.                             {
  32.                                 if (countInstances(wordLetters0,wordLetters0[a]))
  33.                                 {
  34.                                     letterCountCorrect1 = false;
  35.                                     break;
  36.                                 }
  37.                             }
  38.                             if (x != y && x != z && letterCountCorrect1)
  39.                             {
  40.                                 for (int w = 0; w < words.Length; w++)
  41.                                 {
  42.                                     bool letterCountCorrect2 = true;
  43.                                     char[] wordLetters2 = words[z].tocharArray().Concat(words[y].tocharArray()).Concat(words[x].tocharArray()).Concat(words[w].tocharArray()).ToArray();
  44.                                     for (int a = 0; a < wordLetters0.Length; a++)
  45.                                     {
  46.                                         if (countInstances(wordLetters0,wordLetters0[a]))
  47.                                         {
  48.                                             letterCountCorrect2 = false;
  49.                                             break;
  50.                                         }
  51.                                     }
  52.                                     if (w != x && w != y && w != z && letterCountCorrect2)
  53.                                     {
  54.                                         char[] row1 = words[z].tocharArray();
  55.                                         char[] row2 = words[y].tocharArray();
  56.                                         char[] row3 = words[x].tocharArray();
  57.                                         char[] row4 = words[w].tocharArray();
  58.                                         char[] wordLetterArray = row1.Concat(row2).Concat(row3).Concat(row4).ToArray();
  59.                                         Array.Sort(wordLetterArray);
  60.                                         if (wordLetterArray == letters)
  61.                                         {
  62.                                             string col1 = new string(new char[] { row1[0],row2[0],row3[0],row4[0] });
  63.                                             if (col1 != words[z] && col1 != words[y] && col1 != words[x] && col1 != words[w])
  64.                                             {
  65.                                                 string col2 = new string(new char[] { row1[1],row2[1],row3[1],row4[1] });
  66.                                                 if (col2 != words[z] && col2 != words[y] && col2 != words[x] && col2 != words[w])
  67.                                                 {
  68.                                                     string col3 = new string(new char[] { row1[2],row2[2],row3[2],row4[2] });
  69.                                                     if (col3 != words[z] && col3 != words[y] && col3 != words[x] && col3 != words[w])
  70.                                                     {
  71.                                                         string col4 = new string(new char[] { row1[3],row2[3],row3[3],row4[3] });
  72.                                                         if (col4 != words[z] && col4 != words[y] && col4 != words[x] && col4 != words[w])
  73.                                                         {
  74.                                                             if (words.Contains<String>(col1.ToLower()) && words.Contains<String>(col2.ToLower()) && words.Contains<String>(col3.ToLower()) && words.Contains<String>(col4.ToLower()))
  75.                                                             {
  76.                                                                 Console.WriteLine(new string(row1) + " " + new string(row2) + " " + new string(row3) + " " + new string(row4));
  77.                                                                 //Console.WriteLine(col1.ToString() + " " + col2.ToString() + " " + col3.ToString() + " " + col4.ToString());
  78.                                                             }
  79.                                                         }
  80.                                                     }
  81.                                                 }
  82.  
  83.                                             }
  84.                                         }
  85.                                     }
  86.                                 }
  87.                             }
  88.                         }
  89.                     }
  90.                 }
  91.             }
  92.         }
  93.  
  94.         private static int countInstances(char[] arrToSearch,char charToFind)
  95.         {
  96.             int count = 0;
  97.             for (int x = 0; x < arrToSearch.Length; x++)
  98.             {
  99.                 if (arrToSearch[x] == charToFind)
  100.                 {
  101.                     count++;
  102.                 }
  103.             }
  104.             return count;
  105.         }
  106.     }
  107. }

这是一个例子,按要求：

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

  1. T O
  2. O N

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

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

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

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

解决方法

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

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

  1. static readonly int[] Counts = new int[256];
  2. static void Add(string s) {
  3.     foreach (var c in s) {
  4.         Counts[c]++;
  5.     }
  6. }
  7. static bool Sub(string s) {
  8.     var res = true;
  9.     foreach (var c in s) {
  10.         res &= --Counts[c] >= 0;
  11.     }
  12.     if (!res) {
  13.         Add(s);
  14.     }
  15.     return res;
  16. }

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

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

  1. foreach (var w0 in Words) {
  2.     if (!Sub(w0)) continue;
  3.     foreach (var w1 in Words) {
  4.         if (!Sub(w1)) continue;
  5.         foreach (var w2 in Words) {
  6.             if (!Sub(w2)) continue;
  7.             foreach (var w3 in Words) {
  8.                 if (!Sub(w3)) continue;
  9.                 // Check if the w0..w3 combination yields four valid words
  10.                 // when you read it vertically,and restore the state
  11.                 Add(w3);
  12.             }
  13.             Add(w2);
  14.         }
  15.         Add(w1);
  16.     }
  17.     Add(w0);
  18. }

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

  1. var allExist = true;
  2. for (var i = 0; allExist && i != 4; i++) {
  3.     vert[0] = w0[i];
  4.     vert[1] = w1[i];
  5.     vert[2] = w2[i];
  6.     vert[3] = w3[i];
  7.     allExist = Words.Contains(new string(vert));
  8. }
  9. if (allExist) {
  10.     found = true;
  11.     Console.WriteLine(w0);
  12.     Console.WriteLine(w1);
  13.     Console.WriteLine(w2);
  14.     Console.WriteLine(w3);
  15.     Console.WriteLine();
  16. }

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

猜你在找的C#相关文章

C#使用SharpZipLib创建压缩文件，并指定压缩文件夹路径（解决SharpZipLib压缩长路径显示问题）
在项目中使用SharpZipLib压缩文件夹的时候，遇到如果目录较深，则压缩包中的文件夹同样比较...
C#使用Parallel处理数据同步写入Datatable并使用BulkInsert批量导入数据库
项目需要，几十万张照片需要计算出每个照片的特征值（调用C++编写的DLL）。 业务流...
C# byte和10进制、16进制相互转换
var array = new byte[4]; var i = Encoding.UTF8.GetBytes(100.ToString(&quot;x2&am...
Winform下的Combox根据值来选中项
其实很简单，因为Combox的Item是一个K/V的object，那么就可以把它的items转换成IEnumerabl...
HM NIS Edit制作安装包时检测是否有.net4.6环境，没有的时候自动安装。
把.net4.6安装包打包进安装程序。 关键脚本如下： 头部引用字符串对比库 !include &qu...
WPF下使用FreeRedis操作RedisStream实现简单的消息队列
Redis Stream简介 Redis Stream是随着5.0版本发布的一种新的Redis数据类型： 高效消费者组...
C#进行图片压缩（对jpg压缩效果最好）
直接上代码 1 public static class ImageCompress 2 { 3 /// &lt;summary&gt; 4 /...
CefSharp访问需要认证网页或接口(在Request的Headers中添加认证Token)
然后在使用的时候，就可以获取到Header的内容了。
C#使用FileSystemWatcher来监控指定文件夹，并使用TCP/IP协议通过Socket发送到另外指定文件夹
项目需求： 局域网内有两台电脑，电脑A(Windows系统)主要是负责接收一些文件（远程桌面粘贴...
绿色版Mysql自动建立my.ini和命令行启动并动态指定datadir路径
1、先去下载绿色版的Mysql(https://cdn.mysql.com//archives/mysql-5.7/mysql-5.7.20-winx...
PHPJavaJava SEPythonC#C&C++RubyVBasp.NetGoPerlnettyDjangoDelphiJsp.NET CoreSpringFlaskSpringbootSpringMVCLuaLaravelMybatisAspGroovyThinkPHPYiiswoole
文件时间pythonm相等性PHP Warning时间问题问题解决pcntl_signal采样点wav模块动态文本调用频率限制对外暴露多个访问请求更新数据表模型结构type()方法比较速度手写体sobel算子保存模型Image类nn.Conv2dpytorch1.0kaggleDCGAN交并比range()用法打印模型反卷积卷积