1
\$\begingroup\$

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);
    });
}
\$\endgroup\$
  • \$\begingroup\$ Any reason to use ES5 but not ES6? \$\endgroup\$ – Daerdemandt Jun 15 '17 at 18:43
  • \$\begingroup\$ @Daerdemandt No particular reason. \$\endgroup\$ – zero298 Jul 13 '17 at 14:44
1
\$\begingroup\$

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)
}
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ While your code simply ignores input "1", OP will return an empty array. Not sure whether this is intentional by OP though, as it seems odd. \$\endgroup\$ – le_m May 16 '17 at 18:18
  • \$\begingroup\$ @le_m I should have included a test case for "1". However, what would be the most appropriate thing to return? \$\endgroup\$ – zero298 Jul 13 '17 at 14:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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