Você quer abrir um novo zoológico. Vai ser incrível. Mas, sendo o preço mais baixo que você é, você só quer pagar animais de três letras (todo mundo sabe que o custo de um animal é proporcional ao tamanho do nome). Lá vai o seu sonho de fazer as pessoas pagarem para ver um elephant. Mas de repente você tem uma ideia brilhante. Se você colocar os animais corretamente na caneta, poderá criar a ilusão de ótica de um elephant! Aqui está uma visão de cima para baixo do seu novo "composto de elefantes":

elk
  eel
   pig
    hog
     ant

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

Haha, esses visitantes crédulos!

^{Sim, é assim que a percepção funciona.}

O desafio

Dada uma palavra não vazia que consiste apenas em letras minúsculas em inglês, determine se ela pode ser formada sobrepondo as seguintes 30 palavras animais de três letras:

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

^{Sim, existem mais de 30, mas esse é um bom número redondo.}

Opcionalmente, você pode receber esta lista como entrada (em qualquer formato razoável de lista ou sequência, desde que não seja pré-processado). Você provavelmente desejará fazer isso, a menos que ler e processar essa lista de entrada seja muito mais caro que codificá-la e compactá-la no seu idioma preferido. Observe que, mesmo que você tome a lista como entrada, você pode assumir que sempre será exatamente essa lista; portanto, se o seu código se basear na lista passada com 30 elementos e sem conter uma palavra z, tudo bem.

Cada palavra pode ser usada várias vezes. Os animais não podem ser cortados nas extremidades, apenas parcialmente escondidos por outros animais. Portanto, oxnão é uma string possível, mesmo que tenhamos fox.

A saída deve ser verdadeira, se isso for possível, e falsificar o contrário.

Você pode escrever um programa ou função, recebendo entrada via STDIN (ou alternativa mais próxima), argumento da linha de comando ou argumento da função e emitindo o resultado via STDOUT (ou alternativa mais próxima), valor de retorno da função ou parâmetro da função (saída).

Seu código deve lidar com qualquer um dos casos de teste em alguns segundos.

Aplicam-se as regras padrão de código de golfe .

Mais exemplos

• Qualquer palavra de uma ou duas letras é obviamente falsa.
• O mesmo ocorre com qualquer palavra de três letras que não esteja na lista acima.
• Mesmo que temos gnue rat, gnaté Falsas já que não há maneira de organizá-los de tal forma que você só vê duas cartas de cada um (que não quer cortar animais em terços).

Alguns exemplos verdadeiros:

pigment

    ant
  bee
 olm
pig

antioxidant

   fox
 koi  ide
ant     ant

Casos de teste

A maioria dos casos de teste foi retirada da execução de uma implementação de referência em um dicionário. As últimas "palavras" foram geradas aleatoriamente e existem apenas para garantir que os envios sejam suficientemente eficientes.

Verdade:

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

Japt, 51 48 45 36 33 19 bytes

Guardado 9 bytes graças a @PeterTaylor

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

Teste online!

Recebe a entrada como a sequência a ser testada, seguida pela lista de palavras de três letras, delimitada por |. Nota: isso não funciona na versão mais recente do intérprete, portanto, use o link em vez de copiar e colar o código.

Como funciona

A idéia básica é pegar a sequência de entrada e substituir repetidamente qualquer uma das 30 palavras nela por dois caracteres de preenchimento. Eu uso um espaço como caractere de preenchimento. Além disso, queremos substituir o antin elephant, o a  in ela   , o  ntin e   ntetc. Então, o que queremos fazer é alterar a sequência de 30 palavras para um regex que corresponda a qualquer uma dessas combinações:

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

Podemos fazer isso facilmente:

;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 + " ]".

No entanto, isso tem o efeito indesejável de combinar também três espaços, o que não afeta o resultado e, portanto, encerra a substituição recursiva. Podemos contornar isso substituindo a partida por dois espaços em vez de três:

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

Aqui está uma demonstração básica de como e por que isso funciona (usando .no lugar de um espaço):

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

Para casos de teste de verdade, isso nos deixa com uma sequência de todos os espaços. Para casos de teste falsos, ainda temos algumas letras na mistura. Isso pode ser traduzido para verdadeiro / falso da seguinte forma:

     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.

E é isso! Um bônus desse método é que mesmo os maiores casos de teste terminam em menos de 5 milissegundos. ( Testado aqui )

GNU grep, 62 + 1 = 63 bytes

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

Isso requer a Popção Espera-se que a entrada seja o animal a ser sintetizado, seguido por um espaço, seguido pela lista de animais de três letras abertos, fechados e delimitados por pontos de exclamação. Exemplo de uso (assumindo que o programa foi salvo como 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!

Para uma entrada verdadeira, a linha de entrada é repetida. Para uma entrada falsa, não há saída.

Agradeço a Martin por detectar um bug e me alertar sobre a existência de \Bpalavras não-limite.

ES6, 122 121 119 104 bytes

Eu havia descoberto como fazer isso na resposta da ETHproduction, mas não conseguia pensar em como lidar com o ,,,problema *, tão naturalmente quando vi o comentário de Peter Taylor, tudo ficou claro. Em seguida, a ETHproductions conseguiu encontrar uma maneira melhor de lidar com o problema, que economiza 15 bytes.

Entrada é a palavra alvo e uma matriz de palavras animais.

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

Edit: Salvo 1 byte 3 bytes graças a @ETHproductions.

* Exceto que eu usei o & s porque parece melhor no meu replace.

JS ES6, 77 bytes

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

(isto é anônimo fn)

Entrada é igual à entrada de exemplo grep acima