Optimal Alphabet Stepping
up vote
20
down vote
favorite
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
toz
(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!
code-golf alphabet
add a comment |
up vote
20
down vote
favorite
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
toz
(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!
code-golf alphabet
Do we need to handle empty input?
– pizzapants184
17 hours ago
1
@pizzapants184 No. I've updated the question to specify the input will be non-empty
– Jo King
17 hours ago
Can we take input as an array of characters?
– Shaggy
14 hours ago
@Shaggy Sure you can
– Jo King
13 hours ago
Is there a reason this uses letters instead of numbers?
– Post Left Garf Hunter
7 hours ago
add a comment |
up vote
20
down vote
favorite
up vote
20
down vote
favorite
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
toz
(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!
code-golf alphabet
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
toz
(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!
code-golf alphabet
code-golf alphabet
edited 13 hours ago
asked 18 hours ago
Jo King
20.3k245107
20.3k245107
Do we need to handle empty input?
– pizzapants184
17 hours ago
1
@pizzapants184 No. I've updated the question to specify the input will be non-empty
– Jo King
17 hours ago
Can we take input as an array of characters?
– Shaggy
14 hours ago
@Shaggy Sure you can
– Jo King
13 hours ago
Is there a reason this uses letters instead of numbers?
– Post Left Garf Hunter
7 hours ago
add a comment |
Do we need to handle empty input?
– pizzapants184
17 hours ago
1
@pizzapants184 No. I've updated the question to specify the input will be non-empty
– Jo King
17 hours ago
Can we take input as an array of characters?
– Shaggy
14 hours ago
@Shaggy Sure you can
– Jo King
13 hours ago
Is there a reason this uses letters instead of numbers?
– Post Left Garf Hunter
7 hours ago
Do we need to handle empty input?
– pizzapants184
17 hours ago
Do we need to handle empty input?
– pizzapants184
17 hours ago
1
1
@pizzapants184 No. I've updated the question to specify the input will be non-empty
– Jo King
17 hours ago
@pizzapants184 No. I've updated the question to specify the input will be non-empty
– Jo King
17 hours ago
Can we take input as an array of characters?
– Shaggy
14 hours ago
Can we take input as an array of characters?
– Shaggy
14 hours ago
@Shaggy Sure you can
– Jo King
13 hours ago
@Shaggy Sure you can
– Jo King
13 hours ago
Is there a reason this uses letters instead of numbers?
– Post Left Garf Hunter
7 hours ago
Is there a reason this uses letters instead of numbers?
– Post Left Garf Hunter
7 hours ago
add a comment |
10 Answers
10
active
oldest
votes
up vote
5
down vote
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.
add a comment |
up vote
4
down vote
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.
144 bytes
– Shaggy
14 hours ago
add a comment |
up vote
3
down vote
Python 2, 222 bytes
A=map(chr,range(65,91))
def t(s,l,S=0):
a=i=A.index(s[0])
for c in s[1:]:
while a!=A.index(c):
S+=1;a+=l;a%=26
if a==i:return float('inf')
i=a
return S
def f(s):T=[t(s,l)for l in range(26)];return T.index(min(T))
Try it online!
-8 bytes from Jo King
This would be shorter in a language with a prime number of letters (wouldn't need the Actually, this submission would still need that for handling strings like "aaa".float('inf')
handling of 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 float('inf')
if impossible).
1
216 bytes
– Jo King
15 hours ago
1
Usewhile a!=A(c)and S<len(s)*26:
and you may removeif a==i:return float('inf')
, sincelen(s)*26
is upper bound of any answer.
– tsh
14 hours ago
add a comment |
up vote
3
down vote
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$, which stops the recursion 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 or s
add a comment |
up vote
3
down vote
Ruby, 121 114 112 108 bytes
->a{(0..25).min_by{|i|c=a[j=0];h=1;z=a.size;(i.times{c=c.next[-1]};j+=1;c==a[h]?h+=1:0)while h<z&&j<26*z;j}}
Try it online!
0-indexed. Takes input as an array of characters.
add a comment |
up vote
3
down vote
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.
add a comment |
up vote
2
down vote
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!
add a comment |
up vote
2
down vote
Python 3, 191 178, bytes
I always see python 2 being used for golfing, let me know if it can do better, I'm new around here and I only know 3.
w=list(map(ord,input()))
a=
for i in range(26):
n=1
p=w[0]
for c in w:
while p!=c:
n+=1
p+=i
if p>122:p-=26
if n>len(w)*26:break
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 (max 99 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.
New contributor
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 bea+=[n]
; the first line would be shorter as mapw=list(map(ord,input()))
, (actually with your current algorithm, in Py2 you could droplist(...)
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
)
– Kirill L.
6 hours ago
Also, thatn>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.
– Kirill L.
6 hours ago
@KirillL.Yeah thatn>99
was a bit shifty so I changed it. Would you believe I spent a good while looking for a way to do if statements in one line like that and came up empty handed? I guess my googling skills aren't great. Thanks for all the advice!
– Terjerber
6 hours ago
BTW, you can still get rid of thatlist(...)
in Py3 and also of one extraif
: 165 bytes. Also, take a look at this tips topic, I'm sure you'll greatly improve your skills using advices from there!
– Kirill L.
5 hours ago
1
Although it looks terrible and goes against everything Python is, you can changen+=1
andp+=i
on seperate lines ton+=1;p+=i
on one.
– nedla2004
3 hours ago
|
show 1 more comment
up vote
2
down vote
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.
add a comment |
up vote
1
down vote
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)
add a comment |
10 Answers
10
active
oldest
votes
10 Answers
10
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
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.
add a comment |
up vote
5
down vote
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.
add a comment |
up vote
5
down vote
up vote
5
down vote
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.
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.
answered 11 hours ago
Neil
78.7k744175
78.7k744175
add a comment |
add a comment |
up vote
4
down vote
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.
144 bytes
– Shaggy
14 hours ago
add a comment |
up vote
4
down vote
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.
144 bytes
– Shaggy
14 hours ago
add a comment |
up vote
4
down vote
up vote
4
down vote
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.
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.
edited 13 hours ago
answered 15 hours ago
tsh
8,18511546
8,18511546
144 bytes
– Shaggy
14 hours ago
add a comment |
144 bytes
– Shaggy
14 hours ago
144 bytes
– Shaggy
14 hours ago
144 bytes
– Shaggy
14 hours ago
add a comment |
up vote
3
down vote
Python 2, 222 bytes
A=map(chr,range(65,91))
def t(s,l,S=0):
a=i=A.index(s[0])
for c in s[1:]:
while a!=A.index(c):
S+=1;a+=l;a%=26
if a==i:return float('inf')
i=a
return S
def f(s):T=[t(s,l)for l in range(26)];return T.index(min(T))
Try it online!
-8 bytes from Jo King
This would be shorter in a language with a prime number of letters (wouldn't need the Actually, this submission would still need that for handling strings like "aaa".float('inf')
handling of 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 float('inf')
if impossible).
1
216 bytes
– Jo King
15 hours ago
1
Usewhile a!=A(c)and S<len(s)*26:
and you may removeif a==i:return float('inf')
, sincelen(s)*26
is upper bound of any answer.
– tsh
14 hours ago
add a comment |
up vote
3
down vote
Python 2, 222 bytes
A=map(chr,range(65,91))
def t(s,l,S=0):
a=i=A.index(s[0])
for c in s[1:]:
while a!=A.index(c):
S+=1;a+=l;a%=26
if a==i:return float('inf')
i=a
return S
def f(s):T=[t(s,l)for l in range(26)];return T.index(min(T))
Try it online!
-8 bytes from Jo King
This would be shorter in a language with a prime number of letters (wouldn't need the Actually, this submission would still need that for handling strings like "aaa".float('inf')
handling of 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 float('inf')
if impossible).
1
216 bytes
– Jo King
15 hours ago
1
Usewhile a!=A(c)and S<len(s)*26:
and you may removeif a==i:return float('inf')
, sincelen(s)*26
is upper bound of any answer.
– tsh
14 hours ago
add a comment |
up vote
3
down vote
up vote
3
down vote
Python 2, 222 bytes
A=map(chr,range(65,91))
def t(s,l,S=0):
a=i=A.index(s[0])
for c in s[1:]:
while a!=A.index(c):
S+=1;a+=l;a%=26
if a==i:return float('inf')
i=a
return S
def f(s):T=[t(s,l)for l in range(26)];return T.index(min(T))
Try it online!
-8 bytes from Jo King
This would be shorter in a language with a prime number of letters (wouldn't need the Actually, this submission would still need that for handling strings like "aaa".float('inf')
handling of 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 float('inf')
if impossible).
Python 2, 222 bytes
A=map(chr,range(65,91))
def t(s,l,S=0):
a=i=A.index(s[0])
for c in s[1:]:
while a!=A.index(c):
S+=1;a+=l;a%=26
if a==i:return float('inf')
i=a
return S
def f(s):T=[t(s,l)for l in range(26)];return T.index(min(T))
Try it online!
-8 bytes from Jo King
This would be shorter in a language with a prime number of letters (wouldn't need the Actually, this submission would still need that for handling strings like "aaa".float('inf')
handling of 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 float('inf')
if impossible).
edited 15 hours ago
answered 16 hours ago
pizzapants184
2,614716
2,614716
1
216 bytes
– Jo King
15 hours ago
1
Usewhile a!=A(c)and S<len(s)*26:
and you may removeif a==i:return float('inf')
, sincelen(s)*26
is upper bound of any answer.
– tsh
14 hours ago
add a comment |
1
216 bytes
– Jo King
15 hours ago
1
Usewhile a!=A(c)and S<len(s)*26:
and you may removeif a==i:return float('inf')
, sincelen(s)*26
is upper bound of any answer.
– tsh
14 hours ago
1
1
216 bytes
– Jo King
15 hours ago
216 bytes
– Jo King
15 hours ago
1
1
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.– tsh
14 hours ago
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.– tsh
14 hours ago
add a comment |
up vote
3
down vote
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$, which stops the recursion 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 or s
add a comment |
up vote
3
down vote
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$, which stops the recursion 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 or s
add a comment |
up vote
3
down vote
up vote
3
down vote
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$, which stops the recursion 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 or s
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$, which stops the recursion 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 or s
edited 9 hours ago
answered 10 hours ago
Arnauld
71.3k688298
71.3k688298
add a comment |
add a comment |
up vote
3
down vote
Ruby, 121 114 112 108 bytes
->a{(0..25).min_by{|i|c=a[j=0];h=1;z=a.size;(i.times{c=c.next[-1]};j+=1;c==a[h]?h+=1:0)while h<z&&j<26*z;j}}
Try it online!
0-indexed. Takes input as an array of characters.
add a comment |
up vote
3
down vote
Ruby, 121 114 112 108 bytes
->a{(0..25).min_by{|i|c=a[j=0];h=1;z=a.size;(i.times{c=c.next[-1]};j+=1;c==a[h]?h+=1:0)while h<z&&j<26*z;j}}
Try it online!
0-indexed. Takes input as an array of characters.
add a comment |
up vote
3
down vote
up vote
3
down vote
Ruby, 121 114 112 108 bytes
->a{(0..25).min_by{|i|c=a[j=0];h=1;z=a.size;(i.times{c=c.next[-1]};j+=1;c==a[h]?h+=1:0)while h<z&&j<26*z;j}}
Try it online!
0-indexed. Takes input as an array of characters.
Ruby, 121 114 112 108 bytes
->a{(0..25).min_by{|i|c=a[j=0];h=1;z=a.size;(i.times{c=c.next[-1]};j+=1;c==a[h]?h+=1:0)while h<z&&j<26*z;j}}
Try it online!
0-indexed. Takes input as an array of characters.
edited 7 hours ago
answered 10 hours ago
Kirill L.
3,4751218
3,4751218
add a comment |
add a comment |
up vote
3
down vote
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.
add a comment |
up vote
3
down vote
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.
add a comment |
up vote
3
down vote
up vote
3
down vote
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.
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.
edited 7 hours ago
answered 8 hours ago
Dennis♦
185k32295734
185k32295734
add a comment |
add a comment |
up vote
2
down vote
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!
add a comment |
up vote
2
down vote
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!
add a comment |
up vote
2
down vote
up vote
2
down vote
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!
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!
answered 9 hours ago
Galen Ivanov
6,11211032
6,11211032
add a comment |
add a comment |
up vote
2
down vote
Python 3, 191 178, bytes
I always see python 2 being used for golfing, let me know if it can do better, I'm new around here and I only know 3.
w=list(map(ord,input()))
a=
for i in range(26):
n=1
p=w[0]
for c in w:
while p!=c:
n+=1
p+=i
if p>122:p-=26
if n>len(w)*26:break
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 (max 99 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.
New contributor
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 bea+=[n]
; the first line would be shorter as mapw=list(map(ord,input()))
, (actually with your current algorithm, in Py2 you could droplist(...)
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
)
– Kirill L.
6 hours ago
Also, thatn>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.
– Kirill L.
6 hours ago
@KirillL.Yeah thatn>99
was a bit shifty so I changed it. Would you believe I spent a good while looking for a way to do if statements in one line like that and came up empty handed? I guess my googling skills aren't great. Thanks for all the advice!
– Terjerber
6 hours ago
BTW, you can still get rid of thatlist(...)
in Py3 and also of one extraif
: 165 bytes. Also, take a look at this tips topic, I'm sure you'll greatly improve your skills using advices from there!
– Kirill L.
5 hours ago
1
Although it looks terrible and goes against everything Python is, you can changen+=1
andp+=i
on seperate lines ton+=1;p+=i
on one.
– nedla2004
3 hours ago
|
show 1 more comment
up vote
2
down vote
Python 3, 191 178, bytes
I always see python 2 being used for golfing, let me know if it can do better, I'm new around here and I only know 3.
w=list(map(ord,input()))
a=
for i in range(26):
n=1
p=w[0]
for c in w:
while p!=c:
n+=1
p+=i
if p>122:p-=26
if n>len(w)*26:break
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 (max 99 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.
New contributor
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 bea+=[n]
; the first line would be shorter as mapw=list(map(ord,input()))
, (actually with your current algorithm, in Py2 you could droplist(...)
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
)
– Kirill L.
6 hours ago
Also, thatn>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.
– Kirill L.
6 hours ago
@KirillL.Yeah thatn>99
was a bit shifty so I changed it. Would you believe I spent a good while looking for a way to do if statements in one line like that and came up empty handed? I guess my googling skills aren't great. Thanks for all the advice!
– Terjerber
6 hours ago
BTW, you can still get rid of thatlist(...)
in Py3 and also of one extraif
: 165 bytes. Also, take a look at this tips topic, I'm sure you'll greatly improve your skills using advices from there!
– Kirill L.
5 hours ago
1
Although it looks terrible and goes against everything Python is, you can changen+=1
andp+=i
on seperate lines ton+=1;p+=i
on one.
– nedla2004
3 hours ago
|
show 1 more comment
up vote
2
down vote
up vote
2
down vote
Python 3, 191 178, bytes
I always see python 2 being used for golfing, let me know if it can do better, I'm new around here and I only know 3.
w=list(map(ord,input()))
a=
for i in range(26):
n=1
p=w[0]
for c in w:
while p!=c:
n+=1
p+=i
if p>122:p-=26
if n>len(w)*26:break
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 (max 99 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.
New contributor
Python 3, 191 178, bytes
I always see python 2 being used for golfing, let me know if it can do better, I'm new around here and I only know 3.
w=list(map(ord,input()))
a=
for i in range(26):
n=1
p=w[0]
for c in w:
while p!=c:
n+=1
p+=i
if p>122:p-=26
if n>len(w)*26:break
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 (max 99 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.
New contributor
edited 6 hours ago
New contributor
answered 7 hours ago
Terjerber
414
414
New contributor
New contributor
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 bea+=[n]
; the first line would be shorter as mapw=list(map(ord,input()))
, (actually with your current algorithm, in Py2 you could droplist(...)
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
)
– Kirill L.
6 hours ago
Also, thatn>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.
– Kirill L.
6 hours ago
@KirillL.Yeah thatn>99
was a bit shifty so I changed it. Would you believe I spent a good while looking for a way to do if statements in one line like that and came up empty handed? I guess my googling skills aren't great. Thanks for all the advice!
– Terjerber
6 hours ago
BTW, you can still get rid of thatlist(...)
in Py3 and also of one extraif
: 165 bytes. Also, take a look at this tips topic, I'm sure you'll greatly improve your skills using advices from there!
– Kirill L.
5 hours ago
1
Although it looks terrible and goes against everything Python is, you can changen+=1
andp+=i
on seperate lines ton+=1;p+=i
on one.
– nedla2004
3 hours ago
|
show 1 more comment
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 bea+=[n]
; the first line would be shorter as mapw=list(map(ord,input()))
, (actually with your current algorithm, in Py2 you could droplist(...)
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
)
– Kirill L.
6 hours ago
Also, thatn>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.
– Kirill L.
6 hours ago
@KirillL.Yeah thatn>99
was a bit shifty so I changed it. Would you believe I spent a good while looking for a way to do if statements in one line like that and came up empty handed? I guess my googling skills aren't great. Thanks for all the advice!
– Terjerber
6 hours ago
BTW, you can still get rid of thatlist(...)
in Py3 and also of one extraif
: 165 bytes. Also, take a look at this tips topic, I'm sure you'll greatly improve your skills using advices from there!
– Kirill L.
5 hours ago
1
Although it looks terrible and goes against everything Python is, you can changen+=1
andp+=i
on seperate lines ton+=1;p+=i
on one.
– nedla2004
3 hours ago
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
)– Kirill L.
6 hours ago
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
)– Kirill L.
6 hours ago
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.– Kirill L.
6 hours ago
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.– Kirill L.
6 hours ago
@KirillL.Yeah that
n>99
was a bit shifty so I changed it. Would you believe I spent a good while looking for a way to do if statements in one line like that and came up empty handed? I guess my googling skills aren't great. Thanks for all the advice!– Terjerber
6 hours ago
@KirillL.Yeah that
n>99
was a bit shifty so I changed it. Would you believe I spent a good while looking for a way to do if statements in one line like that and came up empty handed? I guess my googling skills aren't great. Thanks for all the advice!– Terjerber
6 hours ago
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!– Kirill L.
5 hours ago
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!– Kirill L.
5 hours ago
1
1
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.– nedla2004
3 hours ago
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.– nedla2004
3 hours ago
|
show 1 more comment
up vote
2
down vote
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.
add a comment |
up vote
2
down vote
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.
add a comment |
up vote
2
down vote
up vote
2
down vote
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.
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.
answered 3 hours ago
Dennis♦
185k32295734
185k32295734
add a comment |
add a comment |
up vote
1
down vote
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)
add a comment |
up vote
1
down vote
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)
add a comment |
up vote
1
down vote
up vote
1
down vote
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)
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)
edited 1 hour ago
answered 1 hour ago
Kevin Cruijssen
35.2k554186
35.2k554186
add a comment |
add a comment |
If this is an answer to a challenge…
…Be sure to follow the challenge specification. However, please refrain from exploiting obvious loopholes. Answers abusing any of the standard loopholes are considered invalid. If you think a specification is unclear or underspecified, comment on the question instead.
…Try to optimize your score. For instance, answers to code-golf challenges should attempt to be as short as possible. You can always include a readable version of the code in addition to the competitive one.
Explanations of your answer make it more interesting to read and are very much encouraged.…Include a short header which indicates the language(s) of your code and its score, as defined by the challenge.
More generally…
…Please make sure to answer the question and provide sufficient detail.
…Avoid asking for help, clarification or responding to other answers (use comments instead).
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f177404%2foptimal-alphabet-stepping%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Do we need to handle empty input?
– pizzapants184
17 hours ago
1
@pizzapants184 No. I've updated the question to specify the input will be non-empty
– Jo King
17 hours ago
Can we take input as an array of characters?
– Shaggy
14 hours ago
@Shaggy Sure you can
– Jo King
13 hours ago
Is there a reason this uses letters instead of numbers?
– Post Left Garf Hunter
7 hours ago