Menu
Given a set of sixteen letters and an English dictionary file, need to find a solution where those sixteen letters can fit into a 4x4 grid so that a valid word can be read across each row, and down each column.
My current solution:
1) Get a list of all of the possible 4-letter words that can be made with those letters (anagram generator) and assign them to an array.
2) Loop through each word, trying it in every row, while checking that the correct number of each letter is used.
3) Checking if the word created in each column exists in the anagram array.
The logic works, but it's been running over an hour and I'm on word 200 of the 400+ array of anagrams. Any suggestions?
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;
}
}
}
Here is an example, as requested:
Given the letters "N, O, O, and T" find a solution where these letters fit into a 2x2 grid so that when read across and down, English words can be created. The answer would be:
T O
O N
Except this problem is for a 4x4 grid.
UPDATE: Thanks for your help, but I'm an idiot. I didn't fix my copy/pasted variables (which, I suppose, goes back to the guy who suggested I refactor). Also, the way I was comparing arrays was faulty. Fixed these issues and ran against known working word list, worked like a charm. Ran again against my original data, took 13 seconds. No results. Thanks again for your help.
UPDATE 2: Since I don't have enough rep to answer my own question, here is my working code (...code deleted...see dasblinklight's answer below)
UPDATE 3: Please see dasblinkenlight's answer below. Much more elegant, fewer loops. Thanks!
895
Growing variables in a loop takes very long. Each time you increase the length of the variable, a million times here, you force MATLAB to first create a variable with the initial length+1, then copy the contents, then delete the old variable. That's probably what is taking your code so long.
A faster way to loop in Python is using built-in functions. In our example, we could replace the for loop with the sum function. This function will sum the values inside the range of numbers. The code above takes 0.84 seconds.
The looping can be defined as repeating the same process multiple times until a specific condition satisfies. It is known as iteration also.
In programming, iteration is often referred to as 'looping', because when a program iterates it 'loops' to an earlier step.
Use a backtracking algorithm.
Start by reading my series of articles on how to use a backtracking algorithm to solve the graph colouring problem:
http://blogs.msdn.com/b/ericlippert/archive/tags/graph+colouring/
You do not have exactly the same problem, but it is very close.
Here's what you do. Suppose the grid is
11 12 13 14
21 22 23 24
31 32 33 34
41 42 43 44
You start with your sixteen letters: IDNVJGIEKGEESSSO, say.
make a guess as to what goes in 11. Say, I.
That now constrains what can possibly go in 12 and 21. Only those letters from words that begin with I and have a second letter from the remaining letters DNVJGIEKGEESSSO can be in 12 and 21. That enormously constrains the problem.
Now make a guess for 12. Say, D. That then constrains 13 and 22, further constraining the problem.
Now make a guess for 21, say, N, which constrains 22 (again) and 31.
Now make a guess for 22. It can't be V, J or G because no words begin NV, NJ or NG. Maybe it is I...
Keep doing that until you either find a solution, or you end up in a situation where there is no possible solution. If there is a solution, you're done. If there is no possible solution given the guesses you've made, you must backtrack to the previous guess and make a different guess until all possible guesses are exhausted. Then backtrack again. And so on. The key is to lower the number of possibilities for each guess quickly.
158
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
