Generating all keypad possibilities

Question

I ran into this question on Stack Overflow. It looked like a really cool thing to try myself, being that I haven't done any recursion for ages (read at least 2 years).

var keypadPossibilities = (function()
{
    var keypad_mapping = [
        [],
        ['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']
    ];

    function getPosibilities(keypad_mapping_indexes)
    {
        //if only 1 keypad mapping index: simply return the characters
        if ( keypad_mapping_indexes.length === 1)
        {
            return keypad_mapping[keypad_mapping_indexes.shift()];
        }

        //still multiple keypad mapping index left. lets do some magic
        var currentIndex = keypad_mapping_indexes.shift(), posibilities = [],
            characters = keypad_mapping[currentIndex];

        var charactersToGlueAtEnd = getPosibilities(keypad_mapping_indexes);

        for ( var i in characters )
        {
            for ( var j in charactersToGlueAtEnd )
            {
                posibilities.push(characters[i]+charactersToGlueAtEnd[j]);
            }
        }

        return posibilities;
    }

    return function(pressed_keys)
    {
        return getPosibilities(pressed_keys);
    }

})();

Usage would be:

keypadPossibilities([1,2,3]);

It works, so thats nice (no debugging required, that was a first). So, shoot, code remarks, performance remakrs, ... You can go full package. Everything to learn new cool stuff about JS.

Answer 1

Overall, I'd say recursion is a good way to go. Good use of an IIFE to keep things tidy as well. I do however have some concerns.

Input checking

Firstly, if I pass an empty array, I get a stack overflow, since you only check for a length of 1 - not for a length < 1. I am technically passing the correct type (an array) to the function, so it should handle it (if I pass something that's not an array, then it's my own fault).

Also, if I pass [9] (or [31415]) I just get undefined back, though an empty array would probably be more fitting.

shift() is destructive

Be careful with shift()! You're modifying the array that's been passed to the function, even though it doesn't really "belong to you". The caller might still have a use for it.

For instance,

var numbers = [1, 2, 3];
var words = keypadPossibilities(numbers);
console.log("You typed " + numbers.length + " digits, producing " + words.length + " possible words");

will print

You typed 0 digits, producing 27 possible words

Wait, zero digits? Thing is, numbers is suddenly empty; everything's been shifted out by passing it to keypadPossibilities.

This of course also happens when the function recurses, which could spell trouble. Luckily, in your case, you don't use the input array for anything after having recursed, but if you did you'd find that the recursion had truncated it down to empty.

Don't use for...in for arrays

for...in will iterate properties of an object, and with no guaranteed order. It usually works for arrays, but it's not a sure thing. It's semantically different from iterating the actual, indexed elements in the array. So use either a regular ol' for loop, or - if you're targeting modern runtimes, maybe a forEach().

However, you could also use map() and reduce() in this case (see below).

Other stuff

This function-wrapper around a call to getPosibilities is unnecessary:

return function(pressed_keys)
{
    return getPosibilities(pressed_keys);
}

(Oh, and there's a typo: getPosibilities is missing an extra "s". I'll just use the corrected name from hereon out)

You could simply replace the above with just:

return getPossibilities;

and done.

However, with the point about shift() in mind, the easiest thing to do would probably be something like

return function(pressed_keys)
{
    return getPossibilities(pressed_keys.slice());
}

Now, pressed_keys gets sliced (duplicated) before it's passed to getPossibilities.

You could also do the slicing in getPossibilities (and do the direct return, shown above), but - as the code's already proved - you don't really need it there. But in the interest of being thorough, it'd look something like:

var currentIndex = keypad_mapping_indexes[0]
// ... snip ...
var charactersToGlueAtEnd = getPossibilities(digits.slice(1)); // duplicate array from index 1 and up

A few notes on style

In terms of style, I'm not a fan of brace-on-new-line in JavaScript. Yes, it works, but it can bite you, since JS will sometimes do automatic semicolon insertion at newlines and break your code. So the convention is to use brace-on-same-line style.

Also by convention, all names in JS should be camelCase. You're using a bit of both; aim for consistency.

---

Here's a possible version incorporating the points above

var keypadPossibilities = (function() {
  var keypadMapping = [
    null,
    ['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']
  ];

  function getPossibilities(digits) {
    var characters = keypadMapping[digits.shift()],
        charactersToGlueAtEnd;

    if(!digits.length) {
      return characters || [];
    }

    charactersToGlueAtEnd = getPossibilities(digits);

    return characters.reduce(function (memo, character) {
      var words = charactersToGlueAtEnd.map(function (string) { return character + string; });
      return memo.concat(words);
    }, []);
  }

  return function (digits) {
    return getPossibilities(digits.slice()); // make sure we work on a copy of the input array
  };
})();