Полностью палиндромные треугольники

18

Рассмотрим строку 160615051. Он может быть «триангулирован» как таковой:

  1
 606
15051

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

  1  |   1   |   
 6   |    6  |      
1    |     1 | 15051 

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

Ввод: строка печатных символов ASCII от 0x20 до 0x7E. Это может быть массив символов, отдельная строка или массив кодовых точек ASCII. Ваш вход всегда можно будет триангулировать (то есть его длина всегда будет идеальным квадратом).

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

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

input => output

1 => true
A => true
AAAA => true
nope => false
{{}} => false
1101 => true
1011 => false
1202 => false
111110001 => true
160615051 => true
160625052 => false
1111111111111111 => true
1121123211234321123454321 => true
HHeHHeleHHellleHHellolleH => true
HellolleHHellleHHeleHHeHH => false
111111111111111111111111111111111111 => true
abcbdefeddefgfedbcdefedcbabcdefedcba => true
Конор О'Брайен
источник

Ответы:

10

Желе , 14 12 байт

J’ƲœṗZ⁻¦µU⁼

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

Фон

Начнем с рассмотрения 0-значных индексов входной строки.

 H  H  e  H  H  e  l  e  H  H  e  l  l  l  e  H  H  e  l  l  o  l  l  e  H
 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

Чтобы получить строки треугольника, мы можем разбить строку перед индексами 1 , 1 + 3 = 4 , 1 + 3 + 5 = 9 и 1 + 3 + 5 + 7 = 16 . Поскольку (n + 1) ² = n² + (2n + 1) , эти суммы являются в точности положительными, идеальными квадратами в списке индексов. Если мы также разбиваем строку до 0 , это так же просто, как разбивать перед всеми индексами на основе 0, которые являются идеальными квадратами.

После разбиения мы получаем следующие строки.

""
"H"
"HeH"
"HeleH"
"HellleH"
"HellolleH"

Далее мы заменим пустую строку в начале всеми символами в первом столбце.

"HHHHH"
"H"
"HeH"
"HeleH"
"HellleH"
"HellolleH"

Задача теперь сводится к проверке того, дает ли обращение всех строк один и тот же массив строк.

Как это устроено

Сначала Jгенерирует все основанные на 1 индексы входной строки J, затем уменьшает их на 1, чтобы получить все основанные на 0 индексы. Ʋпроверяет все 0-основанные индексы на прямоугольность. Для нашего примера сверху это приводит к следующему логическому массиву.

 1  1  0  0  1  0  0  0  0  1  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0

Далее мы вызываем œṗдля разделения входной строки, например,

 H  H  e  H  H  e  l  e  H  H  e  l  l  l  e  H  H  e  l  l  o  l  l  e  H

перед всеми 1 (на самом деле, все правдивые элементы). Для нашего примера это приводит к следующему массиву строк.

['', 
 'H',
 'HeH',
 'HeleH',
 'HellleH',
 'HellolleH'
]

Z⁻¦пожалуй, самая интересная часть этого ответа. Давайте Z1¦сначала проанализируем более простое .

¦это редкий быстрый. Он потребляет две ссылки из стека, в частности, 1и Zв этом случае. Первый Zприменяется к его аргументу: массив строк из ранее. Zявляется атомом почтового индекса и читает массив строк / массив символов 2D по столбцам, получая

['HHHHH',
 'eeee',
 'Hlll',
 'ell',
 'Hlo',
 'el',
 'Hl',
 'e',
 'H'
]

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

Теперь ¦заглядывает 1и находит единственный индекс: 1 . Таким образом, первая строка в исходном массиве строк заменяется первой строкой в ​​возвращаемом значении Z; Строки с другими индексами остаются без изменений.

['HHHHH',
 'H',
 'HeH',
 'HeleH',
 'HellleH',
 'HellolleH'
]

Давайте назовем этот массив .

Мы использовали Z⁻¦вместо Z1¦, но это не имеет никакого значения: сравнивает строковый массив с входной строкой для неравенства, получая 1, так как они не равны. Разница между ними в том, что Z⁻¦это двоично, потому что позволяет нам писать œṗZ⁻¦вместо œṗ¹Z1¦. Это связано с тем, что dyad ( œṗ), за которым следует monad ( œṗ¹Z1¦), является форком (монада применяется к аргументу цепочки / входной строке, а возвращаемое значение передается в качестве правильного аргумента œṗ), в то время как диада следует за другой диадой. (или в конце цепочки) является крючком , т. е. его правый аргумент является аргументом цепочки.

Осталось только проверить палиндромность. µначинается новая (одноместный) цепью Кто есть аргумент . Вверх ноги атом меняет все строки в A (но не сам), а затем сравнивает результат с А для равенства. Возвращенный логический 1 указывает на полностью палиндромный треугольник; другие строки вернут 0 .U

Деннис
источник
Я действительно должен научиться читать желе. (Объяснение, пожалуйста?)
CAD97
1
Я отредактировал свой ответ.
Деннис
6

Japt , 25 21 17 байт

Сохранено 2 байта благодаря @obarakon

ò@°T ¬v1
pUmg)eêP

Проверьте это онлайн!

Как это устроено

 ò@  ° T ¬ v1   // Implicit: U = input string, T = 0
UòXY{++T q v1}  // First line; reset U to the result of this line.
UòXY{        }  // Partition U at indices where
     ++T q      //   the square root of T incremented
           v1   //   is divisible by 1.
                // This breaks U at square indices, giving rows of 1, 3, 5, ... chars.
 pUmg)eêP
UpUmg)eêP
  Umg           // Take the first char of every item of U.
Up   )          // Append this to U.
      e         // Check that every item in the resulting array
       êP       // is a palindrome.
                // Implicit: output result of last expression

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

ETHproductions
источник
Является ли эта многострочная вещь новой особенностью Japt?
Люк
@ Люк Да, я только добавил это во вторник. Это мой первый шанс показать это :-)
ETHproductions
Не берите в голову мой совет игры в гольф. Он просто проверяет, была ли каждая строка палиндромной, что также дало правильные результаты ...
Луки
4

05AB1E , 18 байт

gÅÉ£õÜÐíQs€¬āÈÏÂQ*

Использует кодировку 05AB1E . Попробуйте онлайн!

Аднан
источник
Вы можете сохранить один байт, слегка его изменивgÅÉ£ÐíQs€¬āÈÏJÂQ*
kalsowerus
gÅÉ£ты хитрая лиса ... Я недооцениваю ихlist-commands.py
Волшебный Осьминог Урна
4

Желе , 18 16 байтов

J²‘Ṭœṗ⁸ZḢ$ṭ$ŒḂ€Ạ

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

Спасибо Джонатану Аллану за тривиальную, но не столь очевидную экономию -2 байта.

Эрик Outgolfer
источник
Используйте мою конструкцию треугольника и сохраните байт:JƲ0;œṗ⁸ZḢ$ṭ$ŒḂ€Ạ
Джонатан Аллан
... на самом деле объедините эту идею с неправдой и сохраните еще один байт, поскольку разбиение будет "кратчайшим":J²‘Ṭœṗ⁸ZḢ$ṭ$ŒḂ€Ạ
Джонатан Аллан
@JonathanAllan Ммм ... зачем мне вообще это нужно ½? Теперь Jимеет больше смысла ...
Эрик Outgolfer
3

JavaScript (ES6), 112 байт

f=(s,n=1,t='',u='',g=([...a])=>''+a==a.reverse())=>s?g(s.slice(0,n))&f(s.slice(n),n+2,t+s[0],u+s[n-1]):g(t)&g(u)

tи uсобрать стороны, чтобы они могли быть проверены в конце.

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

C #, 184 байта

using System.Linq;
b=a=>string.Concat(a.Reverse())==a
f=>{string c=f[0]+"",d=c,e="";for(int i=1,k=1,s=f.Length;i<s;)
{c+=f[i];d+=f[(i+=k+=2)-1];e=f.Substring(s-k);}return b(c)&b(d)&b(e);}

Думал, что решение выглядело хорошо, пока я не добрался до палиндромной части

Безголовая версия:

Func<string, bool> b = a => string.Concat(a.Reverse()) == a;
        Func<string, bool> func = f => {

            string c = f[0] + "", d = c, e = "";

            for (int i = 1, k = 1, s = f.Length; i < s;) {
                c += f[i];
                d += f[(i += k += 2) - 1];
                e = f.Substring(s - k);
            }

            return b(c) & b(d) & b(e);
        };
LiefdeWen
источник
Можете ли вы перейти e=..на строку цикла for, чтобы сохранить байт? Нет необходимости подсчитывать переводы строки в счетчик байтов, так что я полагаю, что нет.
TheLethalCoder
Нет, я не считаю новые строки, я не могу переместить e в цикл, потому что он мне нужен в операторе return.
LiefdeWen
Я имел в виду, что это....; i < s;e = f.Substring(s - k)){c+=....
TheLethalCoder
2

Java 8, 358 301 байт

import java.util.*;s->{List<String>l=new Stack();for(int i=0,p=1,t=1;p<=s.length();p+=t+=2)l.add(s.substring(i,i=p));String a="",b=a;for(String q:l){a+=q.charAt(0);b+=q.charAt(q.length()-1);}return p(a)&p(b)&p(l.get(l.size()-1));}boolean p(String s){return s.equals(new StringBuffer(s).reverse()+"");}

Вход - это Stringвыход boolean.

Объяснение:

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

import java.util.*;               // Required import for List and Stack

s->{                              // Method (1) with String parameter and boolean return-type
  List<String>l=new Stack();      //  Create a String-list
  for(int i=0,p=1,t=1;            //  Initialize some index/counter integers
      p<=s.length();              //  Loop (1) over the String in sections
      p+=t+=2)                    //    And increase `p` like this after every iteration: 1,4,9,16,25,etc.
    l.add(s.substring(i,i=p));    //   And add a substring-section to the list (0,1 -> 1,4 -> 4,9 -> 9,16 -> etc.)
                                  //  End of loop (1) (implicit / single-line body)
  String a="",b=a;                //  Two temp Strings
  for(String q:l){                //  Loop (2) over the list
    a+=q.charAt(0);               //   And append the first character to String `a`
    b+=q.charAt(q.length()-1);    //   And the last character to String `b`
  }                               //  End of loop (2)
  return p(a)                     //  Return if String `a` is a palindrome
        &p(b)                     //   as well as String `b`
        &p(l.get(l.size()-1));    //   as well as the last String in the list
}                                 // End of method (1)

boolean p(String s){              // Method (2) with String parameter and boolean return-type
  return s.equals(new StringBuffer(s).reverse()+"");
                                  //  Return if this String is a palindrome
}                                 // End of method (2)
Кевин Круйссен
источник
1

Желе ,  20  21 байт

+2 байта - я выпустил глючный код :(
-1 байт - перешел от формовки как нечетных целых чисел к разделению по квадратным индексам

JƲ0;œṗ⁸ZḢ$ṭ$ŒḂ€Ạ

Монадическая ссылка, принимающая список символов и возвращающая 1(Truthy) или 0(Falsey).
Примечание: здесь используется та часть спецификации, которая ограничивает входные данные квадратной длиной.

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

Это можно упростить до 17 байт , отметив, что если все строки являются палиндромами, то только одна «сторона» нуждается в проверке ( JƲ0;œṗ⁸ZḢ$ṭ$ŒḂ€Ạ), однако Эрик-аутголфер уже заметил этот факт и использовал его в своем ответе, поэтому я дал им метод построения треугольника, сохраняя его. байт там.

Кроме того, это, в свою очередь, может быть улучшено до 16 байтов, если заметить, что разбиение по истинным индексам не имеет значения, если в левом аргументе есть избыток ( J²‘Ṭœṗ⁸ZḢ$ṭ$ŒḂ€Ạ).

Как?

JƲ0;œṗµ2BịЀ⁸Z;⁸ŒḂ€Ạ - Link: list, a      e.g. "abcbazxza"
J                     - range of length of a  = [1,2,3,4,5,6,7,8,9]
 Ʋ                   - is square? (vectorises) [1,0,0,1,0,0,0,0,1]
   0;                 - prepend a zero        [0,1,0,0,1,0,0,0,0,1]
     œṗ               - partition a at 1s     ["a","bcb","azxza"]
       µ              - monadic chain separation, call that t
        2B            - 2 in binary = [1,0]
             ⁸        - chain's left argument, t
          ịЀ         - map with index into    ["aa","bb","aa"] (1st and last of each of t)
              Z       - transpose              ["aba","aba"] (left and right "sides" of t)
               ;⁸     - concatenate t          ["aba","aba","a","bcb","azxza"]
                 ŒḂ€  - palindromic? for €ach  [1,1,1,1,1]
                    Ạ - all?                   1
Джонатан Аллан
источник
1
Черт, я как раз собирался сделать ответ Желе. Хотя технически я ошибаюсь и люблю вдвое больше ...
отличная
«отмечая, что разбиение по истинным индексам не возражает, если в левом аргументе есть избыток», тоже заметил перед чтением.
Эрик Outgolfer
1

Mathematica, 156 байт

B=StringTake;Count[PalindromeQ/@Join[A=Table[B[#,{i^2+1,(i+1)^2}],{i,0,(s=Sqrt@StringLength@#)-1}],{StringJoin@Table[B[A[[i]],1],{i,Length@A}]}],True]==s+1&


вход

[ "1101"]

J42161217
источник
Вы не можете заменить If[<stuff>, True, False]просто <stuff>? И я думаю, что And@@(...)короче Count[...,True]==s, что также означает, что вам не нужно определять sкак переменную.
Не дерево
Подождите, это на самом деле проверить диагонали? Я получаю ложные срабатывания для пары тестовых случаев ( "1202"и "160625052").
не дерево
все проблемы исправлены
J42161217
1

PHP , 97 байт

for($t=1;~$s=substr($argn,$i**2,$i++*2+1);$d.=$s[0])$t&=strrev($s)==$s;$t&=strrev($d)==$d;echo$t;

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

Йорг Хюльсерманн
источник
Подождите, это на самом деле проверить диагонали? Я получаю ложные срабатывания для пары тестовых случаев («1202» и «160625052»).
J42161217
@Jenny_mathy теперь это работает
Йорг Хюльсерманн
1

Java, 136 байт

l->{for(int i=0,j,k=1;i<l.size();i=j,k+=2)if(!l.subList(i,j=i+k).equals(l.subList(i,j).asReversed().toList()))return false;return true;}

Использует MutableList<Character>из коллекции Eclipse

Function<MutableList<Character>, Boolean> func = l->{
   for(int i=0,j,k=1;i<l.size();i=j,k+=2)  // `i` is the start index, `j` is the end index, `k` increments by 2
       if(!l.subList(i,j=i+k).equals( //Check that the first partition equals
           l.subList(i,j).asReversed().toList())  // The same sublist reversed
       )
       return false;
   return true;
};
Натан Меррилл
источник
1

Perl 5 , 81 + 1 ( -p) = 82 байта

$a[0].=$1while($a[++$q]=substr$_,0,($#i+=2),'')=~/(.)/;$\||=$_ ne reverse for@a}{

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

Выходы undef(т. Е. Пустые, нулевые) для true, любое число для false

Xcali
источник
0

Excel VBA, 87 байт

Функция анонимного непосредственного окна VBE, которая принимает входные данные из ячейки [A1]и выводит их в непосредственное окно VBE

k=1:For i=1To[Len(A1)^.5]:s=Mid([A1],j+1,i*2-1):j=j+i*2-1:k=k*(s=StrReverse(s)):Next:?k
Тейлор Скотт
источник