Better ways of solving the substitution cipher puzzle

Question

---

here is the puzzle description

Your task is to decode messages that were encoded with substitution ciphers. In a substitution cipher, all occurrences of a character are replaced by a different character. For example, in a cipher that replaces "a" with "d" and "b" with "e", the message "abb" is encoded as "dee".

The exact character mappings that are used in the substitution ciphers will not be known to you. However, the dictionary of words that were used will be given. You will be given multiple encoded messages to decode (one per line) and they may use different substitution ciphers. The same substitution cipher is used on all of the words in a particular message .

For each scrambled message in the input, your program should output a line with the input line, followed by the string " = " (without the quotes), followed by the decoded message.

NOTE: All inputs are from stdin and output to stdout. The input will be exactly like how it's given in the problem and your output should exactly match the given example output

Example:
input file :
//dict
hello
there
yello
thorns

//secret
12334 51272
12334 514678


output:
12334 51272 = hello there
12334 514678 = hello thorns

after some thought, I came up with the following algorithm to solve.

Question: what are the other possible ways to solve this. can we optimize the current solution i have?

thanks

class Program
{
    static void Main(string[] args)
    {
        var dict = new List<string> { "hello", "there", "yello", "thorns" };
        var listEncryptedSentences = new List<string> { "12334 51272", "12334 514678" };
        var listListWords = new List<List<string>>();

        foreach (var encryptedSentence in listEncryptedSentences)
        {
            listListWords.Add(encryptedSentence.Split(' ').ToList());
        }
        foreach (var listWords in listListWords)
        {
            SolveAndPrint(dict, listWords);
        }

        Console.ReadKey();
    }

    private static void SolveAndPrint(List<string> dict, List<string> encodedWords)
    {
        var previousSolutions = new List<string>();
        var currentSolutions = new List<string>();
        var totalSolutions = new List<string>();

        string totalWordTillNow = "";

        foreach (var encodedWord in encodedWords)
        {
            currentSolutions = GetMatchingStrings(dict, encodedWord);
            totalWordTillNow += encodedWord;
            totalSolutions = GetMatchingStrings(CrossJoin(previousSolutions, currentSolutions), totalWordTillNow);
            previousSolutions = totalSolutions;
        }

        string encodedString = "";
        var decodedStrings = new List<string>();

        foreach (var solution in totalSolutions)
            decodedStrings.Add("");

        foreach (var encodedWord in encodedWords)
        {
            encodedString += encodedWord + " ";
            for (int i = 0; i < totalSolutions.Count; i++)
            {
                decodedStrings[i] += " " + totalSolutions[i].Substring(0, encodedWord.Length);
                totalSolutions[i] = totalSolutions[i].Substring(encodedWord.Length, totalSolutions[i].Length - encodedWord.Length);
            }
        }
        foreach (var decodedString in decodedStrings)
        {
            Console.WriteLine(encodedString + "=" + decodedString);
        }
    }

    private static List<string> GetMatchingStrings(List<string> possibleWords, string word)
    {
        var result = new List<string>();
        var wordPattern = GetWordLettersPattern(word);

        foreach (var possibleWord in possibleWords)
        {
            if (CompareCounts(wordPattern, GetWordLettersPattern(possibleWord)))
                result.Add(possibleWord);
        }

        return result;
    }

    private static List<List<int>> GetWordLettersPattern(string word)
    {
        var distinctletters = word.ToCharArray().Distinct();
        var letterPattern = new List<List<int>>();

        foreach (var letter in distinctletters)
        {
            letterPattern.Add(GetPositions(word, letter.ToString()));
        }

        return letterPattern;
    }

    public static List<int> GetPositions(string source, string searchString)
    {
        List<int> ret = new List<int>();
        int len = searchString.Length;
        int start = -len;
        while (true)
        {
            start = source.IndexOf(searchString, start + len);
            if (start == -1)
            {
                break;
            }
            else
            {
                ret.Add(start);
            }
        }
        return ret;
    }

    public static bool CompareCounts(List<List<int>> left, List<List<int>> right)
    {
        bool returnVal = true;
        returnVal &= left.Count == right.Count;

        if (returnVal)
        {
            for (int i = 0; i < left.Count; i++)
            {
                returnVal &= left[i].Count == right[i].Count;
                if (!returnVal) break;
            }
        }

        return returnVal;
    }

    public static List<string> CrossJoin(List<string> left, List<string> right)
    {
        var returnVal = new List<string>();

        if (left.Count == 0)
            returnVal.AddRange(right);
        else if (right.Count == 0)
            returnVal.AddRange(left);
        else foreach (var leftItem in left)
            {
                foreach (var rightItem in right)
                {
                    returnVal.Add(leftItem + rightItem);
                }
            }

        return returnVal;
    }

}

Answer 1

A tad tighter, but the same solution overall:

static class Program
{
    static void Main()
    {
        var dict = new List<string> { "hello", "there", "yello", "thorns" };
        var listEncryptedSentences = new List<string> { "12334 51272", "12334 514678" };
        var listListWords = listEncryptedSentences.Select(encryptedSentence => encryptedSentence.Split(' '));

        foreach (var listWords in listListWords)
        {
            SolveAndPrint(dict, listWords);
        }

        Console.ReadKey();
    }

    private static void SolveAndPrint(IEnumerable<string> dict, IEnumerable<string> encodedWords)
    {
        IEnumerable<string> previousSolutions = new List<string>();
        IList<string> totalSolutions = null;
        var totalWordTillNow = string.Empty;

        foreach (var encodedWord in encodedWords)
        {
            var currentSolutions = GetMatchingStrings(dict, encodedWord);

            totalWordTillNow += encodedWord;
            totalSolutions = GetMatchingStrings(CrossJoin(previousSolutions, currentSolutions), totalWordTillNow);
            previousSolutions = totalSolutions;
        }

        if (totalSolutions == null)
        {
            totalSolutions = new List<string>();
        }

        var encodedString = string.Empty;
        var decodedStrings = totalSolutions.Select(solution => string.Empty).ToList();

        foreach (var encodedWord in encodedWords)
        {
            encodedString += encodedWord + " ";
            for (var i = 0; i < totalSolutions.Count; i++)
            {
                decodedStrings[i] += " " + totalSolutions[i].Substring(0, encodedWord.Length);
                totalSolutions[i] = totalSolutions[i].Substring(encodedWord.Length, totalSolutions[i].Length - encodedWord.Length);
            }
        }

        foreach (var decodedString in decodedStrings)
        {
            Console.WriteLine(encodedString + "=" + decodedString);
        }
    }

    private static IList<string> GetMatchingStrings(IEnumerable<string> possibleWords, string word)
    {
        var wordPattern = GetWordLettersPattern(word);

        return possibleWords
            .Where(possibleWord => CompareCounts(wordPattern, GetWordLettersPattern(possibleWord)))
            .ToList();
    }

    private static IList<IEnumerable<int>> GetWordLettersPattern(string word)
    {
        return word
            .ToCharArray()
            .Distinct()
            .Select(letter => GetPositions(word, letter.ToString(CultureInfo.InvariantCulture)))
            .ToList();
    }

    public static IEnumerable<int> GetPositions(string source, string searchString)
    {
        var ret = new List<int>();
        var len = searchString.Length;
        var start = -len;

        while (true)
        {
            start = source.IndexOf(searchString, start + len, StringComparison.InvariantCulture);
            if (start == -1)
            {
                return ret;
            }

            ret.Add(start);
        }
    }

    public static bool CompareCounts(IList<IEnumerable<int>> left, IList<IEnumerable<int>> right)
    {
        var returnVal = true;

        returnVal &= left.Count() == right.Count();
        if (returnVal)
        {
            for (var i = 0; i < left.Count(); i++)
            {
                returnVal &= left[i].Count() == right[i].Count();
                if (!returnVal)
                {
                    return false;
                }
            }
        }

        return returnVal;
    }

    public static List<string> CrossJoin(IEnumerable<string> left, IEnumerable<string> right)
    {
        var returnVal = new List<string>();

        if (!left.Any())
        {
            returnVal.AddRange(right);
        }
        else if (!right.Any())
        {
            returnVal.AddRange(left);
        }
        else
        {
            foreach (var leftItem in left)
            {
                var item = leftItem;

                returnVal.AddRange(right.Select(rightItem => item + rightItem));
            }
        }

        return returnVal;
    }
}