Alternative phone number conversions

The problem was converting lowercase letters (and blanks) to numbers, following the rules used by the phone keypad. In a previous post I gave a possible C++ solution, and I got as feedback a couple of alternative solutions. It is interesting to compare them, to see different approaches taken by different programmers.

Arthur's solution is on github. In a few words, he loops on the input string, calling for each character a support function named encodeChar() that returns a pair where first is the resulting number, and second the number of needed repetition.

The encodeChar() function delegates to the compiler the task of generating a string that maps the valid character to the relative expected position, filled with underscores for invalid positions. Then find() is used to get requested character and its multiplier.

Interesting features of this solution:

- C++11 range-based for loop. Code is more compact and readable.
- Use of STL data structure and algorithms.
- The lookup table is ingeniously mapped to a single string.

Some more chatting could be done on:

- C++11 use of the auto keyword. Using it when it is not a necessity (or a nice shortcut that improve readability) just makes code less clear. For instance, the C++11 std::stol() always return a long int, there is no advantage in assigning its returned value to an auto variable.
- Mapping the lookup table to a single string full implies that we should use find() to get converted character and its multiplier. We should be aware that find() has O(n) time complexity, against O(1) of a lookup table.

I couldn't help to rewrite the function main loop to get rid of the temp variable used to keep track of the last inserted key. Admittedly, it is just a minimal improvement, still, I nerdly fill better to see the code changed in this way:

for(char c : input)
{
  Token token = encodeChar(c);
  if(!output.empty() && token.first == output.back())
    output += ' ';
  output += std::string(token.second, token.first);
}

Anonymous put his solution on ideone, compiled on C++11 (gcc-4.7.2). I guess he is a fan of generic programming, and his job is a cool example of this technique. The main issue here is that there is no reason, beside the fun of writing it, to come out with such a complex piece of code to solve this problem. So it sorts make sense that he named his lambda function that determines the associated key for the current letter "magic", because it takes a while to understand it, and at first sight it looks really as it works for a kind of magic.

It is difficult to summarize the good stuff we could see in that piece of code, nice use of templates, decltype, auto declarations, and a static assertion to check at compile time the generic function actual correctness. I think it could be used as an introductory example to generic programming.

There is only a (minor) issue in the code, it does not manage consecutive blanks. In the t9_transform() main loop, there is a "else" that covers the blank case (assuming nothing else than lower case letters and blanks are in the input string). There we should add a check on the previously checked character, as we do in the "if".

More interestingly, I spent some time understanding how "magic" actually works. To show how it works, I think it could be useful to see the original one-liner lambda converted to an equivalent "normal" longish function. For sake of simplicity, I sacrificed the genericity of magic(), writing a char2rep() that works only for plain chars:

auto magic = [](decltype(*f) i) { return '2' + std::min(7, (i - (i >> 4)) / 3); };

char char2rep(char input)
{
  if(input == 'z')
    return '9';

  int shift = input > 'r' ? 1 : 0;
  int code = input - 'a';
  return '2' + (code - shift) / 3;
}

To understand how magic() works, we have to think about what it wants to achieve. Any number in the keypad, starting from 2, is the result of the conversion of three consecutive letters. If the number of letters was a precise multiple of three, the function would have been trivial. But there are two keys, 7 and 9, that should map four, and not three letters. So we have to plan for a couple of adjustment.
If the input letter is bigger that 'r', we need to shift one position, and the last character, AKA 'z', should follow a special rule. For magic() the trick is done maximizing the shift to 7, alternatively, we could just say that 'z' is converted to '9'.

So, after all it was no magic, just an obscure piece of code ;)