Impostores en el zoológico

42

Quieres abrir un nuevo zoológico. Será asombroso. Pero siendo el tacaño que eres, solo quieres permitirte animales de tres letras (todos saben que el costo de un animal es proporcional a la longitud de su nombre). Ahí va tu sueño de hacer que la gente pague para ver un elephant. Pero de repente tienes una idea brillante. Si solo coloca los animales correctamente en el corral, ¡puede crear la ilusión óptica de un elephant! Aquí hay una vista de arriba hacia abajo de su nuevo "compuesto de elefante":

elk
  eel
   pig
    hog
     ant

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

Jaja, esos crédulos visitantes!

Sí, así es como funciona la percepción.

El reto

Dada una palabra no vacía que consiste solo en letras minúsculas en inglés, determine si se puede formar solapando las siguientes 30 palabras animales de tres 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

Sí, hay más de 30, pero ese es un buen número redondo.

Opcionalmente, puede recibir esta lista como entrada (en cualquier lista razonable o formato de cadena, siempre que no esté preprocesada). Probablemente desee hacer esto, a menos que leer y procesar esta lista de entrada sea mucho más costoso que codificarlo y comprimirlo en el idioma que elija. Tenga en cuenta que incluso si toma la lista como entrada, puede suponer que siempre será exactamente esta lista, por lo que si su código se basa en que la lista aprobada tiene 30 elementos y no contiene una palabra z, está bien.

Cada palabra se puede usar varias veces. Los animales no pueden ser cortados en los extremos, solo parcialmente ocultos por otros animales. Entonces oxno es una cadena posible, aunque la tengamos fox.

La salida debe ser veraz si esto es posible, y falsa de lo contrario.

Puede escribir un programa o función, tomando la entrada a través de STDIN (o la alternativa más cercana), argumento de línea de comando o argumento de función y generando el resultado a través de STDOUT (o la alternativa más cercana), el valor de retorno de la función o el parámetro de función (out).

Su código debe manejar cualquiera de los casos de prueba en unos segundos.

Aplican reglas estándar de .

Más ejemplos

  • Cualquier palabra de una o dos letras es obviamente falsa.
  • Lo mismo ocurre con cualquier palabra de tres letras que no esté en la lista anterior.
  • A pesar de que tenemos gnuy rat, gnates falso, ya que no hay forma de organizarlos de modo que solo veas dos letras de cada uno (no queremos cortar animales en tercios).

Algunos ejemplos verdaderos:

pigment

    ant
  bee
 olm
pig
antioxidant

   fox
 koi  ide
ant     ant

Casos de prueba

La mayoría de los casos de prueba se tomaron de ejecutar una implementación de referencia contra un diccionario. Las últimas "palabras" se generaron al azar y están ahí para garantizar que las presentaciones sean lo suficientemente eficientes.

Verdad:

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
fuente
Todavía estoy tomando sugerencias para un mejor título ...
Martin Ender
You may optionally receive this list as input- ¿eso significa que no cuenta para el puntaje, mientras que codificarlo sí?
marinus
@marinus Sí. Por lo tanto, es probable que desee tomarlo como entrada adicional, a menos que leer más de una cadena en la entrada sea realmente engorroso en el idioma que elija. (No quiero permitir la codificación rígida + "si lo hace, restarlo de su puntaje", porque entonces la gente lo codificará y comprimirá, lo que esencialmente les daría una bonificación a su puntaje).
Martin Ender
¿El parámetro " función (fuera) " incluye parámetros por referencia ?
mınxomaτ
55
No puedo creer que me perdí el comentario del "número redondo" en el sandbox. ¡Qué vergüenza, señor! Alrededor de estas partes, el número 32 es un número redondo, no 30. (Y no se trata por completo de que se hayan omitido los nombres de los animales machos, ver cerdo).
Peter Taylor

Respuestas:

7

Japt, 51 48 45 36 33 19 bytes

Guardado 9 bytes gracias a @PeterTaylor

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

¡Pruébelo en línea!

Toma la entrada como la cadena a probar, seguida de la lista de palabras de tres letras, delimitadas con |. Nota: esto no funciona en la última versión del intérprete, así que utilice el enlace en lugar de copiar y pegar el código.

Cómo funciona

La idea básica es tomar la cadena de entrada y reemplazar repetidamente cualquiera de las 30 palabras con dos caracteres de relleno. Yo uso un espacio como el relleno de char. Además, queremos reemplazar el antin elephant, el a  in ela   , el  ntin e   nt, etc. Entonces, lo que queremos hacer es cambiar la cadena de 30 palabras a una expresión regular que coincida con cualquiera de estas combinaciones:

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

Podemos hacer esto con bastante facilidad:

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

Sin embargo, esto tiene el efecto no deseado de hacer coincidir también tres espacios, lo que no tiene ningún efecto en el resultado y, por lo tanto, finaliza el reemplazo recursivo. Podemos evitar esto reemplazando la coincidencia con dos espacios en lugar de tres:

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

Aquí hay una demostración básica de cómo y por qué funciona esto ( .en lugar de un espacio):

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 prueba verdaderos, esto nos deja con una cadena de todos los espacios. Para los casos de prueba falsos, nos quedan algunas letras en la mezcla. Esto se puede traducir a verdadero / falso así:

     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.

¡Y eso es todo! Una ventaja de este método es que incluso los casos de prueba más grandes terminan en menos de 5 milisegundos. ( Probado aquí )

ETHproducciones
fuente
" Esto no es algo fácil con regex solo ", ¿qué tiene de malo (?!,,,)?
Peter Taylor
@PeterTaylor facepalm Gracias, eso ahorra unos 10 bytes ...
ETHproductions
1
@PeterTaylor He encontrado un método mucho más corto: simplemente reemplácelo con dos espacios en lugar de tres. ¡Hasta 19 bytes!
ETHproductions
¿Otro momento de facepalm entonces?
Neil
@Neil Sí, más o menos. Pensé en probar dos espacios en lugar de tres, pero no me di cuenta de que funcionaría tan bien hasta esta mañana, al pensar en muchas estrategias alternativas.
ETHproductions
3

GNU grep, 62 + 1 = 63 bytes

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

Esto requiere la Popción. Se espera que la entrada sea el animal que se va a sintetizar, seguido de un espacio, seguido de la lista de animales de 3 letras abiertos, cerrados y delimitados por signos de exclamación. Ejemplo de uso (suponiendo que el programa se guarde 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 una entrada verdadera, la línea de entrada se repite. Para una entrada falsa, no hay salida.

Gracias a Martin por detectar un error y alertarme sobre la existencia de \Bsin límite de palabras.

Feersum
fuente
¿Grep no tiene límites que no sean de palabras \Bpara que pueda deshacerse de la última búsqueda anticipada? (Si no es así, cambiar a Retina ahorraría unos pocos bytes. De hecho, creo que ahorraría un byte de todos modos, porque no necesita la Popción)
Martin Ender
No puedo probar con grep en este momento, pero ¿esto realmente maneja los grandes casos de prueba falsa en unos segundos? En Retina, el retroceso lleva bastante tiempo.
Martin Ender
1
@ MartinBüttner Para los últimos dos casos falsos, en realidad se rindió e imprimió grep: exceeded PCRE's backtracking limit.
feersum
1
Usar GNU para resolver esto parece muy apropiado.
Antti29
2

ES6, 122 121 119 104 bytes

Había resuelto cómo hacer esto en lo que respecta a la respuesta de ETHproduction, pero no podía pensar en cómo manejar el ,,,problema *, así que, naturalmente, cuando vi el comentario de Peter Taylor, todo quedó claro. Luego, ETHproductions logró encontrar una mejor manera de manejar el problema que ahorra 15 bytes.

La entrada es la palabra objetivo y un conjunto de palabras animales.

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

Editar: Guardado 1 byte 3 bytes gracias a @ETHproductions.

* Excepto que usé & s porque se ve mejor en mi replace.

Neil
fuente
¡Muy agradable! ¿Funcionaría alguna de estas cosas: 1) usar (`(?!&&&)(${a.map...})`)como cadena, 2) eliminar los paréntesis después de hacer eso, 3) usar eval`/(?!&&&).../` ?
ETHproductions
@ETHproductions Cometí el error de eliminar los ()s externos que no funcionan; con el ()funciona y me ahorra un byte. evaltambién necesita el ()s para que no guarde nada más, lo siento.
Neil
Creo que también tienes un par extra de paréntesis a.replace(...).
ETHproductions
Puede ahorrar un montón: s=s.replace(RegExp(a.map(a=>a.replace(/./g,"[&$&]")).join`|`),'&&')Reemplazar con dos caracteres en lugar de tres elimina la posibilidad de atascarse reemplazando los mismos tres caracteres una y otra vez.
ETHproductions
0

JS ES6, 77 bytes

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

(esto es anónimo fn)

La entrada es la misma que la entrada de ejemplo grep anterior

username.ak
fuente
Si está tomando entrada con, prompt()¿no debería usar la salida alert()? (Alternativamente, simplemente haga que esto sea una función.)
Neil
@Neil gracias, solía anon. fn
username.ak