Введение

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

Для этой задачи мы рассмотрим двустороннее палиндромное закрытие, так что

• Левое палиндромное закрытие входной строки - самый короткий палиндром, который начинается с входной строки.
• Правое палиндромное закрытие входной строки - самый короткий палиндром, который заканчивается входной строкой.
• Двустороннее палиндромное замыкание входной строки является короче левого или правого палиндромного замыкания входной строки.

задача

Ваша задача проста. Если задана строка (состоящая только из печатного ASCII, новых строк и пробелов), выведите двустороннее палиндромное замыкание этой строки. В случае галстука допустимы выходные данные либо левого, либо правого палиндромного замыкания.

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

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

Несколько примеров:

<Input>   -> <Output>
"abcdef"  -> "abcdefedcba"  (or "fedcbabcdef")
"abcba"   -> "abcba"
"abcb"    -> "abcba"
"cbca"    -> "acbca"

Начальная идея идёт в VisualMelon, последняя идея с помощью Мартина и Згарба

Термины палиндромное закрытие, лево-паллиндромное закрытие и право-палиндромное закрытие были впервые использованы и определены в этой статье .

Пиф, 22 19

hfq_TTsm,+z_d+_dzyz

Попробуйте онлайн .

объяснение

Двустороннее палиндромное замыкание имеет либо форму, AXлибо XA, где Xявляется входной строкой и Aявляется подстрокой X. На самом деле я должен быть непрерывной подстрокой X, префиксом для одной формы, суффиксом для другой формы. Но мне плевать на эти ошибки. Подстрока (смежная или нет) - все, что мне нужно в Pyth.

                        Implicit: z = raw_input() // Read a string
                 yz     A list with all substrings (contiguous or not) of z
       m                For each of these substrings d, build
        ,                  a pair of two strings:
         +z_d              ( z + inveres(d) ,
             +_dz            inverse(d) + z )
      s                 Sum (put all created pairs into a list)
 fq_TT                  filter elements T, where inverse(T) == T (Palindrom)
h                          Take the first element

редактировать

Старая версия заказывала строки после фильтрации по длине .olN.... Только что понял, что yвозвращает подстроки, упорядоченные по длине. Так что эти палиндромы уже отсортированы.

Зажим , 40

(sl`f[a=ava}+m[i+v+ixx}Rlxm[i+xvu0ix}Rlx

пример

Documents>java -jar Clip4.jar palindrome.clip
abcb
abcba

объяснение

(sl`                                        .- The shortest                     -.
    f[a=ava}                                .- palindrome                       -.
            +                               .- among the following two sets:    -.
             m[i      }Rlx                  .- For each number up to length(x)  -.
                +                           .- combine                          -.
                 v+ix                       .- the last i chars of x, reversed  -.
                     x                      .- and x.                           -.
                          m[i       }Rlx    .- For each number up to length(x)  -.
                             +              .- combine                          -.
                              x             .- x and                            -.
                               vu0ix        .- the first i chars of x, reversed.-.

CJam, 30 байтов

Очень надеялся увидеть ответ CJam к настоящему времени.

q:Q,{)QW%/(Q+Q@+s}%{,}${_W%=}=

Я действительно ненавижу это {,}$ блок там, но я получаю неупорядоченный список возможных палиндромов из-за алгоритма генерации, который я использую.

Объяснение кода

q:Q,{            }%             "Read the input string, store in Q, take length and";
                                "run the code block that many times";
     )QW%                       "Increment the iteration index and Put reversed Q on stack";
         /                      "Split reversed Q into parts of incremented iteration index";
          (Q+                   "Take out the first part and prepend it to Q";
             Q@+s               "Take the rest of the parts and append them to Q";
                   {,}$         "At this point, we have all possible prepended and appended";
                                "sequences of the input string. Sort them by length";
                       {_W%=}=  "Take the first sequence which is a palindrome";

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

Python 2, 115 113 109 105 96 байт

f=lambda x:[x for x in sum([[x[:~i:-1]+x,x+x[i::-1]]for i in range(len(x))],[])if x==x[::-1]][0]

Можно надеяться, что гольф дальше. Биты, возможно, заслуживают внимания:

• используя сумму для двух пониманий списка в одном
• построение терминов в отсортированном порядке, чтобы избежать необходимости в min (предложено @Jakube)

Mathematica, 96 байт

Должен быть более элегантный способ, чем этот ...

""<>#&@@SortBy[r=Reverse;#/.{b___,a__/;r@{a}=={a}}:>{b,r@{b,a}}&/@{r@#,#}&@Characters@#,Length]&

Это определяет безымянную функцию, которая принимает строку и возвращает результат.

Основная идея заключается в

• Разбейте строку на Characters.
• Сформируйте массив с этим списком и его обратным.

• Используйте сопоставление с образцом, чтобы найти правильный палиндромик каждого из них:

  {b___,a__/;r@{a}=={a}}:>{b,r@{b,a}}
  

  Обратите внимание, что это на самом деле не возвращает плоский список. Например, {a,b,c}вы получите

  {a,b,{c,b,a}}
  

• Сортировать два результата по длине.

• Выберите короче и присоедините его обратно в строку с ""<>#&@@.

Брахилог (2), 6 байт, языковые проблемы

~{↔?a}

Попробуйте онлайн!

Как обычно для Brachylog, это функция, а не полная программа.

объяснение

~{↔?a}
~{   }   Find a value that produces {the input} upon doing the following:
  ↔        reversing it;
   ?       asserting that we still have the same value;
    a      and taking either a prefix, or a suffix.

Насколько я знаю (это не мой язык, но кажется маловероятным), a он не был добавлен в Brachylog для этой задачи, но он очень удобен. Мы используем метод «обратный, и утверждаем, что он не изменился», чтобы утверждать, что найденное нами значение является палиндромом.

Что касается того, почему это дает самый короткий палиндром, порядок оценки Пролога (и, следовательно, Брахилога) сильно зависит от того, что он оценивает первым. В данном случае это «обратная» команда, и (как и большинство операций со списками) она устанавливает порядок оценки, целью которого является минимизация размера результирующего списка. Так как это равняется размеру вывода, программа довольна тем, что случайно свела абсолютно правильные вещи, то есть мне не нужно было добавлять какие-либо явные подсказки.

Рубин, 76 + 2 = 78

С флагами командной строки -pl( lможет не понадобиться в зависимости от того, как вы делаете ввод), запустите

$_=[[$_,r=$_.reverse]*"\0",r+"\0#$_"].min_by{|s|s.sub!(/(.*)\0\1/){$1}.size}

Для данной строки 'abaa' генерирует строки 'cbca 0 acbc' и 'acbc 0 cbca', где 0 - непечатаемый символ с кодом ascii 0. Затем удаляется одна копия самой длинной повторяющейся строки, обрамляющей 0 он находит в каждой, «a» в первом и «cbc» во втором, чтобы получить два замыкания. Затем выводится кратчайший результат.

Единственная действительно странная вещь в коде для игры в гольф состоит в том, что он сокращает строки на месте при сортировке, и с этим можно обойтись, потому min_byчто блок выполняется только один раз для сравниваемого элемента (как потому, что это преобразование Шварца, так и потому, что существует только два элементы для сравнения).

Python 3, 107 байт

f=lambda a:[i for i in[a[:i:-1]*j+a+a[-1-i::-1]*(1-j)for i in range(len(a))for j in(0,1)]if i==i[::-1]][-1]

Тестировать:

>>> print("\n".join(map(f, ["abcdef", "abcba", "abcb", "cbca"])))
abcdefedcba
abcba
abcba
acbca

Haskell, 107 байт

import Data.List
r=reverse
f s=snd$minimum[(length x,x)|x<-map(s++)(tails$r s)++map(++s)(inits$r s),x==r x]

Тест:

*Main> mapM_ (putStrLn.f) ["abcdef", "abcba", "abcb", "cbca"]
abcdefedcba
abcba
abcba
acbca

J, 66 62 байта

3 :'>({~[:(i.>./)(#%~[-:|.)@>),(<@([,|.@{.~)"#:i.@#"1)y,:|.y'

Довольно просто. Два трюка, которые я использую:

Правое палиндромное закрытие - это левое палиндромное закрытие перевернутой струны.

Нахождение длины строки с минимальной длиной и палиндромом с помощью выражения min (is_palindrome / length).

   f=.3 :'>({~[:(i.>./)(#%~[-:|.)@>),(<@([,|.@{.~)"#:i.@#"1)y,:|.y'

   f 'lama'
lamal

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