3
\$\begingroup\$

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.

enter image description here

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?

\$\endgroup\$
1
\$\begingroup\$

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:

enter image description here

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

\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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