7
\$\begingroup\$

For this challenge you need to make a given word by concatenating "pieces" (a.k.a contiguous substrings) from other words. Given a word and a list of words as input, output the fewest number of pieces needed to create the first word.

Rules

  • Words consist of characters in the ASCII range 33 to 126.
  • The word list may have repeats.
  • Construction of words is case sensitive (you can not use the piece "Head" as part of the word "forehead".)
  • Once you have used a piece in a construction, you can not use any part of that piece again (e.g if I use "lo" from "lone" as part of constructing "lolo", I cannot use "lo" from that "lone" again. However, if I had two "lone" in my word list, I could use one "lo" from each.)
  • Once you use a piece, you can still make pieces out of unused substrings in the word. (E.g. If I used "tt" in "butter", I still have "bu" and "er" left over to use. However, I can't combine them into one "buer" piece.)
  • If it is impossible to construct the input word using the word list given, output nothing, or something other than a positive integer.

Examples

(you only need to output the number)

  • "snack" ["food","Shoe","snack"] => 1 (snack)
  • "Snack" ["food","Shoe","snack"] => 2 (S + nack)
  • "frog" ["cat","dog","log"] => 0
  • "~~Frank~~" ["Frog~","~~Love","Hank~"] => 4 (~~ + Fr + ank~ + ~)
  • "loop-de-loop" ["loop", "frien-d","-elk","pool"] => 7 (loop + -d + e + - + l + oo + p)
  • "banana" ["can","can","boa"] => 4 (b+an+an+a)
  • "banana" ["can","boa"] => 0
  • "13frnd" ["fr13nd"] => 3 (13 + fr + nd)

Let me know if you think of more useful test cases.

\$\endgroup\$
  • 1
    \$\begingroup\$ pieces are usually called contiguous substrings. \$\endgroup\$ – Mr. Xcoder Jul 22 '17 at 16:58
  • \$\begingroup\$ @Mr.Xcoder thanks, updated. \$\endgroup\$ – geokavel Jul 22 '17 at 17:11
2
\$\begingroup\$

JavaScript, 209 206 bytes

f=(a,b,F)=>a?[...a].map((_,i)=>[...Array(i+1)].map((_,j)=>F||b.forEach((q,k)=>!F&&~(I=q.indexOf(a[S='substring'](j,r=a.length-i+j)))&&(F=b[k]=q[S](0,I)+' '+q[S](I+r+j),a=a[S](0,j)+a[S](r)))))&&F&&1+f(a,b):0

Try it online

Returns NaN if the combination is not found.

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