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":


--------  (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 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:



 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.




  • \$\begingroup\$ I'm still taking suggestions for a better title... \$\endgroup\$ Jan 27, 2016 at 14:44
  • \$\begingroup\$ You may optionally receive this list as input - does that mean it doesn't count towards the score, whereas hard-coding it would? \$\endgroup\$
    – marinus
    Jan 27, 2016 at 14:52
  • \$\begingroup\$ @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.) \$\endgroup\$ Jan 27, 2016 at 14:54
  • \$\begingroup\$ Does "function (out) parameter" include parameters by reference? \$\endgroup\$
    – user42643
    Jan 27, 2016 at 15:04
  • 5
    \$\begingroup\$ 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). \$\endgroup\$ Jan 27, 2016 at 16:34

4 Answers 4


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:

[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: 
ele..   (ant)
el..    (eel)
...     (elk)
..      (...)

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

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

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)

  • \$\begingroup\$ "This is not an easy thing to with regex alone" - what's wrong with (?!,,,)? \$\endgroup\$ Jan 28, 2016 at 19:46
  • \$\begingroup\$ @PeterTaylor facepalm Thanks, that saves about 10 bytes... \$\endgroup\$ Jan 28, 2016 at 19:51
  • 1
    \$\begingroup\$ @PeterTaylor I've found a much shorter method: simply replace with two spaces instead of three. Down to 19 bytes! \$\endgroup\$ Jan 30, 2016 at 14:26
  • \$\begingroup\$ Another facepalm moment then? \$\endgroup\$
    – Neil
    Jan 30, 2016 at 17:03
  • \$\begingroup\$ @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. \$\endgroup\$ Jan 30, 2016 at 17:08

GNU grep, 62 + 1 = 63 bytes


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.

  • \$\begingroup\$ 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.) \$\endgroup\$ Jan 27, 2016 at 16:08
  • \$\begingroup\$ 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. \$\endgroup\$ Jan 27, 2016 at 16:27
  • 1
    \$\begingroup\$ @MartinBüttner For the last couple of falsy cases, it actually gave up and printed grep: exceeded PCRE's backtracking limit. \$\endgroup\$
    – feersum
    Jan 27, 2016 at 16:32
  • 1
    \$\begingroup\$ Using GNU something to solve this seems highly appropriate. \$\endgroup\$
    – Antti29
    Nov 21, 2017 at 18:49

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.


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

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

  • \$\begingroup\$ 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`/(?!&&&).../` ? \$\endgroup\$ Jan 28, 2016 at 20:28
  • \$\begingroup\$ @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. \$\endgroup\$
    – Neil
    Jan 28, 2016 at 20:43
  • \$\begingroup\$ I think you also have an extra pair of parentheses around a.replace(...). \$\endgroup\$ Jan 28, 2016 at 20:48
  • \$\begingroup\$ 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. \$\endgroup\$ Jan 30, 2016 at 14:44

JS ES6, 77 bytes


(this is anonymous fn)

Input is the same as the above grep example input

  • \$\begingroup\$ If you're taking input with prompt() shouldn't you output using alert()? (Alternatively just make this a function.) \$\endgroup\$
    – Neil
    Jan 30, 2016 at 17:00
  • \$\begingroup\$ @Neil thanks, i used anon. fn \$\endgroup\$ Jan 30, 2016 at 20:32

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.