Найти трассы внутри массива
Прогон определяется как три или более чисел, которые увеличиваются от предыдущего с постоянным шагом. Например, [1,2,3] будет прогоном с шагом 1, [1,3,5,7] будет прогоном с шагом 2, а [1,2,4,5] не будет прогоном.
Мы можем выразить эти прогоны через обозначения «i к j через s», где i - это первый номер прогона, j - последний номер прогона, а s - шаг. Однако прогоны шага 1 будут обозначены как «i - j».
Таким образом, используя массивы ранее, мы получаем:
[1,2,3] -> "1to3"
[1,3,5,7] -> "1to7by2"
[1,2,4,5] -> "1 2 4 5"
В этом задании ваша задача сделать это для массивов, которые могут иметь несколько прогонов.
Пример кода Python с рекурсией:
def arr_comp_rec(a, start_index):
# Early exit and recursion end point
if start_index == len(a)-1:
return str(a[-1])
elif start_index == len(a):
return ''
# Keep track of first delta to compare while searching
first_delta = a[start_index+1] - a[start_index]
last = True
for i in range(start_index, len(a)-1):
delta = a[i+1] - a[i]
if delta != first_delta:
last = False
break
# If it ran through the for loop, we need to make sure it gets the last value
if last: i += 1
if i - start_index > 1:
# There is more than 2 numbers between the indexes
if first_delta == 1:
# We don't need by if step = 1
return "{}to{} ".format(a[start_index], a[i]) + arr_comp_rec(a, i+1)
else:
return "{}to{}by{} ".format(a[start_index], a[i], first_delta) + arr_comp_rec(a, i+1)
else:
# There is only one number we can return
return "{} ".format(a[start_index]) + arr_comp_rec(a, i)
вход
Массив отсортированных положительных целых (без дубликатов)
Выход
Строка прогонов, разделенных пробелом, или массив строк прогонов
Не нужно быть жадным в определенном направлении
Может иметь пробел в конце
Тестовые случаи
In: [1000, 1002, 1004, 1006, 1008, 1010]
Out: "1000to1010by2"
In: [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233]
Out: "1to3 5 8 13 21 34 55 89 144 233"
In: [10, 20, 30, 40, 60]
Out: "10to40by10 60"
In: [5, 6, 8, 11, 15, 16, 17]
Out: "5 6 8 11 15to17"
In: [1, 2, 3, 4, 5, 6, 7, 9, 11, 13, 15, 30, 45, 50, 60, 70, 80, 90, 91, 93]
Out: "1to7 9to15by2 30 45 50to90by10 91 93"
Это код-гольф, поэтому выигрывает наименьшее количество байтов.
источник
[4, 5, 6, 7, 9, 11, 13, 15]не может быть4to6 7to15by2?)Ответы:
Желе ,
4240 байт-2 благодаря Кевину Круйссену (отфильтровывать двойки
ḟ2, а не заменять двойки нулями2,0y)Полная программа печати результата.
(В качестве монадической ссылки будет получен список, содержащий смесь целых чисел и символов)
Попробуйте онлайн!
(Слишком неэффективно, чтобы выполнить самый большой тестовый пример в течение 60 секунд, поэтому я удалил
[1,2,3,4].)Как?
источник
2,0ySƲÞможно сыграть в гольфḟ2SƊÞна -2 байта.P, а не по сумме,Sи мне понадобились бы нули.Swift, 246 байт
Попробуйте онлайн!
источник
К (нгн / к) , 102 байта
Попробуйте онлайн!
источник
JavaScript (ES6), 129 байт
Возвращает массив строк.
Попробуйте онлайн!
Как?
Шаг 1
Сначала мы добавляем к каждому номеру суффикс, состоящий из
'-'начального числа, за которым следует разница со следующим номером, за исключением последней записи, которая остается неизменной. Этот новый массив приведен к строке.Пример:
Шаг 2
Мы идентифицируем все прогоны в результирующей строке и заменяем их соответствующими обозначениями.
Пример:
Шаг 3
Наконец, мы разбиваем строку на оставшиеся суффиксы, включая запятые.
Пример:
источник
Рубин ,
125118 байтПопробуйте онлайн!
объяснение
В Ruby's Enumerable есть полезный
chunkметод, который делает именно то, что нам нужно - он группирует элементы по последовательным прогонам одного и того же возвращаемого значения из блока, в нашем случае - разницы между значением current (x) и previous (y).Предостережение заключается в том, что такая стратегия не будет захватывать первый элемент цикла, например, здесь сгруппированы только два последних элемента:
Следовательно, при отображении в правильно отформатированные строки, когда мы сталкиваемся с новым потенциальным прогоном (чанк с> 1 элементом), мы должны отслеживать, был ли предыдущий элемент единственным (
i=1) или уже использовался в другом запуске (i=0). Если есть неиспользуемый отдельный элемент, он становится отправной точкой цикла и снижает порог размера куска с 3 до 2.источник
R ,
180175 байтПопробуйте онлайн!
Концептуально это порт моего ответа Ruby , хотя технически он явно немного другой.
5 байтов сохранены JayCe.
источник
rleно было слишком ленивым ... вы можете сэкономить 1 байт, делаяsum(1|x)вместоlength(x): TIOcatна 175 байтов: TIOR ,
238217 байтСпасибо @digEmAll за -19 байт.
Попробуйте онлайн!
источник
Fвместо того,nкак он уже инициализирован0, что должно сэкономить несколько байтов, я думаю.split,diffиrle. К сожалению, жадный поиск прогонов требует много хлопот.'by'[D>1]хороший трюк.JavaScript (Node.js) ,
177173 байтаПопробуйте онлайн!
источник
Чисто ,
208... 185 байтПопробуйте онлайн!
источник
Желе , 41 байт
Попробуйте онлайн!
Полная программа.
источник
Python 2 ,
170166 байтПопробуйте онлайн!
источник
Python 2 ,
138136 байт-2 байта благодаря Эрику Аутгольферу .
Попробуйте онлайн!
источник
гвм (совершить 2612106байт-код ), 108 байт
Ожидается размер массива в одной строке, затем каждый член в одной строке.
HexDump:
Тестовые прогоны:
Собранный вручную из этого:
источник
05AB1E (наследие) ,
4950 байтовСлишком долго, но я уже рад, что это работает. Эта задача намного сложнее, чем кажется на первый взгляд. Без сомнения, можно играть в гольф дальше.
Σ€g2KO>}¤порт ответа2,0ySƲÞṪот JJ @athonanAllan 's Jelly (спасибо!).Попробуйте онлайн.(ПРИМЕЧАНИЕ. Время ожидания для больших тестовых случаев.)
+1 байт как исправление ошибки, потому что
0при сортировке всегда ставится на конечную позицию.Объяснение:
источник
Perl 5 , 154 байта
То же самое с пробелами, переводом строки, #comments и
sub by:Попробуйте онлайн!
... для прохождения испытаний от ОП.
источник
Сетчатка 0.8.2 , 77 байт
Попробуйте онлайн! Ссылка включает в себя тестовые случаи. Объяснение:
Преобразовать в одинарный.
Вычислить последовательные различия.
Конвертировать работает в
to...byсинтаксис.Удалить неконвертированные различия и
by1.Преобразовать в десятичную.
источник