Another iteration of Alien Language

Question

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:

1. any characters in the test case within brackets are possible characters. (choose one)
2. Since I'm looping through to work out all possible combinations I'm testing the substring to see if the dictionary allows it.
3. 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.

Answer 1

You need a clever data structure in order to avoid to check all possible combinations. I would suggest Trie structure with some additional statistic for every char position. Using Trie you can pretty quick find which letter is possible in which position and which isn't possible.

One more and better idea - use regexp, the every test case looks like a regexp condition ;) All you need is just correct test case string, loop over all dictionary words and execute the match(corrected_test_case_string), and increase the counter if it matches.

I would post python code, as a pseudo code, it's tiny and you can see the idea behind the second approach:

import sys, re
f = open(sys.argv[1])
_, d, n = map(int, f.readline().split())
dict = ''.join([next(f) for _ in range(d)])
i = 1
for test_case in f:
    regexp = '^' + test_case.replace("(","[").replace(")","]")
    print("Case #%d: %d" % (i, len(re.findall(regexp, dict, re.M))))
    i += 1

C# version:

using System;
using System.Text.RegularExpressions;

namespace AlienLanguage
{
    class Program
    {
        static void Main(string[] args)
        {
            var allLines = System.IO.File.ReadAllLines(@"\path\to\A-large-practice.in");
            string[] p = allLines[0].Split(' ');
            String words = "";
            for (int i = 1; i <= int.Parse(p[1]); i++)
            {
                words += allLines[i] + " ";
            }
            for (int i = int.Parse(p[1]); i <= int.Parse(p[2]); i++)
            {
                int result = new Regex(allLines[i].Replace("(", "[").Replace(")", "]")).Matches(words).Count;
                Console.WriteLine("Case #{0}: {1}", i + 1 - int.Parse(p[1]), result);
            }
        }
    }
}

Answer 2

To build on what cat_baxter suggested with regular expressions, try this:

1. Concatenate all "words" into a single string separated by spaces.
2. For each pattern:
   1. Turn () into [].
   2. Use new Regex(pattern).Matches(wordList).Count() to get the number of possible words.
   3. Output results for that pattern

Regular expressions can get slow, but it's very straight forward code.

---

Another possibility would be to store the words in a dictionary of nested dictionaries. The key would be a letter, and the value is another dictionary of every letter that can follow that. Repeat until you've reached the maximum depth.

For the sample case, this would look like

{'a', {'b', {'c'}}}
{'b', {'c', {'a'}}}
{'c', {'b', {'a'}}}
{'d', {'a', {'c'}},
      {'b', {'a'}}}

Then you can use LINQ to find matches by recursively building up a query which looks like:

(ab)(bc)(ca)

wordArray.Where(x => x.Key == 'a' || x.Key == 'b').SelectMany(x => x.Value)
         .Where(x => x.Key == 'b' || x.Key == 'c').SelectMany(x => x.Value)
         .Where(x => x.Key == 'c' || x.Key == 'a').SelectMany(x => x.Value)
         .Count();

Here's a pseudo-coded recursive function to build the query, since I'm feeling lazy and don't want to double check all the string functions. I haven't tested it for speed - it might be too slow, but I think it should work.

class WordList
{
    public Dictionary<char, WordList> Words { get; set;}
}
public int ParseWord(IEnumerable<WordList> query, string remainingWord)
{
    if (remainingWord == "") 
    {
       return query.Count();
    }
    else if (remainingWord[0] == '(')
    {
       var options = remainingWord.Substring(/* read to first ')' */);
       var remainder = remainingWord.Substring(/* everything after the ')' */);
       return ParseWord(query.Select(x => x.Words).Where(x => options.Any(o => x.Key == o).SelectMany(x => x.Value), remainder);
    }
    else
    {
       var letter = remainingWord[0];
       var remainder = remainingWord.Substring(/* everything after the first character */);
       return ParseWord(query.Select(x => x.Words).Where(x => options.Any(o => x.Key == o).SelectMany(x => x.Value), remainder);
    }
  }