Полупалиндромная головоломка

23

Палиндром - это слово, обратное ему.

Теперь есть некоторые слова, которые могут выглядеть как палиндромы, но это не так. Например, рассмотрим слово sheesh, sheeshне являющееся палиндромом, потому что его противоположность - hseehsэто другое, однако, если мы рассмотрим shодну букву, то наоборот sheesh. Такое слово мы будем называть полупалиндром.

В частности, слово является полупалиндромом, если мы можем разделить его на некоторое количество фрагментов, чтобы при изменении порядка фрагментов формировалось исходное слово. (Для sheeshэтих чанков есть sh e e sh) Мы также не будем требовать, чтобы чанк содержал буквы из обеих половин слова (иначе каждое слово было бы полупалиндромом). Например rear, не является полупалиндромом, потому что r ea rимеет chunk ( ea), который содержит буквы с обеих сторон исходного слова. Мы считаем, что центральный символ в слове нечетной длины находится с обеих сторон слова, поэтому для слов с нечетной длиной центральный символ всегда должен быть в своем собственном фрагменте.

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

Ответы будут оцениваться в байтах, причем меньшее количество байтов будет лучше.

Тест-кейсы

[] -> True
[1] -> True
[2,1,2] -> True
[3,4,2,2,3,4] -> True
[3,5,1,3,5] -> True
[1,2,3,1] -> False
[1,2,3,3,4,1] -> False
[11,44,1,1] -> False
[1,3,2,4,1,2,3] -> False

Программа для генерации большего количества тестов.


Борьори указал, что они похожи на обобщенные палиндромы смарандаш . Так что, если вы хотите продолжить чтение, начните с одного.

Мастер пшеницы
источник
2
Почему вы определили полупалиндромы, используя строки, но ваши входные данные представляют собой массивы целых чисел? Помимо того, что мы путаемся, это означает, что мы не можем протестировать наш исходный код, используя нашу собственную программу.
BradC
@BradC Палиндромы и тому подобное часто объясняются словами, так как это немного проще.
Эрик Outgolfer
@BradC Строки имеют тенденцию вводить странные крайние случаи, особенно с точки зрения символов против байтов. Я выбираю номер, потому что они проще. Я думал, что слова будут легче в целях объяснения.
Пшеничный волшебник
2
Эти типы палиндромов известны в литературе как обобщенные паландромы Смарандаке.
ужасно
1
@RosLuP Да, «истинные» палиндромы также являются полупалиндромами, просто обрабатывайте каждый символ / целое как есть, без дополнительной «порции».
BradC

Ответы:

6

Retina 0.8.2 , 85 69 байт

M`^(.+,)*(\d+,)?(?<-1>\1)*$(?(1)^)|M`^(.+,)*(\d+,)?(?<-1>\1)*$(?(1)^)

Попробуйте онлайн! Объяснение:

M`

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

^

Матч должен начинаться с начала.

(.+,)*

Захватите несколько серий персонажей. Каждый прогон должен заканчиваться запятой.

(\d+,)?

При желании сопоставьте ряд цифр и запятую.

(?<-1>\1)*

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

$

Матч должен заканчиваться в конце.

(?(1)^)

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

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

Желе , 27 23 байта

ṖUṁ@Ƒ€ṚẸHḢŒŒHḢŒṖUṁ@Ƒ€ṚẸ

Возвращает 1 для полупалиндромов, 0 в противном случае.

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

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

ṖUṁ@Ƒ€ṚẸHḢŒŒHḢŒṖUṁ@Ƒ€ṚẸ  Main link. Argument: A (array)

          Œ              Invalid token. Everything to its left is ignored.
           ŒH            Halve; divide A into two halves similar lengths. The middle
                         element (if there is one) goes into the first half.
             Ḣ           Head; extract the first half.
              ŒṖ         Generate all partitions of the first half.
                U        Upend; reverse each chunk of each partition.
                         Let's call the result C.

                     Ṛ   Yield R, A reversed.
                   Ƒ€    Fixed each; for each array P in C, call the link to the left
                         with arguments P and R.
                         Return 1 if the result is P, 0 if not.
                 ṁ@          Mold swapped; replace the n integers of C, in reading
                             order, with the first n integers of R.
                     Ẹ   Exists; check if one of the calls returned 1.
Деннис
источник
4

Python 2 , 157 153 147 143 байта

-4 байта благодаря тш .

s=lambda x,i=0:len(x)<2or[]<x[i:]and(x[-i:]==x[:i])&s(x[i:-i])|s(x,i+1)
s=lambda x,i=0:len(x)<2or[]<x[i:]and(x[-i:]==x[:i])&s(x[i:-i])|s(x,i+1)

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

овс
источник
1
Изменить, x==x[::-1]чтобы len(x)<2сохранить 2 * 2 байта; 143 байт
TSH
4

05AB1E , 59 47 43 41 байт

2äøø€.œ`âʒ`RQ}gĀIg_^q2äøø€.œ`âʒ`RQ}gĀIg_^

-12 байт благодаря @Emigna .

Попробуйте онлайн или проверьте все контрольные примеры .

Объяснение:

2ä               # Split the input into two parts
                 #  i.e. [3,4,2,0,2,3,4] → [[3,4,2,0],[2,3,4]]
  øø             # Zip twice without filler
                 # This will remove the middle item for odd-length inputs
                 #  i.e. [[3,4,2,0],[2,3,4]] → [[3,2],[4,3],[2,4]] → [[3,4,2],[2,3,4]]
    €.œ          #  Then take all possible partitions for each inner list
                 #   i.e. [[3,4,2],[2,3,4]]
                 #    → [[[[3],[4],[2]],[[3],[4,2]],[[3,4],[2]],[[3,4,2]]],
                 #       [[[2],[3],[4]],[[2],[3,4]],[[2,3],[4]],[[2,3,4]]]]
`                # Push both lists of partitions to the stack
 â               # Take the cartesian product (all possible combinations) of the partitions
                 #  i.e. [[[[3],[4],[2]],[[2],[3],[4]]],
                 #        [[[3],[4],[2]],[[2],[3,4]]],
                 #        ...,
                 #        [[[3,4,2]],[[2,3,4]]]]
  ʒ   }          # Filter this list of combinations by:
   `             #  Push both parts to the stack
    RQ           #  Check if the second list reversed, is equal to the first
                 #   i.e. [[3,4],[2]] and [[2],[3,4]] → 1 (truthy)
       gĀ        # After the filter, check if there are any combinations left
                 #  i.e. [[[[3,4],[2]],[[2],[3,4]]]] → 1 (truthy)
         Ig_     # Check if the length of the input was 0 (empty input-list edge-case)
                 #  i.e. [3,4,2,0,2,3,4] → 7 → 0 (falsey)
            ^    # Bitwise-XOR
                 #  i.e. 1 XOR 0 → 1 (truthy)
             q   # Stop the program (and then implicitly output the top of the stack)
2äøø€.œ`âʒ`RQ}gĀIg_^
                 # Everything after the `q` are no-ops to comply to the challenge rules
Кевин Круйссен
источник
Вы можете обойти проблему с помощью списков нечетной длины с помощью øøε.œ} `, экономя 6 байтов. Вы также, кажется, оставили 30 неиспользованных байтов в ...
Emigna
@Emigna, нокауты в конце должны соответствовать ограниченному требованию источника вызова
Камил Дракари
@KamilDrakari: Да, верно. Забыл эту часть. Хорошая новость заключается в том, что 6-байтовое сохранение будет 12 байтов тогда :)
Emigna
@Emigna Очень умный трюк с двойным почтовым индексом. Я не был доволен этой частью, но это намного лучше! Кстати, поскольку Elixir rewrite можно использовать 2-байтовые команды вместо ε }. :)
Кевин Круйссен
@KevinCruijssen: Ах, круто. Я этого не знал.
Emigna
4

05AB1E , 37 байт

Использует примерно ту же технику, что придумал Джонатан .

.œʒ€gηOZ;îå}εÂQ}ZĀqĀZ}QÂε}åî;ZOηg€ʒ.œ

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


.œʒ€gηOZ;îå}εÂQ}ZĀqĀZ}QÂε}åî;ZOηg€ʒ.œ

Полная программа. Получает список из STDIN, выводит 1 или 0 в STDOUT.

.œʒ        }

Фильтр-оставь разделы, которые удовлетворяют ...

   €gηOZ;îå

Это условие: длины каждого ( €g) сохраняются в списке, чьи префиксы ( η) затем суммируются ( O), что дает нам кумулятивные суммы списка длин. Затем в стек помещается запрограммированная половина максимума этого списка, но при этом сохраняется и исходный список ( Z;î), и, если он встречается ( å) в кумулятивных суммах, функция возвращает истину.

εÂQ}

Для каждого из сравнения ( Q) с вспять, которые выталкиваются отдельно в стеке . Возвращает список 0 с и 1 с.Â

ZĀq

Максимум. Если что-либо является правдивым, то 1 еще 0 . Конец казни. Все, что следует, полностью игнорируется.

Мистер Xcoder
источник
3

Python 2 , 275 251 205 байт

-24 байта благодаря @KevinCruijssen

-44 байта благодаря @PostLeftGhostHunter

Еще -2 байта благодаря @KevinCruijssen

def s(x):
 l=len(x)
 if l<2:return 1>0
 for i in range(1,l/2+1):
	if x[l-i:]==x[:i]:return s(x[i:l-i])
def s(x):
 l=len(x)
 if l<2:return 1>0
 for i in range(1,l/2+1):
	if x[l-i:]==x[:i]:return s(x[i:l-i])

Возвращает True для полупалиндрома, в противном случае - None

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

Cowabunghole
источник
1
Или просто верните 1
Джо Кинг,
Почему s (x) определено дважды?
Доктор У Вит
Потому что они говорят, что считать палиндромом ... но можно определить одну функцию с тем же именем ???
РосЛюП
@RosLuP Да, вы можете. Второй просто перезаписывает первый
Джо Кинг,
3

Желе ,  33  32 байта

-1 Спасибо Erik the Outgolfer.
Благодарю также Денниса за исправление ошибки и за изменение деталей реализации в Jelly.

ẸƇŒḂƇƊ$ƊĊHṀċÄẈṖŒŒṖẈÄċṀHĊƊ$ƊƇŒḂƇẸ

Полупалиндромы дают 1, другие дают 0.

О(2N)

Или посмотрите набор тестов .

Единственные фрагменты - это ŒḂs ({3- й и 4- й } против {29- го и 30- го } байтов), просто для того, чтобы код мог анализировать.

Как?

Все работы выполняются с правой стороны - «Main Link»:

ŒṖẈÄċṀHĊƊ$ƊƇŒḂƇẸ - Main Link: list
ŒṖ               - all partitions
           Ƈ     - filter keep those for which this is truthy (i.e. non-zero):
          Ɗ      -   last three links as a monad:
  Ẉ              -     length of each
         $       -     last two links as a monad:
   Ä             -       cumulative addition
        Ɗ        -       last three links as a monad:
     Ṁ           -         maximum
      H          -         halve
       Ċ         -         ceiling
    ċ            -     count
              Ƈ  - filter keep those for which this is truthy:
            ŒḂ   -   is palindrome?
               Ẹ - any?
Джонатан Аллан
источник
3

Perl 6 , 87 79 байт

-8 байт с некоторыми хитростями из ответа Джо Кинга

$!={/\s/&&/^(.+)\s[(.+)\s]*$0$/&&$1.$!}#$!={/\s/&&/^(.+)\s[(.+)\s]*$0$/&&$1.$!}

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

Порт ответа от tsh на JavaScript. Возвращает два разных объекта Regex.

nwellnhof
источник
1

C (gcc) (X86), 216 байт

p(L,a,n)int*a;{return n?(memcmp(a,a+L-n,n*4)|p(L-2*n,a+n,L/2-n))&&p(L,a,n-1):1<L;}
#define p(L,a)p(L,a,L/2)//p(L,a,n)int*a;{return n?(memcmp(a,a+L-n,n*4)|p(L-2*n,a+n,L/2-n))&&p(L,a,n-1):1<L;}
#define p(L,a)p(L,a,L/2)

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

p(L,a,n)возвращает 0, если массив aдлины Lявляется полупалиндромом, 1 в противном случае. Учитывая, что все префиксы длины >nуже проверены, он сравнивает префикс длины nс суффиксом длины n. p(L,a)это точка входа.

К сожалению, более интересное решение длиннее:

224 байта

(f(L,a,n))//#define p(L,a)(n=L/2,
int*a,n;
{return n?(memcmp(a,a+L-n,n*4)|f(L-2*n,a+n,L/2-n))&&f(L,a,n-1):1<L;}//{return n?(memcmp(a,a+L-n,n*4)|f(L-2*n,a+n,L/2-n))&&f(L,a,n-1):1<L;}
int*a,n;
#define p(L,a)(n=L/2,f(L,a,n))//(

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

Ungolfed:

(f(L,a,n)) //#define p(L,a)(n=L/2,
int*a,n;
{
  return n 
    ? (memcmp(a, a+L-n, n*4) | f(L-2*n, a+n, L/2-n)) &&
      f(L,a,n-1)
    : 1 < L;
} // { ... } 
int*a,n;
#define p(L,a)(n=L/2,f(L,a,n)) //(
eush77
источник
1

Japt , 66 байт


@¯X eUsXn}a1 "
ʧV?UÊ<2:ßUéV sVÑ
@¯X eUsXn}a1 "
ʧV?UÊ<2:ßUéV sVÑ

Japt Переводчик

Большое улучшение в этой версии, теперь она превосходит большинство практических языков. Теперь работает с массивом целых чисел, так как в предыдущем методе была ошибка.

Объяснение:

@        }a1         Find the first number n > 0 such that...
 ¯X                   the first n elements
     UsXn             and the last n elements
    e                 are the same

"
ʧV?UÊ<2:ßUéV sVÑ    String literal to make it a Semi-palindrome
@¯X eUsXn}a1 "

ʧV?                 If n >= length of input...
    UÊ<2              return true if the length is less than 2
        :            Otherwise...
          UéV         move n elements from the end of the input to the start
              sVÑ     remove the first 2*n elements
         ß            and repeat on the remaining elements
Камил Дракари
источник
0

PHP 237 байт

function f($a){for($x=2>$c=count($a);++$i<=$c/2;)$x|=($s=array_slice)($a,0,$i)==$s($a,-$i)&f($s($a,$i,-$i));return$x;}#function f($a){for($x=2>$c=count($a);++$i<=$c/2;)$x|=($s=array_slice)($a,0,$i)==$s($a,-$i)&f($s($a,$i,-$i));return$x;}

рекурсивная функция, возвращает true(для входных данных, содержащих менее двух элементов) или 1для истинных,
0для ложных. Попробуйте онлайн (содержит разбивку).

Фактическая длина кода составляет 118 байтов; полупалиндром, созданный путем дублирования кода.

Для лучшей производительности замените &на &&и вставьте !$x&&перед ++$i.

Titus
источник
0

Scala, 252 байта

def^(s:Seq[Int]):Int={val l=s.size;if(l>1)(1 to l/2).map(i=>if(s.take(i)==s.takeRight(i))^(s.slice(i,l-i))else 0).max else 1}//def^(s:Seq[Int]):Int={val l=s.size;if(l>1)(1 to l/2).map(i=>if(s.take(i)==s.takeRight(i))^(s.slice(i,l-i))else 0).max else 1}

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

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

PPS. Не кандидат в гольф-код, а чисто функциональное решение с использованием сопоставления с образцом:

  def f(s:Seq[Int], i:Int=1):Int = {
    (s, i) match {
      case (Nil ,_) => 1
      case (Seq(_), _) => 1
      case (l, _) if l.take(i) == l.takeRight(i) => f(l.slice(i,l.size-i), 1)
      case (l, j) if j < l.size/2 => f(l, i+1)
      case (_, _) => 0
    }
  }
Доктор У Вит
источник
Задача требует, чтобы ваш код также был полупалиндромом. Это самое интересное в вызове.
Пшеничный волшебник
@PostLeftGhostHunter, я добавил исходный код в комментарий, чтобы удовлетворить требования. Кстати, в чем удовольствие делать исходный код полупалиндромом? Если я не ошибаюсь, каждое решение в этой теме будет в два раза короче без этого требования. Знаете ли вы о каком-либо решении не так?
Доктор У Вит
0

Perl 6 , 81 байт

($!={/../&&/^(.+)(.*)$0$/&&$1.$!})o&chrs#($!={/../&&/^(.+)(.*)$0$/&&$1.$!})o&chrs

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

Возвращает регулярное выражение /../для True и регулярное выражение /^(.+)(.*)$0$/для False. Работает аналогично ответу nwellnhof , но предварительно преобразует список в строку.

Джо Кинг
источник