Optimally break a string into words

Question

Given a string, like potatocarrot, break it into the smallest number of substrings possible. These substrings can consist either be a single character, or one of a list of words passed as input. For example, if [carrot, potato] was the input, the optimal way to break the string up would be [potato][carrot]. If the list was [potat, tatocarr, rot], the optimal way would be [p][o][tatocarr][o][t].

You can take the string in any reasonable format, and the list of substrings in any reasonable format. As for output, any of the following would be examples of allowed output formats:

• Inserting characters into the string to delimit substrings (e.g., "potato,carrot" or "[potato][carrot]")
• Delimiting words, but not individual characters (e.g., "po[tatocarr]ot", but not "po,tatocarr,ot")
• Returning an array of substrings (e.g., ["potato", "carrot"])

You can assume the input strings consist of lowercase letters, and that there won't be duplicates or strings with a length of 0 or 1 in the list of substrings.

This is code-golf, so shortest answer (in bytes) per language wins.

Test cases:

STRING          WORDS                   OPTIMAL SOLUTION
potatocarrot    potato, carrot          [potato][carrot]
potatocarrot    pot, tatocarr, rot      [p][o][tatocarr][o][t]
potatocarrot    atocarr, ot             [p][ot][atocarr][ot]
potatocarrot    tatocarr, potato, carr  [potato][carr][o][t]
purpur                                  [p][u][r][p][u][r]
purpur          carrot                  [p][u][r][p][u][r]
purpur          pur                     [pur][pur]
purpur          pu, rp                  [pu][r][pu][r] OR [pu][rp][u][r]
purpur          pu, rp, urp             [pu][r][pu][r] OR [pu][rp][u][r] OR [p][urp][u][r]
todoornottodo   to, do, or, not         [to][do][or][not][to][do]
todoornottodo   tod, nott, door         [t][o][door][nott][o][d][o]

Answer 1

Python, 82 bytes

f=lambda s,d:s and min([[w,*f(s[len(w):],d)]for w in[*d,*s]if w+"~">s>=w],key=len)

Attempt This Online!

Depth-first search over solution space.

-6 bytes thanks to loopy walt

Answer 2

APL(Dyalog Unicode), 42 bytes ^SBCS

Assumes index origin 0. Takes the string as right argument ⍵ and the word list as left argument ⍺.

{e⊃⍨⊃⍋≢¨e←d/⍨(1∧.=≢¨∨∊∘⍺)¨d←⊂∘⍵¨~,⍳1+×⍳≢⍵}

Try it on APLgolf!

⍳≢⍵ Indices of the string: 0 1 ... (length-1)
1+× Sign of that incremented: 1 2 2 ... 2 2
,⍳ Indices of an array of that shape, flattened. All these indices have a 0 in the first position and some combination of 1's and 0's after that.
~ Boolean inverse.
d←⊂∘⍵¨ Partition the string according to each of these sequences. This yields a list of all partitions. (Call this d)
≢¨∨∊∘⍺ ¨ For each substring in each partition, take the gcd of its length and the boolean indicating whether it is in the word list. This is only 1 if at least one of the values is 1.
1∧.= For each partition, are all values 1?
e←d/⍨ Only keep partitions where this is the case and call these e.
e⊃⍨⊃⍋≢¨ Pick the partition with minimal length.

Answer 3

Ruby, 60 53 bytes

->s,l,r=""{s=~/^#{r+="(.|"+l*?|+?)}$/?$~[1..-1]:redo}

Try it online!

Answer 4

Retina, 81 65 bytes

/,;/^+%L$w`\b(\w(\w+)?)(\w*;(?(2).*\b\1\b))
$`$1,$3$'
0G`,;
,;.*

Try it online! Link includes test cases. Explanation:

/,;/^+

Repeat until a complete substring list has been found...

%L$w`\b(\w(\w+)?)(\w*;(?(2).*\b\1\b))

... find all of the leading substrings of the rest of the input that are either a single character or are present in the list of words, ...

$`$1,$3$'

... and create new substring lists containing each of those substrings.

0G`,;
,;.*

Output just the first complete list of substrings.

Answer 5

Python, 353 348 342 309 bytes

import re,itertools as I
def f(s,a):
 u=[]
 for e in I.permutations(a):
  *r,=s
  for x in e:
   if x in s:
    p=0
    for _ in"_"*s.count(x):
     b=s.index(x,p);p=b+len(x);j=''.join(r[b:p])
     if j.isalpha():r[b]='<'+r[b];r[p-1]+='>'
  u+=''.join(r),
 return min(u,key=lambda x:len(re.sub('<.+?>','',x)))

Attempt This Online!

-5 bytes thanks to ophact

-33 bytes thanks to pxeger

Answer 6

JavaScript (ES6),  104 102 97  96 bytes

Expects (word_list)(string). Returns a list of substrings.

a=>g=(s,O=o='',...b)=>[s[O.length],...a].every(e=>e&&g(s,O+e,...b,e))|O!=s||b[o&&o.length]?o:o=b

Try it online!

Answer 7

Python3, 145 bytes:

lambda s,w:min(f(s,w),key=len)
f=lambda s,w,c=[]:[c]if''==s else[x for y in w for x in f(s[len(y):],w,c+[y])if s[:len(y)]==y]+f(s[1:],w,c+[s[0]])

Try it online!

Answer 8

Charcoal, 73 67 bytes

≔⟦⟦Ｓ⟧⟧θ≔⟦⟧ηＷＳ⊞ηιＦθ«≔⊟ιζ¿ζＦ⁺η⟦§ζ⁰⟧Ｆ⁼κ✂ζ⁰Ｌκ⊞θ⁺ι⟦κ✂ζＬκ⟧⊞υι»⊟Φυ⁼Ｌι⌊ＥυＬλ

Try it online! Link is to verbose version of code. Takes input as a newline-terminated list of words and outputs each substring on its own line (default output for an array of substrings). Explanation:

≔⟦⟦Ｓ⟧⟧θ

Start a breadth-first search with an empty substring list that still has the initial input to processes.

≔⟦⟧ηＷＳ⊞ηι

Input the list of words.

Ｆθ«

Loop over the list of substring lists.

≔⊟ιζ

Remove the remainder of the input from this substring list.

¿ζ

If there is still any input left:

Ｆ⁺η⟦§ζ⁰⟧

For each of the input words, plus the first letter of the remainder of the input, ...

Ｆ⁼κ✂ζ⁰Ｌκ

... if the remainder of the input begins with this string, ...

⊞θ⁺ι⟦κ✂ζＬκ⟧

... then push a new substring list obtained by splitting the input after that string.

⊞υι

Otherwise, save this substring list.

»⊟Φυ⁼Ｌι⌊ＥυＬλ

Output any one shortest substring list.