# Check whether a number can be dialed on a phone keypad without diagonal moves

I'm trying to write/come up with an algorithm for a phone keypad traversal.

Let's say I have a rook on a keypad. The rook can traverse only horizontally and vertically. My code has to input a phone number and check whether the rook is able to dial it (shouldn't go diagonally) and return a boolean based on the result.

Example: A phone number "4632871" is termed as "true" since the rook can traverse without going diagonally whereas "4853267" is termed as "false"

Below is my code implementation:

var data = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9],
];

function rookTraversal(arr, phoneNumber) {

var arrIndex = [],
numArray = [];

var number = phoneNumber.split('');

for (var i = 0; i < arr.length; i++) {
for (var j = 0; j < arr.length; j++) {
arrIndex.push([i, j]);
}
}

arrIndex = arrIndex.map((item, index) => ({
[index + 1]: item,
}));

number.forEach((item) => {
numArray.push(arrIndex[item - 1]);
});

let numArrayKeys = numArray.reduce((acc, x) => [...acc, Object.values(x).map((y) => y)], []);

for (let i = 1; i < numArrayKeys.length; i++) {
var x1 = numArrayKeys[i - 1][0][0];
var y1 = numArrayKeys[i - 1][0][1];
var x2 = numArrayKeys[i][0][0];
var y2 = numArrayKeys[i][0][1];

if (x1 !== x2 && y1 !== y2) {
return false;
}
}

return true;
}

console.log(rookTraversal(data, '4631782'));
console.log(rookTraversal(data, '4853267'));

Is there a way to optimize this piece of code?

There are a lot of different traits you could optimize for. I like to optimize for lines of code, so I'll try that.

You can simplify the testing by building a "graph" (2-dimensional array) of reachable numbers. Each row and column index is a phone digit. If the value at (i,j) is true, then j is reachable from i.

To do this, take all the numbers in each digit's row/column and create an array where those indexes have a value of 1.

The reachability graph looks like this:

The digit 6 can reach 3,4,5,6,9 and you can see that reachable[6][x] is true for x=3,4,5,6 or 9.

Then simply run through the list of numbers and test if reachable[current][next] is true.

I've assumed the rook can dial repeated numbers like 3333. If no, you can test for that in the graph creation or during reachability testing.

function rookTraversal(rows, phoneNumber) {
var cols=rows[0].map((col, i) => rows.map(row => row[i])),
digits=phoneNumber.match(/(\d)/g),
reachable=[];
for (var row = 0; row < rows.length; row++) {
for (var col = 0; col < cols.length; col++) {
reachable[ rows[row][col] ] = rows[row].concat(cols[col]).reduce( (map, value) => { map[value]=1; return map }, [] );
}
}
// console.log({reachable,digits});
for (var i=0; i<digits.length-1; ++i) if (! reachable[ digits[i] ][ digits[i+1] ]) return false;
return true;
}

var data = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9],
];

console.log(rookTraversal(data, '4631782'));
console.log(rookTraversal(data, '4853267'));