Свернуть антистринг

27

В этом задании вы получите буквенную строку в качестве входных данных. Мы определим «анти-строку» данного ввода как строку со случаем, когда все буквы инвертированы. Например

AaBbbUy -> aAbBBuY

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

В качестве примера, если вам дали строку

fAbbAcGfaBBagF

Части, выделенные полужирным шрифтом, будут самой длинной парой против струн.

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

fAbbAcGfaBBagF

станет

fAcGfagF

Ваша программа должна повторять этот процесс до тех пор, пока самая длинная строковая пара строк не станет одним символом или короче.

Например, работая с той же самой строкой, новая самая длинная пара после коллапса

fAcGfagF

Таким образом, мы снова сворачиваем строку

fAcGag

Теперь строка не может быть свернута дальше, поэтому мы должны вывести ее.

В случае связи между парами-кандидатами (пример AvaVA) вы можете сделать или сокращение ( AaAили AvV, но не Aa).

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

Тестовые случаи

fAbbAcGfaBBagF  ->  fAcGag
AvaVA ->  AaA / AvV
QQQQQQQ -> QQQQQQQ
fAbbAcQQQQaBBacqqqqA -> fAbcQBcq
gaq -> gaq
fAbbAcGfaBBagFaBBa -> fcGaBBag

Мотивы

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

Мастер пшеницы
источник
Если самая большая подстрока с подстрокой с антистроки имеет более одной подстроки anit-string, все подстроки должны быть свернуты или только первые две?
Джонатан Фрех
@JonathanFrech Любые два. Это тот случай, когда между парами кандидатов есть связь.
Пшеничный волшебник
Так что aaaAAAaaa -> aAaaa?
Джонатан Фрех
Кое-что о подмножестве этой проблемы кричит Куайн, но я не могу указать на это.
Волшебная Урна Осьминога
1
@MagicOctopusUrn Что-то наподобие записи двухциклового квинуса, в котором выходные данные программы являются антистрокой ?
Джонатан Фрех

Ответы:

8

Perl, 64 61 байт

Включает +1в себя дляp

perl -pE 's/(.\K.{$%})(.*)(?=(.))(??{$1^$"x$%.$"})/$2$3/ while$%=--pos' <<< fAbbAcGfaBBagFaBBa
Тон Хоспел
источник
6

JavaScript (ES6), 200 байт

Использует массивы символов для ввода / вывода.

f=a=>(m=M=C=>a.map((_,i)=>a.map((_,j)=>C(i,j-i+1))))(I=>M((i,j)=>a.slice(i,i+j).some((n,k)=>n[c='charCodeAt']()^(a[I+k]||'')[c]()^32)|I+j>i|j<m||(x=[i,I],m=j)))&&m-->1?f(a,x.map(p=>a.splice(p+1,m))):a

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

Arnauld
источник
3

Сетчатка , 119 байт

.+
$&¶$&
T`Ll`lL`.*¶
/(.).*¶.*\1/^&0A`
¶&Lv$`(?<=(.)*)((.)(.)*).*¶(?>((?<-1>.)*.)(?<-4>.)*)(.*)\2
$5$6$3$'
N$`
$.&
}0G`

Попробуйте онлайн! Ссылка включает в себя тестовые случаи. Объяснение:

.+
$&¶$&
T`Ll`lL`.*¶

Дублируйте ввод и переверните регистр первой копии.

/(.).*¶.*\1/^&0A`

Если анти-строк вообще нет, удалите перевернутый дубликат.

¶&Lv$`(?<=(.)*)((.)(.)*).*¶(?>((?<-1>.)*.)(?<-4>.)*)(.*)\2
$5$6$3$'

Перечислите все возможные свернутые антиструны.

N$`
$.&
}0G`

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

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

Python 3 , 189 181 байт

Благодарим Джонатана Фреха за то, что он сделал его чистым.

f=lambda s,x=set():any(u in s[j+i:]and(x.add(s[:j+1]+s[j+i:].replace(u,u[0],1))or 1)for i in range(len(s),1,-1)for j in range(len(s))for u in[s[j:j+i].swapcase()])and f(x.pop())or s

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

Моя собственная версия, сейчас устаревшая (189 байт):

x=set()
def f(s):
 while any(u in s[j+i:]and(x.add(s[:j+1]+s[j+i:].replace(u,u[0],1))or 1)for i in range(len(s),1,-1)for j in range(len(s))for u in[s[j:j+i].swapcase()]):s=x.pop()
 return s

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

any()для раннего раскрытия вложенных циклов и set()для изменяемого глобального объекта, используемого в понимании. Все остальное - это простая реализация требований использования str.swapcase.

Python 2 , 160 байт

def f(s):
 for i in range(len(s),1,-1):
	for j in range(len(s)):
	 u=s[j:j+i].swapcase()
	 if u in s[j+i:]:return f(s[:j+1]+s[j+i:].replace(u,u[0],1))
 return s

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

Оказывается, что обычный вложенный цикл с ранним прорывом returnнамного короче, чем «умный» трюк с any.

фонтанчик для питья
источник
181 байт ; рекурсивный подход. Изменяемый setкак функция по умолчанию не будет конфликтовать с дальнейшими вызовами, так как я думаю, что ваш код полностью выдает набор, чтобы быть пустым.
Джонатан Фрех
Извините, я думал, что xэто останется не пустым. Как у вас есть, я думаю, что это соответствует.
Джонатан Фрех
Это хорошо, и спасибо за улучшение.
Bubbler
3

C (gcc) , 240 238 227 225 222 216 байт

  • Сохранено два байта; удалено определение случайных переменных.
  • Сохранено одиннадцать тринадцать байтов; golfed b|=S[p+m]!=S[q+m]+32-(S[q+m]>90)*64до b|=abs(S[p+m]-S[q+m])-32к b|=32-S[p+m]+S[q+m]&63.
  • Сохранено три байта; golfed for(...;...;p++)S[p+1]=S[p+L];к for(...;...;S[++p]=S[p+L]);.
  • Сохранено шесть байтов благодаря функциюcatcat .
p,P,q,Q,l,L,b,m;f(char*S){for(p=0;S[p];p++)for(l=0;S[l+++p];)for(q=0;b=S[q+~-l];!b&p+l<=q&l>L?L=l,P=p,Q=q:0,q++)for(b=0,m=l;m--;)b|=32-S[p+m]+S[q+m]&63;for(;b-2;)for(p=b++?-~Q-L:P;S[p];S[++p]=S[L+p]);~-L?L=0,f(S):0;}

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

Джонатан Фрех
источник
@ceilingcat Спасибо.
Джонатан Фрех
0

Stax , 30 байт

î☼fúΩ§☺æ╒ºê@Ñ▀'╫Iqa{d]∟Sa5♦⌂─╚

Запустите и отладьте его

Соответствующее представление ascii той же программы таково.

c%Dc:e{%orF..*:{_{32|^mY++_h.$1yh++R

Он использует подход регулярных выражений. Это многократно регулярное выражение для замены строки. Он строит их из каждой смежной подстроки текущего значения. Например, для ввода fAbbAcGfaBBagF, одна из подстрок - AbbAв этом случае регулярное выражение AbbA(.*)aBBaбудет заменено на A$1a.

c                                       get number of characters
 %D                                     repeat rest of program that many times
   c:e                                  get all substrings
      {%or                              order substrings longest to shortest
          F                             for each substring, execute the rest
           ..*:{                        build the string "(.*)"
                _{32|^m                 current substring with case inverted
                       Y                save the inverted case in register y
                        ++              concatenate search regex together
                                            e.g. "aBc(.*)AbC"
                          _h            first character of substring
                            .$1         "$1"
                               yh       first character of inverted case
                                 ++     concatenate replacement regex together
                                            e.g. "a$1A"
                                   R    do regex replacement
рекурсивный
источник
0

Japt -h , 33 байта

à ñÊÅÔ£=rX+"(.*)"+Xc^H ÈÎ+Y+XÎc^H

Попытайся

à ñÊÅÔ£=rX+"(.*)"+Xc^H ÈÎ+Y+XÎc^H     :Implicit input of string U
à                                     :Combinations
  ñ                                   :Sort by
   Ê                                  :  Length
    Å                                 :Remove first element (the empty string)
     Ô                                :Reverse
      £                               :Map each X
       =                              :  Reassign to U
        r                             :  Global replacement
         X+"(.*)"+                    :  Append "(.*)" to X and then append
                  Xc                  :    Charcodes of X
                    ^H                :    XORed with 32
                      È               :  Pass each match X, with captured group Y, through the following function
                       Î+Y+           :    Append Y to the first character of X and then append
                           XÎc^H      :      The charcode of the first character of X XORed with 32
мохнатый
источник