38
\$\begingroup\$

Introduction

We all know prefixes and suffixes. But there are other types of affixes that exist too. Such as circumfixes, a type of affix that has two parts, one of which is a prefix and another of which is a suffix. Figuring out whether some string is a prefix or a suffix of some other string is easy, but what about figuring out whether it might be a circumfix?

That is today's challenge - create a program or function which takes two strings as input, and determine whether the first is a circumfix of the second.

For the purposes of this challenge a string i1 is a circumfix of another string i2 if and only if there exists some non-empty string j which is a contiguous substring of i2 such that removing j from i2 results in i1, and j is neither a prefix nor a suffix of i2 (if it is, you don't have a circumfix, you just have a suffix or a prefix respectively).

For example, "fog" is a circumfix of "frog", because removing "r" from "frog" produces "fog".

When given valid input, your program either needs to output a single consistent value of your choice if the first input string is a circumfix of the second, and any other value if it is not, or vice versa. For example, you may decide have your program output 6 when the first string is a circumfix of the second, in which case any output except 6 is acceptable when it is not.

This is , so do make sure to golf your code.

Test cases

Format:
"String 1", "String 2" -> output
    comments about the test case - in all these test cases, the output will be true if string 1 is a circumfix or string 2 and false otherwise
"apply", "appreciably" -> true
    "app]reciab[ly"
"rake", "racket by the lake" -> true
    multiple options - "r]acket by the l[ake" and "ra]cket by the la[ke"
"trout", "trumpet" -> false
    Doesn't work at all
"bring", "brought him a gong" -> false
    You only get to remove one substring - "br]ought h[i]m a go[ng" is not allowed
"falcon", "false conundrum" -> false
    You can't have extra stuff at the start or end either - "fal]se [con(undrum)" is not allowed
"goose", "goosebumps" -> false
    "goose]bumps[" is just a prefix
"lame", "blame" -> false
    And "]b[lame" is just a suffix
"pale", "pale ale" -> true
    "pale] ale[" is just a prefix, but "pal]e al[e" is a circumfix, so this is allowed
"b", "barb" -> false
    This could be a prefix ("b]arb[") or a suffix ("]bar[b"), but not a circumfix - "b]ar[b" is not allowed
"abba", "aba" -> false
    "abba" can be split into a prefix of "aba" ("ab") and a suffix of "aba" ("ba"), but "abba" is still not a circumfix of "aba"
"friend", "friend" -> false
    It's only a proper circumfix if you actually remove something - "fri][end" doesn't make the cut
"float", "on" -> false
    You may not assume the first input will be shorter than the second one
"", "" -> false
    One or both input strings may be empty
"Twin Sister", "Twister" -> false
    Inputs are ordered - you may reverse the order, but there must be a consistent ordering
"case", "Castle" -> false
    Inputs are case sensitive
"<<@ 23|>", "<<@23??|> 23|>" -> true
    "<<@]23??|>[ 23|>", not all characters will be letters)
\$\endgroup\$
  • \$\begingroup\$ Are empty inputs possible? \$\endgroup\$ – Luis Mendo Oct 26 at 21:17
  • \$\begingroup\$ @LuisMendo Yes, one or both inputs may be empty \$\endgroup\$ – Sara J Oct 26 at 21:19

19 Answers 19

11
\$\begingroup\$

J, 23 21 20 bytes

>&#*]e.1}:@}.-&#]\.[

Try it online!

-1 byte thanks to Bubbler

Return true if:

  • >&# left arg is strictly longer than right (see the "friend"/"friend" test case)
  • * and...
  • ] the right arg
  • e. is an element of the list formed by...
  • 1 }:@}. removing the first and last elements of...
  • -&# ]\. [ all the outfixes \. of the left arg [ whose size is the difference in size between the two args -&#

That is, J has a builtin to subtract the "chunks" in the middle of the necessary size and leave us with the remaining prefixes and suffixes, catted. We simply have to remove the non-proper ones (ie, the first and last elements of the list of outfixes), and check for what we're searching for.

\$\endgroup\$
  • \$\begingroup\$ +1 for the perfect use case of outfix. \$\endgroup\$ – Bubbler Oct 28 at 8:58
  • \$\begingroup\$ 1}:@}. in place of [:}:@}. saves a byte. Try it online! \$\endgroup\$ – Bubbler Oct 28 at 9:04
  • \$\begingroup\$ @Bubbler thanks and nice catch. updated. \$\endgroup\$ – Jonah Oct 28 at 12:46
8
\$\begingroup\$

Python3, 86 84 83 80 77 76 bytes

lambda a,b:len(a)<len(b)*any(a==b[:i]+b[i-len(a):]for i in range(1,len(a)))

Try it online!

-2 bytes thanks to @Value Ink whitespace before and after ==

-1 byte remove whitespace.

-3 bytes thanks to @ovs using any to write for loop in one line.

-3 bytes by replacing and with *

-1 byte by replacing def with lambda

Python3.8, 71 bytes

lambda a,b:(c:=len(a))<len(b)*any(a==b[:i]+b[i-c:]for i in range(1,c))

Try it online!

\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to CGCC! Since the goal is to have a smaller byte count, you will want to remove the whitespace in your a == b... check. \$\endgroup\$ – Value Ink Oct 27 at 0:14
  • \$\begingroup\$ I put your 3.8 code into a shell and got a SyntaxError. \$\endgroup\$ – Alex Hall Oct 27 at 11:35
  • \$\begingroup\$ @AlexHall fixed it. \$\endgroup\$ – Angular Orbit Oct 27 at 12:01
5
\$\begingroup\$

Retina 0.8.2, 17 bytes

^(.+)(.+)¶\1.+\2$

Try it online! Link includes test suite that takes each test on its own line with the test values separated by a tab and converts them into individual tests with the values on separate lines as the main program expects.

\$\endgroup\$
5
\$\begingroup\$

Jelly, 11 bytes

⁻ȧŒṖḢ;ṪƊ€iɗ

Try it online!

Takes string 1 (the potential circumfix) as the right/second argument, string 2 as the left/first argument, and outputs 0 if it's not a circumfix and a positive integer otherwise.

(The test footer is bad, but it's better than nothing.)

⁻              The arguments are not equal,
 ȧ             and
          ɗ    you also get a truthy value from the next three links:
         i     the index of the right argument (defaulting to 0) in
  ŒṖ           the list of all partitions of the left argument
        €      with each partition mapped to
    Ḣ;ṪƊ       the concatenation of its first and last elements.

Although this is mostly just a translation of my Brachylog answer, ŒṖ cannot generate empty elements of partitions while c is obligated to, so prefixes and suffixes are naturally accounted for.

This 15-byte monstrosity is what I had before I just tried putting the at the start of the program... and before I realized I could use Ḣ;Ṫ: ŒṖ1,0ịFƊ€⁸ṭṚi>1

\$\endgroup\$
4
\$\begingroup\$

Ruby, 76 62 bytes

->a,b{s=a.size;s<b.size&&(1..s-2).any?{|i|a==b[0,i]+b[i-s,s]}}

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Brachylog, 13 bytes

~c₃{b&}ᵐ⟨hct⟩

Try it online!

Takes string 1 (the possible circumfix) through the output variable, string 2 through the input variable, and outputs through success or failure.

I recall that at some point this could be 12 bytes, but as of now subscriptless c seems to cycle through all partitions infinitely, causing false test cases to not terminate except it would also cause false positives where the two inputs are equal.

(I tried golfing {b&}ᵐ to Xz∧X (when it's already a shorter alternative to {l>0&}ᵐ), but it has a false positive for the empty test case, since there's no problem cycling an empty list to the length of the longest when everything is empty.)

~c₃              The input variable can be split into three parts, such that
   {  }ᵐ         each of them
    b            can have its first element removed (i.e. it is not empty),
     &           and such that
        h        the first of the three
       ⟨ ct⟩     concatenated with the last of the three
                 is the output variable.
\$\endgroup\$
3
\$\begingroup\$

Zsh, 60 bytes

for ((c=#2;++i<$#1;))t=${1: i}&&2=${2:/${1%$t}?*$t}
((c-#2))

Try it online!

Key constructs here:

  • ${var:/pattern} will replace $var by the empty string if pattern matches the full string.
  • ((#var)) is zero if $var is empty.
\$\endgroup\$
3
\$\begingroup\$

Icon, 70 bytes

procedure f(a,b)
return(1<*a<*b&a==b[1:i:=2to*a]||b[i-1-*a:0]&1)|0
end

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Bracmat, 54 bytes

(C=c w a z.!arg:(?c.?w)&@(!c:%?a (%?z&@(!w:!a % !z))))

This solution uses associative (string) pattern matching and expression evaluation during pattern matching. The associative pattern is %?a %?z, which splits the subject, !c, in two strings, neither of which is empty. (The % prefix ensures that a pattern variable does not accept a neutral element, i.e. an empty string, in the case of string pattern matching.) The expression that is evaluated during pattern matching is @(!w:!a % !z). This happens to be another associative string pattern matching operation.

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Haskell, 72 71 62 bytes

\a b->or[a==take i b++drop j b|j<-[2..length b-1],i<-[1..j-1]]

Try it online!

  • -1 byte by moving l a<l b into the list comprehension, where it only needs a , rather than an &&
  • -9 bytes from benrg's suggestion
\$\endgroup\$
  • 1
    \$\begingroup\$ \a b->or[a==take i b++drop j b|j<-[2..length b-1],i<-[1..j-1]] saves 9 bytes. \$\endgroup\$ – benrg Oct 28 at 3:53
  • \$\begingroup\$ @benrg applied, thanks! \$\endgroup\$ – Joseph Sible Oct 28 at 12:55
3
\$\begingroup\$

05AB1E, 9 8 bytes

.œÅΔćìθQ

Try it online!

Outputs a non-negative number if it is a circumfix, -1 otherwise.

\$\endgroup\$
2
\$\begingroup\$

Python 3, 69 bytes

f=lambda c,s,i=1:i<len(c)<len(s)and(c==s[:i]+s[i-len(c):])|f(c,s,i+1)

Try it online!

-2 bytes thanks to Bubbler

\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 70 bytes

Takes input as (a)(b).

a=>b=>[...a].some((_,i)=>b[l=a.length]&&a==b.slice(0,l-i)+b.slice(-i))

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ Eventually you can avoid returning undefined moving the first test inside some \$\endgroup\$ – edc65 Oct 28 at 10:47
  • \$\begingroup\$ @edc65 Good idea. Updated. \$\endgroup\$ – Arnauld Oct 28 at 10:58
2
\$\begingroup\$

JavaScript (ES6), 72 bytes

s=>t=>[...s].some((x,i)=>t[l=s.length]&&i&&s==t.slice(0,i)+t.slice(i-l))

Return true if

  • the second string is longer than the first
  • there is a position to split the first string in 2 parts, such as the second string starts with the left part and ends with the right part

Test

z=`"apply", "appreciably" -> true
    "app]reciab[ly"
"rake", "racket by the lake" -> true
    multiple options - "r]acket by the l[ake" and "ra]cket by the la[ke"
"trout", "trumpet" -> false
    Doesn't work at all
"bring", "brought him a gong" -> false
    You only get to remove one substring - "br]ought h[i]m a go[ng" is not allowed
"falcon", "false conundrum" -> false
    You can't have extra stuff at the start or end either - "fal]se [con(undrum)" is not allowed
"goose", "goosebumps" -> false
    "goose]bumps[" is just a prefix
"lame", "blame" -> false
    And "]b[lame" is just a suffix
"pale", "pale ale" -> true
    "pale] ale[" is just a prefix, but "pal]e al[e" is a circumfix, so this is allowed
"b", "barb" -> false
    This could be a prefix ("b]arb[") or a suffix ("]bar[b"), but not a circumfix - "b]ar[b" is not allowed
"abba", "aba" -> false
    "abba" can be split into a prefix of "aba" ("ab") and a suffix of "aba" ("ba"), but "abba" is still not a circumfix of "aba"
"friend", "friend" -> false
    It's only a proper circumfix if you actually remove something - "fri][end" doesn't make the cut
"float", "on" -> false
    You may not assume the first input will be shorter than the second one
"", "" -> false
    One or both input strings may be empty
"Twin Sister", "Twister" -> false
    Inputs are ordered - you may reverse the order, but there must be a consistent ordering
"case", "Castle" -> false
    Inputs are case sensitive
"<<@ 23|>", "<<@23??|> 23|>" -> true
    "<<@]23??|>[ 23|>", not all characters will be letters)`

f=s=>t=>[...s].some((x,i)=>t[l=s.length]&&i&&s==t.slice(0,i)+t.slice(i-l))

z.split('\n').forEach((s,i)=>{
    var m = s.match(/"([^"]*)", "([^"]*)" -> (true|false)/)
    if (m) {
        console.log(`"${m[1]}" "${m[2]}" should be ${m[3]} and is ${f(m[1])(m[2])}`)
    }
})

\$\endgroup\$
2
\$\begingroup\$

Ruby, 40 39 bytes

->a,b{a+b=~/^(.+)(.+)(?=#{b}$)\1.+\2$/}

Try it online!

How

Simple regex: if a+b can be split in 5 parts ABCDE where A==C and B==E, and b=CDE, then a is a circumfix of b.

Thanks benrg for pointing out a problem with the first solution (and saving 1 byte).

\$\endgroup\$
  • \$\begingroup\$ I really like this. \$\endgroup\$ – Jonah Oct 27 at 18:46
  • 2
    \$\begingroup\$ This fails on inputs like "aa","aabaa" because it finds an incorrect solution and rejects it without backtracking to look for another one. I don't know Ruby, but could you do something like /^(.+)(.+)(?=\Q$b\E$)\1.+\2$/? Then you wouldn't need the final test. \$\endgroup\$ – benrg Oct 28 at 4:06
1
\$\begingroup\$

Perl 5, 73 77 bytes

sub f{(grep$_[1]=~/^@{[$_[0]=~s|.{$_}|\Q$&\E.+|r]}$/,1..length($_[0])-1)?1:0}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Fails on "....", "any string". Try it online! \$\endgroup\$ – Value Ink Oct 27 at 2:15
  • \$\begingroup\$ This should be one of the tests. Corrected for this now, 4 more bytes. \$\endgroup\$ – Kjetil S. Oct 28 at 8:36
1
\$\begingroup\$

Prolog (SWI), 104 bytes

e([],_).
e([H|T],[H|U]):-e(T,U).
e(L,[_|U]):-e(L,U).
f(X,Y):-string_chars(X,A),string_chars(Y,B),e(A,B).

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 30 bytes

#2/.{p__,__,s__}/;{p,s}==#->0&

Try it online!

Takes two lists of characters as input. Returns 0 if the first string is a circumfix of the second, or the second string otherwise.

\$\endgroup\$
1
\$\begingroup\$

Java (JDK), 132 bytes

a->b->{int i=0,r=0,l=a.length();for(;l<b.length()&++i<l;)r|=b.startsWith(a.substring(0,i))&b.endsWith(a.substring(i))?1:0;return r;}

Try it online!

Credits

\$\endgroup\$
  • 1
    \$\begingroup\$ You could save 2 bytes by doing return r instead of return r>0 at the end. \$\endgroup\$ – Sara J Oct 28 at 15:19
  • 1
    \$\begingroup\$ @SaraJ Indeed, I thought it was true/false because of the examples in the challenge. The output format is nice for once ;-) \$\endgroup\$ – Olivier Grégoire Oct 29 at 10:38

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.