No espírito de Patch the Image , aqui está um desafio semelhante, mas com texto.
Desafio
A podridão por bits afligiu seu texto precioso! Dado um parágrafo composto por caracteres ASCII, com um orifício retangular em algum lugar, seu programa deve tentar preenchê-lo com o texto apropriado, para que o parágrafo seja o melhor possível.
Definições adicionais
- O furo sempre será retangular e poderá abranger várias linhas.
- Só haverá um buraco.
- Observe que o buraco não cai necessariamente nos limites das palavras (na verdade, geralmente não cai).
- O furo terá no máximo 25% do parágrafo de entrada, mas poderá se sobrepor ou se estender além do "final" do texto "normal" (consulte os exemplos de Euclides ou Texugos abaixo).
- Como encontrar o buraco não é o ponto principal desse desafio, ele será composto apenas por marcas de hash
#
para facilitar a identificação. - Nenhum outro local no parágrafo de entrada terá uma marca de hash.
- Seu código não pode usar o texto "normal" nos exemplos abaixo - ele receberá e processará apenas o texto com o orifício nele.
- A entrada pode ser como uma única string de várias linhas, como uma matriz de strings (um elemento por linha), como um arquivo etc. - sua escolha do que for mais conveniente para o seu idioma.
- Se desejado, uma entrada adicional opcional detalhando as coordenadas do furo pode ser obtida (por exemplo, uma tupla de coordenadas ou similares).
- Descreva seu algoritmo em seu envio.
Votação
Os eleitores são convidados a julgar as entradas com base em quão bem o algoritmo preenche o espaço do texto. Algumas sugestões incluem o seguinte:
- A área preenchida corresponde à distribuição aproximada de espaços e pontuação como o restante do parágrafo?
- A área preenchida apresenta uma sintaxe com defeito? (por exemplo, dois espaços seguidos, um período seguido de um ponto de interrogação, uma sequência incorreta como
, ,
etc.) - Se você apertar os olhos (para não ler o texto), consegue ver onde ficava o buraco?
- Se não houver palavras do CamelCase fora do buraco, ele contém alguma? Se não houver letras maiúsculas fora do buraco, o buraco contém alguma? Se houver muitas letras maiúsculas fora do furo, o furo contém uma quantidade proporcional?
Critério de validade
Para que uma submissão seja considerada válida, ela não deve alterar nenhum texto do parágrafo fora do furo (incluindo espaços finais). Uma única nova linha final no final é opcional.
Casos de teste
O formato é um parágrafo original em um bloco de código, seguido pelo mesmo parágrafo com um furo. Os parágrafos com o furo serão usados para entrada.
1 (Corrigir a imagem)
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 (Endereço 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 (Prova de Euclides do 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 (Texugo, Texugo, Texugo 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!
fonte
Respostas:
Python 2
Eu sei que o @atlasologist já postou uma solução em Python 2, mas a maneira como meu trabalho é um pouco diferente. Isso funciona percorrendo todos os buracos, de cima para baixo, da esquerda para a direita, olhando 5 caracteres para trás e para o personagem acima, e encontrando um personagem onde eles correspondam. Se vários caracteres forem encontrados, ele escolherá o mais comum. Caso não sejam encontrados caracteres, ele remove a restrição de caracteres acima. Se ainda não houver caracteres encontrados, isso diminuirá a quantidade de caracteres visualizados e será repetido.
Aqui está o resultado de Texugo, Texugo, Texugo:
Aqui está o resultado da prova:
E o resultado de Jabberwocky:
fonte
Python 2
Esta é uma solução bastante direta. Ele cria uma sequência de amostra composta por palavras que estão entre o comprimento médio das palavras
A
- (A
/ 2) eA
+ (A
/ 2) e, em seguida, aplica pedaços aparados no espaço inicial e final da amostra para a área de amostra. Ele não lida com letras maiúsculas e minúsculas, e tenho certeza de que existe um caso de teste de curva curva que o quebraria, mas funciona bem nos exemplos. Veja o link abaixo para executar todos os testes.Também coloquei um patch no código para uma boa medida.
Lorem Ipsum, original então remendado:
Tente
fonte
mushroger
...#
caracteres no código.@
, nada de interessante.Java Shakespeare
Quem precisa de uma compreensão das convenções padrão em inglês? Apenas faça o seu! Assim como o bardo foi autorizado a inventar suas próprias palavras. Este bot não se preocupa muito em corrigir as palavras cortadas, ele realmente apenas insere palavras aleatórias. O resultado é uma bela poesia. Como um recurso de bônus, o bardo é de um calibre mais alto e pode lidar com vários orifícios, desde que sejam do mesmo tamanho!
Entrada de amostra
Saída bonita
As duas últimas linhas são profundamente poéticas, se é que digo. Ele tem um desempenho surpreendentemente bom no endereço de gettysburg também.
Vamos ver o que faz Shakespeare funcionar. Aqui está o código. Essencialmente, ele se esforça para construir uma base de vocabulário a partir da entrada. Ele então usa essas palavras e as coloca aleatoriamente no buraco (garantindo que elas se encaixem bem). Ele é determinístico, pois usa uma semente fixa para a aleatoriedade.
A maior parte da poesia de Shakespeare é de domínio público.
fonte
Python 2.7
Outra solução Python com uma abordagem diferente. Meu programa vê o texto como uma cadeia de Markov , onde cada letra é seguida por outra com uma certa probabilidade. Portanto, o primeiro passo é construir a tabela de probabilidades. O próximo passo é aplicar essas probabilidades ao patch.
O código completo, incluindo um texto de exemplo, está abaixo. Como um exemplo usou caracteres unicode, incluí uma página de códigos explícita (utf-8) para compatibilidade com esse exemplo.
Exemplo de saída para o Lorem Ipsum:
Uma linha poética extra no Jabberwocky:
fonte
C # 5 maciço como sempre
Eu joguei isso juntos, é um pouco confuso, mas produz alguns resultados positivos algumas vezes. É um algoritmo principalmente determinístico, mas com alguma aleatoriedade (semente fixa) adicionada para evitar que produza a mesma sequência para lacunas semelhantes. É necessário algum esforço para tentar evitar apenas colunas de espaços em ambos os lados das lacunas.
Ele funciona tokenizando a entrada em palavras e pontuação (a pontuação vem de uma lista inserida manualmente, porque não posso me incomodar em descobrir se o Unicode pode fazer isso por mim), para que possa colocar espaços antes das palavras, e não antes pontuação, porque isso é bastante típico. Divide-se no espaço em branco típico. Na veia das cadeias de markov (acho), conta quantas vezes cada token segue um ao outro e, em seguida, não calcula probabilidades para isso (acho que, como os documentos são muito pequenos, faríamos melhor em favorecer as coisas vemos muito onde podemos). Em seguida, realizamos uma pesquisa abrangente, preenchendo o espaço deixado pelos hashes e pelas palavras 'parciais' de ambos os lados, com o custo sendo computado como
-fabness(last, cur) * len(cur_with_space)
, ondefabness
retorna o número de vezes quecur
se seguiulast
para cada token anexado na cadeia gerada. Naturalmente, tentamos minimizar o custo. Como nem sempre podemos preencher a lacuna com palavras e pontuação encontradas no documento, ele também considera um número de tokens 'especiais' de certos estados, incluindo as seqüências parciais de ambos os lados, contra as quais fazemos viés com custos arbitrariamente aumentados.Se o BFS não conseguir encontrar uma solução, tentamos ingenuamente escolher um advérbio aleatório ou apenas inserir espaços para preencher o espaço.
Resultados
Todos os 6 podem ser encontrados aqui: https://gist.github.com/anonymous/5277db726d3f9bdd950b173b19fec82a
O caso de teste de Euclides não correu muito bem ...
Corrigir a imagem
Jabberwocky
Texugo
_Estou feliz com a forma como esta acabou ... é feliz que "texugo, texugo" se encaixa, ou esse não teria se saído tão bem
Código
Execute-o com
Existe bastante disso. A única parte remotamente interessante é o
Fill
método. Incluo a implementação da pilha, porque o .NET não possui uma (POR QUE MS POR QUE ?!).fonte