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 ox
no 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 código de golf .
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
gnu
yrat
,gnat
es 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
fuente
You may optionally receive this list as input
- ¿eso significa que no cuenta para el puntaje, mientras que codificarlo sí?Respuestas:
Japt,
514845363319 bytesGuardado 9 bytes gracias a @PeterTaylor
¡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
ant
inelephant
, ela
inela
, elnt
ine 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:Podemos hacer esto con bastante facilidad:
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:
Aquí hay una demostración básica de cómo y por qué funciona esto (
.
en lugar de un espacio):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í:
¡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í )
fuente
(?!,,,)
?GNU grep, 62 + 1 = 63 bytes
Esto requiere la
P
opció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 comozoo
):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
\B
sin límite de palabras.fuente
\B
para 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 laP
opción)grep: exceeded PCRE's backtracking limit
.ES6,
122121119104 bytesHabí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.
Editar: Guardado
1 byte3 bytes gracias a @ETHproductions.* Excepto que usé & s porque se ve mejor en mi
replace
.fuente
(`(?!&&&)(${a.map...})`)
como cadena, 2) eliminar los paréntesis después de hacer eso, 3) usareval`/(?!&&&).../`
?()
s externos que no funcionan; con el()
funciona y me ahorra un byte.eval
también necesita el()
s para que no guarde nada más, lo siento.a.replace(...)
.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.JS ES6, 77 bytes
(esto es anónimo fn)
La entrada es la misma que la entrada de ejemplo grep anterior
fuente
prompt()
¿no debería usar la salidaalert()
? (Alternativamente, simplemente haga que esto sea una función.)