T9 Translator in node.js

Question

I was reading some programming brain teasers and saw a T9 translator teaser on Crazy for Code and wanted to go about implementing it in node.js.

Print all possible words from phone number digits.

This question is asked by companies like microsoft, google, facebook, Amazon. Lets see example input/output to understand this problem.

For example if input number is 234, possible words which can be formed are (Alphabetical order): adg adh adi aeg aeh aei afg afh afi bdg bdh bdi beg beh bei bfg bfh bfi cdg cdh cdi ceg ceh cei cfg cfh cfi

I'm worried about too many iterations and also readability. I originally did only incrementing in the recursive function, but then needed to do a .reverse() on the resultant array which I figured would be better to just handle in the translation itself by decrementing instead. I'm also wondering if I'm going about my tests in the right manner.

t9.js

/*jslint node:true, es5:true*/

/*
 * Based on problem presented by:
 * http://www.crazyforcode.com/print-words-phone-digits/
 */

"use strict";

/**
 * T9 module
 * @module t9
 */

var t9 = [
    [" "], // 0
    [""], // 1
    ["a", "b", "c"], // 2
    ["d", "e", "f"], // 3
    ["g", "h", "i"], // 4
    ["j", "k", "l"], // 5
    ["m", "n", "o"], // 6
    ["p", "q", "r", "s"], // 7
    ["t", "u", "v"], // 8
    ["w", "x", "y", "z"] // 9
];

function rec(bundles, bundleIdx, letterIdx, str, arr) {
    // Add the new letter
    var concatedStr = str + bundles[bundleIdx][letterIdx];

    // Decrement letter
    if (letterIdx > 0) {
        rec(bundles, bundleIdx, letterIdx - 1, str, arr);
    }

    // Increment bundle
    if (bundleIdx < bundles.length - 1) {
        rec(bundles, bundleIdx + 1, bundles[bundleIdx + 1].length - 1, concatedStr, arr);
    }

    // Not a complete word
    if (concatedStr.length < bundles.length) {
        return;
    }

    // Push word
    arr.push(concatedStr);
}

/**
 * Find all the words that could be made with given number using T9 translation
 * @function translate
 * @param {String} numbers The number to translate with t9
 * @returns {String[]} Possible words that could be made
 * @throws Will throw if a non-number string is provided
 */
function translate(numbers) {
    var possibleWords,
        charArrs;

    if (!/^[0-9]+$/.test(numbers)) {
        throw new Error("Must provide a number string");
    }

    possibleWords = [];
    charArrs = numbers
        .split("")
        .map(function (digit) {
            return t9[parseInt(digit, 10)];
        });

    // Start recursive func
    rec(charArrs, 0, charArrs[0].length - 1, "", possibleWords);

    return possibleWords;
}

module.exports = {
    translate: translate
};

t9.test.js

/*jslint node:true, es5:true*/

"use strict";

var assert = require("assert"),
    t9 = require("../src/t9");

// Throw errors properly
assert.throws(function () {
    t9.translate("hello");
}, Error, "Expected an error");

// Translate 3 letter numbers correctly
var expected234 = ["adg", "adh", "adi", "aeg", "aeh", "aei", "afg", "afh", "afi", "bdg", "bdh", "bdi", "beg", "beh", "bei", "bfg", "bfh", "bfi", "cdg", "cdh", "cdi", "ceg", "ceh", "cei", "cfg", "cfh", "cfi"],
    actual234 = t9.translate("234");
assert.deepEqual(expected234, actual234, "Expected 3 numbers to translate");

// Translates 3 and 4 letter numbers correctly
var expected78 = ["pt", "pu", "pv", "qt", "qu", "qv", "rt", "ru", "rv", "st", "su", "sv"],
    actual78 = t9.translate("78");
assert.deepEqual(expected78, actual78, "Expected 3 and 4 numbers to translate");

// Translates with a space
var expected506 = ["j m", "j n", "j o", "k m", "k n", "k o", "l m", "l n", "l o"],
    actual506 = t9.translate("506");
assert.deepEqual(expected506, actual506, "Expected spaces to work");

// Translate complex message
var expected2067 = ["a mp", "a mq", "a mr", "a ms", "a np", "a nq", "a nr", "a ns", "a op", "a oq", "a or", "a os", "b mp", "b mq", "b mr", "b ms", "b np", "b nq", "b nr", "b ns", "b op", "b oq", "b or", "b os", "c mp", "c mq", "c mr", "c ms", "c np", "c nq", "c nr", "c ns", "c op", "c oq", "c or", "c os", ],
    actual2067 = t9.translate("2067");
assert.deepEqual(expected2067, actual2067, "Complex translate to work");

index.js

/*jslint node:true, es5:true*/

"use strict";

var t9 = require("./src/t9");

function handleInput(toTranslate) {
    console.log("Possible words:");
    t9.translate(toTranslate).forEach(function (possibleWord) {
        console.log(possibleWord);
    });
}

if (process.argv.length > 2) {
    handleInput(process.argv[2]);
} else {
    var rl = require("readline").createInterface({
        input: process.stdin,
        output: process.stdout
    });

    rl.question("What numbers? ", function (answer) {
        rl.close();
        handleInput(answer);
    });
}

Answer 1

This looks good, but I think you've overcomplicated the essential recursion a bit by unnecessarily introducing a 2nd function and by using more parameters than you need.

The following accomplishes the same thing (and note that nearly half of this is simply input validation similar to yours, so that the essence of algorithm is half a dozen lines):

function t9Words(digits, ret = []) {

  if (typeof digits === 'string') {
    digits = digits.split('').map(x => {
      if (!/\d/.test(x)) throw new Error('Input must be digits')
      return parseInt(x)
    })
  }

  if (!digits.length) return ret.sort()                           // recursion bottom case
  if (!ret.length) return t9Words(digits.slice(1), t9[digits[0]]) // top case

  const nextRet = t9[digits[0]].reduce((m, x) =>
    m.concat(ret.map(word => word.concat(x)))
  , [])

  return t9Words(digits.slice(1), nextRet)
}