16
2
Your friend isn't too good with computers so as a practical joke someone scrambled the letters (a-z) on his keyboard. When he sit down and tried to type his name looking at the keyboard he realized that the letters are scrambled and asked your help.
You are smart so you know that if he types his name and then repeatedly retypes what comes up on the screen instead of his name he will succeed inputting in his name eventually. You are also kind and rearrange the keys but want to know how many turns would it take to succeed.
Your task is to write a program or function that given the shuffling of the letters and the friend's name computes the number of turns.
Input details:
- Two string are given as input in a structure convenient for your language.
- The first string is the list of the new lowercase letters in alphabetical order of the old ones. (The first character is the one that is at the position of
a
, last one is at the position ofz
.) Some change will always occur in the string. - The second string is the name. It could contain any printable ascii character but only the upper and lowercase alphabetical characters will be shuffled if any. The name itself might not get shuffled at al.
Output details:
- Output is a single integer the number of turns minimally required. Newline is optional.
Examples:
Input:
'abcfdeghijklmnopqrstuvwxyz' 'Mr. John Doe'
(d, e, f positions changed)
Output:
3
(The shown names are: Mr. John Fod
=> Mr. John Eof
=> Mr. John Doe
)
Input:
'nopqrstuvwxyzabcdefghijklm' 'Mr. John Doe'
(the ROT13 cipher)
Output:
2
(Any input name that contains letters will take 2
rounds to produce the original name.)
Input:
'aebcdjfghiqklmnopzrstuvwxy' 'John Doe'
Output:
140
This is code-golf so the shortest entry wins.
1You should probably include this test case:
aebcdjfghiqklmnopzrstuvwxy
(output 1260 forMr John Doe
). This is the maximum possible - it consists of cycles of order 4, 5, 7, 9 (and an unchangeda
), and every name that contains at least one letter from each cycle will yield 1260. And I guess taking the alphabet itself as input or using an unaffected name are also important edge cases. – Martin Ender – 2015-01-31T13:43:09.737@MartinBüttner Added with modification. – randomra – 2015-01-31T13:53:43.503
I'm a bit confused about how you come up with the number of turns. – FUZxxl – 2015-01-31T17:22:02.417
@FUZxxl In general, you can decompose the permutation into cycles, then you check which cycles include characters from the name. The result is the LCM of the lengths of those cycles (cycles through characters not in the name are irrelevant, of course). However, for this challenge, that's not really necessary... just perform the substitutions until you hit the original name and count how often you had to substitute.
– Martin Ender – 2015-01-31T18:18:53.873Clarification: If no keys were moved, is the output 1? 0? either? – isaacg – 2015-01-31T18:20:27.853
@isaacg 1 as the name would show up in the first try. – randomra – 2015-01-31T18:25:49.363
1As a side note, John File Marker aka
EOF
is totally amazing! – rev – 2015-02-01T00:58:00.260