Is it a circumfix?

Question

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 code-golf, 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)

Answer 1

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.

Answer 2

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!

Answer 3

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.

Answer 4

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

Answer 5

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?

Answer 6

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, 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

Answer 7

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.

Answer 8

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!

Answer 9

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!

Answer 10

05AB1E, 9 8 bytes

.œÅΔćìθQ

Try it online!

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

Answer 11

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!

Answer 12

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

Answer 13

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

Answer 14

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).

Answer 15

Curry, 28 bytes

Tested to work in both PAKCS and KiCS2

f(a:b++c:d)(a:b++_:_++c:d)=1

Try it online!

This returns 1 if the first argument is a circumfix and nothing otherwise. In cases where there are multiple ways the string could be a circumfix it will return 1 multiple times i.e. it is non-deterministic but always gives 1. I think this is fine.

The program is basically just a pattern match checking that the first input is made up of two non-empty strings and that the second is made of the same two strings with another non-empty string between them.

This uses two pattern matching features available to Curry not present in Haskell. The first is ++ patterns, and the second is pattern variables. e.g. we require the two as to be the same a.

This allows it to beat out the Haskell answer handily.

Testing

TIO has a limited ability to test things like this. Paste the following to smap and run in PAKCS 2.2.0 for better testing abilities:

import Control.SetFunctions


f(a:b++c:d)(a:b++_:_++c:d)=1

-- Helper to run tests
helper :: [a] -> [a] -> Bool
helper x y =
  not $ isEmpty $ set0 $ f x y
  
main =
  [ helper "fog" "frog"
  , helper "apply" "appreciably"
  , helper "rake" "racket by the lake"
  , helper "trout" "trumpet"
  , helper "bring" "brought him a gong"
  , helper "falcon" "false conundrum"
  , helper "goose" "goosebumps"
  ]

This test handler will not work in KiCS2 or at least not on the version used by smap. But the function itself does if you want to manually test it.

Answer 16

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!

Answer 17

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])}`)
    }
})

Answer 18

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!

Answer 19

APL (Dyalog Unicode), 21 bytes^SBCS

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

Answer 20

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).

Answer 21

Wolfram Language (Mathematica), 30 bytes

FreeQ@{{p__,s__},{p__,__,s__}}

Try it online!

Now with nicer output.

Input [{i1, i2}] as two lists of characters. Returns False if i1 is a circumfix of i2, and True otherwise.

Answer 22

Perl 5, 73 77 bytes

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

Try it online!

Answer 23

Nekomata + -e, 7 bytes

≠;sᵃN,=

Attempt This Online!

≠;sᵃN,=
≠           Check that the two inputs are not equal
 ;          Split the second input into two parts
  s         Take a suffix of the second part
   ᵃN       Check that both the first part and the suffix are non-empty
     ,      Join the first part and the suffix
      =     Check that the result is equal to the first input