Палиндромизирующие струны

30

Введение

Для тех, кто не знает, палиндром - это когда строка равна строке в обратном направлении (за исключением взаимодействия, пробелов и т. Д.). Примером палиндрома является:

abcdcba

Если вы измените это, вы получите:

abcdcba

Что то же самое. Поэтому мы называем это палиндромом. Чтобы палиндромизировать вещи, давайте рассмотрим пример строки:

adbcb

Это не палиндром. Чтобы палиндромизировать это, нам нужно объединить обратную строку в исходную строку справа от исходной строки , оставив обе версии без изменений. Чем короче, тем лучше.

Первое, что мы можем попробовать, это следующее:

adbcb
bcbda
^^ ^^

Не все символы совпадают, поэтому это не правильная позиция для перевернутой строки. Идем на один шаг вправо:

adbcb
 bcbda
 ^^^^

Это также не соответствует всем персонажам. Мы идем еще один шаг вправо:

adbcb
  bcbda

На этот раз все персонажи совпадают . Мы можем объединить обе строки, оставив нетронутыми . Окончательный результат:

adbcbda

Это палиндромизированная строка .


Задание

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


Контрольные примеры

Input     Output

abcb      abcba
hello     hellolleh
bonobo    bonobonob
radar     radar
hex       hexeh

Это , поэтому выигрывает представление с наименьшим количеством байтов!

Аднан
источник
3
Связанный.
Згарб
6
Вы должны указать, что обратная строка должна быть объединена в исходную строку с обратной строкой справа. Если это может пойти слева, obonoboбыло бы лучшим решением для контрольного примера.
Уровень Река St
2
@LevelRiverSt +1 только потому, что «обонобо» такое удивительное слово
Натаниэль
1
@ Натаниэль Спасибо, но bono b o nobэто целое предложение. Какая разница между Богом и Боно? Бог не бродит по Дублину, притворяясь Боно ;-)
Level River St

Ответы:

5

Желе, 11 10 байт

ṫỤfU$Ḣœ^;U

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

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

ṫỤfU$Ḣœ^;U  Main link. Argument: s (string)

 Ụ          Yield all indices of s, sorted by their corr. character values.
ṫ           Tail; for each index n, remove all characters before thr nth.
            This yields the list of suffixes of s, sorted by their first character,
            then (in descending order) by length.
    $       Combine the two links to the left into a chain:
   U        Upend; reverse all suffixes.
  f         Filter; only keep suffixes that are also reversed suffixes.
            This gives the list of all palindromic suffixes. Since all of them
            start with the same letter, they are sorted by length.
     Ḣ      Head; select the first, longest palindromic suffix.
      œ^    Multiset symmetric difference; chop the selected suffix from s.
         U  Upend; yield s, reversed.
        ;   Concatenate the results to the left and to the right.
Деннис
источник
15

Pyth (commit b93a874), 11 байт

.VkI_IJ+zbB

Тестирование

Этот код использует ошибку в текущей версии Pyth , commit b93a874 . Ошибка в том, что _IJ+zbон анализируется так, как если бы он был q_J+zbJ+zb, что эквивалентно тому _I+zb+zb, когда он должен (по замыслу Pyth) проектироваться как q_J+zbJ, что эквивалентно _I+zb. Это позволяет мне сохранить байт - после исправления ошибки правильный код будет .VkI_IJ+zbJB. Я объясню этот код вместо.

По сути, код перебирает все возможные строки до тех пор, пока не найдет самую короткую строку, которая может быть добавлена ​​к входным данным для формирования палиндрома, и выведет объединенную строку.

.VkI_IJ+zbJB
                z = input()
.Vk             For b in possible strings ordered by length,
       +zb      Add z and b,
      J         Store it in J,
    _I          Check if the result is a palindrome,
   I            If so,
          J     Print J (This line doesn't actually exist, gets added by the bug.
          B     Break.
isaacg
источник
Как вы пришли к такому коду? Это едва читаемый и абсолютно не понятный кем-то, кто не знаком с Питом. Какова цель такого языка.
anukul
5
@momo Цель языка - написать короткий код для развлечения. Это рекреационная деятельность. Я могу написать это, потому что у меня много практики, и потому что я изобрел язык. Я знаю, что это непонятно для тех, кто не знает языка, поэтому я включил объяснение.
Исаак
13

Python, 46 байт

f=lambda s:s*(s==s[::-1])or s[0]+f(s[1:])+s[0]

Если строка является палиндромом, верните ее. В противном случае, поместите первую букву вокруг рекурсивного результата для оставшейся части строки.

Пример разбивки:

f(bonobo)
b  f(onobo) b
b o f(nobo) o b 
b o n f(obo) n o b
b o n obo n o b
XNOR
источник
Я думаю, что вы можете сохранить байт, если используете противоположное условие ( s!=s[::-1])
aditsu
@aditsu Это работает, но с использованием умножения еще короче.
xnor
9

Haskell, 36 байт

f s|s==reverse s=s|h:t<-s=h:f t++[h]

Более читабельно:

f s
 |s==reverse s = s
 |(h:t)<-s     = h:(f t)++[h]

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

Строка sразбита на h:tвторого охранника, избегая наполнителя 1>0для этого случая. Это короче, чем s@(h:t)для ввода.

XNOR
источник
5

Pyth - 16 12 байт

4 байта сохранены благодаря @FryAmTheEggman.

FGITW, много игры в гольф возможно.

h_I#+R_Q+k._

Тестовый пакет .

Maltysen
источник
5

Brachylog , 16 6 5 байт (не конкурирует)

:Ac.r

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

Когда я опубликовал свой первоначальный ответ, он все еще был на старой реализации в Java. Поскольку я перепрограммировал все в Прологе, теперь он работает так, как и должно быть.

объяснение

(?):Ac.        Output is the concatenation of Input with another unknown string A
      .r(.)    The reverse of the Output is the Output

Обратное распространение делает так, что первое допустимое значение для Aнего будет самым коротким, которое вы можете объединить с Input, чтобы сделать его палиндромом.

Альтернативный раствор, 5 байтов

~@[.r

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

Fatalize
источник
4

JavaScript (ES6), 92 байта

(s,a=[...s],r=a.reverse().join``)=>s.slice(0,a.findIndex((_,i)=>r.startsWith(s.slice(i))))+r

Вычисляет и вырезает перекрытие между исходной строкой и ее обращением.

Нил
источник
4

Сетчатка, 29 25

$
¶$_
O^#r`.\G
(.+)¶\1
$1

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

Большое спасибо Мартину за 11 сохраненных байтов!

Это просто создает обратную строку и соединяет их вместе. Единственная действительно интересная часть этого - метод обращения: O^#r`.\Gэто делается с помощью режима сортировки. Мы сортируем буквы второй строки (те, которые не являются символами новой строки и являются последовательными от конца строки, благодаря символу \G) по их числовому значению, которое, поскольку чисел нет, равно 0. Затем мы обращаем порядок результатов этой стабильной сортировки с ^опцией. Все кредиты за необычное использование \Gпринадлежат Мартину :)

FryAmTheEggman
источник
3

CJam, 18

q__,,{1$>_W%=}#<W%

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

Объяснение:

q         read the input
__        make 2 copies
,,        convert the last one to a range [0 … length-1]
{…}#      find the first index that satisfies the condition:
  1$>     copy the input string and take the suffix from that position
  _W%=    duplicate, reverse and compare (palindrome check)
<         take the prefix before the found index
W%        reverse that prefix
          at the end, the stack contains the input string and that reversed prefix
aditsu
источник
3

Луа, 89 88 байт

Я победил Javascript! \ o / Сохранено 1 байт благодаря @LeakyNun ^^

Это полная программа, принимающая входные данные в качестве аргумента командной строки.

i=1s=...r=s:reverse()while s:sub(i)~=r:sub(0,#r-i+1)do i=i+1 end print(s..r:sub(#r-i+2))

ungolfed

i=1                             -- initialise i at 1 as string are 1-indexed in lua
s=...                           -- use s as a shorthand for the first argument
r=s:reverse()                   -- reverse the string s and save it into r
while(s:sub(i)~=r:sub(0,#r-i+1))-- iterate while the last i characters of s
do                              -- aren't equals to the first i characters of r
  i=i+1                         -- increment the number of character to skip
end
print(s..r:sub(#r-i+2))         -- output the merged string
Katenkyo
источник
Я полагаю, скобки рядом whileможно удалить?
Утренняя монахиня
@LeakyNun, конечно, они могут ^^
Katenkyo
Не можете сделать i=i+1end?
Эрик Outgolfer
1
@ EʀɪᴋᴛʜᴇGᴏʟғᴇʀ К сожалению, я не могу. Это попыталось бы оценить 1endкак шестнадцатеричное число. Как правило, вы не можете использовать [abcdef]непосредственно после числа, не считая его шестнадцатеричным. Есть еще одно исключение 0x.
Катенкё
3

Пролог, 43 байта

a(S):-append(S,_,U),reverse(U,U),writef(U).

Это предполагает строку кодов в качестве входных данных, например, в SWI-Prolog 7: a(`hello`).

объяснение

Это в основном порт моего ответа на брахилог.

a(S) :-               % S is the input string as a list of codes
    append(S,_,U),    % U is a list of codes resulting in appending an unknown list to S
    reverse(U,U),     % The reverse of U is U
    writef(U).        % Write U to STDOUT as a list of codes
Fatalize
источник
3

Октава, 78 75 байт

Сохранено 3 байта благодаря E ᴛʜᴇ Gᴏʟғᴇʀ!

function p=L(s)d=0;while~all(diag(s==rot90(s),d++))p=[s fliplr(s(1:d))];end

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

мерный стакан
источник
2

Perl, 37 байт

Основано на ответе xnor.

Включает +2 для -lp

Запустить с вводом на STDIN, например

palindromize.pl <<< bonobo

palindromize.pl:

#!/usr/bin/perl -lp
s/.//,do$0,$_=$&.$_.$&if$_!~reverse
Тон Хоспел
источник
1

J, 20 байт

,[|.@{.~(-:|.)\.i.1:

Это монадический глагол. Попробуй это здесь. Использование:

   f =: ,[|.@{.~(-:|.)\.i.1:
   f 'race'
'racecar'

объяснение

Я использую тот факт, что палиндромизация S - это S + reverse (P) , где P - самый короткий префикс S , удаление которого приводит к палиндрому. В J немного неуклюже выполнить поиск первого элемента массива, который удовлетворяет предикату; отсюда индексация.

,[|.@{.~(-:|.)\.i.1:  Input is S.
        (    )\.      Map over suffixes of S:
         -:             Does it match
           |.           its reversal? This gives 1 for palindromic suffixes and 0 for others.
                i.1:  Take the first (0-based) index of 1 in that array.
 [   {.~              Take a prefix of S of that length: this is P.
  |.@                 Reverse of P.
,                     Concatenate it to S.
Zgarb
источник
1

Haskell, 68 байт

import Data.List
f i=[i++r x|x<-inits i,i++r x==x++r i]!!0
r=reverse

Пример использования: f "abcb"-> "abcba".

Выполняйте поиск по initsвходным данным i(например, inits "abcb"-> ["", "a", "ab", "abc", "abcb"]) до тех пор, пока не найдете тот, к которому он добавлен в обратном направлении, чтобы iпостроить палиндром.

Ними
источник
Не r=reverseнужно идти раньше f i=...?
Эрик Outgolfer
@ EʀɪᴋᴛʜᴇGᴏʟғᴇʀ: Нет, вы можете использовать любой заказ.
Ними,
Я обошелся в 46 байтов. Могу поспорить, что это может быть сделано еще лучше.
theonlygusti
@theonlygusti: см . ответ Xnor .
Ними
1

MATL , 17 16 байт

Слабое вдохновение в ответе CJam от @ aditsu .

`xGt@q:)PhttP=A~

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

объяснение

`        % Do...while loop
  x      %   Delete top of stack, which contains a not useful result from the
         %   iteration. Takes input implicitly on first iteration, and deletes it
  G      %   Push input
  t      %   Duplicate
  @q:    %   Generate range [1,...,n-1], where n is iteration index. On the  first
         %   iteration this is an empty array
  )      %   Use that as index into copy of input string: get its first n elements
  Ph     %   Flip and concatenate to input string
  t      %   Duplicate. This will be the final result, or will be deleted at the
         %   beginning of next iteration
  tP     %   Duplicate and flip
  =A~    %   Compare element-wise. Is there some element different? If so, the
         %   result is true. This is the loop condition, so go there will be a 
         %   new iteration. Else the loop is exited with the stack containing
         %   the contatenated string
         % End loop implicitly
         % Display stack contents implicitly
Луис Мендо
источник
1

Рубин, 44 байта

Этот ответ основан на решениях xnor Python и Haskell .

f=->s{s.reverse==s ?s:s[0]+f[s[1..-1]]+s[0]}
Sherlock9
источник
Не можете сделать ==s?s:?
Эрик Outgolfer
@ EʀɪᴋᴛʜᴇGᴏʟғᴇʀ irb бросает приступ, если я попробую. Должно быть что - то делать с тем, как он разбирает ?между ?:для троичного и ?x == 'x'замены используется с Ruby 1.9
Sherlock9
1

Oracle SQL 11.2, 195 байт

SELECT MIN(p)KEEP(DENSE_RANK FIRST ORDER BY LENGTH(p))FROM(SELECT:1||SUBSTR(REVERSE(:1),LEVEL+1)p FROM DUAL WHERE SUBSTR(:1,-LEVEL,LEVEL)=SUBSTR(REVERSE(:1),1,LEVEL)CONNECT BY LEVEL<=LENGTH(:1));

Un-golfed

SELECT MIN(p)KEEP(DENSE_RANK FIRST ORDER BY LENGTH(p))
FROM (
       SELECT :1||SUBSTR(REVERSE(:1),LEVEL+1)p 
       FROM   DUAL 
       WHERE  SUBSTR(:1,-LEVEL,LEVEL)=SUBSTR(REVERSE(:1),1,LEVEL)
       CONNECT BY LEVEL<=LENGTH(:1)
     );
школа для водителей
источник
1

Серьезно, 34 байта

╩╜lur`╜╨"Σ╜+;;R=*"£M`MΣ;░p╜;;R=I.

Последний символ является неразрывным пробелом (ASCII 127 или 0x7F).

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

Объяснение:

╩╜lur`╜╨"Σ╜+;;R=*"£M`MΣ;░p╜;;R=I.<NBSP>
╩                                        push inputs to registers (call the value in register 0 "s" for this explanation)
 ╜lur                                    push range(0, len(s)+1)
     `              `M                   map (for i in a):
      ╜╨                                   push all i-length permutations of s
        "        "£M                       map (for k in perms):
         Σ╜+                                 push s+''.join(k) (call it p)
            ;;R=                             palindrome test
                *                            multiply (push p if palindrome else '')
                      Σ                  summation (flatten lists into list of strings)
                       ;░                filter truthy values
                         p               pop first element (guaranteed to be shortest, call it x)
                          ╜;;R=I         pop x, push s if s is palindromic else x
                                .<NBSP>  print and quit
Mego
источник
1

C #, 202 байта

Я пытался.

class P{static void Main(string[]a){string s=Console.ReadLine(),o=new string(s.Reverse().ToArray()),w=s;for(int i=0;w!=new string(w.Reverse().ToArray());){w=s.Substring(0,i++)+o;}Console.WriteLine(w);}}

Ungolfed:

class P
{
    static void Main(string[] a)
    {
        string s = Console.ReadLine(), o = new string(s.Reverse().ToArray()), w = s;
        for(int i = 0; w!=new string(w.Reverse().ToArray());)
        {
            w = s.Substring(0, i++) + o;
        }
        Console.WriteLine(w);
        Console.ReadKey();
    }

}

Кто-нибудь может дать мне какие-нибудь идеи для группировки двух вызовов .Reverse (). ToArray ()? Отдельный метод - больше байтов.

SkyPharaoh
источник
0

QBIC , 41 байт

;_FA|C=A{a=a+1~C=_fC||_XC\C=A+right$(B,a)

Объяснение:

;_FA|    Read A$ from the cmd line, then flip it to create B$
C=A      Set C$ to be A$
{        Start an infinite DO-loop
a=a+1    Increment a (not to be confused with A$...)
~C=_fC|  If C$ is equal to its own reversed version
|_XC     THEN end, printing C$
\C=A+    ELSE, C$ is reset to the base A$, with
right$(B the right part of its own reversal
,a)      for length a (remember, we increment this each iteration
         DO and IF implicitly closed at EOF
steenbergh
источник
0

Haskell, 46 байтов

f l|l==reverse l=l|(h:t)<-l=l!!0:(f$tail l)++[l!!0]

Мне интересно, есть ли способ удалить скобки в (f$tail l)++[l!!0]...

theonlygusti
источник