En el espíritu de Patch the Image , aquí hay un desafío similar pero con texto.
Reto
¡La podredumbre ha afectado tu precioso texto! Dado un párrafo compuesto por caracteres ASCII, con un agujero rectangular en algún lugar, su programa debe intentar completar el agujero con el texto apropiado, de modo que el párrafo se mezcle lo mejor posible.
Definiciones adicionales
- El agujero siempre será rectangular y puede abarcar varias líneas.
- Solo habrá un agujero.
- Tenga en cuenta que el agujero no necesariamente cae en los límites de las palabras (de hecho, generalmente no lo hará).
- El agujero será como máximo el 25% del párrafo de entrada, pero puede superponerse o extenderse más allá del "final" del texto "normal" (vea los ejemplos de Euclides o Badger a continuación).
- Dado que encontrar el agujero no es el punto principal de este desafío, estará compuesto únicamente por marcas hash
#
para permitir una fácil identificación. - Ninguna otra ubicación en el párrafo de entrada tendrá una marca hash.
- Su código no puede usar el texto "normal" en los ejemplos a continuación: solo recibirá y procesará el texto con el agujero.
- La entrada puede ser como una sola cadena de varias líneas, como una matriz de cadenas (un elemento por línea), como un archivo, etc., su elección de lo que sea más conveniente para su idioma.
- Si lo desea, se puede tomar una entrada adicional opcional que detalle las coordenadas del agujero (por ejemplo, una tupla de coordenadas o similar).
- Describa su algoritmo en su envío.
Votación
Se les pide a los votantes que juzguen las entradas en función de qué tan bien el algoritmo llena el agujero de texto. Algunas sugerencias incluyen lo siguiente:
- ¿El área rellenada coincide con la distribución aproximada de espacios y puntuación como el resto del párrafo?
- ¿El área rellenada presenta una sintaxis defectuosa? (p. ej., dos espacios seguidos, un punto seguido de un signo de interrogación, una secuencia errónea como
, ,
, etc.) - Si entrecierra los ojos (por lo que en realidad no está leyendo el texto), ¿puede ver dónde solía estar el agujero?
- Si no hay palabras de CamelCase fuera del agujero, ¿el agujero contiene alguna? Si no hay letras en mayúscula fuera del hoyo, ¿contiene el hoyo? Si hay muchas letras en mayúscula fuera del hoyo, ¿el hoyo contiene una cantidad proporcional?
Criterio de validez
Para que un envío se considere válido, no debe alterar ningún texto del párrafo fuera del agujero (incluidos los espacios finales). Una nueva línea final al final es opcional.
Casos de prueba
El formato es el párrafo original en un bloque de código, seguido del mismo párrafo con un agujero. Los párrafos con el agujero se utilizarán como entrada.
1 (parchear la imagen)
In a popular image editing software there is a feature, that patches (The term
used in image processing is inpainting as @minxomat pointed out.) a selected
area of an image, based on the information outside of that patch. And it does a
quite good job, considering it is just a program. As a human, you can sometimes
see that something is wrong, but if you squeeze your eyes or just take a short
glance, the patch seems to fill in the gap quite well.
In a popular image editing software there is a feature, that patches (The term
used in image processing is inpainting as @minxomat pointed out.) a selected
area of an image, #############information outside of that patch. And it does a
quite good job, co#############is just a program. As a human, you can sometimes
see that something#############t if you squeeze your eyes or just take a short
glance, the patch seems to fill in the gap quite well.
2 (Dirección de Gettysburg)
But, in a larger sense, we can not dedicate, we can not consecrate, we can not
hallow this ground. The brave men, living and dead, who struggled here, have
consecrated it, far above our poor power to add or detract. The world will
little note, nor long remember what we say here, but it can never forget what
they did here. It is for us the living, rather, to be dedicated here to the
unfinished work which they who fought here have thus far so nobly advanced. It
is rather for us to be here dedicated to the great task remaining before us-
that from these honored dead we take increased devotion to that cause for which
they gave the last full measure of devotion-that we here highly resolve that
these dead shall not have died in vain-that this nation, under God, shall have
a new birth of freedom-and that government of the people, by the people, for
the people, shall not perish from the earth.
But, in a larger sense, we can not dedicate, we can not consecrate, we can not
hallow this ground. The brave men, living and dead, who struggled here, have
consecrated it, far above our poor power to add or detract. The world will
little note, nor long remember what we say here, but it can never forget what
they did here. It is for us the living, rather, to be dedicated here to the
unfinished work which they who fought here h######################advanced. It
is rather for us to be here dedicated to the######################before us-
that from these honored dead we take increas######################use for which
they gave the last full measure of devotion-######################solve that
these dead shall not have died in vain-that ######################, shall have
a new birth of freedom-and that government of the people, by the people, for
the people, shall not perish from the earth.
3 (Lorem Ipsum)
Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do
eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim
ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut
aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit
in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur
sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt
mollit anim id est laborum.
Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do
eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim
ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut
aliquip ex ea commodo conse################irure dolor in reprehenderit
in voluptate velit esse cil################giat nulla pariatur. Excepteur
sint occaecat cupidatat non################in culpa qui officia deserunt
mollit anim id est laborum.
4 (Jabberwocky)
'Twas brillig, and the slithy toves
Did gyre and gimble in the wabe;
All mimsy were the borogoves,
And the mome raths outgrabe.
'Twas brillig, and the slithy toves
Did gyre a######### in the wabe;
All mimsy #########borogoves,
And the mome raths outgrabe.
5 (Prueba de Euclides del Teorema de Pitágoras)
1.Let ACB be a right-angled triangle with right angle CAB.
2.On each of the sides BC, AB, and CA, squares are drawn,
CBDE, BAGF, and ACIH, in that order. The construction of
squares requires the immediately preceding theorems in Euclid,
and depends upon the parallel postulate. [footnote 14]
3.From A, draw a line parallel to BD and CE. It will
perpendicularly intersect BC and DE at K and L, respectively.
4.Join CF and AD, to form the triangles BCF and BDA.
5.Angles CAB and BAG are both right angles; therefore C, A,
and G are collinear. Similarly for B, A, and H.
6.Angles CBD and FBA are both right angles; therefore angle ABD
equals angle FBC, since both are the sum of a right angle and angle ABC.
7.Since AB is equal to FB and BD is equal to BC, triangle ABD
must be congruent to triangle FBC.
8.Since A-K-L is a straight line, parallel to BD, then rectangle
BDLK has twice the area of triangle ABD because they share the base
BD and have the same altitude BK, i.e., a line normal to their common
base, connecting the parallel lines BD and AL. (lemma 2)
9.Since C is collinear with A and G, square BAGF must be twice in area
to triangle FBC.
10.Therefore, rectangle BDLK must have the same area as square BAGF = AB^2.
11.Similarly, it can be shown that rectangle CKLE must have the same
area as square ACIH = AC^2.
12.Adding these two results, AB^2 + AC^2 = BD × BK + KL × KC
13.Since BD = KL, BD × BK + KL × KC = BD(BK + KC) = BD × BC
14.Therefore, AB^2 + AC^2 = BC^2, since CBDE is a square.
1.Let ACB be a right-angled triangle with right angle CAB.
2.On each of the sides BC, AB, and CA, squares are drawn,
CBDE, BAGF, and ACIH, in that order. The construction of
squares requires the immediately preceding theorems in Euclid,
and depends upon the parallel postulate. [footnote 14]
3.From A, draw a line parallel to BD and CE. It will
perpendicularly intersect BC and DE at K and L, respectively.
4.Join CF and AD, to form the triangles BCF and BDA.
5.Angles CAB and BAG are both right angles; therefore C, A,
and G are #############milarly for B, A, and H.
6.Angles C#############e both right angles; therefore angle ABD
equals ang############# both are the sum of a right angle and angle ABC.
7.Since AB#############FB and BD is equal to BC, triangle ABD
must be co#############iangle FBC.
8.Since A-#############ight line, parallel to BD, then rectangle
BDLK has t############# of triangle ABD because they share the base
BD and hav#############titude BK, i.e., a line normal to their common
base, conn#############rallel lines BD and AL. (lemma 2)
9.Since C #############with A and G, square BAGF must be twice in area
to triangl#############
10.Therefo############# BDLK must have the same area as square BAGF = AB^2.
11.Similar############# shown that rectangle CKLE must have the same
area as square ACIH = AC^2.
12.Adding these two results, AB^2 + AC^2 = BD × BK + KL × KC
13.Since BD = KL, BD × BK + KL × KC = BD(BK + KC) = BD × BC
14.Therefore, AB^2 + AC^2 = BC^2, since CBDE is a square.
6 (tejón, tejón, tejón por weebl)
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Mushroom, mushroom, a-
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Mushroom, mushroom, a-
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Mush-mushroom, a
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Argh! Snake, a snake!
Snaaake! A snaaaake, oooh its a snake!
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Mushroom, mushroom, a-
Badger##################badger, badger,
badger##################badger, badger
Mushro##################
Badger##################badger, badger,
badger##################badger, badger
Mush-mushroom, a
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Argh! Snake, a snake!
Snaaake! A snaaaake, oooh its a snake!
fuente
Respuestas:
Python 2
Sé que @atlasologist ya publicó una solución en Python 2, pero la forma en que funciona es un poco diferente. Esto funciona yendo a través de todos los agujeros, de arriba a abajo, de izquierda a derecha, mirando a los 5 personajes hacia atrás y al personaje de arriba, y encontrando un personaje donde coincidan. Si se encuentran varios caracteres, elige el más común. En caso de que no se encuentren caracteres, se elimina la restricción de caracteres anteriores. Si aún no se encuentran caracteres, disminuye la cantidad de caracteres que mira hacia atrás y se repite.
Aquí está el resultado de Badger, Badger, Badger:
Aquí está el resultado de la prueba:
Y el resultado de Jabberwocky:
fuente
Python 2
Esta es una solución bastante sencilla. Crea una cadena de muestra compuesta de palabras que se encuentran entre la longitud promedio de las palabras
A
: (A
/ 2) yA
+ (A
/ 2), luego aplica fragmentos recortados del espacio inicial y final de la muestra al área del parche. No maneja las mayúsculas, y estoy seguro de que hay un caso de prueba de bola curva que lo rompería, pero funciona bien en los ejemplos. Consulte el siguiente enlace para ejecutar todas las pruebas.También puse un parche en el código por si acaso.
Lorem Ipsum, original y luego parcheado:
Intentalo
fuente
mushroger
...#
caracteres en el código.@
, nada interesante.Java Shakespeare
¿Quién necesita una comprensión de las convenciones inglesas estándar? ¡Solo haz el tuyo! Al igual que al bardo se le permitió inventar sus propias palabras. Este bot no se preocupa demasiado por corregir las palabras cortadas, realmente solo inserta palabras al azar. El resultado es una hermosa poesía. Como característica adicional, el bardo es de un calibre más alto y puede manejar múltiples agujeros siempre que sean del mismo tamaño.
Entrada de muestra
Hermosa salida
Las últimas dos líneas son profundamente poéticas si lo digo yo mismo. Se desempeña sorprendentemente bien en la dirección de Gettysburg también.
Veamos qué hace que Shakespeare funcione. Aquí está el código. Esencialmente se esfuerza por construir una base de vocabulario a partir de la entrada. Luego usa estas palabras y las coloca al azar en el agujero (asegurándose de que encajen bien). Es determinista ya que usa una semilla fija para aleatoriedad.
La mayor parte de la poesía de Shakespeare es de dominio público.
fuente
Python 2.7
Otra solución de Python con un enfoque diferente. Mi programa ve el texto como una cadena de Markov , donde cada letra es seguida por otra letra con una cierta probabilidad. Entonces, el primer paso es construir la tabla de probabilidades. El siguiente paso es aplicar esas probabilidades al parche.
El código completo, incluido un texto de ejemplo, se encuentra a continuación. Debido a que un ejemplo usaba caracteres Unicode, incluí una página de códigos explícita (utf-8) para compatibilidad con ese ejemplo.
Salida de muestra para Lorem Ipsum:
Una línea poética extra en el Jabberwocky:
fuente
C # 5 masivo como siempre
Creé esto, es un poco desordenado, pero produce algunos buenos resultados algunas veces. Es un algoritmo mayormente determinista, pero con cierta aleatoriedad (semilla fija) agregada para evitar que produzca la misma cadena para huecos similares. Es necesario un esfuerzo para tratar de evitar tener columnas de espacios a ambos lados de los espacios.
Funciona mediante la tokenización de la entrada en palabras y puntuación (la puntuación proviene de una lista ingresada manualmente, porque no me molesto en averiguar si Unicode puede hacer esto por mí), para que pueda poner espacios antes de las palabras, y no antes puntuación, porque esto es bastante típico. Se divide en espacios en blanco típicos. En la línea de las cadenas de Markov (creo), cuenta con qué frecuencia cada ficha sigue a la otra ficha, y luego no calcula las probabilidades para esto (me imagino que debido a que los documentos son tan pequeños, sería mejor sesgar las cosas vemos mucho donde podemos). Luego realizamos una búsqueda de amplitud, llenando el espacio dejado por los hashes y las palabras 'parciales' a cada lado, con el costo calculado como
-fabness(last, cur) * len(cur_with_space)
, dondefabness
devuelve el número de veces quecur
ha seguidolast
para cada token agregado en la cadena generada. Naturalmente, tratamos de minimizar el costo. Debido a que no siempre podemos llenar el vacío con las palabras y los signos de puntuación que se encuentran en el documento, también considera una serie de tokens 'especiales' de ciertos estados, incluidas las cadenas parciales en ambos lados, contra las cuales sesgamos con costos arbitrariamente incrementados.Si el BFS no logra encontrar una solución, entonces intentamos ingenuamente elegir un adverbio aleatorio, o simplemente insertar espacios para llenar el espacio.
Resultados
Los 6 se pueden encontrar aquí: https://gist.github.com/anonymous/5277db726d3f9bdd950b173b19fec82a
El caso de prueba de Euclides no salió muy bien ...
Parchear la imagen
Jabberwocky
Tejón
_Estoy contento con la forma en que resultó ... es fortuito que "tejón, tejón" encaje, o este no hubiera funcionado tan bien
Código
Ejecútalo con
Hay bastante de eso. El único bit remotamente interesante es el
Fill
método. Incluyo la implementación del montón, porque .NET no tiene una (¿POR QUÉ MS POR QUÉ?).fuente