43
\$\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\$
2
  • \$\begingroup\$ Are empty inputs possible? \$\endgroup\$ – Luis Mendo Oct 26 '19 at 21:17
  • \$\begingroup\$ @LuisMendo Yes, one or both inputs may be empty \$\endgroup\$ – Sara J Oct 26 '19 at 21:19

22 Answers 22

12
\$\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\$
3
  • \$\begingroup\$ +1 for the perfect use case of outfix. \$\endgroup\$ – Bubbler Oct 28 '19 at 8:58
  • \$\begingroup\$ 1}:@}. in place of [:}:@}. saves a byte. Try it online! \$\endgroup\$ – Bubbler Oct 28 '19 at 9:04
  • \$\begingroup\$ @Bubbler thanks and nice catch. updated. \$\endgroup\$ – Jonah Oct 28 '19 at 12:46
9
\$\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\$
3
  • 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 '19 at 0:14
  • \$\begingroup\$ I put your 3.8 code into a shell and got a SyntaxError. \$\endgroup\$ – Alex Hall Oct 27 '19 at 11:35
  • \$\begingroup\$ @AlexHall fixed it. \$\endgroup\$ – Angular Orbit Oct 27 '19 at 12:01
7
\$\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\$
7
\$\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\$
6
\$\begingroup\$

Brachylog, 13 12 bytes

~c₃{b&}ᵐ↺b↺c

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 my original solution 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₃             Split the input variable into three parts, such that
   {  }ᵐ        each of them
    b&          can have its first element removed (i.e. it is not empty).
        ↺       Rotate the list of partitions left,
         b      remove the first element (which was in the middle),
          ↺     and rotate the remaining partitions again.
           c    Do they concatenate to the output variable?
\$\endgroup\$
5
\$\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\$
5
\$\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\$
5
\$\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\$
5
\$\begingroup\$

Regex (POSIX ERE or better), 17 bytes

Takes the two strings in joined format, delimited by a single newline.

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

Turned out to be identical to Neil's Retina answer (except I chose to separate with a newline), so I'm mainly answering this to demonstrate it in a wide range of regex engines:

Try it online! - ECMAScript (SpiderMonkey)
Try it online! - ECMAScript 2018 (Node.js)
Try it online! - Perl 5
Try it online! - PCRE2 (PHP)
Try it online! - .NET (C#)
Try it online! - Java (JDK)
Try it online! - Python
Try it online! - Ruby
Try it online! - POSIX ERE (sed), tab as delimiter
Try it online! - POSIX ERE (egrep), tab as delimiter

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

05AB1E, 9 8 bytes

.œÅΔćìθQ

Try it online!

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

\$\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\$

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\$
0
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\$
2
  • 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 '19 at 3:53
  • \$\begingroup\$ @benrg applied, thanks! \$\endgroup\$ – Joseph Sible-Reinstate Monica Oct 28 '19 at 12:55
3
\$\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\$
2
  • \$\begingroup\$ I really like this. \$\endgroup\$ – Jonah Oct 27 '19 at 18:46
  • 3
    \$\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 '19 at 4:06
3
\$\begingroup\$

Husk, 6 bytes

€§×+ḣṫ

Try it online!

\$\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\$
2
  • 1
    \$\begingroup\$ Eventually you can avoid returning undefined moving the first test inside some \$\endgroup\$ – edc65 Oct 28 '19 at 10:47
  • \$\begingroup\$ @edc65 Good idea. Updated. \$\endgroup\$ – Arnauld Oct 28 '19 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\$

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
2
\$\begingroup\$

APL (Dyalog Unicode), 21 bytesSBCS

Anonymous infix function. Takes strings 1 and 2 as left and right arguments. Requires ⎕IO←0.

{(⊂⍺)∊∊¨↑∘⍵¨¨(1↓⍳≢⍺)-⊂0,~/≢¨⍺⍵}

Try it online!

{} "dfn"; and are is strings 1 and 2:

⍺⍵ strings 1 and 2

≢¨ length of each

~/ remove elements from the first that are in the second (gives empty list if same length)

0, prepend zero

 enclose to treat as a whole

()- subtract that from the following:

  ≢⍺ length of string 1

   indices zero through that

  1↓ drop the first one (the zero)

This gives us the head-tail pairs to try.

¨¨ for element of each of the head-tail pairs:

  ↑∘⍵ take that many characters from string 2 (from the end if negative)

∊¨ϵnlist (flatten) each

()∊ is the following an ϵlement of that?

  ⊂⍺ the entire string 1

\$\endgroup\$
1
  • \$\begingroup\$ This appears to have a false positive for "abba", "aba" \$\endgroup\$ – Deadcode Mar 30 at 8:38
2
\$\begingroup\$

Java (JDK), 46 bytes

a->b->(a+"\0"+b).matches("(.+)(.+)\0\\1.+\\2")

Try it online!

Credits

  • -2 bytes thanks to ceilingcat
  • -2 bytes thanks to Sara J
  • The 46 bytes solution (-86 bytes) is actually the full implementation in Java of deadcode's regex answer (which incidentally also contains a Java solution, but only to demonstrate the regex).
\$\endgroup\$
5
  • 1
    \$\begingroup\$ You could save 2 bytes by doing return r instead of return r>0 at the end. \$\endgroup\$ – Sara J Oct 28 '19 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 '19 at 10:38
  • \$\begingroup\$ Oh wow, I didn't realize/remember you could do a regex match in Java without a lot of boilerplate. I suppose I'll keep the boilerplated version in my TIO testbed though, since otherwise it has to compile the regex each time it's called, right? \$\endgroup\$ – Deadcode Mar 30 at 9:56
  • 1
    \$\begingroup\$ @Deadcode Yes, Java is boilerplate, but sometimes not as boilerplate as one might thing :-) The JVM keeps a cache of the last 8 regex (number to verify) that it compiled so no need to worry (too much) about performances, therefore you may shrink your version safely. \$\endgroup\$ – Olivier Grégoire Mar 30 at 10:15
  • \$\begingroup\$ I remember now why I didn't use it. It matches the whole string, which would conflict with my format for pure regexes (which have anchors). It's great for golfing Java functions/programs that use regexes, though! Like this. \$\endgroup\$ – Deadcode Mar 30 at 11:08
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\$
2
  • \$\begingroup\$ Fails on "....", "any string". Try it online! \$\endgroup\$ – Value Ink Oct 27 '19 at 2:15
  • \$\begingroup\$ This should be one of the tests. Corrected for this now, 4 more bytes. \$\endgroup\$ – Kjetil S. Oct 28 '19 at 8:36
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\$

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.