Biorąc pod uwagę ciąg wejściowy składający się tylko z liter, zwróć rozmiar kroku, który daje minimalną liczbę kroków potrzebną do odwiedzenia wszystkich liter w kolejności na zawijanym alfabecie, zaczynając od dowolnej litery.

Na przykład, weźmy słowo dog. Jeśli użyjemy kroku o wartości 1, otrzymamy:

defghijklmnopqrstuvwxyzabcdefg   Alphabet
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
defghijklmnopqrstuvwxyzabcdefg   Visited letters
d          o                 g   Needed letters

W sumie 30 kroków.

Jeśli jednak użyjemy kroku 11, otrzymamy:

defghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefg
^          ^          ^          ^          ^          ^
d          o          z          k          v          g   Visited letters
d          o                                           g   Needed letters

W sumie 6 kroków. Jest to minimalna liczba kroków, więc zwracanym wynikiem dogjest rozmiar kroku; 11.

Przypadki testowe:

"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

Zasady

• Dane wejściowe będą niepustym ciągiem znaków lub tablicą znaków składającą się tylko z liter ado z(możesz wybierać między wielkimi i małymi literami)
• Dane wyjściowe mogą być indeksowane 0 (tj. Zakres 0-25) lub indeksowane 1 ( 1-26)
• Jeśli jest remis, możesz wydrukować dowolny rozmiar kroku lub wszystkie
• To jest golf golfowy , więc wygrywa najmniej bajtów dla każdego języka!

Węgiel drzewny , 41 bajtów

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

Wypróbuj online! Link jest do pełnej wersji kodu. 0-indeksowane. Wyjaśnienie:

Ｅβ

Zapętlaj ponad 26 rozmiarów stopni. (Właściwie przeglądam tutaj małe litery i używam zmiennej indeksu.)

Ｅθ∧μ

Zapętlaj każdy znak wejścia po pierwszym.

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

Zapętlaj 26 razy i generuj ciąg znaków wynikający z wykonania 26 kroków o danym rozmiarze kroku, zaczynając (indeksowany 0) od poprzedniego znaku wejścia.

⌕...λ

Znajdź pozycję bieżącego znaku wejścia w tym ciągu lub -1, jeśli nie zostanie znalezione.

Ｅ...⎇⊕⌊ιΣι⌊ι

Weź sumę wszystkich pozycji, chyba że żadnej nie znaleziono, w takim przypadku użyj -1.

≔...θ

Zapisz sumy.

⌊Φθ⊕ι

Znajdź minimalną sumę nieujemną.

Ｉ⌕θ...

Znajdź rozmiar pierwszego kroku z tą sumą i wyślij go.

JavaScript, 143 bajty

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

Wypróbuj online!

Dzięki Shaggy użycie [...Array(26).keys()]oszczędza 9 bajtów.

Galaretka , 28 26 23 bajtów

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

Wyjście jest indeksowane na 0. Wejście jest bajtowaniem i może być w każdym przypadku, ale wielkie litery są znacznie szybsze.

Wprowadzanie pojedynczej litery musi być w specjalnej obudowie i kosztuje 2 bajty. ._.

Wypróbuj online!

Zauważ, że jest to podejście oparte na brutalnej sile; wejścia z czterema lub więcej literami przekroczą limit czasu w TIO. Zestaw testowy przygotowuje się _39 na „wydajność”.

Jak to działa

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.

Galaretka , 17 bajtów

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

Dane wejściowe są testowane na STDIN, dane wyjściowe mają indeks 1.

Wypróbuj online!

Jak to działa

Ɠ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.

JavaScript (Node.js) ,  123 121 116  114 bajtów

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))

Wypróbuj online!

Skomentował

$i$$25$$26$s[k++ >> 5]$g$$32 \times L$$L$

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

Ruby , 121 114 112 108 102 89 bajtów

->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}}}

Wypróbuj online!

0-indeksowane. Pobiera dane wejściowe jako tablicę znaków.

Dzięki ASCII tylko za pomysły na golfa o wartości 12 bajtów.

Python 2 , 230 222 216 194 169 bajtów

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))

Wypróbuj online!

-22 bajtów od tsh

-39 bajtów od Jo King

Starsza wersja z wyjaśnieniem:

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))

Wypróbuj online!

Byłoby to krótsze w języku z największą liczbą liter (nie wymagałoby float('inf')obsługi nieskończonych pętli). Właściwie to przesłanie nadal potrzebowałoby tego do obsługi ciągów takich jak „aaa”. To przesłanie wykorzystuje teraz 26*len(s)jako górną granicę, która zatrzymuje nieskończone pętle.

To przesłanie ma indeks 0 (zwraca wartości od 0 do 25 włącznie).

f pobiera (n wielkich liter) ciąg znaków i zwraca Optimal Alphabet Stepping

tto funkcja pomocnicza, która pobiera ciąg i przesuwanie alfabetu i zwraca liczbę przeskoków potrzebnych do ukończenia ciągu (lub 26*len(s)jeśli jest to niemożliwe).

Czerwony , 197 bajtów

func[s][a: collect[repeat n 26[keep #"`"+ n]]m: p: 99 a: append/dup a a m
u: find a s/1 repeat n 26[v: extract u n
d: 0 foreach c s[until[(v/(d: d + 1) = c)or(d > length? v)]]if d < m[m: d p: n]]p]

Wypróbuj online!

05AB1E (starsza wersja) , 33 27 26 bajtów

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

Używa starszej wersji, ponieważ wydaje się, że występuje błąd, gdy chcesz zmodyfikować / użyć wyniku po zagnieżdżonej mapie w nowej wersji 05AB1E.

Wyjście indeksowane 0.

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie:

Ç                        # 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)

Python 3 , 191 178 162 bajtów

Dziękujemy wszystkim za wszystkie wskazówki! wygląda to bardziej jak golf.

*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)))

Wypróbuj online!

I mój oryginalny kod, jeśli ktoś jest zainteresowany.

Zamienia słowo w listę wartości ASCII, a następnie iteruje wielkości kroków od 0 do 25, sprawdzając, ile kroków zajmuje wyczerpanie listy (istnieje pułap, aby zatrzymać nieskończone pętle).

Liczba kroków jest dodawany do listy A .

Po duży dla pętli indeks najmniejszej wartości wydrukowaniu. Jest to równe wartości i (rozmiar kroku) dla tej iteracji pętli QED.