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);
});
}