Оптимальный степпинг по алфавиту

30

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

Например, возьмите слово 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)
  • Если есть связь, вы можете вывести любой размер шага или все
  • Это , поэтому выигрывает наименьшее количество байтов для каждого языка!
Джо Кинг
источник
Нужно ли обрабатывать пустой ввод?
pizzapants184
1
@ pizzapants184 Нет. Я обновил вопрос, чтобы указать, что ввод будет непустым
Джо Кинг
Можем ли мы принять ввод как массив символов?
Лохматый
@ Shaggy Конечно, вы можете
Джо Кинг
Есть ли причина, по которой вместо цифр используются буквы?
Wheat Wizard

Ответы:

6

Древесный уголь , 41 байт

≔EEβEθ∧μ⌕⭆β§β⁺⌕β§θ⊖μ×κξλ⎇⊕⌊ιΣι⌊ιθI⌕θ⌊Φθ⊕ι

Попробуйте онлайн! Ссылка на подробную версию кода. 0 индексированные. Объяснение:

Eβ

Цикл по 26 размерам ступеней. (На самом деле я зацикливаюсь на строчном алфавите и использую переменную индекса.)

Eθ∧μ

Цикл по каждому символу ввода после первого.

⭆β§β⁺⌕β§θ⊖μ×κξ

Зациклите 26 раз и сгенерируйте строку символов, получив в результате 26 шагов с заданным размером шага, начиная (с 0 индексацией) с предыдущим символом ввода.

⌕...λ

Найти позицию текущего символа ввода в этой строке или -1, если не найден.

E...⎇⊕⌊ιΣι⌊ι

Возьмите сумму всех позиций, если только она не была найдена, в этом случае используйте -1.

≔...θ

Сохранить суммы.

⌊Φθ⊕ι

Найдите минимальную неотрицательную сумму.

I⌕θ...

Найдите первый размер шага с этой суммой и выведите его.

Нил
источник
5

JavaScript, 143 байта

w=>(a=[...Array(26).keys(m=1/0)]).map(s=>~[...w].map(c=>(t+=a.find(v=>!p|(u(c,36)+~v*s-u(p,36))%26==0),p=c),p=t=0,u=parseInt)+t<m&&(m=t,n=s))|n

Попробуйте онлайн!

Благодаря Shaggy, использование [...Array(26).keys()]экономит 9 байтов.

ТТГ
источник
144 байта
лохматый
4

Желе , 28 26 23 байта

S;þḅ26ŒpṢƑƇIŻ€S:g/ƊÞḢg/

Вывод 0 проиндексирован. Ввод является байтовой строкой и может быть в любом случае, но верхний регистр намного быстрее.

Однобуквенный ввод должен иметь специальный регистр и стоит 2 байта. ._.

Попробуйте онлайн!

Обратите внимание, что это метод грубой силы; вводы с четырьмя или более буквами будут задерживаться на TIO. Набор тестов претендует _39 на «эффективность».

Как это работает

S;þḅ26ŒpṢƑƇIŻ€S:g/ƊÞḢg/  Main link. Argument: b (bytestring)

S                        Take the sum (s) of the code points in b.
 ;þ                      Concatenate table; for each k in [1, ..., s] and each c in
                         b, yield [k, c], grouping by c.
   ḅ26                   Unbase 26; map [k, c] to (26k + c).
      Œp                 Take the Cartesian product.
        ṢƑƇ              Comb by fixed sort; keep only increasing lists.
           I             Increments; take the forward differences of each list.
            Ż€           Prepend a 0 to each list.
                         I returns empty lists for single-letter input, so this is
                         required to keep g/ (reduce by GCD) from crashing.
                   Þ     Sort the lists by the link to the left.
              S:g/Ɗ      Divide the sum by the GCD.
                    Ḣ    Head; extract the first, smallest element.
                     g/  Compute the GCD.
Деннис
источник
4

Желе , 17 байт

ƓI%
26×þ%iþÇo!SỤḢ

Ввод - это строка байтов в STDIN, выход - 1-индексированный.

Попробуйте онлайн!

Как это работает

ƓI%            Helper link. Argument: m (26 when called)

Ɠ              Read a line from STDIN and eval it as Python code.
 I             Increments; take all forward differences.
  %            Take the differences modulo m.


26×þ%iþÇoSSỤḢ  Main link. No arguments.

26             Set the argument and the return value to 26.
  ×þ           Create the multiplication table of [1, ..., 26] by [1, ..., 26].
    %          Take all products modulo 26.
       Ç       Call the helper link with argument 26.
     iþ        Find the index of each integer to the right in each list to the left,
               grouping by the lists.
        o!     Replace zero indices (element not found) with 26!.
               This works for strings up to 25! = 15511210043330985984000000 chars,
               which exceeds Python's 9223372036854775807 character limit on x64.
          S    Take the sum of each column.
           Ụ   Sort the indices by their corresponding values.
            Ḣ  Head; extract the first index, which corresponds to the minimal value.
Деннис
источник
4

JavaScript (Node.js) ,  123 121 116  114 байтов

s=>(i=26,F=m=>i--?F((g=x=>s[p]?s[k++>>5]?j=1+g(x+i,p+=b[p]==x%26+97):m:0)(b[p=k=0]+7)>m?m:(r=i,j)):r)(b=Buffer(s))

Попробуйте онлайн!

комментарии

NB . При попытке сопоставить букву в алфавите с заданным шагом , нам нужно продвинуть указатель не более раз. После неудачных итераций, по крайней мере, одно письмо должно быть посещено дважды. Итак, последовательность будет повторяться вечно, и буква, которую мы ищем, не является ее частью. Вот почему мы используем рекурсивную функцию , чтобы она отказывалась после итераций, где - длина входной строки.i2526г 32 × L Ls[k++ >> 5]g32×LL

s => (                        // main function taking the string s
  i = 26,                     // i = current step, initialized to 26
  F = m =>                    // F = recursive function taking the current minimum m
    i-- ?                     // decrement i; if i was not equal to 0:
      F(                      //   do a recursive call to F:
        (g = x =>             //     g = recursive function taking a character ID x
          s[p] ?              //       if there's still at least one letter to match:
            s[k++ >> 5] ?     //         if we've done less than 32 * s.length iterations:
              j = 1 + g(      //           add 1 to the final result and add the result of
                x + i,        //             a recursive call to g with x = x + i
                p += b[p] ==  //             increment p if
                  x % 26 + 97 //             the current letter is matching
              )               //           end of recursive call to g
            :                 //         else (we've done too many iterations):
              m               //           stop recursion and yield the current minimum
          :                   //       else (all letters have been matched):
            0                 //         stop recursion and yield 0
        )(                    //     initial call to g with p = k = 0
          b[p = k = 0] + 7    //     and x = ID of 1st letter
        ) > m ?               //     if the result is not better than the current minimum:
          m                   //       leave m unchanged
        :                     //     else:
          (r = i, j)          //       update m to j and r to i
      )                       //   end of recursive call to F
    :                         // else (i = 0):
      r                       //   stop recursion and return the final result r
)(b = Buffer(s))              // initial call to F with m = b = list of ASCII codes of s
Arnauld
источник
4

Рубин , 121 114 112 108 102 89 байт

->s{(r=0..25).min_by{|l|p,=s;s.sum{|c|t=r.find{|i|(p.ord-c.ord+i*l)%26<1}||1/0.0;p=c;t}}}

Попробуйте онлайн!

0 индексированные. Принимает ввод как массив символов.

Спасибо ASCII-только за идеи игры в гольф стоимостью 12 байтов.

Кирилл Л.
источник
:( закрыть (на основе решения Python)
только для ASCII
100 , вероятно, можно сыграть в гольф немного больше
только ASCII
91
только для ASCII
Отличная идея, -1 байт за p,=*sуловкой, но я не уверен в теоретической устойчивости решения с жестко закодированным штрафным баллом ... Итак, я изменил константу на бесконечность (хотя ваше значение позволило бы отключить еще 2 байта) ).
Кирилл Л.
Всего 2 байта, неплохо
только ASCII
3

Python 2 , 230 222 216 194 169 байт

def t(s,l,S=0):
 a=ord(s[0])
 for c in s[1:]:
	while a-ord(c)and S<len(s)*26:S+=1;a=(a-65+l)%26+65
 return S
def f(s):T=[t(s,l)for l in range(26)];return T.index(min(T))

Попробуйте онлайн!

-22 байта из тш

-39 байтов от Джо Кинга

Старая версия с объяснением:

A=map(chr,range(65,91)).index
def t(s,l,S=0):
 a=A(s[0]) 
 for c in s[1:]:
	while a!=A(c)and S<len(s)*26:
	 S+=1;a+=l;a%=26
 return S
def f(s):T=[t(s,l)for l in range(26)];return T.index(min(T))

Попробуйте онлайн!

Это будет короче в языке с простым числом букв (не нужно float('inf')обрабатывать бесконечные циклы). На самом деле, это представление все еще нужно для обработки строк типа «aaa». Это представление теперь использует 26*len(s)в качестве верхней границы, которая останавливает бесконечные циклы.

Это представление имеет индекс 0 (возвращает значения от 0 до 25 включительно).

f принимает (n заглавную) строку и возвращает оптимальный шаг по алфавиту

tявляется вспомогательной функцией, которая принимает строку и пошаговый алфавит и возвращает количество прыжков, необходимых для завершения строки (или, 26*len(s)если это невозможно).

pizzapants184
источник
2
Используйте, while a!=A(c)and S<len(s)*26:и вы можете удалить if a==i:return float('inf'), так как len(s)*26это верхняя граница любого ответа.
ч. В
165
только для ASCII
155
только в ASCII
1
112
только ASCII
2

05AB1E (наследие) , 33 27 26 байтов

Ç¥ε₂%U₂L<©ε®*₂%Xk'-žm:]øOWk

Использует унаследованную версию, потому что, кажется, есть ошибка, когда вы хотите изменить / использовать результат после вложенной карты в новой версии 05AB1E.

0-индексированный вывод.

Попробуйте онлайн или проверьте все контрольные примеры .

Объяснение:

Ç                        # ASCII values of the (implicit) input
 ¥                       # Deltas (differences between each pair)
  ε                      # Map each delta to:
   ₂%                    #  Take modulo-26 of the delta
     U                   #  Pop and store it in variable `X`
      L<                #  Push a list in the range [0,25]
         ©               #  Store it in the register (without popping)
          ε              #  Map each `y` to:
           ®*            #   Multiply each `y` by the list [0,25] of the register
             ₂%          #   And take modulo-26
                         #   (We now have a list of size 26 in steps of `y` modulo-26)
               Xk        #   Get the index of `X` in this inner list (-1 if not found)
                 '-₄:   '#   Replace the minus sign with "1000"
                         #   (so -1 becomes 10001; others remain unchanged) 
]                        # Close both maps
 ø                       # Zip; swapping rows/columns
  O                      # Sum each
   W                     # Get the smallest one (without popping the list)
    k                    # Get the index of this smallest value in the list
                         # (and output the result implicitly)
Кевин Круйссен
источник
2

Python 3 , 191 178 162 байта

Спасибо всем за все ваши советы! это выглядит гораздо более похоже на гольф.

*w,=map(ord,input())
a=[]
for i in range(26):
 n=1;p=w[0]
 for c in w:
  while n<len(w)*26and p!=c:
   n+=1;p+=i;
   if p>122:p-=26
 a+=[n]
print(a.index(min(a)))

Попробуйте онлайн!

И мой оригинальный код, если кому-то интересно.

Превращает слово в список значений ASCII, затем проходит по шагам с размерами от 0 до 25, проверяя, сколько шагов требуется, чтобы исчерпать список (есть предел для остановки бесконечных циклов).

Количество шагов добавляется в список а .

После большого цикла for выводится индекс наименьшего значения в a . Это равно значению i (размер шага) для этой итерации цикла, QED.

Terjerber
источник
1
Привет и добро пожаловать в PPCG! Начнем с того, что количество опубликованных вами байтов не соответствует таковому на TIO :) Теперь, для пары быстрых подсказок: range(26)достаточно - вам не нужно указывать начало, так как 0 по умолчанию; a.append(n)может быть a+=[n]; первая строка будет короче карты w=list(map(ord,input()))(на самом деле, с вашим текущим алгоритмом, в Py2 вы также можете отказаться от list(...)переноса); избежать дополнительных перерывов разноса / линий как можно больше (например, нет необходимости в oneliners переводов строк: if p>122:p-=26)
Кирилл Львович
1
Кроме того, это n>99выглядит подозрительно, это произвольная константа, чтобы вырваться из бесконечного цикла? Тогда это, вероятно, должно быть что-то вроде 26 * len (w), поскольку вы никогда не знаете, насколько большим будет вход.
Кирилл Л.
1
Кстати, вы все еще можете избавиться от этого list(...)в Py3, а также от одного дополнительного if: 165 байтов . Кроме того, взгляните на эту тему советов , я уверен, что вы значительно улучшите свои навыки, используя советы оттуда!
Кирилл Л.
1
Я не эксперт по питону, но я думаю, что вы можете while p!=c and n>len(w)*26:избавиться от этого последнего оператора if для -8 байт.
Spitemaster
2
Хотя это выглядит ужасно и идет вразрез со всем, что есть в Python, вы можете изменить его n+=1и p+=iна отдельных строках n+=1;p+=iна один.
Недла2004