I'm mostly looking for performance suggestions. Feel free to include more than just that.
Since Google Code Jam is coming around, I thought I would look at some of the previous questions. Alien Language is the one I picked and did this in my lunch / spare time / while waiting for the build to complete.
It's a little messy and this is the third (or fourth) iteration I've done. I'm starting to get quite curious about writing quicker running code. (Not something I would normally focus on.)
Firstly I'd open the file and pull all the relevant sections out. At this point I wasn't worried about performance.
// Open File:
var inputLines = System.IO.File.ReadAllLines(@"C:\A-large-practice.in");
//GetWordlength / DictionaryLength / Number of testCases
int[] ldnValues = inputLines.First().Split(' ').Select(intString => int.Parse(intString)).ToArray();
var LettersInWord = ldnValues[0];
var WordsInLanguage = ldnValues[1];
var NumberOfTestCases = ldnValues[2];
string[] vocabulary = inputLines.Skip(1).Take(WordsInLanguage).OrderBy(word => word).ToArray();
IEnumerable<string> testCases = inputLines.Skip(1).Skip(WordsInLanguage).Take(NumberOfTestCases);
Next I turn the Language (vocabulary) into a bunch of arrays. I do this so that later it can do a straight compare with the substring.
Also turn the list of test cases into a pair of (int, string) so that I can use the Linq.AsParallel
// Create a dictionary of (test case number , test case string) so that it can be paralellised and still keep its test number
int index = 1;
Dictionary<int, string> testCasesWithIndex = testCases.ToDictionary(x => index++, x => x);
var resultDict = new Dictionary<int, string>();
// Create an array of distinct strings for increasing lengths and put into a list.
var allVocabs = new List<string[]>();
for (var i = 1; i <= LettersInWord; i++)
{
allVocabs.Add(vocabulary.Select(word => word.Substring(0, i)).Distinct().OrderBy(word => word).ToArray());
}
I chose a regular expression to split the test cases up:
var pattern = new System.Text.RegularExpressions.Regex(@"([a-z]|\([a-z]+\))", System.Text.RegularExpressions.RegexOptions.Compiled);
Then comes the bad part: looping.
Notes:
- any characters in the test case within brackets are possible characters. (choose one)
- Since I'm looping through to work out all possible combinations I'm testing the substring to see if the dictionary allows it.
- This is the section I've changed the most.
System.Globalization.CompareInfo ci = System.Globalization.CultureInfo.CurrentCulture.CompareInfo;
//Parallelize the test cases and test each against the dictionary
testCasesWithIndex.AsParallel().ForAll(kvp =>
{
int testCaseNumber = kvp.Key;
string testCase = kvp.Value;
// Do a REGEX on the test case split by either a single character or brackets (...)
var matchCollection = pattern.Matches(testCase);
List<string> possibleValues = new List<string>() { "" };
// Loop through all characters (or brackets containing possible characters)
// and search for words in the dictionary
for (int currentMatch = 0; possibleValues.Count > 0 && currentMatch < matchCollection.Count; currentMatch++)
{
var match = matchCollection[currentMatch];
string matchValue = match.Value.Replace("(", "").Replace(")", "");
List<string> newPossibles = new List<string>();
// Through each position in the word find out if the substring is in the language
foreach (char character in matchValue)
{
foreach (string possibleValue in possibleValues)
{
string currentValue = possibleValue + character;
int currentvalueLength = currentValue.Length;
bool validWord = Array.BinarySearch(allVocabs[currentvalueLength -1], currentValue) > -1;
if (validWord)
{
newPossibles.Add(currentValue);
}
}
}
possibleValues = newPossibles;
}
string result = string.Format("Case #{0}: {1}", testCaseNumber, possibleValues.Count);
resultDict[kvp.Key] = result;
});
Then use the dictionary to output all the lines (and for debugging):
string output = System.String.Join("\n", resultDict.Select(kvp => kvp.Value));
System.IO.File.WriteAllText(@"c:\output.txt", output);
I admit that the solution is definitely messy.