Если задана входная строка, состоящая только из букв, верните размер шага, в результате которого будет получено минимальное количество шагов, необходимых для посещения всех букв по порядку в алфавите переноса, начиная с любой буквы.
Например, возьмите слово dog
. Если мы используем шаг размером 1, мы получим:
defghijklmnopqrstuvwxyzabcdefg Alphabet
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
defghijklmnopqrstuvwxyzabcdefg Visited letters
d o g Needed letters
Всего 30 шагов.
Однако, если мы используем шаг размером 11, мы получим:
defghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefg
^ ^ ^ ^ ^ ^
d o z k v g Visited letters
d o g Needed letters
Всего 6 шагов. Это минимальное количество шагов, поэтому возвращаемый результат для dog
является размером шага; 11
,
Тестовые случаи:
"dog" -> 11
"age" -> 6
"apple" -> 19
"alphabet" -> 9
"aaaaaaa" -> 0 for 0 indexed, 26 for 1 indexed
"abcdefga" -> 1 or 9
"aba" -> Any odd number except for 13
"ppcg" -> 15
"codegolf" -> 15
"testcase" -> 9
"z" -> Any number
"joking" -> 19
правила
- Ввод будет не пустая строка или массив символов , состоящих только из букв
a
вz
(вы можете выбрать между строчным и прописным) - Выход может быть 0 проиндексирован (т. Е. Диапазон
0-25
) или 1 проиндексирован (1-26
) - Если есть связь, вы можете вывести любой размер шага или все
- Это код-гольф , поэтому выигрывает наименьшее количество байтов для каждого языка!
Ответы:
Древесный уголь , 41 байт
Попробуйте онлайн! Ссылка на подробную версию кода. 0 индексированные. Объяснение:
Цикл по 26 размерам ступеней. (На самом деле я зацикливаюсь на строчном алфавите и использую переменную индекса.)
Цикл по каждому символу ввода после первого.
Зациклите 26 раз и сгенерируйте строку символов, получив в результате 26 шагов с заданным размером шага, начиная (с 0 индексацией) с предыдущим символом ввода.
Найти позицию текущего символа ввода в этой строке или -1, если не найден.
Возьмите сумму всех позиций, если только она не была найдена, в этом случае используйте -1.
Сохранить суммы.
Найдите минимальную неотрицательную сумму.
Найдите первый размер шага с этой суммой и выведите его.
источник
JavaScript, 143 байта
Попробуйте онлайн!
Благодаря Shaggy, использование
[...Array(26).keys()]
экономит 9 байтов.источник
Желе ,
282623 байтаВывод 0 проиндексирован. Ввод является байтовой строкой и может быть в любом случае, но верхний регистр намного быстрее.
Однобуквенный ввод должен иметь специальный регистр и стоит 2 байта. ._.
Попробуйте онлайн!
Обратите внимание, что это метод грубой силы; вводы с четырьмя или более буквами будут задерживаться на TIO. Набор тестов претендует
_39
на «эффективность».Как это работает
источник
Желе , 17 байт
Ввод - это строка байтов в STDIN, выход - 1-индексированный.
Попробуйте онлайн!
Как это работает
источник
JavaScript (Node.js) ,
123 121 116114 байтовПопробуйте онлайн!
комментарии
NB . При попытке сопоставить букву в алфавите с заданным шагом , нам нужно продвинуть указатель не более раз. После неудачных итераций, по крайней мере, одно письмо должно быть посещено дважды. Итак, последовательность будет повторяться вечно, и буква, которую мы ищем, не является ее частью. Вот почему мы используем рекурсивную функцию , чтобы она отказывалась после итераций, где - длина входной строки.i 25 26 г 32 × L Lg 32×L L
s[k++ >> 5]
источник
Рубин ,
12111411210810289 байтПопробуйте онлайн!
0 индексированные. Принимает ввод как массив символов.
Спасибо ASCII-только за идеи игры в гольф стоимостью 12 байтов.
источник
p,=*s
уловкой, но я не уверен в теоретической устойчивости решения с жестко закодированным штрафным баллом ... Итак, я изменил константу на бесконечность (хотя ваше значение позволило бы отключить еще 2 байта) ).Python 2 ,
230222216194169 байтПопробуйте онлайн!
-22 байта из тш
-39 байтов от Джо Кинга
Старая версия с объяснением:
Попробуйте онлайн!
Это будет короче в языке с простым числом букв (не нужноЭто представление теперь используетfloat('inf')
обрабатывать бесконечные циклы). На самом деле, это представление все еще нужно для обработки строк типа «aaa».26*len(s)
в качестве верхней границы, которая останавливает бесконечные циклы.Это представление имеет индекс 0 (возвращает значения от 0 до 25 включительно).
f
принимает (n заглавную) строку и возвращает оптимальный шаг по алфавитуt
является вспомогательной функцией, которая принимает строку и пошаговый алфавит и возвращает количество прыжков, необходимых для завершения строки (или,26*len(s)
если это невозможно).источник
while a!=A(c)and S<len(s)*26:
и вы можете удалитьif a==i:return float('inf')
, так какlen(s)*26
это верхняя граница любого ответа.Красный , 197 байт
Попробуйте онлайн!
источник
05AB1E (наследие) ,
332726 байтовИспользует унаследованную версию, потому что, кажется, есть ошибка, когда вы хотите изменить / использовать результат после вложенной карты в новой версии 05AB1E.
0-индексированный вывод.
Попробуйте онлайн или проверьте все контрольные примеры .
Объяснение:
источник
Python 3 ,
191178162 байтаСпасибо всем за все ваши советы! это выглядит гораздо более похоже на гольф.
Попробуйте онлайн!
И мой оригинальный код, если кому-то интересно.
Превращает слово в список значений ASCII, затем проходит по шагам с размерами от 0 до 25, проверяя, сколько шагов требуется, чтобы исчерпать список (есть предел для остановки бесконечных циклов).
Количество шагов добавляется в список а .
После большого цикла for выводится индекс наименьшего значения в a . Это равно значению i (размер шага) для этой итерации цикла, QED.
источник
range(26)
достаточно - вам не нужно указывать начало, так как 0 по умолчанию;a.append(n)
может бытьa+=[n]
; первая строка будет короче картыw=list(map(ord,input()))
(на самом деле, с вашим текущим алгоритмом, в Py2 вы также можете отказаться отlist(...)
переноса); избежать дополнительных перерывов разноса / линий как можно больше (например, нет необходимости в oneliners переводов строк:if p>122:p-=26
)n>99
выглядит подозрительно, это произвольная константа, чтобы вырваться из бесконечного цикла? Тогда это, вероятно, должно быть что-то вроде 26 * len (w), поскольку вы никогда не знаете, насколько большим будет вход.list(...)
в Py3, а также от одного дополнительногоif
: 165 байтов . Кроме того, взгляните на эту тему советов , я уверен, что вы значительно улучшите свои навыки, используя советы оттуда!while p!=c and n>len(w)*26:
избавиться от этого последнего оператора if для -8 байт.n+=1
иp+=i
на отдельных строкахn+=1;p+=i
на один.