Im Geiste von Patch the Image gibt es hier eine ähnliche Herausforderung, allerdings mit Text.
Herausforderung
Bit Rot hat Ihren kostbaren Text befallen! Wenn ein Absatz aus ASCII-Zeichen besteht und sich irgendwo ein rechteckiges Loch befindet, sollte Ihr Programm versuchen, das Loch mit geeignetem Text auszufüllen, damit der Absatz so gut wie möglich überblendet.
Weitere Definitionen
- Das Loch ist immer rechteckig und kann mehrere Linien umfassen.
- Es wird immer nur ein Loch geben.
- Beachten Sie, dass die Lücke nicht unbedingt an Wortgrenzen stößt (in der Regel auch nicht).
- Die Lücke macht höchstens 25% des eingegebenen Absatzes aus, kann sich jedoch überlappen oder über das "Ende" des "normalen" Textes hinaus erstrecken (siehe die Euklid- oder Dachs-Beispiele unten).
- Da das Finden des Lochs nicht der Hauptpunkt dieser Herausforderung ist, besteht es nur aus Rautezeichen
#
, um eine einfache Identifizierung zu ermöglichen. - An keiner anderen Stelle im Eingabeabsatz wird ein Rautezeichen angezeigt.
- Ihr Code kann den "normalen" Text in den folgenden Beispielen nicht verwenden - er empfängt und verarbeitet nur den Text mit der darin enthaltenen Lücke.
- Die Eingabe kann als einzelne mehrzeilige Zeichenfolge, als Array von Zeichenfolgen (ein Element pro Zeile), als Datei usw. erfolgen. Wählen Sie aus, was für Ihre Sprache am bequemsten ist.
- Falls gewünscht, kann eine optionale zusätzliche Eingabe mit Einzelheiten zu den Koordinaten des Lochs vorgenommen werden (z. B. ein Tupel von Koordinaten oder dergleichen).
- Bitte beschreiben Sie Ihren Algorithmus in Ihrem Beitrag.
Wählen
Die Wähler werden gebeten, die Einträge danach zu beurteilen, wie gut der Algorithmus das Textloch ausfüllt. Einige Vorschläge umfassen Folgendes:
- Entspricht der ausgefüllte Bereich der ungefähren Verteilung von Leerzeichen und Interpunktion wie der Rest des Absatzes?
- Führt der ausgefüllte Bereich zu einer fehlerhaften Syntax? (z. B. zwei Leerzeichen hintereinander, ein Punkt, gefolgt von einem Fragezeichen, eine falsche Reihenfolge
, ,
usw.) - Wenn Sie die Augen zusammenknicken (damit Sie den Text nicht wirklich lesen), können Sie dann sehen, wo sich das Loch befand?
- Enthält das Loch keine CamelCase-Wörter außerhalb des Lochs? Enthält das Loch keine Großbuchstaben außerhalb des Lochs? Wenn sich viele Großbuchstaben außerhalb des Lochs befinden, enthält das Loch dann einen anteiligen Betrag?
Gültigkeitskriterium
Damit eine Einreichung als gültig angesehen wird, darf sie keinen Text des Absatzes außerhalb der Bohrung (einschließlich Leerzeichen am Ende) ändern. Eine einzelne abschließende Zeile ganz am Ende ist optional.
Testfälle
Format ist der ursprüngliche Absatz in einem Codeblock, gefolgt von demselben Absatz mit einer Lücke. Die Absätze mit dem Loch werden für die Eingabe verwendet.
1 (Bild patchen)
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 (Gettysburg-Adresse)
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 (Euklids Beweis des Satzes von Pythagoras)
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 (Dachs, Dachs, Dachs von 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!
quelle
Antworten:
Python 2
ich weiß das @atlasologist bereits eine Lösung in Python 2 gepostet hat, aber meine Arbeitsweise ist etwas anders. Dies funktioniert, indem Sie alle Löcher von oben nach unten, von links nach rechts durchgehen, 5 Zeichen zurück und auf das Zeichen oben schauen und ein Zeichen finden, bei dem diese übereinstimmen. Wenn mehrere Zeichen gefunden werden, wird das häufigste ausgewählt. Falls keine Zeichen gefunden werden, wird die oben genannte Zeichenbeschränkung aufgehoben. Wenn immer noch keine Zeichen gefunden werden, wird die Anzahl der zurückgesehenen Zeichen verringert und wiederholt.
Hier ist das Ergebnis von Dachs, Dachs, Dachs:
Hier ist das Ergebnis aus dem Beweis:
Und das Ergebnis von Jabberwocky:
quelle
Python 2
Dies ist eine ziemlich einfache Lösung. Es wird eine Beispielzeichenfolge erstellt, die aus Wörtern besteht, deren durchschnittliche Wortlänge zwischen
A
- (A
/ 2) undA
+ (liegt.A
/ 2) liegt. Anschließend werden durch Leerzeichen und Leerzeichen begrenzte Abschnitte vom Sample auf den Patch-Bereich angewendet. Es geht nicht um Großschreibung, und ich bin mir sicher, dass es einen Curveball-Test gibt, der ihn brechen würde, aber in den Beispielen ist es in Ordnung. Klicken Sie auf den folgenden Link, um alle Tests auszuführen.Ich habe auch einen Patch in den Code eingefügt.
Lorem Ipsum, original dann gepatcht:
Versuch es
quelle
mushroger
...#
Zeichen im Code.@
, nichts interessantes.Java Shakespeare
Wer braucht ein Verständnis für Standard-Englisch-Konventionen? Mach einfach dein eigenes! Genau wie der Barde seine eigenen Worte erfinden durfte. Dieser Bot kümmert sich nicht so sehr um die Korrektur der abgeschnittenen Wörter, er fügt nur zufällige Wörter ein. Das Ergebnis ist eine schöne Poesie. Als Bonus-Feature hat der Barde ein höheres Kaliber und kann mit mehreren Löchern umgehen, vorausgesetzt, sie sind gleich groß!
Sample Input
Schöne Ausgabe
Die letzten paar Zeilen sind zutiefst poetisch, wenn ich das selbst sage. Auch auf der Gettysburg-Adresse schneidet es überraschend gut ab.
Mal sehen, was Shakespeare tickt. Hier ist der Code. Im Wesentlichen bemüht er sich, aus den Eingaben eine Vokabelliste zu erstellen. Er benutzt dann diese Wörter und platziert sie zufällig in das Loch (um sicherzustellen, dass es gut passt). Er ist deterministisch, da er einen festen Keim für die Zufälligkeit verwendet.
Der größte Teil von Shakespeares Gedichten ist gemeinfrei.
quelle
Python 2.7
Eine andere Python-Lösung mit einem anderen Ansatz. Mein Programm sieht den Text als Markov-Kette , wobei jedem Buchstaben mit einer bestimmten Wahrscheinlichkeit ein anderer Buchstabe folgt. Der erste Schritt besteht also darin, die Wahrscheinlichkeitstabelle zu erstellen. Der nächste Schritt besteht darin, diese Wahrscheinlichkeiten auf den Patch anzuwenden.
Der vollständige Code, einschließlich eines Beispieltextes, ist unten aufgeführt. Da in einem Beispiel Unicode-Zeichen verwendet wurden, habe ich eine explizite Codepage (utf-8) eingefügt, um die Kompatibilität mit diesem Beispiel zu gewährleisten.
Beispielausgabe für das Lorem Ipsum:
Eine extra poetische Zeile im Jabberwocky:
quelle
C # 5 massiv wie immer
Ich habe das zusammen gewürfelt, es ist ein bisschen chaotisch, aber manchmal liefert es ein paar gute Ergebnisse. Es ist ein größtenteils deterministischer Algorithmus, der jedoch eine gewisse Zufälligkeit (Fixed-Seed) aufweist, um zu vermeiden, dass derselbe String für ähnliche Lücken erzeugt wird. Es ist anstrengend zu vermeiden, dass nur Spalten mit Leerzeichen auf beiden Seiten der Lücken vorhanden sind.
Es funktioniert durch Tokenisierung der Eingabe in Wörter und Interpunktion (die Interpunktion stammt aus einer manuell eingegebenen Liste, da ich nicht die Mühe habe herauszufinden, ob Unicode dies für mich tun kann), sodass Leerzeichen vor Wörter und nicht vor Wörter gesetzt werden können Zeichensetzung, weil dies ziemlich typisch ist. Es spaltet sich in typischen Leerzeichen auf. In der Art von Markov-Ketten (glaube ich) zählt es, wie oft jedes Token aufeinander folgt, und berechnet dann keine Wahrscheinlichkeiten dafür (ich nehme an, dass wir es besser machen, uns auf Dinge zu konzentrieren, weil die Dokumente so winzig sind Wir sehen viel, wo wir können. Dann führen wir eine Breitensuche durch und füllen den durch die Hashes und die 'Teilworte' auf beiden Seiten verbleibenden Raum mit den Kosten
-fabness(last, cur) * len(cur_with_space)
, wobeifabness
die Anzahl der folgenden Rückgaben berechnetcur
wirdlast
für jedes angehängte Token in der generierten Zeichenfolge. Natürlich versuchen wir, die Kosten so gering wie möglich zu halten. Da wir die Lücke nicht immer mit Wörtern und Interpunktionen füllen können, die im Dokument zu finden sind, werden auch einige "spezielle" Token aus bestimmten Staaten berücksichtigt, einschließlich der Teilzeichenfolgen auf beiden Seiten, gegen die wir mit willkürlich erhöhten Kosten vorgehen.Wenn das BFS keine Lösung findet, versuchen wir naiv, ein zufälliges Adverb auszuwählen oder einfach Leerzeichen einzufügen, um das Leerzeichen zu füllen.
Ergebnisse
Alle 6 finden Sie hier: https://gist.github.com/anonymous/5277db726d3f9bdd950b173b19fec82a
Der Euclid-Testfall lief nicht sehr gut ...
Patchen Sie das Image
Jabberwocky
Dachs
_Ich bin froh darüber, wie sich herausgestellt hat ... es ist ein Glück, dass "Dachs, Dachs" passt, sonst hätte das nicht so gut geklappt
Code
Führen Sie es mit
Es gibt ziemlich viel davon. Das einzig entfernt interessante ist die
Fill
Methode. Ich schließe die Heap-Implementierung ein, da .NET keine hat (WARUM MS WARUM ?!).quelle