Набор текста с зашифрованными клавишами

16

Ваш друг не слишком хорошо разбирается в компьютерах, так что в качестве практической шутки кто-то написал буквы (az) на своей клавиатуре. Когда он сел и попытался набрать свое имя, глядя на клавиатуру, он понял, что буквы зашифрованы и попросил вашей помощи.

Вы умны, так что вы знаете, что если он напечатает свое имя, а затем повторно напечатает то, что появляется на экране вместо своего имени, он в конечном итоге преуспеет, введя свое имя. Вы также любезны и переставляете ключи, но хотите знать, сколько ходов потребуется, чтобы добиться успеха.

Ваша задача - написать программу или функцию, которая при перемешивании букв и имени друга вычисляет количество ходов.

Входные данные:

  • В качестве входных данных приводятся две строки в структуре, удобной для вашего языка.
  • Первая строка - это список новых строчных букв в алфавитном порядке старых. (Первый символ - это тот, который находится в позиции a, последний - в позицииz .) В строке всегда будут происходить некоторые изменения.
  • Вторая строка - это имя. Он может содержать любой печатный символ ascii, но перетасовываются только прописные и строчные буквы алфавита, если таковые имеются. Само имя не может быть перетасовано в al.

Выходные данные:

  • Выходное значение представляет собой одно целое число, минимально необходимое число витков. Новая строка необязательна.

Примеры:

Ввод: 'abcfdeghijklmnopqrstuvwxyz' 'Mr. John Doe'(d, e, f позиции изменены)

Вывод: 3(Показанные имена: Mr. John Fod=> Mr. John Eof=> Mr. John Doe)

Вход: 'nopqrstuvwxyzabcdefghijklm' 'Mr. John Doe'( шифр ROT13 )

Вывод: 2(Любое входное имя, содержащее буквы, будет 2обходиться, чтобы создать оригинальное имя.)

Входные данные: 'aebcdjfghiqklmnopzrstuvwxy' 'John Doe'

Выход: 140

Это код-гольф, поэтому выигрывает самый короткий вход.

randomra
источник
1
Вероятно, вам следует включить этот тестовый пример: aebcdjfghiqklmnopzrstuvwxy(вывод 1260 для Mr John Doe). Это максимально возможное значение - оно состоит из циклов порядка 4, 5, 7, 9 (и без изменений a), и каждое имя, которое содержит хотя бы одну букву из каждого цикла, даст 1260. И я предполагаю, что в качестве входных данных взят сам алфавит или использование незатронутого имени также являются важными крайними случаями.
Мартин Эндер
@ MartinBüttner Добавлено с модификацией.
Рандора
Я немного озадачен тем, как вы придумали количество ходов.
FUZxxl
@FUZxxl В общем, вы можете разложить перестановку на циклы , а затем проверить, какие циклы содержат символы из имени. Результатом является LCM длин этих циклов (циклы по символам, не указанным в имени, разумеется, не имеют значения). Тем не менее, для этой задачи в этом нет необходимости ... просто выполняйте подстановки, пока не найдете исходное имя и не посчитайте, как часто вам приходилось заменять.
Мартин Эндер
1
В качестве примечания, John File Marker aka EOFсовершенно потрясающий!
оборот

Ответы:

9

Pyth, 16 байт

JGfqzuXGJrQ0UTz1

Попробуй это здесь.

Входные данные должны быть указаны в двух строках: имя и перестановка. Перестановка должна быть в кавычках. Имя может быть указано или без кавычек. Например:

"John Doe"
"aebcdjfghiqklmnopzrstuvwxy"

Дает 140.

Объяснение:

                            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().
isaacg
источник
Метод ввода должен быть одинаковым для строк.
Рандора
10

CJam, 31 27 25 24 байта

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

Принимает вход в виде:

aebcdjfghiqklmnopzrstuvwxy
Mr. John Doe

т.е. первая строка - алфавиты, вторая строка - имя.

Как это работает :

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";

Попробуйте онлайн здесь

оптимизатор
источник
5

Руби, 58

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

объяснение

  • Входные данные принимаются в качестве аргументов лямбда-выражения.
  • Используйте Enumerable#find(спасибо @Ventero!) И String#tr!заменяйте символы, пока заменяемое не совпадет Stringс настоящим именем.
britishtea
источник
""+nнемного короче n.dup, и вы можете сохранить другой байт, творчески используя Enumerable#findвместо явного счетчика:(1..1e4).find{t.tr!(...)==n}
Ventero
Кроме того, вы можете сэкономить много байтов, введя строчные буквы n
Оптимизатор
@Optimizer Это, кажется, ничего не спасает, метод Ruby для преобразования в нижний регистр довольно длинный (я должен был бы использовать n.downcase!).
Британцы
да, но тогда вам не нужно делать A-Zи+a.upcase
Оптимизатор
A-Z+a.upcaseи n.downcase!\nимеют одинаковую длину :)
британцы
2

CJam, 32 31 байт

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

Проверьте это здесь. Он принимает перестановку в первой строке и имя во второй строке ввода.

объяснение

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.";
Мартин Эндер
источник
2

Пиф 26

KGJ@GrQZfqJusm@zxKdGUTJ!!J

Попробуйте это онлайн здесь.

Существует довольно много неприятных последствий, которые стоят этой программе в байтах, например, необходимость хранить G в K для использования в уменьшении, а также необходимость не использовать (не (J)) для запуска фильтра. Из-за этого я ожидаю, что это все еще можно сыграть в гольф.

Это программа, которая принимает данные как:

aebcdjfghiqklmnopzrstuvwxy
'John Doe'

(Обратите внимание на отсутствие кавычек в первом аргументе)

Объяснение придет после сокрушительного истощения;)

FryAmTheEggman
источник
Должен ли я повторить свой предыдущий комментарий?)
Оптимизатор
@Optimizer: PI потерял этот последний;)
FryAmTheEggman
Ты говорил ? ;)
Оптимизатор
1

Haskell 131 байт

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

Позвоните fсо строкой и именем перестановки, чтобы получить результат

объяснение

-- 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
Jmac
источник
1

GolfScript (33 байта)

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

Принимает ввод в виде двух (одинарных или двойных) строк в кавычках, разделенных любым количеством пробелов; например

'abcfdeghijklmnopqrstuvwxyz' 'Mr. John Doe'

Онлайн демо

рассечение

~           # 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

Транслитерации опираются на тот факт , что все символы затронуты (это {'ABC'?'abc'=}%с отсортированной строкой A$замены 'ABC'и перестановка Aзамены 'abc'); более общие альтернативы не экономят достаточно, потому что фильтр к буквенным символам настолько дешев.

Это также зависит от -1$доступа к нижней части стека, что является относительно редким трюком GS.

Питер Тейлор
источник