7
\$\begingroup\$

I am new to coding and to apply for an internship I need to solve several tasks. This is one of them. I wrote working code, but the program says it takes too long to complete. Help me speed up my code please.

Requirements:

  • Time limit - 1s
  • Memory Limit - 64mb
  • Input- standard input
  • Output- standard output

There is a task:

Hi, your colleague forgot the pin code from the door to the office. The keyboard is:

        ┌───┬───┬───┐
        │ 1 │ 2 │ 3 │
        ├───┼───┼───┤
        │ 4 │ 5 │ 6 │
        ├───┼───┼───┤
        │ 7 │ 8 │ 9 │
        └───┼───┼───┘
            │ 0 │
            └───┘

        

A colleague recalls that it seems that the pin code was 1357, but perhaps each digit should be shifted horizontally or vertically, but not diagonally.

For example, instead of 1 it can be 2 or 4, and instead of 5 it can be 2, 4, 6 or 8.

Help a colleague get into the office.

Input:
A string with a pin code. The length of the string is from 1 to 8 digits, for example, 1357.

Output:
The source pin code and possible pin codes with regard to shifts, sorted and separated by a comma.

Do not forget that the pin codes must be strings, as they can begin with 0, and must be sorted like strings.

Examples

Input: 11 Output: 11,12,14,21,22,24,41,42,44

Input: 8 Output: 0.5,7,8,9

Input: 46 Output: 13,15,16,19,43,45,46,49,53,55,56,59,73,75,76,79

Formalization:

var readline = require("readline");
           var rl = readline.createInterface(process.stdin, process.stdout);
           rl.on("line", function(line) {
             console.log("0,5,7,8,9")
             rl.close();
           }).on("close",function(){
             process.exit(0);
           });

MY code

const readline = require('readline');

const rl = readline.createInterface({
 input: process.stdin,
 output: process.stdout
});

function drawMatrix(InArray) {
   let matrix= [];
   for (let z = 0; z < InArray.length; z++) {
       switch (InArray[z]) {
           case '1':
               row = [1, 2, 4];
               break;
           case '2':
               row = [1, 2, 3, 5];
               break;
           case '3':
               row = [2, 3, 6];
               break;
           case '4':
               row = [1, 4, 5, 7];
               break;
           case '5':
               row = [2, 4, 5, 6, 8];
               break;
           case '6':
               row = [3, 5, 6, 9];
               break;
           case '7':
               row = [4, 7, 8];
               break;
           case '8':
               row = [0, 5, 7, 8, 9];
               break;
           case '9':
               row = [6, 8, 9];
               break;
           case '0':
               row = [0, 8];
               break;
       };
      // console.log(row);
       matrix.push(row);
   };
  //console.log(matrix);
  return matrix;
};

function keyVars(matrix) {
   let positions = [];
   let someVar = [];
   let allVars = [];
   let totalCount = matrix.length;

   for (let  i = 0; i < totalCount; i++) {  
       positions[i] = 0;
   };

   let next = totalCount - 1;

   while (next >= 0) {
       for (let i=0; i < totalCount; i++) {
           someVar.push(matrix[i][positions[i]]);
       };

       next = totalCount - 1;

       let Var = someVar.join('');
       someVar = [];


       while (next >=0 && (positions[next] + 1) >= matrix[next].length) {
       next--;
       };

       positions[next]++;

       for (let i = next + 1; i < totalCount; i++) {
           positions[i] = 0;
       };

       allVars.push(Var);
   };

   let allVarsStr = allVars.join();
   return allVarsStr;
};

rl.on('line', (input) => {
   console.log(`Входные данные: ${input}`);
   console.log(`Выходные данные: ${keyVars(drawMatrix(input))}`);
   rl.close();
 }).on("close",function(){
   process.exit(0);
 });

```    
\$\endgroup\$

migrated from stackoverflow.com Sep 15 at 0:04

This question came from our site for professional and enthusiast programmers.

  • 1
    \$\begingroup\$ You use heayvy array functions. Which are internally a time eater. Why not simply use a string with 10 chars ? either something like "0123456789" or "0 1 2 3 4 5 6 7 8 9" last ones can be fast transformed into array by using the split function. \$\endgroup\$ – Thomas Ludewig Sep 14 at 10:34
  • \$\begingroup\$ "0123456789" can be indexed like an array without any transformation at all. "0123456789"[9] === "9" \$\endgroup\$ – Oh My Goodness Sep 15 at 3:31
3
\$\begingroup\$

We can simplify this quite a bit. At a high level, note that all you are doing is:

  1. Converting each digit of the input to an array of possible neighbors.
  2. Now you have an array of neighbor arrays.
  3. The answer is simply the cartesian cross product of those neighbor arrays.
  4. Sort them.
  5. Turn the into back into strings.

The cartesian cross-product is a simple utility method.

The neighbor possibilities are more compactly expressed as a JS object than by a switch statement, and this representation also makes it easy to map over them.

Putting it all together we get:

function xprod(...arrays) {
  return arrays.reduce((m, x) => m.flatMap(
    results => x.map(elm => results.concat([elm]))
  ), [ [] ])
}

function possibleCodes(code) {
  const neighbors = {
    '1': [1, 2, 4],
    '2': [1, 2, 3, 5],
    '3': [2, 3, 6],
    '4': [1, 4, 5, 7],
    '5': [2, 4, 5, 6, 8],
    '6': [3, 5, 6, 9],
    '7': [4, 7, 8],
    '8': [0, 5, 7, 8, 9],
    '9': [6, 8, 9],
    '0': [0, 8],
  }
  const possibilitiesByDigit = code.split('').map(x => neighbors[x])
  return xprod(...possibilitiesByDigit).map(x => x.join('')).sort()
}
\$\endgroup\$

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.