16
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ You should probably include this test case: aebcdjfghiqklmnopzrstuvwxy (output 1260 for Mr John Doe). This is the maximum possible - it consists of cycles of order 4, 5, 7, 9 (and an unchanged a), 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. \$\endgroup\$ – Martin Ender Jan 31 '15 at 13:43
  • \$\begingroup\$ @MartinBüttner Added with modification. \$\endgroup\$ – randomra Jan 31 '15 at 13:53
  • \$\begingroup\$ I'm a bit confused about how you come up with the number of turns. \$\endgroup\$ – FUZxxl Jan 31 '15 at 17:22
  • \$\begingroup\$ @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. \$\endgroup\$ – Martin Ender Jan 31 '15 at 18:18
  • 1
    \$\begingroup\$ As a side note, John File Marker aka EOF is totally amazing! \$\endgroup\$ – rev Feb 1 '15 at 0:58
9
\$\begingroup\$

Pyth, 16 bytes

JGfqzuXGJrQ0UTz1

Try it here.

Input should be given on two lines, name and then permutation. Permutation should be quoted. Name may be quoted or unquoted. For example:

"John Doe"
"aebcdjfghiqklmnopzrstuvwxy"

Gives 140.

Explanation:

                            Implicit:
                            z = input()              z is the name.
                            Q = eval(input())        Q is the permutation.
                            G = 'abcdefghijklmnopqrstuvwxyz'

JG                          J = G
  f             1           Starting at 1 and counting upwards, find
                            the first case where the following is true:
   qz                       z ==
     u       UTz            reduce, where the accumulator, G, is initialized to z on
      XG                    translate G
        J                   from the normal alphabet, J
         rQ0                to Q.lower().
\$\endgroup\$
  • \$\begingroup\$ Input method should be identical for the strings. \$\endgroup\$ – randomra Jan 31 '15 at 21:30
10
\$\begingroup\$

CJam, 31 27 25 24 bytes

l:A;lel:N{_A_$er_N#}g;],

Takes input in the form of:

aebcdjfghiqklmnopzrstuvwxy
Mr. John Doe

i.e. first line - alphabets, second line - name.

How it works:

l:A;lel:N{_A_$er_N#}g;],
l:A;                         "Read the alphabets from the 1st line in A and pop from stack";
    lel:N                    "Read the name in small caps from 2nd line and store in N";
         {         }g        "Run a while loop until we have the original name back again";
          _                  "Put a dummy string on stack just to keep count of times";
           A                 "Put the alphabets on stack";
            _$               "Copy them and sort the copy to get the correct order";
              er             "Transliterate the right keys with the wrong ones";
                _N#          "Copy the result and see if its equal to the original name";
                     ;]      "Pop the last name and wrap everything in an array";
                       ,     "Get the length now. Since we were putting a dummy string";
                             "on stack in each iteration of the while loop, this length";
                             "represents the number of times we tried typing the name";

Try it online here

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

Ruby, 58

->a,n{t=""+n
(1..2e3).find{t.tr!("a-zA-Z",a+a.upcase)==n}}

Explanation

  • Input is taken as arguments to a lambda.
  • Use Enumerable#find (thanks @Ventero!) and String#tr! to replace characters until the replaced String matches the real name.
\$\endgroup\$
  • \$\begingroup\$ ""+n is a bit shorter than n.dup, and you can save another byte by making creative use of Enumerable#find instead of using an explicit counter: (1..1e4).find{t.tr!(...)==n} \$\endgroup\$ – Ventero Jan 31 '15 at 16:55
  • \$\begingroup\$ Also, you can save a lot of bytes by making the input n lowercase \$\endgroup\$ – Optimizer Jan 31 '15 at 18:26
  • \$\begingroup\$ @Optimizer That doesn't seem to save me anything, Ruby's method to convert to lowercase is quite lengthy (I'd have to use n.downcase!). \$\endgroup\$ – britishtea Jan 31 '15 at 19:08
  • \$\begingroup\$ yeah, but then you dont have to do A-Z and +a.upcase \$\endgroup\$ – Optimizer Jan 31 '15 at 19:11
  • \$\begingroup\$ A-Z+a.upcase and n.downcase!\n have the same length :) \$\endgroup\$ – britishtea Jan 31 '15 at 19:19
2
\$\begingroup\$

CJam, 32 31 bytes

llel_2e3,{;'{,97>3$er_2$=}#)p];

Test it here. It takes the permutation on the first line, and the name on the second line of the input.

Explanation

llel_2e3,{;'{,97>3$er_2$=}#)p];
ll                              "Read both lines into strings.";
  el_                           "Convert the name to lower-case and duplicate.";
     2e3,                       "Get a range from 0 to 1999 to cover all possible results.";
         {               }#     "Find the first index where the block yields a true result.";
          ;                     "Discard the number, it's just a dummy.";
           '{,97>               "Create a string of the lower-case alphabet.";
                 3$             "Copy the permutation.";
                   er           "Substitute letters in the second copy of the name.";
                     _2$=       "Duplicate and check for equality with original name.";
                           )p   "Increment by 1 and print.";
                             ]; "Clear the stack to prevent extraneous output.";
\$\endgroup\$
2
\$\begingroup\$

Pyth 26

KGJ@GrQZfqJusm@zxKdGUTJ!!J

Try it online here.

There are quite a few unfortunate consequences that cost this program bytes, like having to store G in K to use it in the reduce, as well as needing to use not(not(J)) to start the filter. Because of this, I expect this can still be golfed.

This is a program that takes input like:

aebcdjfghiqklmnopzrstuvwxy
'John Doe'

(Note the lack of quotes in the first argument)

Explanation to come after crippling exhaustion ;)

\$\endgroup\$
  • \$\begingroup\$ Should I repeat my previous comment ') \$\endgroup\$ – Optimizer Jan 31 '15 at 16:58
  • \$\begingroup\$ @Optimizer :P I lost that last one ;) \$\endgroup\$ – FryAmTheEggman Jan 31 '15 at 17:03
  • \$\begingroup\$ You were saying ? ;) \$\endgroup\$ – Optimizer Jan 31 '15 at 17:23
1
\$\begingroup\$

Haskell 131 bytes

import Data.Char
h n=(!!((ord n)-97))
g s n m|n==m=1|0<1=1+g s(h n s)m
f s=foldr1 lcm.map((\x->g s(h x s)x).toLower).filter isAlpha

Call f with the permutation string and name to get the result

Explanation

-- h finds the mapping of a character given the permutation
h :: Char   -> -- Character to map
     String -> -- Character permutation
     Char      -- Mapped character

-- g finds the number of character mappings required to reach a given character
-- by calling h on the given character every time it calls itself.
g :: String -> -- The character permutation
     Char   -> -- The current character
     Char   -> -- The character to find
     Int       -- The number of mapped to find the character

-- f finds the number of mappings required to return the given string back to itself
-- by finding the lowest common multiple of the period of all the characters in the
-- given string
g :: String -> -- The permutation string
     String -> -- The string to get back
     Int       -- The final answer
\$\endgroup\$
1
\$\begingroup\$

GolfScript (33 bytes)

~{32|}%\:A&{.{A$?A=}%.-1$=!}do],(

Takes input as two (single- or double-) quoted strings separated by any amount of whitespace; e.g.

'abcfdeghijklmnopqrstuvwxyz' 'Mr. John Doe'

Online demo

Dissection

~           # Eval. Stack: perm name
{32|}%      # Lower-case name (also affects non-alphabetic characters but...)
\:A&        # Store perm in A and filter name to alphabetic characters, giving str_0
{           # do-while loop. Stack: str_0 str_1 ... str_i
  .         #   Duplicate str_i
  {A$?A=}%  #   tr 'a-z' perm   giving str_{i+1}
  .-1$=!    #   Loop while str_{i+1} != str_0
}do         # end do-while loop
],(         # Gather the sequence of permuted strings in an array and take its length - 1
            # to account for containing str_0 twice

The transliteration relies on the fact that all the characters are affected (it's {'ABC'?'abc'=}% with the sorted string A$ replacing 'ABC' and the permutation A replacing 'abc'); the more general alternatives don't save enough because the filter to alphabetic characters is so cheap.

This also relies on -1$ to access the bottom of the stack, which is a relatively rare GS trick.

\$\endgroup\$

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.