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

• Martin Ender: I'm still taking suggestions for a better title...
• marinus: You may optionally receive this list as input - does that mean it doesn't count towards the score, whereas hard-coding it would?
• Martin Ender: @marinus Yes. So you'll probably want to take it as additional input, unless reading more than one string on input is really cumbersome in your language of choice. (I don't want to allow hardcoding + "if you do, subtract it from your score", because then you'll get people hardcoding and compressing it in, which would essentially give them a bonus to their score.)
• user42643: Does "function (out) parameter" include parameters by reference?
• Peter Taylor: I can't believe I missed the "round number" comment in the sandbox. Shame on you, sir! Around these parts 32 is a round number, not 30. (And it's not entirely try that you left out names for male animals - see hog).

Answer 1

Japt, (削除) 51 (削除ここまで) (削除) 48 (削除ここまで) (削除) 45 (削除ここまで) (削除) 36 (削除ここまで) (削除) 33 (削除ここまで) 19 bytes

Saved 9 bytes thanks to @PeterTaylor

;!UeVrE"[$& ]" S2 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 S2 // 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)

• Peter Taylor: "This is not an easy thing to with regex alone" - what's wrong with (?!,,,)?
• ETHproductions: @PeterTaylor facepalm Thanks, that saves about 10 bytes...
• ETHproductions: @PeterTaylor I've found a much shorter method: simply replace with two spaces instead of three. Down to 19 bytes!
• Neil: Another facepalm moment then?
• ETHproductions: @Neil Yep, pretty much. I'd thought about trying two spaces instead of three, but I didn't realize it would work so well until this morning when thinking through many alternate strategies.

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.

• Martin Ender: Does grep not have non-word-boundaries \B so you can get rid of the last lookahead? (If it doesn't, switching to Retina would save a few bytes. Actually I think it would save a byte anyway, because it doesn't need the P option.)
• Martin Ender: I can't test with grep right now, but does this actually handle the large falsy test cases in a few seconds? In Retina the backtracking takes quite a while.
• feersum: @MartinBüttner For the last couple of falsy cases, it actually gave up and printed grep: exceeded PCRE's backtracking limit.
• Antti29: Using GNU something to solve this seems highly appropriate.

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.

• ETHproductions: Very nice! Would any of these things work: 1) using (`(?!&&&)(${a.map...})`) as the string, 2) removing the parentheses after doing that, 3) using eval`/(?!&&&).../` ?
• Neil: @ETHproductions I made the mistake of removing the outer ()s which doesn't work; with the () it works and saves me a byte. eval also needs the ()s so it doesn't save anything further, sorry.
• ETHproductions: I think you also have an extra pair of parentheses around a.replace(...).
• ETHproductions: You can save a bunch: s=s.replace(RegExp(a.map(a=>a.replace(/./g,"[&$&]")).join`|`),'&&') Replacing with two chars instead of three removes the possibility of getting stuck replacing the same three chars over and over.

Answer 4

Python3, 342 bytes

def f(s):
 q,S=[''],[]
 for c in q:
 for i in'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'.split(','):
 for j in range(1,3):
 for C in[c[:-j]+i]+[c+i[j:]]*(c!=''):
 if C==s:return 1
 if any(s.startswith(C[:-t])for t in[1,2])and C not in S:q+=[C];S+=[C]

Try it online!

• ceilingcat: 301 bytes

Answer 5

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

• Neil: If you're taking input with prompt() shouldn't you output using alert()? (Alternatively just make this a function.)