23
\$\begingroup\$

Sometimes authors will write (s)he as a stand in for she or he and for some reason they don't want to use singular they. This is ok for the nominative but doesn't work so well when you want to write "her or him". You can write h(er)(im) which covers both cases but gives two extra "pronouns"

h
her
him
herim

In formalizing these patterns we will strings with no parentheses match the exact same string. So she matches only she etc. Additionally a pattern \$A\left(B\right)C\$, where \$A, B, C\$ are all patterns, matches everything that \$AC\$ and \$ABC\$ match and nothing else.

This lets us nest brackets so for the words so the pattern (they)((s)he) matches

they
she
he

theyshe
theyhe

We will measure the effectiveness of a pattern as the number of incorrect words it generates. So from above (s)he has the best possible effectiveness with 0, while h(er)(im) and h(er)(is) both have effectiveness of 2. If (they)((s)he) is trying to generate they, she, and he then it has effectiveness 3.

Your program or function will take a non-empty set of words as input.

Your program should figure out the smallest possible effectiveness any pattern can have that matches all the inputs. For example in for her and him we have shown a pattern with effectiveness 2, and it is impossible to get a pattern with effectiveness less than 2, so you should output 2.

You don't need to output the solution just its effectiveness score. You may take input and output with the usual rules and you may assume the strings will be strictly alphabetic.

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

Test cases

Each case has a potential pattern below it, there may be more than one.

she -> 0
she
she, he -> 0
(s)he
her, him -> 2
h(er)(im)
her, his -> 2
h(er)(is)
they, she, he -> 3
(they)((s)he)
them, her, him -> 5
(them)(her)(him)
their, her, his -> 5
(their)(her)(his)
their, her -> 2
(thei)(he)r
goca, oc, oca -> 1
(g)oc(a)
goca, soca, oc, goce, soce -> 11
(g)(s)oc(a)(e)
goca, soca, gsocae, goce, soce -> 11
(g)(s)oc(a)(e)
goca, soca, gsxocae, goce, soce, xoce -> 26
(g)(s)(x)oc(a)(e)
\$\endgroup\$
9
  • \$\begingroup\$ Is there a way to do this without bruteforcing and/or regex abuse? \$\endgroup\$
    – emanresu A
    Oct 14, 2021 at 11:06
  • 1
    \$\begingroup\$ @Neil I've edited a bit, which should make it clearer maybe. If you think you know some way to make it clearer feel free to edit it. \$\endgroup\$
    – Wheat Wizard
    Oct 14, 2021 at 11:52
  • 1
    \$\begingroup\$ My official pronoun is her -> herim ;) \$\endgroup\$ Oct 15, 2021 at 15:48
  • 1
    \$\begingroup\$ why has (they)((s)he) an effectiveness of 3? by counting unwanted words, i get two: theyhe and theyshe. what is the third one? \$\endgroup\$ Oct 22, 2021 at 19:44
  • 3
    \$\begingroup\$ @NinaScholz: Maybe the empty string? \$\endgroup\$
    – Ry-
    Oct 22, 2021 at 20:31

1 Answer 1

4
\$\begingroup\$

Python3, 1356 bytes

import itertools as i
def w(s,q=[]):
 if s:
  if not q:yield from w(s[1:],q+[(0,[s[0]])]);yield from w(s[1:],q+[(1,[s[0]])])
  else:
   if q[-1][0]:yield from w(s[1:],q[:-1]+[(q[-1][0],q[-1][1]+[s[0]])])
   yield from w(s[1:],q+[(not q[-1][0],[s[0]])])
 else:yield tuple((a,tuple(set(b)))for a, b in q)
def p(s,l=0):
 if len(s)==1:yield tuple(s);return
 n=min(s,key=len)
 if m:=[n[x:y+1]for x in range(len(n))for y in range(x,len(n))if all(n[x:y+1]in a for a in s)]:
  for q in m:
   a,b=[[*filter(None,x)]for x in zip(*[j.split(q,1)for j in s])];x,y=[p(a,1)]if a else [],[p(b,1)]if b else []
   yield from i.product(*(x+[(q,)]+y))
   if not l:yield (*[(u,)for u in dict.fromkeys(a)],q,*[(u,)for u in dict.fromkeys(b)])
  if not l:
   for j in w(s):
    if any(not x[0]for x in j):yield from i.product(*[p(b,1)if a else[b]for a,b in j])
 else:
  s=[x for y in s for x in(y if any(any(j in v for v in s if v!=y)for j in y)else[y])];yield tuple([(u,)for u in sorted(set(s),key=s.index)])
def e(s):
  yield from map(''.join,i.product(*[[k]if isinstance(k,str)else[*e(k),'']for k in s]))
def t(s):
 for i in s:
  if isinstance(i,str):yield i
  elif any(isinstance(j,str)for j in i):yield tuple(t(i))
  else:yield from t(i)
def f(s):
 s=s.split(', ')
 return min([((v:=tuple(t(i))),sum(j not in s for j in e(v)))for i in set(p(s))],key=lambda x:x[1])

The central strategy is to build possible paths starting with matching substrings from the input passed to p at each call, then surrounding the matching substrings with other possible valid patterns derived from the non-matching remainders.

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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