Optimal Alphabet Stepping

Question

Given an input string consisting of only letters, return the step-size that results in the minimum amount of steps that are needed to visit all the letters in order over a wrapping alphabet, starting at any letter.

For example, take the word, dog. If we use a step-size of 1, we end up with:

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

For a total of 30 steps.

However, if we use a step-size of 11, we get:

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

For a total of 6 steps. This is the minimum amount of steps, so the return result for dog is the step-size; 11.

Test cases:

"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

Rules

• Input will be a non-empty string or array of characters consisting only of the letters a to z (you can choose between uppercase or lowercase)
• Output can be 0 indexed (i.e. the range 0-25) or 1 indexed (1-26)
• If there's a tie, you can output any step-size or all of them
• This is code-golf, so the lowest amount of bytes for each language wins!

Answer 1

Charcoal, 41 bytes

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

Try it online! Link is to verbose version of code. 0-indexed. Explanation:

Ｅβ

Loop over the 26 step sizes. (Actually I loop over the lowercase alphabet here and use the index variable.)

Ｅθ∧μ

Loop over each character of the input after the first.

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

Loop 26 times and generate the string of characters resulting by taking 26 steps at the given step size starting (0-indexed) with the previous character of the input.

⌕...λ

Find the position of the current character of the input in that string, or -1 if not found.

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

Take the sum of all the positions, unless one was not found, in which case use -1.

≔...θ

Save the sums.

⌊Φθ⊕ι

Find the minimum non-negative sum.

Ｉ⌕θ...

Find the first step size with that sum and output it.

Answer 2

JavaScript, 143 bytes

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

Try it online!

Thanks to Shaggy, using [...Array(26).keys()] saves 9 bytes.

Answer 3

Ruby, 121 114 112 108 102 89 bytes

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

Try it online!

0-indexed. Takes input as an array of characters.

Thanks to ASCII-only for golfing ideas worth 12 bytes.

Answer 4

JavaScript (Node.js),  123 121 116  114 bytes

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

Try it online!

Commented

NB: When trying to match a letter in the alphabet with a given step \$i\$, we need to advance the pointer at most \$25\$ times. After \$26\$ unsuccessful iterations, at least one letter must have been visited twice. So, the sequence is going to repeat forever and the letter we're looking for is not part of it. This is why we do s[k++ >> 5] in the recursive function \$g\$, so that it gives up after \$32 \times L\$ iterations, where \$L\$ is the length of the input string.

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

Answer 5

Jelly, 28 26 23 bytes

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

Output is 0-indexed. Input is a bytestring and can be in any case, but uppercase is much faster.

Single-letter input has to be special-cased and costs 2 bytes. ._.

Try it online!

Note that this is a brute-force approach; inputs with four or more letters will time out on TIO. The test suite prepends _39 for "efficiency".

How it works

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.

Answer 6

Jelly, 17 bytes

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

Input is a bytestring on STDIN, output is 1-indexed.

Try it online!

How it works

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

Answer 7

Python 2, 230 222 216 194 169 bytes

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

Try it online!

-22 bytes from tsh

-39 bytes from Jo King

Older version with explanation:

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

Try it online!

This would be shorter in a language with a prime number of letters (wouldn't need the float('inf') handling of infinite loops). Actually, this submission would still need that for handling strings like "aaa". This submission now uses 26*len(s) as an upper bound, which stops infinite loops.

This submission is 0-indexed (returns values from 0 to 25 inclusive).

f takes a(n uppercase) string and returns the Optimal Alphabet Stepping

t is a helper function that takes the string and an alphabet stepping and returns the number of hops needed to finish the string (or 26*len(s) if impossible).

Answer 8

Red, 197 bytes

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]

Try it online!

Answer 9

Python 3, 191 178 162 bytes

Thanks everyone for all your tips! this is looking much more golflike.

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

Try it online!

And my original code if anyone's interested.

Turns the word into a list of ASCII values, then iterates through step sizes 0 to 25, checking how many steps it takes to exhaust the list (there's a ceiling to stop infinite loops).

Number of steps is added to the list a.

After the big for loop, the index of the smallest value in a is printed. This is equal to the value of i (the step size) for that iteration of the loop, QED.

Answer 10

05AB1E (legacy), 33 27 26 bytes

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

Uses the legacy version because there seems to be a bug when you want to modify/use the result after a nested map in the new 05AB1E version..

0-indexed output.

Try it online or verify all test cases.

Explanation:

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