Моя итерация длится бесконечно. Ищем лучший способ
Учитывая набор из шестнадцати букв и файл словаря английского языка, необходимо найти решение, в котором эти шестнадцать букв могут уместиться в сетку 4x4, чтобы допустимое слово можно было прочитать в каждой строке и в каждом столбце.
Мое текущее решение:
1) Получить список всех возможных 4-буквенных слов, которые могут быть составлены из этих букв (генератор анаграмм), и назначить их массиву.
2) Прокрутите каждое слово, пробуя его в каждой строке, проверяя, используется ли правильный номер каждой буквы.
3) Проверка, существует ли слово, созданное в каждом столбце, в массиве анаграмм.
Логика работает, но она работает более часа, и я нахожусь на слове 200 из более чем 400 массивов анаграмм. Есть предложения?
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', 'o', 'o', 'r', '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]) != countInstances(letters, 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]) != countInstances(letters, 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», найдите решение, в котором эти буквы вписываются в сетку 2x2, чтобы при чтении поперек и вниз английский слова могут быть созданы. Ответ будет:
T O
O N
За исключением того, что эта проблема относится к сетке 4x4.
ОБНОВЛЕНИЕ: Спасибо за помощь, но я идиот. Я не исправил свои скопированные / вставленные переменные (что, я полагаю, восходит к парню, который предложил мне провести рефакторинг). Кроме того, способ, которым я сравнивал массивы, был неправильным. Устранены эти проблемы и работает против известного рабочего списка слов, работает как шарм. Снова проверил мои исходные данные, потребовалось 13 секунд. Никаких результатов. В очередной раз благодарим за помощь.
ОБНОВЛЕНИЕ 2: Поскольку у меня недостаточно репутации, чтобы ответить на мой вопрос, вот мой рабочий код (... код удален ... см. Ответ dasblinklight ниже)
ОБНОВЛЕНИЕ 3: см. Ответ dasblinkenlight ниже . Намного наряднее, петель меньше. Спасибо!