Comments 103
Такая функция пишется за 15 минут с помощью гугла и stackoverflow. Если у вас, конечно, не яндекс и не оракл, где движок состоит из подобных функций и разница в одну микросекунду играет огромную роль.
Но зачем? Разве это типичная бизнес-задача?
Как мне показалось интервьер больше смотрел как я от первой идеи пришел к какому-то решению, которое он ожидал увидеть.
Так что подобный навык может пригодиться, по крайней мере в начале пути разработчика =)
Я работаю программистом уже 5 лет. Мне ни разу не приходилось писать программу карандашом на бумаге. Даже на доске как-то не пришлось.
Да более того, я каждый раз забываю порядок параметров в библиотечных функциях, даже таких базовых как memcpy. Не помню ни разу, чтобы хоть кто-то был как-то сильно недоволен кодом, который я пишу.
Отсюда я делаю вывод — навык писать код без Гугла — абсолютно бесполезный
А мне иногда приходится, больше, конечно, псевдо-код, но объяснить некоторым коллегам проще именно на вайтборде.
Да, конечно, без точного совпадение типов параметров и прочей справочной информации.
Но, как минимум, понимая что такое map, flatMap, fold, forEach, Either и т.п. базовые вещи.
Код, а точнее даже каркас, получается строк 10-15 — многим людям так гораздо удобнее воспринимать и нет психологического давления как сидя за компом в ИДЕ.
Такие дела.
На доске в 99% нарисовать блок-схемоподобные кубики быстрее и удобнее, недели изображать псевдокод. Не помню ни одного случая где Either был бы понятнее ромбика с if)
Понятное дело, что знать эти вещи очень полезно, т.к. они описывают довольно мощные концепции, но я бы рекомендовал для них синтаксис Haskell, а не убогий для этих вещей императивный JS.
Either удобнее, т.к. люди видят знакомое, а не ромбики. Не все знают UML, к сожалению, такоей вот мир.
Я тоже не знаю UML :D Ну, не совсем уж не знаю, но никогда его не использовал для доски) Кубик — это просто квадраты, стрелочки — направления передачи данных, остальное на словах)
И я не видел людей, способных понять Either и не способных понять UML)
Есть тип людей такой, им проще псевдокод написать на доске, чем разбираться в квадратиках. Такой вот склад ума, может, возраст.
Ну, это точно не повод продолжать такую традицию на собеседовании)
Я не согласен с данной трактовкой. Относительно традиций на собеседовании — разговор другой, но я могу понять условного инженера из Гугла/Майкрософта, которому надо на собеседовании предоставить код на бумажке/доске.
И они, иногда, таки ждут понимания что такое Either, Option и прочих filter, zip, apply и товарищей.
Проблема не в том, что он меня ждут понимания, а в том, что на собеседованиях в Яндекс/Гугл и прочих сидят чуваки, которые вкусовщину выдают за нечто невероятно важно и что если я вдруг не знаю каких-то методов из стандартной библиотеки Android, то всё — я плохой программист :)
Знать концепии нужно. Можно даже на собесе попросить объянсить эти концепции и в чём их плюсы перед теми же исключениями. Можно даже дать человеку какой-то уже готовый императивный код и попросить его переписать через эти концепции, почему бы и нет.
Но вот давать человеку задачу, а потом забраковать его только за то, что он решил её императивно, а не стильно, модно, молодежно (и очень медленно работающе, к слову), например потому что банально забыл порядок параметров в методе fold, а гугла нет — это как-то перебор.
Человек решает задачу без библиотек, чисто средствами языка.
И я не думаю, что его забракуют за порядок в fold (хотя там перепутать странно и сразу возникают вопросы о общем понимании), но за каскад «if/else if/else» вместо условного when и «закат солнца вручную» вместо условных filterIndexed/zipWithNext точно плюсов в оценку не добавят.
Точно так же как и про нехвостовую рекурсию в императивном решении.
Как-то, в принципе, оно работает но надо же продемонстрировать, что ты понимаешь о чем речь.
Ты же не будешь в гугл сразу лезть или на SO при каких-то вопросах на ревью.
Я и по более тупым вопросам хожу в документацию частенько :) Для меня важно лишь чтобы человек корректно решил задачу и не сделал мне кубической сложности в решении. Остальное — супер вторично и лечится нормальным стайл гайдом и ревью кода. Тем более что все вещи учатся за 1 день. Ну, вот не верю я, что человек не сможет понять эти fold, map, filter и прочее, даже если никогда о них не слышал, но при этом отлично справляется обычными методами.
Но вот давать человеку задачу, а потом забраковать его только за то, что он решил её императивно, а не стильно, модно, молодежно (и очень медленно работающе, к слову), например потому что банально забыл порядок параметров в методе fold, а гугла нет — это как-то перебор.
А это уже ваши додумки. В том же расте итераторы быстрее ручных циклов так-то.
И это единственный язык в котором это так :) И то, только лишь потому, что проверяется каждый раз индекс в массиве. Перепишите любой итератор на unsafe цикл и внезапно получите код быстрее итератора или примерно такой же)
Я переписывал в сишарпе с foreach по массиву на unsafe арифметику на указателях, и получил замедление. Тоже случай был.
unsafe в rust и unsafe в С# вещи совершенно несравнимые) К тому же, если уж и пытаться сравнить, то корректным аналогом итератора из C's будет dyn Iterator (который Trait Object). И он точно работает не быстрее обычного прохода по циклу)
очень смелое заявление, но проверять его я, конечно, не буду
В плохом сценарии, когда все интервалы — тривиальные, ваш код будет делать по аллокации на каждый входной символ и работать на порядки медленнее «хардкорного» варианта.
Читабельность — это прекрасно, но не такой ценой.
Глупый вопрос — а было входное условие что массив будет отсортирован? не увидел у вас в описании задачаи
иии эта задача в таком виде начинает занимать O(n), где n — количество интервалов.
предполагаю, что задача оценивала в том числе способность к reduce с O(1), где на лету добавляются символы к строке.
К тому же — читаемость это спорный вопрос. Читать тридцать строк там, где можно примерно понять, что происходит всего за одну — то еще удовольствие.
код, который будет предельно понятен хаскеллисту, сломает мозг ООП-разработчику. сишника не поймет гофер. JS-ник сойдет с ума от современного C++.
читаемость относительна и контекстна.
И да, бывает.
Попробовал тоже набросать решение. 11 строк против 45, разница не в 30 раз, но 4x — тоже неплохой результат. и на мой вкус — мой вариант ощутимо более читаемый и понятный.
getRanges = ([head, ...tail], prefixFn = s => s) => {
let tip = head;
const toStr = () => prefixFn(head === tip ? `${head}` : `${head}-${tip}`);
while (tail.length > 0) {
if (tail[0] - tip !== 1) {
return getRanges(tail, s => `${toStr()},${s}`)
}
tip = tail.shift();
}
return toStr();
}
Хочу добавить, что TCO в v8 уже нет и неизвестно, когда появится обратно.
Многие помнят, что ее добавили, но меньше знают, что выпилили. :-)
А ничего что входные данные уже занимали по памяти O(n), так что асимптотическая оценка занимаемой памяти не увеличилась, но зато код стал более читаемым, что в больших проектах является критическим. В читаемом коде гораздо меньше вероятность ошибиться и проще найти ошибку, если все же ошибка закралась. Например упоминаемой статье автор решил задачу в "две строки", но при этом допустил ошибку, со стороны выглядит как "запутался в трёх соснах".
Вы видимо не достаточно встречали по-настоящему читаемый код и от ЯП читаемость мало не зависит. Читаемый код читается почти как обычный текст, вначале идут высокоуровневые функции и абстракции, которые затем конкретизируются более низкоуровневыми абстракциями и т.д. Программист впервые увидев такой код, быстро сориентируется что делается в этом участке кода, вплоть до самых низко уровневых операций, двигаясь от общего к деталям.
Я видел по-настоящему читаемый код на большом количестве языков и парадигм, и он был очень разным.
Более того, я в какой-то момент занимался именно вопросами влияния код-стайла на эффективность команд.
Любой текст, в том числе код, имеет когнитивную сложность.
Когда мы начинаем оперировать интерфейсами, которые завязаны на доменную область (не внешние библиотеки), мы все больше и больше растим количество сущностей, которые удерживаем в собственной — не железной, а мясной — оперативной памяти.
Если мы пишем код, в который будут редко приходить и изменять, но могут натыкаться в процессе работы — правильно будет написать эффективный код, покрыть его тестами и забыть. Просто чтобы каждый раз, когда люди доходят до него — они смотрели, думали "вроде он делает это, дальше ковырять не буду" и уходили.
Если мы пишем код, который часто меняется — например, бизнес-логика — он, конечно, должен быть выразительным и оперировать представлениями бизнес-сущностей в коде в ущерб количеству строк, избыточности и перформансу.
let out : String = "";
for (let i = 0; i < intervals.length; i++) {
out += intervals[i].toString(arr);
if (i < intervals.length - 1) {
out += ',';
}
}
Отличная реализация .join(",").
К сожалению, этот пост уже не доступенТак вот же он: habr.com/ru/post/470407
Если исходить из поста про собеседование, то, как по мне, там важнее всего понимать и упомянуть про сложность алгоритма и показать интервьюеру своё мышление.
Задача решается формированием строки результата в один проход циклом по заданному массиву. Больше ничего не нужно писать.
Я считаю, что класс является лишней сущностью. Вообще мое решение было бы таким:
function* generateRanges(numbers: number[]) {
let start = numbers.shift();
let end = start;
const format = (s, e) => s === e ? `${s}` : `${s}-${e}`;
for (const i of numbers) {
if (i !== end + 1) {
yield format(start, end);
start = end = i;
} else {
end = i;
}
}
yield format(start, end);
}
function getRanges(numbers: number[]) {
return [...generateRanges(numbers)].join(',');
}
А так же добавил бы, что при необходимости для большого набора чисел или если они будут идти в потоке, то данный код можно было бы легко оптимизировать избавившись от массива с join()
function getRanges(numbers: number[]) {
let result = "";
for (const range of generateRanges(numbers)) {
result += result === "" ? `${range}`: `,${range}`;
}
return result;
}
Можно и так:
function getRanges(items: number[]): string {
let results: {start: number, end: number}[] = [];
let index=-1;
for (let item of items) {
if (index < 0 || item > results[index].end+1) {
results.push({start: item, end: item});
index++;
} else {
results[index].end = item;
}
}
return results.map(item => item.end > item.start ? item.start+"-"+item.end : item.start).join(",");
}
Можно даже обойтись без массива интервалов и сразу аккумулировать результат, храня лишь данные последнего интервала.
Идея генератора была как раз в том, что бы при желании можно было генерировать данные с константным потреблением памяти для любого размера входящих данных, хоть для терабайта.
Вот если избавится от массива, тогда да, уже интереснее будет.
Продолжаю тренироваться в хаскелле.
Там выглядит вот так:
getRanges :: [Int] -> [(Int, Int)]
getRanges = foldr go ([])
where
go x [] = [(x, x)]
go x t@((l, r):as)
| l - x == 1 = ((x, r) : as)
| otherwise = (x, x) : t
main :: IO ()
main = print $ getRanges [0, 1, 2, 3, 4, 7, 8, 10]
Грустно, что в комментариях много людей старается сразу и объединить интервалы, и вывести на печать. Ведь это совсем разные операции, и лучше их делать по-очереди...
Подумал, что две ветки можно объединить:
getRanges :: [Int] -> [(Int, Int)]
getRanges = foldr go ([])
where
go x t = case t of
((l, r):as) | l - x == 1 -> ((x, r) : as)
_ -> (x, x) : t
main :: IO ()
main = print $ getRanges [0, 1, 2, 3, 4, 7, 8, 10]
Ну я foldr использовал потому что мы матчим по голове списка. Поэтому нужно идти справа налево. По крайней мере в моей голове это так работает.
Ну и можно сразу паттерн-матчить и гард писать без case.
Ну я не настоящий хаскеллист, а только учусь :) Но насколько я понял, это требует установки расширений.
Потом я потратил минуты три, чтобы попытаться выразить нужную семантику через левую свёртку (ибо explicit recursion is the goto of functional programming),
Ну я не стал оптимизировать, потому что через правую свертку естественно выражается. То что можно руками все развернуть и получить красиво ну так это понятно, это же почти что ручные циклы, только в TCO стиле написанные.
Потом один очень упоротый и прошаренный хаскелист предложил однострочник, который можно оставить в качестве упражнения для читателя:
Упражнение сомнительное, потому что мало того что оно такое себе по читаемости, так с моим прелюдом оно даже не компилируется. В частности что за оператор &&&
я не знаю. И мой компилятор не знает.
Там потом, кстати, оказалось, что если взять ваше решение и немного его переписать (чтобы в next оказывался второй элемент пары, а не вся пара, и для разбора того, что вы приconsили, не нужно было вычислять весь case), то ваш foldr тоже оказывается константным по памяти
Я слова вроде понял, а смысл в них вложенный — не очень.
f (x:xs) = (x, x + s) : f (drop s xs) where s = length (takeWhile (\y -> y == -1) (zipWith (-) (x:xs) xs))
Дядюшка Боб писал, что код должен читаться легко как проза, не заставляя подолгу вдумываться и гадать, что автор кода здесь имел ввиду. В таком коде и намного меньше вероятность совершить ошибку, что является критичным в больших проектах.
Хотел бы оставить пример, какой код меня удовлетворил бы, доводись мне как лиду задать такую задачу на собеседовании
function getRanges(input) {
const intervals = [[]]
input.forEach(item => {
const last = intervals[intervals.length - 1]
if (last.length === 0 || last[last.length - 1] === item - 1) {
last.push(item)
} else {
intervals.push([item])
}
})
const result = intervals.map(arr => {
return arr.length == 1 ? arr[0] : `${arr[0]}-${arr[arr.length - 1]}`
})
return result.join(',')
}
разделение расчёта и форматирования
адекватное название переменных
без откровенных хаков
без лишних тяжелых абстракций, типа класса для интервала из поста или генераторов из соседнего комментария
function getRanges(arr){
return arr.reduce((m,n)=>{
let range = m[m.length - 1] || [];
if(range[range.length - 1] + 1 === n){
range.push(n);
}else{
m[m.length - 1] = range.length > 1 ? [range[0], range[range.length-1]].join('-') : range[0];
m.push([n]);
}
return m;
}, [])
.join(',')
}
join — это, строго говоря, второй проход :-)
Если у вас правильный язык (или распоследний ES), то итераторы будут ленивыми и reduce() начнет выполняться только при вызове join, проходя каждый элемент ровно по одному разу.
Мммм, в случае с join, который по определению пройдет весь массив, разницы, в общем-то, и нет, кроме аллокаций — которые вряд ли соптимизируются. Но сразу пытаться строить строку — это сразу угробить читабельность и усложнить изменение выходного формата, потому тут даже и не стоит пытаться без крайней нужды.
Да не обязательно сразу строить строку. У вас же пайплайн проходится за раз. Когда вы вызываете join он берет чоередной элемент из последовательности. Тот в свою очередь вызывает получение интервала. Тот в свою очередь дергает массив и начинаем собирать интервал. Когда первый интервал набран он его отдает как элемент, который передается в джоин, который делает из него первый элемент. После чего он рисует запятую, дергает следующий элемент, и все повторяется.
В итоге в каждый момент времени у вас только пара чисел (begin, end) и растущая строчка с результатом.
И что, какой-то там v8, который даже оптимизацию хвостовой рекурсии не осилил, может сделать такую оптимизацию приведенного кода? Не верю!
Про правильные языки понятно, вопрос не в них :-)
Ну я не про оптимизации, а про то, что так можно руками написать, см. https://fitzgen.github.io/wu.js/
Что-то говорит мне что reduce возвращает не генератор, а массив. А значит join будет делать проход по массиву.
Ну я же выше скинул. Если использовать правильный reduce, то не будет: https://fitzgen.github.io/wu.js/#reduce
Ну вот за минут 7-8 получилось так:
const getRanges = arr =>
arr.reduce(
(intervals, value) => {
const currentInterval = intervals.length && intervals[intervals.length - 1];
if (currentInterval && (currentInterval.length === 1 || value - currentInterval[1] === 1)) {
currentInterval[1] = value;
} else {
intervals.push([value]);
}
return intervals;
},
[]
).reduce(
(formattedString, interval, index) =>
formattedString + (index ? ',' : '') + interval.join('-'),
''
);
Кажется .reduce и ко очень плохо ложатся на такие задачи. Код получается довольно путанным и не очевидным (хотя и рабочим). Т.е. в нём вполне можно разобраться, но когнитивная нагрузка раза в 3-4 выше, чем в случае императивного подхода. ИМХО.
Вопрос привычки, наверное. Я все эти map-reduce-ы легко воспринимаю, хотя по функциональщине особо не упарываюсь. Мне stateful подход с императивщиной больше когнитивной нагрузки создает, особенно в нетривиальных случах, когда за всеми переменными еще следить надо.
Хотя, возможно, я просто привык ко всяким redux-ам с rxjs. Но порог вхождения в них особо сложным не был, насколько помню.
Нет, имхо, это совсем не вопрос привычки. Тут код объективно сложнее. Сравните его с тем, что я предложил. Я тоже в работе куда чаще использую map, reduce, _.transform и прочую артиллерию многие годы (правда из lodash а не из rxjs). Но многие вещи пишутся в императивном стиле гораздо проще, чем я не стесняюсь пользоваться. Я бы даже сказал читаются очевиднее.
Согласен, но разве это тот случай? Посмотрите
getRanges = foldr go ([])
where
go x [] = [(x, x)]
go x t@((l, r):as)
| l - x == 1 = ((x, r) : as)
| otherwise = (x, x) : t
Буквально следующее:
сделай свертку входной коллекции таким образом, что
- если аккумулятор пустой, создай интервал из одного значения (x,x)
- если аккумулятор непустой, пусть t — это наш текущий аккумулятор, который состоит из
l
— левой части головы.r
— правой части головы, иas
— хвоста. Тогда если l — x == 1 то расширь новый интервал, вернув в качестве результата (x,r). Иначе создай новый интервал из одного текущего элемента, а весь текущий аккумулятор сделай хвостом нового.
На примере getRanges([2, 3, 8, 9]);
- Берем элемент 9. У нас аккумулятор пустой, идем по первому правилу. Acc = [(9, 9)]
- Берем элемент 8. Берем голову аккумулятора, l = 9, r = 9, as = []. 9 — 8 == 1, значит идем по первой ветке. Acc = [(8, 9)].
- Берем элемент 3. Берем голову аккумулятора, l = 8, r = 9, as = []. 8 — 3 == 1 — ложь, идем по второй ветке. Acc = [(3,3), (8, 9)]
- Берем элемент 2. Берем голову аккумулятора, l = 3, r = 3, as = [(8, 9)]. 3 — 2 == 1, значит идем по первой ветке. Acc = [(2,3), (8, 9)].
- Элементы кончились. Результат
[(2,3), (8, 9)]
.
И хотя я расписал наверное очень страшно и много текста, по сути тут ничего особо и не происходит. Это проще императивного цикла потому что мы в фолде работаем только с аккумулятором и текущим значением, задачи итерирования и всего прочего берет на себя фолд. А работать с двумя значениями имхо проще, чем с циклом.
Ага, pattern matching сильно упрощает дело. Читается много лучше вереницы if-then-else-&&-whatever. Но к синтаксису Haskell надо привыкать, без вашего объяснения для меня этот код совершенно не понятен (все эти :as, @, foldr, go...).
В общем да, согласен, в такой записи функциональный подход выглядит хорошо.
foldr go []
— это вызов библиотечной функции foldr (правая свертка, по сути жсовый reduce) с двумя параметрами: функцией go в качестве функции свертки и [] в качестве начального значения аккумулятора. Дальше просто идет определение go
. Просто объявление локальной функции и сразу её использование. Получается чуть удобнее, нежели прям инлайн лямбдой фигачить.
t@(a,b)
— это синтаксис для паттерн матчинга. В других языках такой же используется. Если вспомнить что @ переводится как "at" то это достаточно логично. Тогда справа вы указываете паттерн, а слева имя всего паттерна. Полезно, когда нам нужно заглянуть внутрь паттерна, но хочется иметь его на руках целиком, как раз наш случай.
что до :as
— то это тоже часть паттерн матчинга, оператор :
это конструктор списка. a : as
означает "список из а в качестве головы и as в качестве хваоста". Соответственно x:xs
означет "сматч голову списка в x
а хвост в xs
. Я просто переменную назвал as
чтобы показать, что это список уже обработанных элементов. Можно назвать как-то по-другому, просто такая традиция именования, как i/j/k для переменных цикла.
Поэтому t@(head:tail)
означает "попробуй разбить список на голову и хвост. Если получилось, сохрани голову в переменную head, хвост в tail, а всю конструкцию — в t.
Теперь понимаем, что нам нужно заглянуть в содержимое головы, чтобы понять, клеить к текущему интервалу или создавать новый. Нет ничего проще — просто заменяем head
на (left,right)
, чтобы он сматчил соответствующие значения тапла. Так и получаем t@((left, right):tail)
.
Вопрос сноровки :) Когда начинаете пользоваться оказывается очень удобно и ёмко. Я только начал хаскель изучать, по результатам небольшой словарик для программистов на обычных ЯП организовался (см. второй раздел). Можете почитать, если интересно, синтаксис на самом деле очень краткий, но точный.
Мне оба одинаково понятны. :)
Для меня восприятие базавой функциональщины очень-очень сильно зависит от языка и библиотек. "Объектные" msp/reduce/filter типа array.filter().reduce() воспринимаются куда проще "функциональных" reduce(filter(array)), анонимные функции с ключевым словом проще чем со стрелочным, всякие compose/pipe делают код совсем нечитаемым даже в простейших случаях, а пошаговую отладку практически невозможной.
const getRanges = (array: number[]): string => {
let result = "";
for (let i = 0; i < array.length; i++) {
result += array[i];
let rangeLength = 1;
while (array[i] + rangeLength === array[i + rangeLength]) {
rangeLength++;
}
if (rangeLength > 1) {
result += `-${array[i + --rangeLength]}`;
i += rangeLength;
}
result += ",";
}
return result.slice(0, -1);
};
К сожалению, этот пост уже не доступен, и приведенное решение я сейчас не восстановлю.
Кстати, вот то решение «в духе Яндекса»:
const getRanges = arr => arr.reduceRight((r, e) => r.length ? (r[0][0] === e + 1 ? r[0].unshift(e) : r.unshift([e])) && r : [[e]], []).map(a => a.join('-')).join(',')
function renderInterval({ from, to }) {
return to === from ? from : `${from}-${to}`;
}
function getRanges(sourceArr) {
if (!sourceArr.length) return '';
// predefined first interval
let lastInterval = { from: sourceArr[0], to: sourceArr[0] };
const result = [lastInterval];
for(let idx = 1; idx < sourceArr.length; ++ idx) {
const n1 = sourceArr[idx - 1];
const n2 = sourceArr[idx];
if (n2 !== n1 + 1) {
// close the previous interval and start a new one
lastInterval = { from: n2, to: n2 };
result.push(lastInterval);
} else {
lastInterval.to = n2; // amend right edge
}
}
return result.map(renderInterval).join(',');
};
А вот так достаточно простой и понятный код? Не совсем понятно зачем автор сделал целый класс ради ручной имплементации .join('-')
.
P.s. Уверен, можно было бы и лучше написать, но скопировал напрямую с Яндекс.Контест (где я решал)
/**
* Дан список целых чисел, повторяющихся элементов в списке нет.
* Нужно преобразовать это множество в строку,
* сворачивая соседние по числовому ряду числа в диапазоны.
*/
compress([1, 4, 5, 2, 3, 9, 8, 11, 0]) // '0-5,8-9,11'
compress([1, 4, 3, 2]) // '1-4'
compress([1, 4]) // '1,4'
// 0 1 2 3 4 5 8 9 11
function compress(list) {
const sortedArr = list.sort((a,b)=>a>b?1:-1);
const result = [];
let position = 0;
for (let i=1; i<=sortedArr.length; ++i){
if (sortedArr[i]-i+position!==sortedArr[position]){
if (sortedArr[i-1] === sortedArr[position]){
result.push(sortedArr[position].toString());
} else {
result.push(sortedArr[position] + '-' + sortedArr[i-1]);
}
position = i;
}
}
return result.join(',');
}
Небольшое уточнение по стандартной JS библиотеке (Array.prototype.sort):
const a = [3, 2, 1];
const b = a.sort();
console.log(a); // [1, 2, 3] Ooops
Это JS, тут нельзя просто a.sort()
. Тут надо так: const b=a.slice().sort((l,r)=>l-r)
, если вы не хотите изменить a
и получить в b
отсортированный массив.
Сделайте в консоли [1, 11, 2].sort()
и посмотрите что получится.
Вы комментарием не ошиблись? :) Я то как раз в курсе.
Вы правы. Я ошибся. Я супер невнимателен.
Чтобы исправиться, следует мой комментарий считать дополнением к Вашему, а не якобы опровергающем его.
Дополнение касается не просто того, что базовый массив меняется, но и к тому что перед сортировкой данные приводятся к строкам.
Вы правы, можно было копирнуть массив или работать уже с тем что получил (Копирование массива тоже имеет цену). Каюсь, не подумал. Хотя все равно ничего страшного, в переменную будет присвоена ссылка, мир не разрушится.
Повторюсь. Ибо код писал в Яндекс код (извиняюсь, в первом комменте написал Яндекс.Контест, хз чем отличается)
А значит, у меня не было ни дебаггера, ни возможности его проверить. Да и вообще, это вне зоны комфорта.
P.s. да, мне не нравится подход: «писать на листочке».
Так что, думаю, на такие вещи можно глаза закрыть :)
Пруф:
А зачем вы вообще сортируете? Сортировку лучше потребовать как предусловие алгоритма, если в задаче явно не сказано иного. Тот же бинарный поиск ничего не сортирует, подсунули бяку — сами виноваты.
package main
import (
"fmt"
"strconv"
"strings"
)
type Period struct {
start *int
end *int
}
func (period *Period) AddStart(start int) {
period.start = &start
}
func (period *Period) AddEnd(end int) {
period.end = &end
}
func (period *Period) ToString() string {
if period.start == nil {
return strconv.Itoa(*period.end)
}
if period.end == nil {
return strconv.Itoa(*period.start)
}
return strconv.Itoa(*period.start) + "-" + strconv.Itoa(*period.end)
}
type Language struct {
Periods []Period
}
func (language *Language) ToString() string {
out := []string{}
for _, token := range (*language).Periods {
out = append(out, token.ToString())
}
return strings.Join(out, ",")
}
func main() {
arr := []int{1, 2, 3, -1, 10, 11, 12, 4, 5, 6, 12, 13, -1, -2, -1, 0}
str := GetRanges(arr)
fmt.Print(str)
}
func GetRanges(arr []int) string {
language := Tokenize(arr)
return language.ToString()
}
func Tokenize(arr []int) (tokens Language) {
lexema := &Period{}
for index, item := range arr {
switch true {
case index == 0:
lexema.AddStart(item)
break
case index == len(arr)-1:
lexema.AddEnd(item)
tokens.Periods = append(tokens.Periods, *lexema)
break
case item+1 != arr[index+1]:
lexema.AddEnd(item)
tokens.Periods = append(tokens.Periods, *lexema)
lexema = &Period{}
break
case item+1 == arr[index+1] && lexema.start == nil:
lexema.AddStart(item)
break
}
}
return
}
g x = foldl f [(head x, head x)] (tail x) where f ((a,b):xs) c = if b + 1 == c then (a,c):xs else (c,c):(a,b):xs
def get_ranges(inp):
if len(inp) == 0: return ""
out = ""
i = s = e = 0
while i < len(inp):
i += 1
if i != len(inp) and inp[e] + 1 == inp[i]:
e = i
continue
out = ("{}{}," if s == e else "{}{}-{},").format(out, inp[s], inp[e])
s = e = i
return out[:-1]
create function dbo.get_ranges()
returns varchar(max)
as
begin
return
stuff(
(select ',' + cast(i1.item as varchar) + isnull('-' + cast(
(select min(i2.item)
from items i2
where not exists(select * from items where item=i2.item+1) and i2.item>i1.item) as varchar),'')
from items i1
where not exists(select * from items where item=i1.item-1)
for xml path(''),type).value('.','varchar(max)'),
1, 1, '')
end
go
create table items (item int)
insert into items (item) select 0 union select 1 union select 2 union select 3 union select 4 union select 7 union select 8 union select 10
select dbo.get_ranges()
partitionByCond :: Ord a => (a -> a -> Bool) -> [a] -> [[a]]
partitionByCond cond = para psi where
psi t = case t of
Nil -> []
Cons x (a:_, a':b') | cond x a -> (x:a'):b'
Cons x (_, r) -> [x]:r
> partitionByCond (\x y -> x == y - 1) [0, 1, 2, 3, 4, 7, 8, 10]
[[0,1,2,3,4],[7,8],[10]]
Я бы такой код не пропустил на код-ревью по параметру читаемости:
- комментарии не просто говорят, а кричат о необходимости выноса кусков в отдельные функции
- скорее всего отдельные функции и тела циклов
- возможно условия в переменные
public static String getRanges(List<Integer> l) {
// Begin ranges & End ranges (br & er)
List<Integer> br = new ArrayList<>();
List<Integer> er = new ArrayList<>();
l.stream().reduce(l.get(0)-2, (a, b) -> {
if (Math.abs(a-b) > 1 && a < b) {
er.add(a);
br.add(b);
}
return b;
});
er.remove(0);
er.add(l.get(l.size()-1));
// Zip & join
return IntStream
.range(0, Math.min(br.size(), er.size()))
.mapToObj(i -> (br.get(i) != er.get(i))
? br.get(i) + "-" + er.get(i)
: br.get(i) + "")
.collect(Collectors.joining(", "));
}
Какой код нужно показывать на собеседовании