30
\$\begingroup\$

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 , so the lowest amount of bytes for each language wins!
\$\endgroup\$
  • \$\begingroup\$ Do we need to handle empty input? \$\endgroup\$ – pizzapants184 Dec 12 '18 at 4:32
  • 1
    \$\begingroup\$ @pizzapants184 No. I've updated the question to specify the input will be non-empty \$\endgroup\$ – Jo King Dec 12 '18 at 4:33
  • \$\begingroup\$ Can we take input as an array of characters? \$\endgroup\$ – Shaggy Dec 12 '18 at 6:54
  • \$\begingroup\$ @Shaggy Sure you can \$\endgroup\$ – Jo King Dec 12 '18 at 7:58
  • \$\begingroup\$ Is there a reason this uses letters instead of numbers? \$\endgroup\$ – Sriotchilism O'Zaic Dec 12 '18 at 13:54

10 Answers 10

6
\$\begingroup\$

Charcoal, 41 bytes

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

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

Eβ

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

Eθ∧μ

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.

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

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.

I⌕θ...

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

\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.
\$\endgroup\$
4
\$\begingroup\$

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.
\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ :( close (based off python solution) \$\endgroup\$ – ASCII-only Jan 28 at 5:57
  • \$\begingroup\$ 100, probably can be golfed quite a bit more \$\endgroup\$ – ASCII-only Jan 28 at 5:58
  • \$\begingroup\$ 91 \$\endgroup\$ – ASCII-only Jan 28 at 9:27
  • \$\begingroup\$ Great idea, -1 more byte by p,=*s trick, but I'm not so sure about theoretical robustness of a solution with a hardcoded penalty score... So, I changed the constant to infinity (although your value would allow for another 2 bytes off). \$\endgroup\$ – Kirill L. Jan 28 at 16:32
  • \$\begingroup\$ Only 2 bytes, not bad \$\endgroup\$ – ASCII-only Jan 29 at 0:45
3
\$\begingroup\$

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

\$\endgroup\$
  • 2
    \$\begingroup\$ Use while a!=A(c)and S<len(s)*26: and you may remove if a==i:return float('inf'), since len(s)*26 is upper bound of any answer. \$\endgroup\$ – tsh Dec 12 '18 at 6:41
  • \$\begingroup\$ 165 \$\endgroup\$ – ASCII-only Jan 23 at 5:19
  • \$\begingroup\$ alternative method, 166 \$\endgroup\$ – ASCII-only Jan 23 at 5:32
  • \$\begingroup\$ 155 \$\endgroup\$ – ASCII-only Jan 23 at 6:40
  • 1
    \$\begingroup\$ 112 \$\endgroup\$ – ASCII-only Jan 24 at 2:40
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Hi & Welcome to PPCG! For starters, your posted byte count doesn't match that on TIO :) Now, for a couple of quick hints: range(26) is enough - you don't need to specify the start, since 0 is the default; a.append(n) could be a+=[n]; the first line would be shorter as map w=list(map(ord,input())), (actually with your current algorithm, in Py2 you could drop list(...) wrapping as well); avoid extra spacing/line breaks as much as possible (e.g., no need for newlines in oneliners: if p>122:p-=26) \$\endgroup\$ – Kirill L. Dec 12 '18 at 15:06
  • 1
    \$\begingroup\$ Also, that n>99 look suspicious, is that an arbitrary constant to break out of inifinite loop? Then it probably should be something like 26*len(w), as you never know, how large the input will be. \$\endgroup\$ – Kirill L. Dec 12 '18 at 15:07
  • 1
    \$\begingroup\$ BTW, you can still get rid of that list(...) in Py3 and also of one extra if: 165 bytes. Also, take a look at this tips topic, I'm sure you'll greatly improve your skills using advices from there! \$\endgroup\$ – Kirill L. Dec 12 '18 at 15:44
  • 1
    \$\begingroup\$ I'm not a python expert, but I think you can do while p!=c and n>len(w)*26: and get rid of that last if statement for -8 bytes. \$\endgroup\$ – Spitemaster Dec 12 '18 at 18:19
  • 2
    \$\begingroup\$ Although it looks terrible and goes against everything Python is, you can change n+=1 and p+=i on seperate lines to n+=1;p+=i on one. \$\endgroup\$ – nedla2004 Dec 12 '18 at 18:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.