27
\$\begingroup\$

In this challenge you will be given an alphabetic string as input. We will define the "anti-string" of a given input to be the string with the case of all the letters inverted. For example

AaBbbUy -> aAbBBuY

You should write a program that takes a string as input and searches for the longest contiguous substring whose anti-string is also a contiguous substring. The two substrings should not overlap.

As an example if you were given the string

fAbbAcGfaBBagF

The bolded portions would be the longest string anti-string pair.

Your program should, once it has found the pair, collapse them into a single character each. It should do this by removing all but the first character of each substring. For example the string above

fAbbAcGfaBBagF

would become

fAcGfagF

Your program should then repeat the process until the longest string anti-string pair is a single character or shorter.

For example working with the same string the new longest pair after the collapse is

fAcGfagF

So we collapse the string again

fAcGag

Now the string cannot be collapsed further so we should output it.

In the case of a tie between candidate pairs (example AvaVA) you may make either reduction (AaA or AvV, but not Aa).

This is so answers will be scored in bytes with fewer bytes being better.

Test Cases

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

Motivations

While this problem may seem arbitrary it is actually a problem I encountered while making code to process fundamental polygons. This process can be used to reduce a fundamental polygon to a smaller n-gon. After I tried it I thought it would make a nice little golf.

\$\endgroup\$
  • \$\begingroup\$ If the largest substring with anti-string substrings has more than one anit-string substring, should all substrings be collapsed or only the first two? \$\endgroup\$ – Jonathan Frech Feb 21 '18 at 23:29
  • \$\begingroup\$ @JonathanFrech Any two. That is a case where there is a tie between candidate pairs. \$\endgroup\$ – Ad Hoc Garf Hunter Feb 21 '18 at 23:31
  • \$\begingroup\$ So aaaAAAaaa -> aAaaa? \$\endgroup\$ – Jonathan Frech Feb 21 '18 at 23:35
  • \$\begingroup\$ Something about a subset of this problem screams quine but I can't put my finger on it. \$\endgroup\$ – Magic Octopus Urn Feb 22 '18 at 0:57
  • 1
    \$\begingroup\$ @MagicOctopusUrn Something like Write a two-cycle quine where the program's output is its antistring? \$\endgroup\$ – Jonathan Frech Feb 22 '18 at 1:24
8
\$\begingroup\$

Perl, 64 61 bytes

Includes +1 for p

perl -pE 's/(.\K.{$%})(.*)(?=(.))(??{$1^$"x$%.$"})/$2$3/ while$%=--pos' <<< fAbbAcGfaBBagFaBBa
| improve this answer | |
\$\endgroup\$
6
\$\begingroup\$

JavaScript (ES6), 200 bytes

Uses arrays of characters for I/O.

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

Try it online!

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Retina, 119 bytes

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

Try it online! Link includes test cases. Explanation:

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

Duplicate the input and flip the case of the first copy.

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

If there are no anti-strings at all then delete the flipped duplicate.

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

List all the possible collapsed anti-strings.

N$`
$.&
}0G`

Sort them in order of length, take the shortest (i.e. longest anti-string), and repeat until all the anti-strings have been collapsed.

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Python 3, 189 181 bytes

Credit to Jonathan Frech for making it pure one-liner.

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

Try it online!

My own version, now obsolete (189 bytes):

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

Try it online!

any() to break out nested loops early, and set() for mutable global object usable in the comprehension. The rest is just the straightforward implementation of the requirements using str.swapcase.

Python 2, 160 bytes

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

Try it online!

Turns out that regular nested for loop with early breaking through return is way shorter than the "clever" trick with any.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 181 bytes; recursive approach. The mutable set as function default will not collide with further calls, as I think your code fully pops the set to be empty. \$\endgroup\$ – Jonathan Frech Feb 22 '18 at 1:20
  • \$\begingroup\$ Sorry, I thought that x would be left behind being not empty. As you have it, I think it complies. \$\endgroup\$ – Jonathan Frech Feb 22 '18 at 1:22
  • \$\begingroup\$ That's fine, and thanks for the improvement. \$\endgroup\$ – Bubbler Feb 22 '18 at 1:23
3
\$\begingroup\$

C (gcc), 240 238 227 225 222 216 bytes

  • Saved two bytes; removed a stray variable definition.
  • Saved eleven thirteen bytes; golfed b|=S[p+m]!=S[q+m]+32-(S[q+m]>90)*64 to b|=abs(S[p+m]-S[q+m])-32 to b|=32-S[p+m]+S[q+m]&63.
  • Saved three bytes; golfed for(...;...;p++)S[p+1]=S[p+L]; to for(...;...;S[++p]=S[p+L]);.
  • Saved six bytes thanks to ceilingcat.
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;}

Try it online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ @ceilingcat Thank you. \$\endgroup\$ – Jonathan Frech Sep 15 '19 at 19:17
0
\$\begingroup\$

Python 2, 180 bytes

def f(s):
 L=len(s)
 for x,y in[(i,i+j)for j in range(L,1,-1)for i in range(L-j)]:
	t=s[x:y];T=t.swapcase()
	if T in s[y:]:return f(s.replace(t,t[0],1).replace(T,T[0],1))
 return s

Try it online!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Stax, 30 bytes

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

Run and debug it

The corresponding ascii representation of the same program is this.

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

It uses a regex approach. It repeatedly regex string replacement. It builds these from each contiguous substring of the current value. For instance for the input fAbbAcGfaBBagF, one of the substrings is AbbA, in which case the regex AbbA(.*)aBBa will be replaced with 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
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Wolfram Language (Mathematica), 148 bytes

#//.s_:>MinimalBy[StringReplaceList[s,a:(p_~~__)~~x___~~b:(q_~~__)/;(32==##&@@Abs[(t=ToCharacterCode)@a-t@b]):>p<>x<>q]/.{}->{s},StringLength][[1]]&

Try it online!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Japt -h, 33 bytes

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

Try it

à ñÊÅÔ£=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
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.