0
\$\begingroup\$

I wrote a terrible function to map E.161 keys to letter strings.

I think the logic could be simplified using a recursive function; however I have never been good at recursive methods. Any suggestions are welcomed.

My Code:

#LINQPad optimize+
void Main()
{
    var summary = BenchmarkRunner.Run<MyClass>();
    summary.Dump();
}

public class MyClass
{

    [Params("2", "24", "247", "2474", "24747")]
    public string DTMF_Input { get; set; }

    List<char> DTMFtoString(char c)
    {
        return c switch
        {
            '2' => new List<char>() { 'A', 'B', 'C' },
            '3' => new List<char>() { 'D', 'E', 'F' },
            '4' => new List<char>() { 'G', 'H', 'I' },
            '5' => new List<char>() { 'J', 'K', 'L' },
            '6' => new List<char>() { 'M', 'N', 'O' },
            '7' => new List<char>() { 'P', 'Q', 'R', 'S' },
            '8' => new List<char>() { 'T', 'U', 'V' },
            '9' => new List<char>() { 'W', 'X', 'Y', 'Z' },
            _ => throw new ArgumentOutOfRangeException($"The specified character '{c}' is not supported."),
        };
    }

    [Benchmark]
    public void GetCombosFromDTMF()
    {
        var Tones = new System.Collections.Generic.Stack<char>(DTMF_Input.ToCharArray().Reverse());

        var MyPrefixes = new List<string>();
        while (Tones.Any())
        {
            var Combos = new List<string>();
            var entries = DTMFtoString(Tones.Pop());
            if (MyPrefixes.Any())
            {
                foreach (var existing in MyPrefixes)
                {
                    foreach (var newTone in entries)
                    {
                        Combos.Add(existing + newTone);
                    }
                }
            }
            else
            {
                Combos = entries.Select(c => Char.ToString(c)).ToList();
            }

            MyPrefixes = Combos;
        }

        MyPrefixes.OrderBy(r => r).ToList();
    }
}

Benchmarks

|            Method | DTMF_Input |         Mean |       Error |      StdDev |
|------------------ |----------- |-------------:|------------:|------------:|
| GetCombosFromDTMF |          2 |     671.0 ns |    11.26 ns |    10.54 ns |
| GetCombosFromDTMF |         24 |   1,537.1 ns |    25.25 ns |    21.09 ns |
| GetCombosFromDTMF |        247 |   8,690.2 ns |   160.62 ns |   134.12 ns |
| GetCombosFromDTMF |       2474 |  30,870.3 ns |   557.15 ns |   762.63 ns |
| GetCombosFromDTMF |      24747 | 168,660.9 ns | 3,008.75 ns | 3,344.22 ns |
\$\endgroup\$
4
  • \$\begingroup\$ Could you please share with us what DTMF stands for? \$\endgroup\$ Oct 17, 2022 at 14:02
  • 1
    \$\begingroup\$ @PeterCsala Dual tone multi-frequency (DTMF) is the sounds or tones generated by a telephone when the numbers are pressed. Essentially if you look at your phone keypad, each digit represents 0,3, or 4 characters. For my usage, I am only interested in the keys representing letters. \$\endgroup\$
    – KellCOMnet
    Oct 17, 2022 at 14:04
  • 2
    \$\begingroup\$ The code really does not do anything regarding tones and frequencies. It's really a decoder of a very specific keypad layout. Other layouts have a max of 3 letters per digit, with Q and Z being omitted. \$\endgroup\$
    – Rick Davin
    Oct 17, 2022 at 14:36
  • 2
    \$\begingroup\$ It seems that this is the E1.61 telephone pad layout. \$\endgroup\$ Oct 17, 2022 at 15:12

2 Answers 2

2
\$\begingroup\$

If you are unhappy with the DTMFtoString method then here is my suggestion:

Rather than recreating a List<char> for each and every method call, use a Dictionary<char, List<char> structure and perform a lookup.

Dictionary<char, List<char>> DTMFLookup = new()
{
    { '2', new List<char>() { 'A', 'B', 'C' }},
    { '3', new List<char>() { 'D', 'E', 'F' }},
    { '4', new List<char>() { 'G', 'H', 'I' }},
    { '5', new List<char>() { 'J', 'K', 'L' }},
    { '6', new List<char>() { 'M', 'N', 'O' }},
    { '7', new List<char>() { 'P', 'Q', 'R', 'S' }},
    { '8', new List<char>() { 'T', 'U', 'V' }},
    { '9', new List<char>() { 'W', 'X', 'Y', 'Z' }}
};

With this approach you allocate memory only once.

If you want to make this lookup table immutable then you can do that like this

static readonly ImmutableDictionary<char, ImmutableList<char>> DTMFLookup = new Dictionary<char, List<char>>()
{
    { '2', new List<char>() { 'A', 'B', 'C' }},
    { '3', new List<char>() { 'D', 'E', 'F' }},
    { '4', new List<char>() { 'G', 'H', 'I' }},
    { '5', new List<char>() { 'J', 'K', 'L' }},
    { '6', new List<char>() { 'M', 'N', 'O' }},
    { '7', new List<char>() { 'P', 'Q', 'R', 'S' }},
    { '8', new List<char>() { 'T', 'U', 'V' }},
    { '9', new List<char>() { 'W', 'X', 'Y', 'Z' }}
}.ToImmutableDictionary(kp => kp.Key, kp => kp.Value.ToImmutableList());

And finally the lookup code:

var @char = Tones.Pop();
if (!DTMFLookup.TryGetValue(@char, out var entries))
    throw new ArgumentOutOfRangeException($"The specified character '{@char}' is not supported.");
\$\endgroup\$
1
\$\begingroup\$

I wonder if you really wanted a code review, or if you really wanted help on creating a recursive version in hopes of better performance. One would think recursion should be faster, particularly since you (1) reverse the input digits to create the combinations of words (what you call MyPrefixes), and then (2) re-order MyPrefixes, which at its heart is simply reversing the combinations.

All of this suggests that maybe there is a better way.

Since benchmarks very per machine, here are bench marks of your original code on my laptop:

Method DTMF_Input Mean Error StdDev
GetCombosFromDTMF 2 514.8 ns 8.01 ns 7.49 ns
GetCombosFromDTMF 24 1,232.3 ns 14.71 ns 11.49 ns
GetCombosFromDTMF 247 7,148.6 ns 127.21 ns 130.63 ns
GetCombosFromDTMF 2474 24,246.7 ns 381.71 ns 318.74 ns
GetCombosFromDTMF 24747 134,660.1 ns 981.09 ns 765.97 ns

I have other versions that did not improve the times that much, if at all. My 2nd attempt was using @PeterCsala 's dictionary suggestion returning List<char>, and the 3rd returned char[] instead.

My 4th version used recursion where I process the input digits in the order they are given. This has benefit of also producing the output in the desired order. I am using .NET 6 on a Windows 10 laptop. Confession: bench marking is not my strong suit. I had to fumble around with NuGet to install BenchmarkDotNet package. I could not find an equivalent for summary.Dump().

using BenchmarkDotNet.Parameters;
using BenchmarkDotNet.Running;
using BenchmarkDotNet.Attributes;

var summary = BenchmarkRunner.Run<MyClass>();

public class MyClass
{

    [Params("2", "24", "247", "2474", "24747")]
    public string DTMF_Input { get; set; }

    Dictionary<char, char[]> DTMFLookup = new()
    {
        { '2', new char[] { 'A', 'B', 'C' } },
        { '3', new char[] { 'D', 'E', 'F' } },
        { '4', new char[] { 'G', 'H', 'I' } },
        { '5', new char[] { 'J', 'K', 'L' } },
        { '6', new char[] { 'M', 'N', 'O' } },
        { '7', new char[] { 'P', 'Q', 'R', 'S' } },
        { '8', new char[] { 'T', 'U', 'V' } },
        { '9', new char[] { 'W', 'X', 'Y',  'Z' } }
    };


    [Benchmark]
    public void GetCombosFromDTMF()
    {
        var digits = DTMF_Input.ToCharArray();
        var word = new char[digits.Length];  // Same array used repeatedly for recursion
        var combinations = GetCombinationsRecursively(digits, word, index: 0);
        // I don't know if BenchMarkDotNet requires IEnumerables to be realized as a List.
        var words = combinations.ToList();
    }

    private IEnumerable<string> GetCombinationsRecursively(char[] digits, char[] word, int index)
    {
        if (!DTMFLookup.TryGetValue(digits[index], out var letters))
            throw new ArgumentOutOfRangeException($"The specified character '{digits[index]}' is not supported.");

        bool keepRecursing = index < (digits.Length - 1);

        foreach (var letter in letters)
        {
            word[index] = letter;
            if (keepRecursing)
            {
                var collection = GetCombinationsRecursively(digits, word, index + 1);
                foreach (var item in collection)
                {
                    yield return item;
                }
            }
            else
            {
                yield return new string(word);
            }
        }
    }

}

The results are significantly better:

Method DTMF_Input Mean Error StdDev
GetCombosFromDTMF 2 126.7 ns 2.51 ns 2.58 ns
GetCombosFromDTMF 24 496.1 ns 9.42 ns 9.25 ns
GetCombosFromDTMF 247 2,091.7 ns 18.58 ns 15.52 ns
GetCombosFromDTMF 2474 6,985.7 ns 75.83 ns 59.20 ns
GetCombosFromDTMF 24747 29,454.0 ns 572.26 ns 744.10 ns

For a small number of digits, the times are cut in half. As you add more digits, the times are cut by 1/3 to 1/4. I'd like to think that what I have could be improved somewhat, both in performance and code maintenance, but the main reason for my answer was to show that recursion should be pursued.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.