Imposters at the Zoo

Question

You want to open a new zoo. It'll be amazing. But being the cheapskate that you are, you only want to afford three-letter animals (everyone knows that an animal's cost is proportional to the length of its name). There goes your dream of making people pay to see an elephant. But suddenly you have a brilliant idea. If you just place the animals correctly in the pen, you can create the optical illusion of an elephant! Here is a top-down view of your new "elephant compound":

elk
  eel
   pig
    hog
     ant

--------  (fence)
    ^
    | viewing direction

Haha, those gullible visitors!

^{Yes, this is how perception works.}

The Challenge

Given a non-empty word consisting only of lowercase English letters, determine if it can be formed from overlapping the following 30 three-letter animal words:

ant ape asp ass bat bee boa cat cod cow 
dab dog eel elk emu fly fox gnu hog ide 
jay kea kob koi olm owl pig rat ray yak

^{Yes, there are more than 30, but that's a nice round number.}

You may optionally receive this list as input (in any reasonable list or string format, as long as it's not pre-processed). You'll probably want to do this, unless reading and processing this input list is much more expensive than hardcoding and compressing it in your language of choice. Note that even if you take the list as input you may assume that it will always be exactly this list, so if your code relies on the passed list being 30 elements long and not containing a word with z, that's fine.

Each word can be used multiple times. Animals cannot be cut off at the ends, only partially hidden by other animals. So ox is not a possible string, even though we have fox.

Output should be truthy if this is possible, and falsy otherwise.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

Your code should handle any of the test cases in a few seconds.

Standard code-golf rules apply.

More Examples

• Any one- or two-letter word is obviously falsy.
• So is any three-letter word which is not in the above list.
• Even though we have gnu and rat, gnat is falsy since there's no way to arrange them such that you only see two letters of each (we don't want to cut animals into thirds).

Some truthy examples:

pigment

    ant
  bee
 olm
pig

antioxidant

   fox
 koi  ide
ant     ant

Test Cases

Most of the test cases were taken from running a reference implementation against a dictionary. The last few "words" were generated randomly and are just there to ensure that submissions are sufficiently efficient.

Truthy:

ant
owl
bass
pride
bobcat
peafowl
elephant
hedgehogs
crocodile
antidemocrat
aspidoganoidei
biodegradability
angioelephantiasis
propreantepenultimate
acategnukeaidabeleenaspcodcoidyakwakoasshogattkjaypigkobolcodidaskearaywelkwboaxbeeuflapaspoapemaassaaspeewoglmabiemuwjadogacagnuepigjaycownbatjaemuifoxkeaeekekeagratsseeluejdoghogaolmgpigbeaeelemulasphogjaydabemukgnunueifoasdoglrayyadogpewlayroassasslgnuaspyyakkbokeaodxilopgnuasppigkobelratelkolmakob
koigdgaspslycoyakehrdabowbatdkkeapogkobelrowlyarpidepetlfoxeboaiderbeefoxbgnuapeocowgiecowlkoieeltbategspemuideatdogbeeecatgeaoccattbbeassgnasolkeaflyelkaognubeeabrratoccolmobodoglyelraywelkoxantowleedrayflypeappigogatraoyakccpiganaaspkobabjaspkointantybjbeeanolmuijaylratojaynueidflyjarayabatmmpigtfly
eolmantjkobeeaorayogaowldfoxayeassapibatmflylyraelaspsseolmbelkkaoantlmufodasgnueantaidenthyakcodoxuepigodggnuantatlcatnuuelkpemucbapeeoiahdogplkowletbatdrayarayoaelkgrayodcatgkantewkobeljaybeeyfkobtbdabadoghbatfoxtflygaspdeidogtowlkeaolmyraelfleelejayehogowlccatoxeabiemkobpigolmdkobrcidekyakabboyidep

Falsy:

a
ox
ram
bear
koala
antelope
albatross
zookeeper
salamander
caterpillar
hippopotamus
koigdgaspslycoyakehrdabowbatdkkeapogkobelrowlyarpidepetlfoxeboaiderbeefoxbgnuapeocowgiecowlkoieeltbategspemuideatdogbeezcatgeaoccattbbeassgnasolkeaflyelkaognubeeabrratoccolmobodoglyelraywelkoxantowleedrayflypeappigogatraoyakccpiganaaspkobabjaspkointantybjbeeanolmuijaylratojaynueidflyjarayabatmmpigtfly
koigdgaspslycoyakehrdabowbatdkkeapogkobelrowlyarpidepetlfoxeboaiderbeefoxbgnuapeocowgiecowlkoieeltbategspemuideatdogbeeecatgeaoccattbbeassgnasolkeaflxelkaognubeeabrratoccolmobodoglyelraywelkoxantowleedrayflypeappigogatraoyakccpiganaaspkobabjaspkointantybjbeeanolmuijaylratojaynueidflyjarayabatmmpigtfly
beyeodpgspeclxlkbkaylldnceepkocbdmymsaogsowpbawbauaioluaaagaetdoaoialeoxaagspoelegflpylptylnolnatrjabaorkdteeydloiebbptatdtfdfgoodtbkoafmounbduaffcrfelcnawmxaskgaoenaattbaobgbgabnhkesbgaaaaotafkiiieatworginaeowaehuddegooaalowaoososaksahoimkulbtoadyyelkcmkacbuostadppcuglbnmotedfgfkoleldonknemomnmoutykg

Answer 1

Japt, 51 48 45 36 33 19 bytes

Saved 9 bytes thanks to @PeterTaylor

;!UeVrE"[$& ]" S² x

Test it online!

Takes input as the string to test, followed by the list of three-letter words, delimited with |. Note: this doesn't work in the latest version of the interpreter, so please use the link instead of copy-pasting the code.

How it works

The basic idea is to take the input string and repeatedly replace any of the 30 words in it with two filler chars. I use a space as the filler char. Also, we want to replace the ant in elephant, the a   in ela   , the  nt in e   nt, etc. So what we want to do is to change the 30-word string to a regex that matches any of these combinations:

ant|ape|asp|...
Becomes:
[a ][n ][t ]|[a ][p ][e ]|[a ][s ][p ]|...

We can do this pretty easily:

;VrE"[$& ]"
          // Implicit: V = "ant|ape|asp|..."
;         // Set the vars A-J to various values. E is set to "[a-z]".
VrE       // Take V and replace each lowercase letter with:
"[$& ]"   //  "[" + the char + " ]".

However, this has the undesired effect of also matching three spaces, which has no effect on the result and thus ends the recursive replacement. We can get around this by replacing the match with two spaces instead of three:

Ue    S²  // Take U, and recursively replace matches of the regex with " ".repeat(2).

Here's a basic demonstration of how and why this works (using . in place of a space):

First match at the end: 
eleant
ele..   (ant)
el..    (eel)
...     (elk)
..      (...)
true

First match at the beginning: 
antmua
..mua   (ant)
...a    (emu)
..a     (...)
..      (boa)
true

First match in the middle: 
cantay
c..ay   (ant)
..ay    (cat)
...     (jay)
..      (...)
true

For truthy test-cases, this leaves us with a string of all spaces. For falsy test-cases, we have some letters left in the mix. This can be translated to true/false like so:

     x   // Trim all spaces off the ends of the resulting string.
!        // Take the logical NOT of the result.
         // Empty string -> true; non-empty string -> false.

And that's about it! A bonus of this method is that even the largest test cases finish in under 5 milliseconds. (Tested here)

Answer 2

GNU grep, 62 + 1 = 63 bytes

^(((.+)(?=.*!\3))*(...)(?=.*\4!)((.+)(?=.*\6!))*([^qvz]\B)?)+ 

This requires the P option. The input is expected to be the animal to be synthesized, followed by a space, followed by the list of 3-letter animals opened, closed, and delimited by exclamation marks. Example usage (assuming the program is saved as zoo):

> grep -Pf zoo
hippopotamus !ant!ape!asp!ass!bat!bee!boa!cat!cod!cow!dab!dog!eel!elk!emu!fly!fox!gnu!hog!ide!jay!kea!kob!koi!olm!owl!pig!rat!ray!yak!

For a true input, the input line is echoed back. For a false input, there is no output.

Thanks to Martin for spotting a bug and alerting me to the existence of \B for word non-boundary.

Answer 3

ES6, 122 121 119 104 bytes

I had worked out how to do this as far as ETHproduction's answer but couldn't think of how to handle the ,,,* problem, so naturally when I saw Peter Taylor's comment it all became clear. Then ETHproductions managed to find a better way to handle the problem which helpfully saves 15 bytes.

Input is the target word and an array of animal words.

(s,a)=>[...s].map(_=>s=s.replace(RegExp(a.map(a=>a.replace(/./g,"[&$&]")).join`|`),'&&'))&&!/\w/.test(s)

Edit: Saved 1 byte 3 bytes thanks to @ETHproductions.

*Except I used &s because it looks nicer in my replace.

Answer 4

JS ES6, 77 bytes

s=>/^(((.+)(?=.*!\3))*(...)(?=.*\4!)((.+)(?=.*\6!))*([^qvz][^\b])?)+/.test(s)

(this is anonymous fn)

Input is the same as the above grep example input