42
\$\begingroup\$

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 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
\$\endgroup\$
  • \$\begingroup\$ I'm still taking suggestions for a better title... \$\endgroup\$ – Martin Ender Jan 27 '16 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 '16 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\$ – Martin Ender Jan 27 '16 at 14:54
  • \$\begingroup\$ Does "function (out) parameter" include parameters by reference? \$\endgroup\$ – mınxomaτ Jan 27 '16 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\$ – Peter Taylor Jan 27 '16 at 16:34
7
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ "This is not an easy thing to with regex alone" - what's wrong with (?!,,,)? \$\endgroup\$ – Peter Taylor Jan 28 '16 at 19:46
  • \$\begingroup\$ @PeterTaylor facepalm Thanks, that saves about 10 bytes... \$\endgroup\$ – ETHproductions Jan 28 '16 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\$ – ETHproductions Jan 30 '16 at 14:26
  • \$\begingroup\$ Another facepalm moment then? \$\endgroup\$ – Neil Jan 30 '16 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\$ – ETHproductions Jan 30 '16 at 17:08
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\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\$ – Martin Ender Jan 27 '16 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\$ – Martin Ender Jan 27 '16 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 '16 at 16:32
  • 1
    \$\begingroup\$ Using GNU something to solve this seems highly appropriate. \$\endgroup\$ – Antti29 Nov 21 '17 at 18:49
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\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\$ – ETHproductions Jan 28 '16 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 '16 at 20:43
  • \$\begingroup\$ I think you also have an extra pair of parentheses around a.replace(...). \$\endgroup\$ – ETHproductions Jan 28 '16 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\$ – ETHproductions Jan 30 '16 at 14:44
0
\$\begingroup\$

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

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

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.