Информация об изменениях

Сообщение Re[2]: Простая с виду задачка с подвохом от 21.09.2020 15:56

Изменено 21.09.2020 16:07 Lazytech

Re[2]: Простая с виду задачка с подвохом
Здравствуйте, dead0k, Вы писали:

D>R = 0, G = 1, B = 2.
D>Несложно заметить, что функция определения элемента следующего ряда f(Ci, Ci+1 ) = (0 — Ci — Ci+1) mod 3.
D>Тогда можно переработать алгоритм на целочисленную математику и получить ускорение на порядок-другой.

Переход на целочисленную математику действительно значительно ускорил код! По времени всё равно не уложился, но уже что-то.
  Еще одно решение 
function triangle(row) {
  const colors = 'RGB';  
  let a, b, ab;  
  let rowArr = row.split('').map( char => colors.indexOf(char) );
  
  for (let i = rowArr.length; i > 1; i--) {
    a = rowArr[0];
    
    for (let j = 1; j < i; j++) {
      b = rowArr[j];
      ab = ( 6 - a - b ) % 3;
      a = b;
      rowArr[j - 1] = ab;
    }
  }

  return colors[ rowArr[0] ];
}

Спасибо за подсказку.
Re[2]: Простая с виду задачка с подвохом
Здравствуйте, dead0k, Вы писали:

D>R = 0, G = 1, B = 2.
D>Несложно заметить, что функция определения элемента следующего ряда f(Ci, Ci+1 ) = (0 — Ci — Ci+1) mod 3.
D>Тогда можно переработать алгоритм на целочисленную математику и получить ускорение на порядок-другой.

Переход на целочисленную математику действительно значительно ускорил код! По моим грубым прикидкам, на пару-тройку порядков (самое быстрое из старых решений в лучшем случае проходило один тест со строкой средней длины, а новое решение прошло все сто таких тестов, плюс пару тестов со строками большой длины). По времени всё равно не уложился, но уже что-то.
  Еще одно решение 
function triangle(row) {
  const colors = 'RGB';  
  let a, b, ab;  
  let rowArr = row.split('').map( char => colors.indexOf(char) );
  
  for (let i = rowArr.length; i > 1; i--) {
    a = rowArr[0];
    
    for (let j = 1; j < i; j++) {
      b = rowArr[j];
      ab = ( 6 - a - b ) % 3;
      a = b;
      rowArr[j - 1] = ab;
    }
  }

  return colors[ rowArr[0] ];
}

Спасибо за подсказку.