Найти максимально возможное время HH: MM, переместив четыре заданные цифры

Ответ 1

Вот решение без грубой силы, с которым я столкнулся. Ознакомьтесь с комментариями в коде, чтобы узнать, как это работает. Если какой-либо из них неясен, я могу помочь уточнить.

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 and 2's
    if (counts[2] === 0) return 'NOT POSSIBLE';
    // if there are no 0 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];
}

Ответ 2

Добавлен исполняемый фрагмент и некоторые тестовые примеры

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

Ответ 3

Рассуждение об этом стало намного проще, когда я убедился в том, что вы можете рассматривать проблему как "сгенерировать число меньше 24 и число меньше 60" вместо того, чтобы пытаться работать с отдельными цифрами.

Это проходит через пары чисел в наборе, находит самый большой допустимый час, который может быть сделан из этой пары цифр, а затем находит самую большую допустимую минуту, которая может быть сделана из остатков.

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 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 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 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 --------------------- */

Ответ 4

Подход с использованием предварительно вычисленной строки, содержащей все возможные перестановки.

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}

Ответ 5

Идея:

• Найти все комбинации массива (всего 24)
• отфильтровать все недопустимые комбинации (формат времени)
• найдите значение времени
• выводит массив с максимальным значением времени

Решение:

Сначала allCom вернет всю комбинацию из 4-х чисел (всего 24 комбинации)

Затем для 24 массива (комбинации) вызов .forEach пройдите через каждый массив, проверьте, является ли он допустимым форматом времени. Если это допустимый формат времени, тогда вычислите значение времени с помощью

Если время AB: CD, то значение:

A = A * 10 часов = A * 10 * 3600s = A * 36000s

B = B * 1 час = B * 3600s

C = C * 10s

D = D

Общее value = A * 36000 + B * 3600 + C * 10 + D

Теперь вы получили значение текущего массива, сравните с сохраненным Max, замените max, если это значение больше.

В конце цикла определите, найден ли max или он недействителен.

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>

Ответ 6

Я бы использовал JavaScript Date объект, чтобы определить, было ли определенное время действительным, путем разбора строки как строки даты и времени ISO (например, 1970-01-01T62:87), а затем тестирование !isNaN( aDateInstance.getTime() ) и сравнение экземпляра Date с ранее сохраненным наибольшим экземпляром Date (если применимо):

// permutator() borrowed from https://stackoverflow.com/a/20871714
function permutator( inputArr ) {
  var results = [];

  function permute( arr, memo ) {
    var cur, memo = memo || [];

    for( var i = 0; i < arr.length; i++ ) {
      cur = arr.splice( i, 1 );
      if( arr.length === 0 ) {
        results.push( memo.concat( cur ) );
      }
      permute( arr.slice(), memo.concat( cur ) );
      arr.splice( i, 0, cur[ 0 ] );
    }

    return results;
  }

  return permute( inputArr );
}

function generate( A, B, C, D ) {
  var r = null;
  permutator( [ A, B, C, D ] ).forEach( function( p ) {
    var d = new Date( '1970-01-01T' + p[ 0 ] + '' + p[ 1 ] + ':' + p[ 2 ] + '' + p[ 3 ] );
    if( !isNaN( d.getTime() ) && d > r ) {
      r = d;
    }
  } );

  var h, m;
  return r ? ( ( h = r.getHours() ) < 10 ? '0' + h : h ) + ':' + ( ( m = r.getMinutes() ) < 10 ? '0' + m : m ) : 'NOT POSSIBLE';
}

Ответ 7

function pickN(arr, clause){
	const index = arr.findIndex(clause);
	if(index >= 0){
		return arr.splice(index, 1)[0];
	}
}

function getMaxTime(args, tryN1 = 2){
	let paramsArray = Array.from(args).sort((a , b) => a < b);

	let n1 = pickN(paramsArray, n => n <= tryN1);
	let n2 = pickN(paramsArray, n => n1 === 2 ? n <= 3 : n);
	let n3 = pickN(paramsArray, n => n <= 5);
	let n4 = paramsArray.pop();

	if([n1,n2,n3,n4].some(n => typeof(n) === `undefined`)){
		return tryN1 > 0 && getMaxTime(args, --tryN1);
	}

	return `${n1}${n2}:${n3}${n4}`;
}

function generate(A, B, C, D) {
	let maxTime = getMaxTime(arguments);
	if(maxTime){
		return maxTime;
	}

	return `NOT POSSIBLE`;
}


////////////////////////
// TESTING MANY TIMES //
////////////////////////
let times = 100;
while(times--){
	let paramA = randomNumbers();
	let paramB = randomNumbers();
	let paramC = randomNumbers();
	let paramD = randomNumbers();
	let result = generate(paramA, paramB, paramC, paramD);

	console.log(`${paramA},${paramB},${paramC},${paramD} = ${result}`);
}

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

Ответ 8

Вот что я придумал. Вряд ли элегантный, я могу попытаться привести его в порядок, сделав его немного более эффективным. Я чувствую, что подход грубой силы будет самым чистым и эффективным способом сделать это. Это беспорядок.

// w: highest value 2 or less
// UNLESS: 1 of b, c, or d are less than 3 while the other two are greater than 7
// x: highest value
// UNLESS: last was 2 then highest value less than 2
// y: highest value less than 5
// z: highest remaining value

function findhighestwhere(array, condition) {
  let res = null
  let val = -1
  let i = 0
  for (let x of array) {
    if (x !== null && condition(x) && x > val) {
      res = i
      val = x
    }
    i++
  }
  // console.log(`Test index: ${res} \n Test value: ${val}`)
  return res
}

function generate(a,b,c,d) {
  // console.log(`Testing: ${a}${b}${c}${d}`)
  let array = [a,b,c,d]
  let wi = findhighestwhere(array, x => x <= 2)
  // That one pain in the conditional edge-case
  if ( array[wi] == 2 ) {
    // console.log(`Encountered First Position 2 Checking for Edge Case`)
    let i = 0
    let lowcount = 0
    let highcount = 0
    for (let x of array) {
      if ( i != wi && x <= 3 ) lowcount++
      if ( i != wi && x >= 6 ) highcount++
      i++
    }
    if ( lowcount == 1 && highcount == 2 ) {
      // console.log(`Edge Case Encountered`)
      wi = findhighestwhere(array, x => x <= 1)
    }
  }
  if ( wi === null ) return false
  let w = array[wi]
  // console.log(`W: ${w}`)
  array[wi] = null  
  if ( w == 2 ) {
    var xi = findhighestwhere(array, x => x <= 3)
  } else {
    var xi = findhighestwhere(array, x => true)
  }
  if ( xi === null ) return false
  let x = array[xi]
  // console.log(`X: ${x}`)
  array[xi] = null
  let yi = findhighestwhere(array, x => x <= 5)
  if ( yi === null ) return false
  let y = array[yi]
  // console.log(`Y: ${y}`)
  array[yi] = null
  let zi = findhighestwhere(array, x => true)
  if ( zi === null ) return false
  let z = array[zi]
  // console.log(`Z: ${z}`)
  array[zi] = null

  return `${w}${x}:${y}${z}`
}


console.log(`6520: ${generate(6,5,2,0)}`) // 6520: 20:56
console.log(`3950: ${generate(3,9,5,0)}`) // 3950: 09:53
console.log(`7638: ${generate(7,6,3,8)}`) // 7638: false
console.log(`1727: ${generate(1,7,2,7)}`) // 1727: 17:27

Ответ 9

ОБНОВЛЕНО

Просто попробуйте найти способ улучшить производительность, новая идея вдохновлена ​​подсчетом сортировки.

Просто подсчитайте количество каждой цифры, затем закрепите в следующей цепочке зависимостей, скорейшим найдите оптимальные возможности. Ответ был бы первым, первым приоритетом:

• 2 [max digit <= 3]: [max digit <= 5] [*]
• 1 [*]: [max digit <= 5] [*]
• 0 [*]: [max digit <= 5] [*]

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

  while (times--) {
    var A = randNum();
    var B = randNum();
    var C = randNum();
    var D = randNum();
    generate(A, B, C, D);
    if (times == 0) {
      var totalTime = Math.floor(Date.now()) - startTime;
      var 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 --------------------- */
  
  function generate(A,B,C,D){
      var cnt = [0,0,0,0,0,0,0,0,0,0], ans = ['', ''];      
      cnt[A]++; cnt[B]++; cnt[C]++; cnt[D]++;
      
      function gen(part, max){
         for(var i=max; i>=0; i--) if(cnt[i]){
              ans[part] += i;
              cnt[i]--;
              return 1;
          }
          return 0;
      }
      function rollback(first){
          cnt[first]++;
          for(var i in ans[0]) cnt[ans[0][i]]++;
          for(var i in ans[1]) cnt[ans[1][i]]++;
          ans[0] = ans[1] = '';
      }
      /*** Main logic, based on the chain of dependencies ***/
      if(cnt[2]){
          cnt[2]--;
          if(!gen(0, 3) || !gen(1,5) || !gen(1,9)) rollback(2);
          else return '2' + ans[0] + ':' + ans[1];
      }
      if(cnt[1]){
          cnt[1]--;
          if(!gen(0, 9) || !gen(1,5) || !gen(1,9)) rollback(1);
          else return '1' + ans[0] + ':' + ans[1];
      }
      if(cnt[0]){
          cnt[0]--;
          if(!gen(0, 9) || !gen(1,5) || !gen(1,9)) rollback(0);
          else return '0' + ans[0] + ':' + ans[1];
      }
      return 'NOT POSSIBLE';
  }
  console.log(generate(1,7,2,7));
  console.log(generate(0,0,2,9));
  console.log(generate(6,5,2,0));
  console.log(generate(3,9,5,0));
  console.log(generate(7,6,3,8));
  console.log(generate(0,0,0,0));
  console.log(generate(9,9,9,9));
  console.log(generate(1,2,3,4));

Ответ 10

Я мог бы делать с т if и else, но я уверен, что это уже сделано. Вместо этого я иду по-другому.

• Получаем все перестановки заданных четырех чисел. Здесь я использую свой алгоритм rotPerm. Я думаю, что это один из самых быстрых в JS.
• Отфильтровать недействительные времена
• Выберите наибольшее из оставшихся значений
• Формат как время.

function getMaxTime(...a){
  
  function perm(a){
    var r = [[a[0]]],
        t = [],
        s = [];
    if (a.length <= 1) return a;
    for (var i = 1, la = a.length; i < la; i++){
      for (var j = 0, lr = r.length; j < lr; j++){
        r[j].push(a[i]);
        t.push(r[j]);
        for(var k = 1, lrj = r[j].length; k < lrj; k++){
          for (var l = 0; l < lrj; l++) s[l] = r[j][(k+l)%lrj];
          t[t.length] = s;
          s = [];
        }
      }
      r = t;
      t = [];
    }
    return r;
  }
  
  function isValidTime(a){
    return 10*a[0]+a[1] < 24 && 10*a[2]+a[3] < 60;
  }
  
  var time = perm(a).filter(t => isValidTime(t))         // filter out the invalids
                    .map(t => t.reduce((p,c) => 10*p+c)) // convert them into 4 digit integer
                    .reduce((p,c) => p > c ? p : c, -1); // get the biggest
  return time >= 0 ? ("0" + ~~(time/100)).slice(-2) + ":" + time%100 : "No way..!";
}
console.log(getMaxTime(6, 5, 2, 0));
console.log(getMaxTime(3, 9, 5, 0));
console.log(getMaxTime(7, 6, 3, 8));

Ответ 11

Для мест, AB:CD,

If at any point a condition cannot be fulfilled:
  return NOT POSSIBLE

If there are two numbers greater than 5:
  place the larger in B, smaller in D

for non-filled places from left to right:
  if B > 3:
    place a 1 in A
  else:
    place the largest number smaller than 3 in A

  if A is 2:
    place the largest number smaller than 4 in B
  else:
    place the largest number in B

  place the largest number smaller than 6 in C
  place the remaining number in D

Ответ 12

Здесь моя попытка. Добавлены встроенные комментарии с пояснениями.

// think of the result of the form {h1}{h2}:{ms}
function generate(a, b, c, d) {
  const digits = [a, b, c, d];

  // extract possible starting digits
  const possibleH1s = [2, 1, 0].filter(digit => digits.includes(digit));
  
  // check result, starting from the highest possible h1 digit
  // if digits doesn't contains any of [2,1,0], we're done
  for (const h1 of possibleH1s) {

    // extract the remaining digits after h1
    const withoutH1 = removeFrom(digits, h1);
    
    // determine all possible h2 digits based on the h1 digit
    const possibleH2s = h1 === 2
      ? [3,2,1,0]
      : [9,8,7,6,5,4,3,2,1,0];

    // find the highest possible h2 digit (works because array of possible digits above is in descending order)
    // if none exist, loop iteration is done
    const h2 = possibleH2s.find(d => withoutH1.includes(d));
    if (typeof h2 !== 'number') {
      continue;
    }
    
    // remove h2 so we can search for the remaining ms digits
    const [possibleMS1, possibleMS2] = removeFrom(withoutH1, h2);
    
    // build the two possible combinations for ms    
    const possibleMs = [
      Number(`${possibleMS1}${possibleMS2}`),
      Number(`${possibleMS2}${possibleMS1}`)
    ];
    
    // determine the min and max ms value
    const maxMs = Math.max(...possibleMs);
    const minMs = Math.min(...possibleMs);

    // find the largest valid ms value
    // if none exist, loop iteration is done
    const ms = maxMs < 60 ? maxMs : minMs < 60 ? minMs : undefined;
    if (typeof ms !== 'number') {
      continue;
    }

    // yay, time
    return `${h1}${h2}:${padWithZero(ms)}`;
  }
  
  return 'NOT POSSIBLE';
}

// returns a new array by removing a single element 
// that is equal to `val` from the given array
// (performs better than splice cause if doesn't do array shift)
function removeFrom(arr, val) {
  const newArr = [];
  for (let i = 0, l = arr.length, found = false; i < l; i++) {
    if (arr[i] !== val || found) {
      newArr.push(arr[i]);
    } else {
      found = true;
    }
  }
  return newArr;
}

function padWithZero(digit) {
  return digit < 10 ? `0${digit}` : `${digit}`;
}

/* --------------- Tests --------------------- */

const speedTest = (times = 10000) => {
  let counter = times;
  const start = performance.now();
  while (counter--) {
    const A = randNum();
    const B = randNum();
    const C = randNum();
    const D = randNum();
    generate(A, B, C, D);
    if (counter == 0) {
      const ms = performance.now() - start;
      console.log(`${times} times to run generate took ${ms} ms`);
    }
  }
}

const randNum = () => Math.floor(Math.random() * (9 - 0 + 1)) + 0;

const accuracyTest = () => {
  console.assert(generate(1,7,2,7) === '17:27');
  console.assert(generate(0,0,2,9) === '20:09');
  console.assert(generate(6,5,2,0) === '20:56');
  console.assert(generate(3,9,5,0) === '09:53');
  console.assert(generate(7,6,3,8) === 'NOT POSSIBLE');
  console.assert(generate(0,0,0,0) === '00:00');
  console.assert(generate(9,9,9,9) === 'NOT POSSIBLE');
  console.assert(generate(1,2,3,4) === '23:41');
  console.log('All good!');
}

speedTest();
accuracyTest();

Ответ 13

С небольшим входным и выходным пространством всегда можно выбрать справочную таблицу; однако я обнаружил, что в JavaScript размер таблицы имеет удивительно большое влияние на скорость.

Если мы начнем с сортировки ввода для получения канонической версии, так что 4,3,2,1 и 3,1,4,2 преобразуются в 1,2,3,4, существует менее 400 возможностей, которые приводят к действительному результату. Но как только я добавил более 200 записей в справочную таблицу, скорость значительно снизилась (что, вероятно, зависит от браузера).

Однако есть только пять типов цифр:

0,1    <- can be first digit of hours followed by any digit
2      <- can be first digit of hours followed by 0-3
3      <- can be second digit of hours after a 2 to form 23 hours
4,5    <- can be first digits of minutes
6-9    <- can only be second digit of hours or minutes

Внутри этих типов цифры взаимозаменяемы; оптимальная перестановка будет одинаковой:

2,4,0,6  ->  20:46  (ACBD)
2,5,1,9  ->  21:59  (ACBD)

Если вы представляете цифры по типам цифр "0" (0-1), "2", "3", "4" (4-5) и "6" (6-9), есть только 48 комбинаций, которые приводят к действительному решению, каждый из которых использует одну из 16 различных перестановок. Код с этими меньшими справочными таблицами оказывается намного быстрее:

function generate(A, B, C, D) {
    var swap; // sorting network
    if (A > B) { swap = A; A = B; B = swap; }
    if (C > D) { swap = C; C = D; D = swap; }
    if (A > C) { swap = A; A = C; C = swap; }
    if (B > D) { swap = B; B = D; D = swap; }
    if (B > C) { swap = B; B = C; C = swap; }

    var table = {"0000":15, "0002":15, "0003":14, "0004":14, "0006":14, "0022":15, 
                 "0023":14, "0024":13, "0026":12, "0033":11, "0034":11, "0036":11, 
                 "0044":11, "0046":11, "0066":10, "0222":15, "0223":14, "0224":13, 
                 "0226":12, "0233":11, "0234": 9, "0236": 8, "0244": 7, "0246": 6, 
                 "0266": 4, "0333": 5, "0334": 5, "0336": 5, "0344": 5, "0346": 5, 
                 "0366": 4, "0444": 5, "0446": 5, "0466": 4, "2222":15, "2223":14, 
                 "2224":13, "2226":12, "2233":11, "2234": 9, "2236": 8, "2244": 7, 
                 "2246": 6, "2333": 5, "2334": 3, "2336": 2, "2344": 1, "2346": 0};

    var type = ['0','0','2','3','4','4','6','6','6','6'];
    var key = type[A] + type[B] + type[C] + type[D];
    var permutation = table[key];
    if (permutation == undefined) return "NOT POSSIBLE";

    var digits = [[2,3,C,D], [2,3,D,C], [2,3,3,D], [2,3,D,3], 
                  [A,D,B,C], [A,D,C,B], [2,A,C,D], [2,A,D,C], 
                  [2,3,A,D], [2,3,D,A], [B,D,A,C], [B,D,C,A], 
                  [2,B,A,D], [2,B,D,A], [C,D,B,A], [D,C,B,A]];

    var time = digits[permutation];
    return "" + time[0] + time[1] + ':' + time[2] + time[3];
}

function rndDigit() { return Math.floor(Math.random() * 10); }
for (var tests = 0; tests < 11; tests++) {
    var d = [rndDigit(), rndDigit(), rndDigit(), rndDigit()];
    document.write(d + " &rarr; " + generate(d[0],d[1],d[2],d[3]) + "<BR>");
}

Ответ 14

Я думаю, что этот метод называется Brute Force. Взяли тестовые образцы из ответа @Dummy.

<script>
function generate(A, B, C, D) {
    var result = -1
    var v = [A, B, C, D]
    for (i = 0; i < 4; i++) {
        for (j = 0; j < 4; j++) if (j != i) {
            for (k = 0; k < 4; k++) if (k != j && k != i) {
                for (m = 0; m < 4; m++) if (m != k && m != j && m != i) {
                    if (v[i]*10 + v[j] < 24 && v[k]*10 + v[m] < 60) { //legal time
                        if (v[i]*1000 + v[j]*100 + v[k]*10 + v[m] > result) {
                            result = v[i]*1000 + v[j]*100 + v[k]*10 + v[m]
                        }
                    }
                }
            }
        }
    }
    return result >= 0? Math.floor(result/100) + ':' + result%100: 'NOT POSSIBLE'
} 

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))
</script>

Ответ 15

Ну, начиная с это предложение о перестановках в JavaScript, где, если массив значений получает все возможные уникальные перестановки, я получил это решение:

• Предполагая, что у вас есть все возможные комбинации с 4 цифрами,
• и считая, что значение правых часов находится в диапазоне 00-23
• и считая, что значение правой минуты находится в диапазоне 00-59

Вы можете использовать этот простой код для выполнения действия:

function maxTime(a, b, c, d) {
  var ps = Array.from(uniquePermutations([a, b, c, d]));
  while (maxHour = ps.pop()) {
    var timing = maxHour.join('').replace(/([0-9]{2})([0-9]{2})/, '$1:$2');

    if (/([0-1][0-9]|2[0-3])\:[0-5][0-9]/.test(timing)) {
      return timing;
    }
  }
  return false;
}

function swap(a, i, j) {
  const t = a[i];
  a[i] = a[j];
  a[j] = t;
}

function reverseSuffix(a, start) {
  if (start === 0) {
    a.reverse();
  } else {
    let left = start;
    let right = a.length - 1;

    while (left < right)
      swap(a, left++, right--);
  }
}

function nextPermutation(a) {
  // 1. find the largest index `i` such that a[i] < a[i + 1].
  // 2. find the largest `j` (> i) such that a[i] < a[j].
  // 3. swap a[i] with a[j].
  // 4. reverse the suffix of `a` starting at index (i + 1).
  //
  // For a more intuitive description of this algorithm, see:
  //   https://www.nayuki.io/page/next-lexicographical-permutation-algorithm
  const reversedIndices = [...Array(a.length).keys()].reverse();

  // Step #1; (note: `.slice(1)` maybe not necessary in JS?)
  const i = reversedIndices.slice(1).find(i => a[i] < a[i + 1]);

  if (i === undefined) {
    a.reverse();
    return false;
  }

  // Steps #2-4
  const j = reversedIndices.find(j => a[i] < a[j]);
  swap(a, i, j);
  reverseSuffix(a, i + 1);
  return true;
}

function* uniquePermutations(a) {
  const b = a.slice().sort();

  do {
    yield b.slice();
  } while (nextPermutation(b));
}


function maxTime(a, b, c, d) {
  var ps = Array.from(uniquePermutations([a, b, c, d]));
  while (maxHour = ps.pop()) {
    var timing = maxHour.join('').replace(/([0-9]{2})([0-9]{2})/, '$1:$2');

    if (/([0-1][0-9]|2[0-3])\:[0-5][0-9]/.test(timing)) {
      return timing;

    }
  }
  return false;
}
console.log(maxTime(6, 5, 2, 0));
console.log(maxTime(3, 9, 5, 0));
console.log(maxTime(7, 6, 3, 8));

Ответ 16

Хммм... Я думаю, это очень просто, если вы разделите его на более простые проблемы: например, найдите все действительные часы (00-23), для каждого из этих действительных часов используйте оставшиеся номера, чтобы найти действительные минуты (00- 59), объединить и сортировать. В псевдокоде что-то вроде следующего

    valid_times = []
    function get_max(digits[]) {
                for each d1 in digits[]
            for each d2 in (digits[] except d1)
                res = is_valid_hour(d1, d2)
                if(res > 0) {
                    if(res == 2)
                        swap(d1, d2)
                    d3 = one of the rest in (digits except d1 and d2)
                    d4 = digit left in digits[]
                    res = is_valid_minute(d3, d4)
                    if(res > 0)
                        if(res == 2)
                            swap(d3, d4)
                        add (d1, d2, d3, d4) to valid_times;
                }
        sort(valid_times)
        print valid_times[0]
    }

    function is_valid_hour(a, b) {
        if (a*10+b<24)
            return 1

        if (b*10+a<24)
            return 2

        return 0;
    }

    function is_valid_minute(a, b) {
        if (a*10+b<60)
            return 1

        if (b*10+a<60)
            return 2

        return 0;
    }

Ответ 17

Это не элегантно или красиво, но, похоже, это трюк!

const NOT_POSSIBLE = 'NOT POSSIBLE';

function generate(A, B, C, D) {
	var args = [A, B, C, D];
	var idx = -1;
	var out = NOT_POSSIBLE;
	var firstN, secondN;

	MAIN: {
		args.sort(NUMERIC_ASCENDING);
		// number has to start with 0, 1 or 2
		if (args[0] > 2) break MAIN;

		while (args[++idx] < 3) {}

		// take the higest 2, 1, or 0
		firstN = args[--idx];
		args = pop(args, idx);

		if (firstN === 2) {
			// make sure that the first number doesn't exceed 23 and
			// the second number 59
			if (args[0] > 3 || args[0] > 1 && args[1] > 5)
				break MAIN;
			// advance to the first number < 3 or the length
			idx = 0;
			while (args[++idx] < 3){}
		} else {
			// much simpler if we have a 0 or 1, take the biggest n remaining
			idx = args.length;
		}

		secondN = args[--idx];
		args = pop(args, idx);
		// if minutes number is too large, swap
		if (args[0] > 5) {
			out = '' + secondN + args[1] + ':' + firstN + args[0];
		} else {
			// if bottom number is low enough, swap for more minutes
			out = '' + firstN + secondN + (args[1] < 6 ? ':' + args[1] + args[0] : ':' + args[0] + args[1]);
		}
	}
	return out;
}

// numeric comparator for sort
function NUMERIC_ASCENDING(x, y) {
	return x > y ? 1 : y > x ? -1 : 0;
}

// specialized "array pop" I wrote out longhand that very optimized; might be cheating =D
function pop(arr, target) {
	switch (arr.length) {
	case 3:
		switch (target) {
		case 0: return [arr[1], arr[2]];
		case 1: return [arr[0], arr[2]];
		default: return [arr[0], arr[1]];
		}
	case 4:
		switch (target) {
		case 0: return [arr[1], arr[2], arr[3]];
		case 1: return [arr[0], arr[2], arr[3]];
		case 2: return [arr[0], arr[1], arr[3]];
		default: return [arr[0], arr[1], arr[2]];
		}
	}
}

/* --------------- Start Speed Test --------------------- */
let startTime = Math.floor(Date.now());
let times = 10000;
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);
  }
}
function randNum() {
  return Math.floor(Math.random() * (9 - 0 + 1)) + 0;
}
/* --------------- END Speed Test --------------------- */

Ответ 18

Мой подход состоит в том, чтобы иметь массив доступных чисел (stack), а другой - с возвращаемым значением (ret). Сначала я вставляю недопустимые значения "-1". Затем я сортирую стеки в нисходящем и петлевом петле, чтобы попытаться назначить наибольшее возможное число для возврата стека.

function swap(a, b, p1, p2) {
  var temp = a[p1];
  a[p1] = b[p2];
  b[p2] = temp;
}

function t(a, b, c, d) {
  var stack = [a, b, c, d];
  var ret   = [-1, -1, -1, -1];

  stack.sort().reverse();
  var change = true;
  var i = 0;
  // this while is assigning HOURS
  while(change === true || i < 4) {
    change = false;
    
    // Assigning at first position (Hh:mm), so number must be lower or equal to 2
    if(stack[i] <= 2 && ret[0] < stack[i]) {
      swap(ret, stack, 0, i);
      change = true;
      i = 0;
    } 
    // Assigning at second position (hH:mm), so number must be <= 4 if number 
    // at first position is 2, otherwise just make sure valid number 
    // (0 to 1) is assigned at first position
    else if(((ret[0] === 2 && stack[i] <= 4) || ret[0] < 2 && ret[0] >= 0) && ret[1] < stack[i]) {
      swap(ret, stack, 1, i);
      change = true;
      i = 0;
    }
    else i++;
  }
  
  stack.sort().reverse();
  change = true;
  i = 0;
  // This while is assigning minutes
  while(change === true || i < 4) {
    change = false;
    
    if(stack[i] <= 5 && ret[2] < stack[i]) {
      swap(ret, stack, 2, i);
      change = true;
      i = 0;
    } 
    else if(stack[i] <= 9 && ret[3] < stack[i]) {
      swap(ret, stack, 3, i);
      change = true;
      i = 0;
    }
    else i++;
  }
  
  // If return stack contains -1, invalid combination was entered
  return Math.min.apply(Math, ret) > -1
    ? ret[0] + "" + ret[1] + ":" + ret[2] + "" + ret[3]
    : "NOT POSSIBLE";
}

console.log(t(6, 5, 2, 0)); // 20:56
console.log(t(3, 9, 5, 0)); // 09:53
console.log(t(2, 5, 6, 8)); // NOT POSSIBLE

Ответ 19

Действительно опаздываю на вечеринку, но я думаю, что есть довольно простое решение проблемы (медленнее и уродливее, чем другие решения). Просто повторите (без жесткого кодирования, без перестановок) через все целочисленные значения от 2359 до 0 и проверьте, содержат ли они предоставленные цифры:

Number.prototype.pad = function(size) {
    var s = String(this);
    while (s.length < (size || 2)) {s = "0" + s;}
    return s;
}

getHHMM = (val) => `${Math.floor(val / 100).pad(2)}:${(val % 100).pad(2)}`;

isValidDate = value => !isNaN(new Date(`1970-01-01T${getHHMM(value)}`).getTime());

isFit = function(a, b, c, d, value) {
    var valStr = value.pad(4).split("").sort().join("");
    var digStr = [a, b, c, d].sort().join("");
    return valStr === digStr;
}

generate = function(a, b, c, d) {
    for (var i = 2359; i >= 0; i--) {
        if (isFit(a, b, c, d, i) && isValidDate(i))
            return getHHMM(i);
    }
    return "NOT POSSIBLE";
}

Ответ 20

Это решение находится в Swift 3.0.

func returnValue (_ value :inout Int, tempArray : [Int] , compareValue : Int) -> Int {

    for i in tempArray {

        if value <= i && i <= compareValue {
            value = i
        }
    }

    return value
}

func removeValue(_ value : Int, tempArr : inout [Int]) -> Bool {
    let index = tempArr.index(of: value)
    tempArr.remove(at: index ?? 0)
    return index != nil ? true : false
}

public func solution(_ A : Int, _ B : Int, _ C : Int, _ D : Int) -> String {

    var tempArray = [A, B, C, D]

    let mainArray = [A, B, C, D]

    var H1 : Int = -1, H2: Int = -1, M1 : Int = -1, M2 : Int = -1;

    H1 = returnValue(&H1, tempArray: tempArray, compareValue: 2)

    if !removeValue(H1, tempArr: &tempArray) {
        return "NOT POSSIBLE"
    }

    for value in tempArray {

        if H1 < 2 {
            if H2 <= value && value <= 9 {
                H2 = value
            }
        } else {
            if H2 <= value && value <= 3 {
                H2 = value
            }
        }
    }

    if !removeValue(H2, tempArr: &tempArray) {
        return "NOT POSSIBLE"
    }

    M1 = returnValue(&M1, tempArray: tempArray, compareValue: 5)


    if M1 >= 0 {

        if !removeValue(M1, tempArr: &tempArray) {
            return "NOT POSSIBLE"
        }
    } else if mainArray.contains(0) || mainArray.contains(1) {

        H1 = -1

        H1 = returnValue(&H1, tempArray: mainArray, compareValue: 1)

        for value in mainArray {

            if H1 < 2 {
                if H2 <= value && value <= 9 {
                    H2 = value
                }
            } else {
                if H2 <= value && value <= 3 {
                    H2 = value
                }
            }
        }


        tempArray.removeAll()

        for value in mainArray {
            tempArray.append(value)
        }


        var index = tempArray.index(of: H1)
        tempArray.remove(at: index!)

        index = tempArray.index(of: H2)
        tempArray.remove(at: index!)

        M1 = -1
        M1 = returnValue(&M1, tempArray: tempArray, compareValue: 5)

        if !removeValue(M1, tempArr: &tempArray) {
            return "NOT POSSIBLE"
        }

    } else {
        return "NOT POSSIBLE"
    }

    // Now last we have M2 = temp.last

    if let lastValue = tempArray.last {
        M2 = lastValue
    }

    if M2 < 0 {
        return "NOT POSSIBLE"
    }

    return "\(H1)\(H2):\(M1)\(M2)"
}


print(solution(1,7,2,7))
print(solution(0,0,2,9))
print(solution(6,5,2,0))
print(solution(3,9,5,0))
print(solution(7,6,3,8))
print(solution(0,0,0,0))
print(solution(9,9,9,9))
print(solution(1,2,3,4))

 17:27
 20:09
 20:56
 09:53
 NOT POSSIBLE
 00:00
 NOT POSSIBLE
 23:41