Trying to solve telephone word more elegantly with recursion

Question

I have looked through Stack Overflow but have not been able to get anything to work. I apologize if I missed a blatantly obvious post.

I had a school problem that involved taking a phone number, getting all the possible word combinations, and then writing it to a text file. I did that and got full credit for my assignment. I was able to do this with seven nested loops but that is not very elegant and is very rigid. I was blown away and totally disappointed to find the textbook solution was seven nested loops. My instructor did not have any answers either.

I have tried many different approaches but I have not been able to get it dialed in. I identified a recursion and the kill point but never was able to get it to work. I can produce the letter sequences but nowhere close to how many there should be. I commented out my attempts so you can see my failed thought processes :) Please take a look and let me know if you have any ideas.

public partial class TelephoneWorderizer : Form
{
    protected Dictionary<int, IEnumerable<string>> KeyMappings = new Dictionary<int, IEnumerable<string>>();
    protected string[][] ActiveLettersGroups = null;
    protected List<string> Words = new List<string>();
    protected List<string> RecursiveWords = new List<string>();
    protected int Iteration = 0;

    public TelephoneWorderizer()
    {
        InitializeComponent();

        this.KeyMappings = this.GetKeyMappings();
    }

    private void btnGetWords_Click(object sender, EventArgs e)
    {
        string textBoxContent = textBoxNumber.Text;

        int[] digits = this.GetPhoneNumbers(textBoxContent);

        List<string> words = this.GetWords(digits);

        using (StreamWriter writer = new StreamWriter(@"E:\words.txt"))
        {
            foreach (var word in words)
            {
                writer.WriteLine(word);
            }
        }

        textBoxNumber.Clear();
    }

    private List<string> GetWords(int[] digits)
    {
        List<string[]> letterGroupings = new List<string[]>();

        //digits array of numbers
        for (int i = 0, j = digits.Length; i < j; i++)
        {
            int digit = digits[i];

            //if the number has a letter group mapped to it
            if (this.KeyMappings.ContainsKey(digit))
            {
                // letters mapped to a given number
                letterGroupings.Add(this.KeyMappings[digit].ToArray());
            }
        }

        this.WordMakerLoop(letterGroupings);
        //this.WordMaker(letterGroupings);

        return this.Words;
        //return this.RecursiveWords;
    }

    //private void RecursionTest(string word, List<string[]> groups, int letterCtr, int groupCtr)
    //{
    //    string[] Group = groups[groupCtr];

    //    word += Group[letterCtr];

    //    letterCtr += 1;

    //    if (letterCtr < Group.Length - 1)
    //    {
    //        letterCtr = 0;
    //        groupCtr += 1;

    //        // Hit bottom
    //        if (groupCtr == groups.Count - 1)
    //        {
    //            groupCtr -= 1;
    //        }

    //        RecursionTest(word, groups, letterCtr, groupCtr);
    //    }
    //}

    private void WordMaker(List<string[]> letterCollections)
    {
        string newword = "";
        int numberLength = letterCollections.Count;

        this.ActiveLettersGroups = letterCollections.ToArray();

        string[] letterGroup = this.ActiveLettersGroups[0];

        this.RecursiveGetWords(newword, 0, 0);
    }

    /// <summary>
    /// 
    /// </summary>
    /// <param name="word"></param>
    /// <param name="groupIndex"></param>
    /// <param name="letterIndex"></param>
    private void RecursiveGetWords(string word, int groupIndex, int letterIndex)
    {

        /*
         * 
         * 
         * 
         */


        var numActiveLetterGroups = this.ActiveLettersGroups.Length;

        if (this.ActiveLettersGroups.Length > 0 && this.Iteration < numActiveLetterGroups)
        {
            if (groupIndex < numActiveLetterGroups)
            {
                var letters = this.ActiveLettersGroups[groupIndex]; // Picks the a letter group ex: A, B, C 

                if (letterIndex < letters.Length)
                {
                    //var letter1 = letters.Select(x => 
                    string letter = letters[letterIndex]; // Picks a letter from the group ex: A

                    word += letter;

                    this.RecursiveGetWords(word, groupIndex + 1, this.Iteration);
                }
                else
                {
                    //this.RecursiveWords.Add(word);
                    //word = "";

                    //this.RecursiveGetWords(word, 0, 1);
                }
            }
            else
            {
                this.RecursiveWords.Add(word);
                word = "";
                this.Iteration++;

                this.RecursiveGetWords(word, 0, this.Iteration);
            }
        }
    }

    #region
    private void WordMakerLoop(List<string[]> letterGroups)
    {
        string word = "";

        // array of string[]
        var newGroup = letterGroups.ToArray();

        //grabs a letter group
        for (int i = 0; i < newGroup.Length; i++)
        {
            var letterGroup1 = newGroup[i];

            //grabs a letter from group 1
            for (int j = 0; j < letterGroup1.Length; j++)
            {
                string letter1 = letterGroup1[j];

                if (i + 1 < newGroup.Length)
                {
                    var letterGroup2 = newGroup[i + 1];

                    //grabs a letter from group 2
                    for (int k = 0; k < letterGroup2.Length; k++)
                    {
                        string letter2 = letterGroup2[k];

                        if (i + 2 < newGroup.Length)
                        {
                            var letterGroup3 = newGroup[i + 2];

                            //grabs a letter from group 3
                            for (int l = 0; l < letterGroup3.Length; l++)
                            {
                                string letter3 = letterGroup3[l];

                                if (i + 3 < newGroup.Length)
                                {
                                    var letterGroup4 = newGroup[i + 3];

                                    //grabs a letter from group 4
                                    for (int m = 0; m < letterGroup4.Length; m++)
                                    {
                                        string letter4 = letterGroup4[m];

                                        if (i + 4 < newGroup.Length)
                                        {
                                            var letterGroup5 = newGroup[i + 4];

                                            //grabs a letter from group 5
                                            for (int n = 0; n < letterGroup5.Length; n++)
                                            {
                                                string letter5 = letterGroup5[n];

                                                if (i + 5 < newGroup.Length)
                                                {
                                                    var letterGroup6 = newGroup[i + 5];

                                                    //grabs a letter from group 6
                                                    for (int o = 0; o < letterGroup6.Length; o++)
                                                    {
                                                        string letter6 = letterGroup6[o];

                                                        if (i + 6 < newGroup.Length)
                                                        {
                                                            var letterGroup7 = newGroup[i + 6];

                                                            //grabs a letter from group 6
                                                            for (int p = 0; p < letterGroup7.Length; p++)
                                                            {
                                                                string letter7 = letterGroup7[p];

                                                                word = letter1 + letter2 + letter3 + letter4 + letter5 + letter6 + letter7;
                                                                this.Words.Add(word);
                                                                word = "";
                                                            }
                                                        }
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    // Sanitizes input text and converts the string into and arra of int
    private int[] GetPhoneNumbers(string content)
    {
        int[] phoneNumbers = null;

        string cleanString = this.SanitizeString(content);

        int numbers;

        if (Int32.TryParse(cleanString, out numbers))
        {
            //phoneNumbers = this.GetIntArray(numbers).OfType<int>().ToList();
            phoneNumbers = this.GetIntArray(numbers);
        }

        return phoneNumbers;
    }

    // Removes potential unwanted characters from the phone number
    private string SanitizeString(string content)
    {
        content = content.Replace("-", "");
        content = content.Replace("(", "");
        content = content.Replace(")", "");

        return content;
    }

    //breaks a number into an array of its individual digits
    private int[] GetIntArray(int num)
    {
        List<int> listOfInts = new List<int>();

        while (num > 0)
        {
            listOfInts.Add(num % 10);
            num = num / 10;
        }

        listOfInts.Reverse();

        return listOfInts.ToArray();
    }

    //gets the mappings for the numerical values
    private Dictionary<int, IEnumerable<string>> GetKeyMappings()
    {
        List<string> alphabet = new List<string>() { "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z" };
        Dictionary<int, IEnumerable<string>> mappings = new Dictionary<int, IEnumerable<string>>();

        for (int i = 0; i < 10; i++)
        {
            string[] letters = null;
            switch (i)
            {
                case 0:
                case 1:
                    break;
                case 2:
                case 3:
                case 4:
                case 5:
                case 6:
                case 8:
                    letters = alphabet.Take(3).ToArray();
                    mappings.Add(i, letters);
                    alphabet.RemoveRange(0, 3);
                    break;
                case 7:
                case 9:
                    letters = alphabet.Take(4).ToArray();
                    mappings.Add(i, letters);
                    alphabet.RemoveRange(0, 4);
                    break;
                default:
                    break;
            }
        }

        return mappings;
    }
    #endregion
}

Let me emphasize that the school assignment is over for those people in doubt. I want to do this better and more efficient. I can post my project on gitHub if that would help.

Answer 1

I'm too lazy to write any code at the moment, but you should definitely be able to do this via recursion instead of seven nested loops, and in fact you should be able to design a method that should work on any arbitrary-length telephone number.

The basic idea is that you would design a recursive method something like this:

void recurse(String phone, int index, StringBuilder sb)
{
   // Get the number at position phone[index]
   // Loop through the possible letters for that particular number (eg. A, B, C):
      // Add the letter to the StringBuilder
      // Call recurse(phone, index + 1, sb)
      // Subtract last letter from the StringBuilder
}

Each time you recurse you are working on the next number / letter position.

Of course if you run into the terminating condition (sb length == phone length), then instead of recursing you just write the current value of the StringBuilder to file and return.

Hope this helps.

Edit: Getting around to actually writing some code. It's really this simple, no LINQ required:

   class Program
   {
      static Dictionary<Char, String> DigitMap = new Dictionary<Char, String>()
      {
         {'0', "0"},
         {'1', "1"},
         {'2', "ABC"},
         {'3', "DEF"},
         {'4', "GHI"},
         {'5', "JKL"},
         {'6', "MNO"},
         {'7', "PQRS"},
         {'8', "TUV"},
         {'9', "WXYZ"}
      };

      static void Main(string[] args)
      {
         String phone = Regex.Replace("867-5309", "[^0-9]", "");
         recurse(phone, 0, new StringBuilder());
      }

      static void recurse(String phone, int index, StringBuilder sb)
      {
         // Terminating condition
         if (index == phone.Length)
         {
            Console.WriteLine(sb.ToString());
            return;
         }

         // Get digit and letters string
         Char digit = phone[index];
         String letters = DigitMap[digit];

         // Loop through all letter combinations for digit
         foreach (Char c in letters)
         {
            sb.Append(c);
            recurse(phone, index + 1, sb);
            sb.Length -= 1;
         }
      }
   }
}

In this code (where I made a simple console app) I'm just writing the words to the console but you could be adding the strings to an array or writing them to disk instead.

Answer 2

I have made the assumption that you probably want to translate each digit to itself as well as all the normal letter mappings, plus mapping 0 to +. So I made this dictionary to handle the mappings:

var map = new Dictionary<char, string>()
{
    { '0', "+0"},
    { '1', "1" },
    { '2', "2ABC"},
    { '3', "3DEF"},
    { '4', "4GHI"},
    { '5', "5JKL"},
    { '6', "6MNO"},
    { '7', "7PQRS"},
    { '8', "8TUV"},
    { '9', "9WXYZ"},
};

My permutate function then looks like this:

Func<IEnumerable<char>, IEnumerable<IEnumerable<char>>> permutate = null;
permutate = cs =>
{
    var result = Enumerable.Empty<IEnumerable<char>>();
    if (cs.Any())
    {
        result = map[cs.First()].Select(c => new [] { c });
        if (cs.Skip(1).Any())
        {
            result =
                from xs in result
                from ys in permutate(cs.Skip(1))
                select xs.Concat(ys);
        }
    }
    return result;
};

That's it.

You can use it like this:

var digits = "(08) 8234-5678"
    .Where(x => char.IsDigit(x));

var results =
    permutate(digits)
        .Select(x => new string(x.ToArray()));

The result is a list of strings where each string is a permutation of the input number.

If you don't want to map digits to digits, just take them out of the original dictionary definition, but you must keep a single character for the digit 1 for it to work.

Let me know if this works for you.