Как вам такое решение задачки?

Question

[Александр Буки]

Данная задачка была на одном из собеседований в ай-ти компанию.
Свертка списка в диапазоны.
Дан список интов, повторяющихся элементов в списке нет.
Нужно преобразовать это множество в строку, сворачивая соседние по числовому ряду числа в диапазоны.
Примеры:
[1, 4, 5, 2, 3, 9, 8, 11, 0] => "0-5, 8-9, 11"
[1, 4, 3, 2] => "1-4"
[1, 4] => "1, 4"

Ниже мое решение, хочу понять насколько оно грамотное.

function range (arr) {
  arr.sort((a, b) => a - b)
  let str = arr[0]
  let iteration
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] + 1 === arr[i + 1]) {
      iteration = true
    } else {
      if (!iteration) {
        str += ',' + arr[i]
      } else {
        str += '-' + arr[i]
        if (arr[i + 1] + 1 === arr[i + 2]) {
          str += ',' + arr[i + 1]
        }
        iteration = false
      }
    }
  }
  return str
}

Comments

[dominus_augustus]

function package(initArr) {
  let str = "";
  let arr = [].concat(initArr).sort((a, b) => a-b)
  arr.forEach((curItem, i) => {
    if(i === 0) {
      str += curItem;
    }
    else {
      let prevItem = arr[i - 1];
      let nextItem = arr[i + 1];
      if(prevItem + 1 === curItem && nextItem - 1 !== curItem) {
        str += `-${curItem}`;
      }
      if(prevItem + 1 < curItem) {
        str += `, ${curItem}`;
      }
    }
    return
  })
  return str;
}

Answer 1

[Дмитрий]

Немного кривоватое на мой взгляд, я бы сделал так

const range = arr => arr
   .sort((a, b) => a - b)
   .reduce((agg, v) => {
      const currRange = agg[agg.length - 1]
      if (!currRange || v > currRange.last + 1) {
         agg.push({first: v, last: v})
      } else {
         currRange.last = v
      }
      return agg
   }, [])
   .map(v => v.first + (v.first !== v.last ? '-' + v.last : '')).join()

Answer 2

[0xD34F]

Что меня здесь бесит:

1. Мутирование переданного массива
   
2. Для массивов нулевой и единичной длины результат не строка
   
3. Многовато if'ов, слишком сложно
   

UPD. Ну и ещё результаты кривоваты. Посмотрите [ 1, 2 ], например. Или [ 5, 6, 8, 9 ].
Т.е., задача по сути не решена.

UPD. Варианты решения.

const range = ([...arr]) => arr
  .sort((a, b) => a - b)
  .reduce((acc, n, i, a) => (
    (n === a[i - 1] + 1) || acc.push([ n ]),
    acc[acc.length - 1][1] = n,
    acc
  ), [])
  .map(([ a, b ]) => a === b ? a : `${a}-${b}`)
  .join(', ');

const range = arr => ''.concat(...arr
  .slice()
  .sort((a, b) => a - b)
  .reduce((acc, n, i, a) => (
    n !== a[i - 1] + 1 && acc.push(i ? `, ${n}` : n),
    n === a[i - 1] + 1 && n !== a[i + 1] - 1 && acc.push(`-${n}`),
    acc
  ), [])
);

Comments

[Александр Буки]

Спасибо!

[Arris]

И `;` нету! Нуачо, не надо облегчать жизнь транслятору, он же умный, да?

[Stalker_RED]

Arris, ну да, специально ведь ASI прикрутили, чтоб пореже ставить эти ненужные закорючки.

[Arris]

Stalker_RED, на что только люди не пойдут, чтобы лень оправдать. Ведь нажать 1 кнопку это так сложнааааааааа!!!!!

P.S. Физиологически не воспринимаю код без ";"

[Stalker_RED]

Arris, наоборот, код без ";" выглядит чище.
Впрочем, все эти закорючки и отступы - вкусовщина. Можно прикрутить автоматический бьютифаер же, и прекратить страдать.

[Arris]

Stalker_RED, чище или понятнее?

Впрочем, да, цвет фломастеров.

Answer 3

[profesor08]

Твоя функция может вернуть строку, может вернуть число, а может вернуть undefined. Такое не должно происходить. Глянь ниже тестовые данные. Далее ты вручную строишь строки на основе массива, это сильно снижает читабельность кода, если не вникать то вообще не понятно что там происходит.

function range(array: number[]): string { 
  return array.sort(
    (a, b) => a - b
  ).reduce((acc, next, i) => {
    const prev = array[i - 1];

    if (prev !== undefined && next - prev === 1) {
      acc[acc.length - 1][1] = next;
    }
    else {
      acc.push([next]);
    }

    return acc;
  }, []).map(
    arr => arr.join("-")
  ).join(", ");
}

console.log(range([1, 4, 5, 2, 3, 9, 8, 11, 0])); // 0-5, 8-9, 11
console.log(range([1, 4, 3, 2])); // 1-4
console.log(range([1, 4])); // 1, 4
console.log(range([1])); // 1
console.log(range([])); // ""

Answer 4

[Сергей Соколов]

Предложу свой велосипед на костылях. Без сортировки!

const zip = arr => arr
  .reduce((agg, c) => {
    const iR = agg.indexOf(c + 1);
    const iL = agg.lastIndexOf(c - 1);
    if (!!~iR && !!~iL) agg.splice(iL, 2); // закрыли дырку
    else if (!!~iR) agg[iR] = c; // сдвинули границу
    else if (!!~iL) agg[iL] = c; // то же
    else { // вставляем сироту - найти позицию сразу после меньшего
      let pos = 0;
      while (pos < agg.length  &&  agg[pos] < c) pos++;
      agg.splice(pos, 0, c, c); // вставляем дважды
    }
    return agg;
  }, [])
  .reduce((agg, c, i, arr) => {
    if (!(i&1)) agg.push(arr[i+1] === c ? c : [c, arr[i+1]].join('-'));
    return agg;
  }, [])
  .join(', ')
;

Массив границ диапазонов, в нём всегда чётное число элементов.
Очередное число вставляем в массив: ищем, есть ли его ближайшие соседи слева и справа.

• Если есть оба, число закрывает «дырку», надо просто убрать этих двух соседей.
  
• Если нашёлся только один – заменяем его собой, сдвигая границу.
  
• Если ни одного соседа, значит, число пока сирота, вставляем его дважды,
  как будто это и левая и правая граница диапазона.
  

Так из первого примера получается [ 0, 5, 8, 9, 11, 11 ]
Остаётся форматирование. Смотрим только чётные элементы. Если текущий и следующий элементы равны, это «одинокое» число. Если не равны — это диапазон через дефис. И склеиваем через запятую-с-пробелом.

Учитывая сортированность собираемого массива, можно ускорить, заменив indexOf() и lastIndexOf() на самописный поиск, останавливающийся на элементе, бОльшем или меньшем искомого.

Fiddle с тестами

Comments

[Егор]

Красивая разминка для ума. Но если взвесить. На одной стороне весов асимптотическая сложность (да и просто сложность), а на другой простая, быстрая, понятная сортировка и один проход по массиву. Очевидно что лучше выбрать второе.

[Сергей Соколов]

Егор, именно разминка. За что и люблю Тостер QnA.

Answer 5

[Flying]

Можно воспользоваться тем фактом что в JavaScript в reduce()передаётся текущий индекс и сам массив, это позволяет упростить backreference. В итоге у меня получилось нечто подобное:

/**
 * @param {Array} list
 * @return {string}
 */
const range = list => list
    .sort((a,b) => a - b)
    .reduce((r, v, i, a) => {
        if (i > 0 &&  v - a[i - 1] === 1) {
            let l = r.pop();
            l.push(v);
            r.push(l);
        } else {
            r.push([v]);
        }
        return r;
    }, [])
    .map(v => v.length > 1 ? `${v.shift()}-${v.pop()}` : v)
    .join(', ');

Кусок с pop/push можно ускорить за счёт усложнения обращения к массивам, но так код получается выразительнее.

Отдельное спасибо Дмитрий за .sort((a,b) => a - b) - не знал

Comments

[Дмитрий]

Чтобы не жертвовать скоростью в угоду выразительности просто сделайте функцию last

const last = arr => arr[arr.length - 1];

const range = list => list
    .sort((a,b) => a - b)
    .reduce((r, v, i, a) => (i > 0 &&  v - a[i - 1] === 1 && last(r).push(v) || r.push([v])) && r, [])
    .map(v => v.length > 1 ? `${v[0]}-${last(v)}` : v)
    .toString()

[Flying]

Дмитрий, Можно конечно, но задачи оптимизации вроде не ставилось, писал на скорую руку.

[Дмитрий]

Flying, Такие вещи глупо писать даже на скорую руку

let l = r.pop();
l.push(v);
r.push(l);

`${v.shift()}-${v.pop()}`

shift и pop изменяют существующий массив, как вы сами догадываетесь. Просто не используйте их для обращения к первому и последнему элементу без необходимости изменять массив, тогда нечего будет оптимизировать

[Flying]

Дмитрий, Согласен с вами, хотя в случае преобразования в строку мутация массива уже не выглядит проблемной, он всё равно прекращает существование на этой стадии.

[Дмитрий]

Flying, Трата ресурсов плюс кривизна кода

Answer 6

[Егор]

Вопрос автору, где такие задачи задают?
Мой код, решение универсальное работает с повторениями. По классике

function range (a) {
    if (a.length < 2) return a
    a.sort( (a, b) => a-b )
    let pred = null
    let e = false
    let result = ''
    for (let i of a) {    
        if (pred === null) {  
            result = pred = i
            continue
        }
        if (i != pred+1 )  {
            e ? result += '-' + pred + ', ' + i : result += ', ' + i
            e = false
        } else e = true
        pred = i
    }
if (e) result += '-' + pred 
return result
}

console.log(range([1, 4, 5,  2, 3, 9, 8, 11, 0]))
console.log(range([1, 4, 3, 2]))
console.log(range([1, 4, 8]))

Или так

function range (a) {
    a.sort( (a, b) => a-b )
    a = [...a,'']
    return a.reduce((st, item, i, arr) => i==0 ? st += item : ( item != arr[i-1]+1  ) ? st += '-' + arr[i-1] + ', ' + item :  st = st, '')
            .split(',')
            .map((item) => (eval(item) == 0 ? item.slice(0, item.indexOf('-')) : item).trim())
            .slice(0, -1)
            .join(', ')
  
}

console.log(range([1, 4, 5,  2, 3, 9, 8, 11, 0]))
console.log(range([1, 4, 3, 2]))
console.log(range([1, 4, 8]))

И для полной идиоматичности сделаем так

const range = a => [...a.sort( (a, b) => a-b ),''].reduce((st, item, i, arr) => i==0 ? st += item : ( item != arr[i-1]+1  ) ? st += '-' + arr[i-1] + ', ' + item :  st = st, '')
                                                  .split(',')
                                                  .map((item) => (eval(item) == 0 ? item.slice(0, item.indexOf('-')) : item).trim())
                                                  .slice(0, -1)
                                                  .join(', ')

console.log(range([1, 4, 5,  2, 3, 9, 8, 11, 0]))
console.log(range([1, 4, 3, 2]))
console.log(range([1, 4, 8]))

Comments

[Александр Буки]

в Яндексе давали. Есть еще, позже буду выкладывать.
Вы в Яндекс чемпионате последнем не участвовали?

[Егор]

Участвовал, но бросил посчитав затраты времени. Вот задача аналогичная вашей https://www.codewars.com/kata/51ba717bb08c1cd60f00002f. Поискав понял что уже делал её пару лет назад. Для таких задач тесты рулят. Моё решение выше (функциональное) не полное, не будут учитываться отрицательные числа. Дописанное:

const solution = a => [...a.sort( (a, b) => a-b ),''].reduce((st, item, i, arr) => i==0 ?  st += item : ( item != arr[i-1]+1 ) ? st += ' - ' + arr[i-1] + ', ' + item :  st = st, '')
                                                       .split(',')
                                                       .map((item) => (eval(item) == 0 ? item.slice(0, item.indexOf(' - ')) : eval(item) == -1 ? item.replace(' - ',',') : item).trim())
                                                       .slice(0, -1)
                                                       .join(', ')
                                                       .replace(/\s/g,'')

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

function solution(nums){
 nums = nums.map((v, i) => nums[i - 1] == v - 1 && nums[i + 1] == v + 1 ? '-' : v);
    return nums.filter((v, i) => v != '-' || nums[i - 1] != '-').join(',').replace(/,-,/g, '-');
}

[Александр Буки]

Егор, не помните какая у вас задача A была?
Случайно не эта Что нужно сделать в задаче? Что значит выпирающие точки?
Уже несколько дней не могу дойти до полного решения

Answer 7

[Rsa97]

Как минимум ошибка в том, что arr[i+1] и arr[i+2] будут неопределёнными на последних итерациях цикла.

Comments

[Александр Буки]

Rsa97, разве мы туда попадем на последних итерациях?

[Шохрух Шаймардонов]

Александр Буки, разве нет?

for (let i = 1; i < arr.length; i++)

[Александр Буки]

Шохрух Шаймардонов, в это условие мы все равно не попадем, будет undefined1 и undefined, можно конечно доп проверку поставить, что они в целом определены

if (arr[i + 1] + 1 === arr[i + 2]) {
str += ',' + arr[i + 1]
}

[Шохрух Шаймардонов]

Александр Буки, ну раз не попадет, то мб тогда лучше сразу сделать цикл до arr.length - 2? Чтобы не было никаких эксепшнов и андефайнд

[Александр Буки]

Шохрух Шаймардонов, тогда совсем все развалится)

[Шохрух Шаймардонов]

Александр Буки, значит решение не лучшее) кстати. Вам бы еще валидацию аргументов сделать)

[profesor08]

Шохрух Шаймардонов, зачем пропускать две итерации? Тут все итерации нужны.

Для валидации аргументов есть typescript.
Проводить ее на уровне одной фунции нет смысла, нужна некая фабрика, которая будет заниматься валидацией аргументов для функций.

Answer 8

[Андрей]

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

const rangeIt = data => {
  const a = [...data].sort((a, b) => a-b), r = [[a[0], a[0]]];
  for (i = 1; i < a.length; i++) {
    if (r[r.length - 1][1] + 1 === a[i]) {
      r[r.length - 1][1] = a[i];
    } else {
      r.push([a[i], a[i]]);
    }
  }
  return r.map(rr => rr[0] === rr[1] ? rr[0] : rr.join('-')).join(', ');
}

вот как-то так :)

const rangeIt = data => {
  const a = [...data].sort((a, b) => a - b), r = [[a[0], a[0]]];
  const calcRanges = (n, i) => {
    if (!i) return;
    if (r[r.length - 1][1] + 1 === n) {
      r[r.length - 1][1] = n;
    } else {
      r.push([n, n]);
    }
  };
  a.forEach(calcRanges);
  return r.map(rr => rr[0] === rr[1] ? rr[0] : rr.join('-')).join(', ');
}

или так

Answer 9

[BENGE]

dart
https://replit.com/@Bakhbk/sviertka-spiska-v-diapa...