Trouver le maximum de temps possible HH:MM en permutant quatre chiffres

Question

J'ai récemment participé à un codage de test pour une promotion au travail. C'était l'une des tâches que j'ai vraiment lutté avec et je me demandais quelle est la meilleure façon de le faire. J'ai utilisé une charge de si et si d'autre, pas la solution la plus propre, mais fait le travail.

La question que m'a posée était la suivante:

4 Format des nombres à un horaire de 24 heures (00:00), trouver le maximum (plus tard) de temps possible, en tenant compte du fait que le max heures 23 minutes max serait de 59. Si pas possible, PAS de retour POSSIBLE.

Ainsi, par exemple:

6, 5, 2, 0 ne serait-20:56

3, 9, 5, 0 serait 09:53

7, 6, 3, 8 serait PAS POSSIBLE

L'exemple de la fonction qui a dû retourner le temps ou chaîne ressemblait à ça, A, B, C, D étant un nombre différent à partir de la liste séparée par des virgules ci-dessus:

function generate(A, B, C, D) {
    // Your code here
} 

Comment peut-on remédier à cette situation?

Answer 1

Ici, c'est un non de la force brute solution que j'ai trouvé. Découvrez les commentaires dans le code pour voir comment il fonctionne. Si tout cela n'est pas claire, je peux aider à clarifier.

function generate(A, B, C, D) {
    vals = [A, B, C, D];
    counts = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
    for (i = 0; i < vals.length; i++) {
        for (j = vals[i]; j < counts.length; j++) counts[j]++;
    }
    // counts is now populated with the number of values less than or equal to the index it belongs to
    // so counts[2] is the total number of 0's, 1's and 2's
    if (counts[2] === 0) return 'NOT POSSIBLE';
    // if there are no 0's and 1's, then it must start with 2
    mustStartWith2 = counts[1] === 0;
    if (mustStartWith2 && counts[3] === 1) return 'NOT POSSIBLE';
    // We want a count of the number of free digits that are 5 or less (for the minute digit)
    numbersAvailableForMinute = counts[5] - (mustStartWith2 ? 2 : 1); 
    if (numbersAvailableForMinute === 0) return 'NOT POSSIBLE';
    // we now know that it is a valid time
    time = [0, 0, 0, 0];
    // we also know if it starts with 2
    startsWith2 = mustStartWith2 || (numbersAvailableForMinute >= 2 && counts[2] > counts[1]);
    // knowing the starting digit, we know the maximum value for each digit
    maxs = startsWith2 ? [2, 3, 5, 9] : [1, 9, 5, 9];
    for (i = 0; i < maxs.length; i++) {
        // find the first occurrence in counts that has the same count as the maximum
        time[i] = counts.indexOf(counts[maxs[i]]);
        // update counts after the value was removed
        for (j = time[i]; j < counts.length; j++) counts[j]--;
    }
    // create the time
    return time[0]+""+time[1]+":"+time[2]+""+time[3];
}

Answer 2

Ajouté exécutable extrait et quelques cas de test

function generate(A, B, C, D) {
  var combinations = []
  arguments = Array.from(arguments)
  for (var i = 0; i < 4; i++) {
    for (var j = 0; j < 4; j++) {
      if (i !== j) {
        var num = +(arguments[i] + '' + arguments[j])
        if (num <= 59 && combinations.indexOf(num) === -1)
          combinations.push(num)
      }
    }
  }
  combinations.sort((a, b) => a - b);
  var hours = combinations.filter(hour => hour <= 23);

  for (var i = hours.length - 1; i >= 0; i--) {
    for (var j = combinations.length - 1; j >= 0; j--) {
      if (computeMax(hours[i], combinations[j], arguments))
        return hours[i] + ':' + combinations[j]
    }
  }
  return 'not possible'
}

function computeMax(maxHour, maxMinute, args) {
  var minute = String(maxMinute)
  var hour = String(maxHour)
  for (var k = 0; k < minute.length; k++)
    if (hour.indexOf(minute[k]) > -1 && args.indexOf(+minute[k]) === args.lastIndexOf(+minute[k]))
      return false
  return true
}
console.log('generate(1,7,2,7)', generate(1,7,2,7))
console.log('generate(6,5,2,0)', generate(6,5,2,0))
console.log('generate(3,9,5,0)', generate(3,9,5,0))
console.log('generate(7,6,3,8)', generate(7,6,3,8))
console.log('generate(0,1,2,3)', generate(0,1,2,3))
console.log('generate(1,1,1,2)', generate(1,1,1,2))
console.log('generate(1,1,1,1)', generate(1,1,1,1))
console.log('generate(5,6,7,8)', generate(5,6,7,8))
console.log('generate(2,9,3,1)', generate(2,9,3,1))

Answer 3

Le raisonnement c'est beaucoup plus facile une fois que j'ai informés du fait que vous pouvez traiter le problème comme "générer un nombre inférieur à 24, et un certain nombre de moins de 60" au lieu de chercher à travailler avec les chiffres.

Cela passe par le nombre de paires dans le jeu, trouve le plus grand valide heure qui peut être faite à partir de la paire de chiffres, puis trouve le plus grand valide minutes qui peuvent être fabriqués à partir de restes.

var generate = function(a, b, c, d) {
  var biggest = function(a, b, max) {
    // returns largest of 'ab' or 'ba' which is below max, or false.
    // I'm sure there's a more concise way to do this, but:
    var x = '' + a + b;
    var y = '' + b + a;
    if (max > x && max > y) {
      var tmp = Math.max(x,y);
      return (tmp < 10) ? "0"+tmp : tmp;
    }
    if (max > x) return x;
    if (max > y) return y;
    return false;
  }

  var output = false;

  var input = [].slice.call(arguments);
  for (var i = 0; i < arguments.length; i++) {
    for (var j = i + 1; j < arguments.length; j++) {
      // for every pair of numbers in the input:
      var hour = biggest(input[i], input[j], 24); // What's the biggest valid hour we can make of that pair?
      if (hour) {
        // do the leftovers make a valid minute?
        var tmp = input.slice(); // copy the input
        tmp.splice(j, 1);
        tmp.splice(i, 1);
        var minute = biggest(tmp[0], tmp[1], 60);
        if (hour && minute) {
          // keep this one if it's bigger than what we had before:
          var nval = hour + ':' + minute;
          if (!output || nval > output) output = nval;
        }
      }
    }
  }
  return output || 'NOT POSSIBLE';
}

/* --------------- Start correctness test --------------------- */
  var tests = ['0000', '1212', '1234', '2359', '2360','2362','2366', '1415', '1112', '1277', '9999', '0101'];
console.log('---');
for (var i = 0; i < tests.length; i++) {
  console.log(
    tests[i],
    generate.apply(this, tests[i].split(''))
  )
}



/* --------------- Start Speed Test --------------------- */

let startTime = Math.floor(Date.now());
let times = 10000; //how many generate call you want?
let timesHolder = times;

while (times--) {
  let A = randNum();
  let B = randNum();
  let C = randNum();
  let D = randNum();
  generate(A, B, C, D);
  if (times == 0) {
    let totalTime = Math.floor(Date.now()) - startTime;
    let msg = timesHolder + ' Call Finished Within -> ' + totalTime + ' ms <-';
    console.log(msg);
    // alert(msg);
  }
}

function randNum() {
  return Math.floor(Math.random() * (9 - 0 + 1)) + 0;
}

/* --------------- END Speed Test --------------------- */

Answer 4

Une approche à l'aide d'un précalculées chaîne contenant toutes les permutations possibles.

function generate(A,B,C,D){
  var isValidTime = /^(?:[01]\d|2[0-3]):(?:[0-5]\d)$/;
  var pattern = "0123012 0132013 0213021 0231023 0312031 0321032".replace(/\d/g, i => arguments[+i]);
  var max = "";
  for(var i=pattern.length-4; i--; ){
    var time = pattern.substr(i,2) + ":" + pattern.substr(i+2,2);
    if(time > max && isValidTime.test(time)) 
      max = time;
  }
  return max || "NOT POSSIBLE";
}

[
  [6,5,0,2],
  [3,9,5,0],
  [7,6,3,8]
].forEach(arr => console.log(arr + ' -> ' + generate(...arr)));

.as-console-wrapper{top:0;max-height:100%!important}

mais nous pouvons l'améliorer, en utilisant les regex pour trouver seulement valide fois:

function generate(A,B,C,D){	
  var pattern = "0123012 0132013 0213021 0231023 0312031 0321032".replace(/\d/g, i => arguments[+i]);
  console.log(pattern);
  var matchValidTime = /([01]\d|2[0-3])([0-5]\d)/g, m, max = "";
  while(m = matchValidTime.exec(pattern)){
    var time = m[1] + ":" + m[2];
    if(time > max) max = time;
    console.log("index: %o  time: %o  max: %o", m.index, time, max);
    matchValidTime.lastIndex = m.index+1; //to find intersecting matches
  }
  return max || "NOT POSSIBLE";
}

   [
  [1,2,3,4],
  //[6,5,0,2],
  //[3,9,5,0],
  //[7,6,3,8]
].forEach(arr => console.log(arr + ' -> ' + generate(...arr)));

.as-console-wrapper{top:0;max-height:100%!important}

Answer 5

L'idée:

• Trouver toutes les combinaisons array (24 au total)
• filtrer toutes les combinaisons non valides (format de l'heure)
• trouver la valeur de temps
• sortie le tableau avec le temps maximum de la valeur

Solution:

Premier allCom sera de retour tous les combinaison des 4 nombre (total 24 combinaisons)

Ensuite, pour le 24 array (combinaisons) appel .forEach aller à travers chaque tableau de vérifier s'il est valide, format de l'heure. Si elle est valide format de l'heure puis calculer la valeur de temps avec

Si le temps est AB:CD, puis la valeur:

A = A * 10 heures = A * 10 * 3600s = A * 36000s

B = B * 1 heure = B * 3600s

C = C * 10s

D = D

Valeur totale = A*36000 + B*3600 + C*10 + D

Maintenant, vous avez la valeur de la matrice en cours, de les comparer avec les sauvés Max, remplacer le max si cette valeur est plus grande.

À la fin de la boucle de déterminer si un max trouvé ou s'il n'est pas valide.

generate(6, 5, 2, 0);
generate(3, 9, 5, 0);
generate(7, 6, 3, 8);
generate(1, 7, 2, 7);
generate(1, 1, 1, 2);

// return all combination of 4 number (24 combination total)
function allCom(inputArray) {
  var result = inputArray.reduce(function permute(res, item, key, arr) {
    return res.concat(arr.length > 1 && arr.slice(0, key).concat(arr.slice(key + 1)).reduce(permute, []).map(function(perm) {
      return [item].concat(perm);
    }) || item);
  }, []);
  return result;
}

// core function to determine the max comb
function generate(A, B, C, D) {
  let input = [A, B, C, D];
  let allComb = allCom(input);
  let max = '';
  let maxA = [];

  allComb.forEach(function(comb, index, arr) {
    if (validCom(comb)) {
      let temp = calValue(comb);
      maxA = temp > max ? comb : maxA;
      max = temp > max ? temp : max;
    }
    if (index == allComb.length - 1) {
      if (max) {
        return console.log('For ' + JSON.stringify(input) + ' found max comb: ' + maxA[0] + maxA[1] + ':' + maxA[2] + maxA[3]);
      }
      return console.log('Sorry ' + JSON.stringify(input) + ' is not valid');
    }
  });
}

// check if this array is valid time format, ex [1,2,9,0] false, [2,2,5,5] true
function validCom(ar) {
  if (ar[0] <= 2 && ((ar[0] == 2 && ar[1] < 4) || (ar[0] != 2 && ar[1] <= 9)) && ar[2] <= 5 && ar[3] <= 9) {
    return true;
  }
  return false;
}

// calculate the total value of this comb array
function calValue(ar) {
  return +ar[0] * 36000 + +ar[1] * 3600 + +ar[2] * 10 + +ar[0];
}


$('button').on('click', function(e) {
    let inp = $('select');
    generate(inp[0].value, inp[1].value, inp[2].value, inp[3].value);
});


var s = $('<select />');
for(i=0;i<10;i++) {
    $('<option />', {value: i, text: i}).appendTo(s);
}
s.clone().appendTo('#myform');
s.clone().appendTo('#myform');
s.clone().appendTo('#myform');
s.clone().appendTo('#myform');

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<form id="myform">
</form>
<br>
<button type="button">Submit</button>

---

J'invite aussi les gens à mettre ce code pour tester la vitesse de course de leur algorithme. (utilisé un code de @Diego ZoracKy pour faire cela, merci!). Avoir Du Plaisir!!!

/* --------------- Start Speed Test --------------------- */
let startTime = Math.floor(Date.now());
let times = 10000; //how many generate call you want?
let timesHolder = times;

while (times--) {
  let A = randNum();
  let B = randNum();
  let C = randNum();
  let D = randNum();
  generate(A, B, C, D);
  if (times == 0) {
    let totalTime = Math.floor(Date.now()) - startTime;
    let msg = timesHolder + ' Call Finished Within -> ' + totalTime + ' ms <-';
    console.log(msg);
    alert(msg);
  }
}

function randNum() {
  return Math.floor(Math.random() * (9 - 0 + 1)) + 0;
}
/* --------------- END Speed Test --------------------- */

/* --------------- Start Speed Test --------------------- */
let startTime = Math.floor(Date.now());
let times = 10000; //how many generate call you want?
let timesHolder = times;

while (times--) {
  let A = randNum();
  let B = randNum();
  let C = randNum();
  let D = randNum();
  generate(A, B, C, D);
  if (times == 0) {
    let totalTime = Math.floor(Date.now()) - startTime;
    let msg = timesHolder + ' Call Finished Within -> ' + totalTime + ' ms <-';
    console.log(msg);
    alert(msg);
  }
}

function randNum() {
  return Math.floor(Math.random() * (9 - 0 + 1)) + 0;
}
/* --------------- END Speed Test --------------------- */

// return all combination of 4 number (24 combination total)
function allCom(inputArray) {
  var result = inputArray.reduce(function permute(res, item, key, arr) {
    return res.concat(arr.length > 1 && arr.slice(0, key).concat(arr.slice(key + 1)).reduce(permute, []).map(function(perm) {
      return [item].concat(perm);
    }) || item);
  }, []);
  return result;
}

// core function to determine the max comb
function generate(A, B, C, D) {
  let input = [A, B, C, D];
  let allComb = allCom(input);
  let max = '';
  let maxA = [];

  allComb.forEach(function(comb, index, arr) {
    if (validCom(comb)) {
      let temp = calValue(comb);
      maxA = temp > max ? comb : maxA;
      max = temp > max ? temp : max;
    }
    if (index == allComb.length - 1) {
      if (max) {
        return 'For ' + JSON.stringify(input) + ' found max comb: ' + maxA[0] + maxA[1] + ':' + maxA[2] + maxA[3];
      }
      return 'Sorry ' + JSON.stringify(input) + ' is not valid';
    }
  });
}

// check if this array is valid time format, ex [1,2,9,0] false, [2,2,5,5] true
function validCom(ar) {
  if (ar[0] <= 2 && ((ar[0] == 2 && ar[1] < 4) || (ar[0] != 2 && ar[1] <= 9)) && ar[2] <= 5 && ar[3] <= 9) {
    return true;
  }
  return false;
}

// calculate the total value of this comb array
function calValue(ar) {
  return +ar[0] * 36000 + +ar[1] * 3600 + +ar[2] * 10 + +ar[0];
}