Korrigieren Sie den Absatz

32

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!
AdmBorkBork
quelle
Darf ich annehmen, dass das Loch mindestens drei Zeichen breit ist
Rohan Jhunjhunwala
@ RohanJhunjhunwala Sicher. Angesichts der Größe des Textes ist dies eine ziemlich sichere Annahme.
AdmBorkBork
Das Gettysburg-Beispiel enthält anscheinend Bindestriche, die nicht einfach sind. Ich möchte nur darauf hinweisen, dass Sie in Ihren Kommentaren in einer der Antworten angegeben haben, dass Sie einfache ASCII-Testfälle verwenden würden.
SuperJedi224
@ SuperJedi224 Danke - behoben.
AdmBorkBork

Antworten:

15

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.

def fix(paragraph, holeChar = "#"):
    lines = paragraph.split("\n")
    maxLineWidth = max(map(len, lines))
    lines = [list(line + " " * (maxLineWidth - len(line))) for line in lines]
    holes = filter(lambda pos: lines[pos[0]][pos[1]] == holeChar, [[y, x] for x in range(maxLineWidth) for y in range(len(lines))])

    n = 0
    for hole in holes:
        for i in range(min(hole[1], 5), 0, -1):
            currCh = lines[hole[0]][hole[1]]
            over = lines[hole[0] - 1][hole[1]]
            left = lines[hole[0]][hole[1] - i : hole[1]]

            same = []
            almost = []
            for y, line in enumerate(lines):
                for x, ch in enumerate(line):
                    if ch == holeChar:
                        continue
                    if ch == left[-1] == " ":
                        continue
                    chOver = lines[y - 1][x]
                    chLeft = lines[y][x - i : x]
                    if chOver == over and chLeft == left:
                        same.append(ch)
                    if chLeft == left:
                        almost.append(ch)
            sortFunc = lambda x, lst: lst.count(x) / (paragraph.count(x) + 10) + lst.count(x)
            if same:
                newCh = sorted(same, key=lambda x: sortFunc(x, same))[-1]
            elif almost:
                newCh = sorted(almost, key=lambda x: sortFunc(x, almost))[-1]
            else:
                continue
            lines[hole[0]][hole[1]] = newCh
            break


    return "\n".join(map("".join, lines))

Hier ist das Ergebnis von Dachs, Dachs, Dachs:

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- b               
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! 

Hier ist das Ergebnis aus dem Beweis:

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 the same areamilarly for B, A, and H.                            
6.Angles CAB and CA, sqe both right angles; therefore angle ABD            
equals angle ABD becaus both are the sum of a right angle and angle ABC.   
7.Since ABD because theFB and BD is equal to BC, triangle ABD              
must be construction ofiangle FBC.                                         
8.Since A-angle ABD becight line, parallel to BD, then rectangle           
BDLK has the same area  of triangle ABD because they share the base        
BD and have the base thtitude BK, i.e., a line normal to their common      
base, conngle and G, sqrallel lines BD and AL. (lemma 2)                   
9.Since C = BD × BK + with A and G, square BAGF must be twice in area     
to triangle FBC. (lemma                                                    
10.Therefore angle and  BDLK must have the same area as square BAGF = AB^2.
11.Similarly for B, A,  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.

Und das Ergebnis von Jabberwocky:

'Twas brillig, and the slithy toves
Did gyre and the mo in the wabe;   
All mimsy toves, anborogoves,      
And the mome raths outgrabe.       
Loovjo
quelle
5
Dieser Dachs ist ziemlich beeindruckend, und Jabberwocky sieht aus, als könnte es das legitime Gedicht sein. Gute Arbeit.
AdmBorkBork
6

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) und A+ (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.

def patch(paragraph):
    sample = [x.split() for x in paragraph if x.count('#') < 1]
    length = max([x.count('#') for x in paragraph if x.find('#')])
    s = sum(####################
    sample,[####################
    ])      ####################
    avg=sum(####################
    len(w)  ####################
    for w in####################
    s)//len(s)
    avg_range = range(avg-(avg//2),avg+(avg//2))
    sample = filter(lambda x:len(x) in avg_range, s)
    height=0
    for line in paragraph:
        if line.find('#'):height+=1
        print line.replace('#'*length,' '.join(sample)[(height-1)*length:height*length].strip())
    print '\n'

Lorem Ipsum, original dann gepatcht:

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 conseore dolore magnairure dolor in reprehenderit
in voluptate velit esse cilenim minim quisgiat nulla pariatur. Excepteur
sint occaecat cupidatat nonnisi mollit aniin culpa qui officia deserunt
mollit anim id est laborum.

Versuch es

Atlasologe
quelle
3
Hehe mushroger...
AdmBorkBork
Nun, Ihr Code wird nicht auf interessante Weise gepatcht.
mbomb007
@ mbomb007 Das liegt an den anderen #Zeichen im Code.
Atlasologe
@atlasologist Auch wenn du sie in etwas anderes änderst @, nichts interessantes.
mbomb007
4

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

 Von den schönsten Kreaturen wünschen wir uns mehr,
  Damit die Rose der Schönheit niemals stirbt,
  Aber wie der Reifer mit der Zeit sterben sollte,
  Sein Angebot ############ trägt sein Gedächtnis:
  Aber du hast deine eigenen hellen Augen,
  Füttere die ############ ame mit eigennützigem Kraftstoff,
  Eine Hungersnot machen, in der Überfluss liegt,
  Dein Selbst, dein Feind, zu deinem süßen Selbst, zu grausam:
  Du bist jetzt das frische Ornament der Welt.
  Und nur Vorbote des bunten Frühlings,
  In deiner eigenen Knospe begrabe deinen Inhalt,
  Und zarte Churl Mak'st war ############ Ding:
    Schade um die Welt, sonst t ############ sein,
    Um die Schuld der Welt zu essen, b ########### und dich.


                     2
  Wenn vierzig Winter deine Stirn belagern werden,
  Und grabe tiefe Gräben auf dem Felde deiner Schönheit
  Die stolze Bemalung deines Jünglings,
  Wird ein zerlumptes Unkraut von geringem Wert gehalten:  
  Dann gefragt, wo all deine Schönheit liegt,
  Wo all der Schatz deiner lustvollen Tage ist;
  In deinen eigenen, tief gesunkenen Augen zu sagen:
  Waren eine Schande und ein sparsames Lob.
  Wie viel mehr Lob verdient die Verwendung Ihrer Schönheit,
  Wenn du nicht antworten könntest: Dieses schöne Kind von mir
  Soll ich zählen und meine alte Entschuldigung machen?
  Beweise seine Schönheit durch deine Nachfolge.
    Dies sollte neu gemacht werden, wenn du alt bist,
    Und sieh dein Blut warm an, wenn du es kalt fühlst.


                     3
  Schau in dein Glas und sag dem Gesicht, das du siehst,
  Jetzt ist die Zeit, in der das Gesicht ein anderes formen sollte,
  Wessen frische Reparatur, wenn du jetzt nicht erneuerst,
  Du verführst die Welt, lass Mutter nicht segnen.
  Denn wo ist sie so schön, deren ungeborene Gebärmutter
  Verachtet die Bodenbearbeitung deiner Landwirtschaft?
  Oder wer ist er so gern wird das Grab sein,
  Von seiner Selbstliebe, die Nachwelt aufzuhalten?  
  Du bist das Glas deiner Mutter und sie in dir
  Ruft den schönen April ihrer Blüte zurück,
  So wirst du durch Fenster deines Alters sehen,
  Trotz ############# deiner goldenen Zeit.
    Aber wenn die ############ mbered nicht sein,
    Die singl ############ Bild stirbt mit dir.

Schöne Ausgabe

 Von den schönsten Kreaturen wünschen wir uns mehr,
  Damit die Rose der Schönheit niemals stirbt,
  Aber wie der Reifer mit der Zeit sterben sollte,
  Sein Angebot sollte sein Gedächtnis tragen:
  Aber du hast alle deine eigenen hellen Augen verletzt,
  Feed'st th Proving Oder bin mit eigennützigem Kraftstoff,
  Eine Hungersnot machen, in der Überfluss liegt,
  Dein Selbst, dein Feind, zu deinem süßen Selbst, zu grausam:
  Du bist jetzt das frische Ornament der Welt.
  Und nur Vorbote des bunten Frühlings,
  In deiner eigenen Knospe begrabe deinen Inhalt,
  Und zärtlich war er mein Ding:
    Schade um die Welt oder sonst
    Um die Welt zu verspeisen, wie es dir und dir gebührt.


                     2
  Wenn vierzig Winter deine Stirn belagern werden,
  Und grabe tiefe Gräben auf dem Felde deiner Schönheit
  Die stolze Bemalung deines Jünglings,
  Wird ein zerlumptes Unkraut von geringem Wert gehalten:  
  Dann gefragt, wo all deine Schönheit liegt,
  Wo all der Schatz deiner lustvollen Tage ist;
  In deinen eigenen, tief gesunkenen Augen zu sagen:
  Waren eine Schande und ein sparsames Lob.
  Wie viel mehr Lob verdient die Verwendung Ihrer Schönheit,
  Wenn du nicht antworten könntest: Dieses schöne Kind von mir
  Soll ich zählen und meine alte Entschuldigung machen?
  Beweise seine Schönheit durch deine Nachfolge.
    Dies sollte neu gemacht werden, wenn du alt bist,
    Und sieh dein Blut warm an, wenn du es kalt fühlst.


                     3
  Schau in dein Glas und sag dem Gesicht, das du siehst,
  Jetzt ist die Zeit, in der das Gesicht ein anderes formen sollte,
  Wessen frische Reparatur, wenn du jetzt nicht erneuerst,
  Du verführst die Welt, lass Mutter nicht segnen.
  Denn wo ist sie so schön, deren ungeborene Gebärmutter
  Verachtet die Bodenbearbeitung deiner Landwirtschaft?
  Oder wer ist er so gern wird das Grab sein,
  Von seiner Selbstliebe, die Nachwelt aufzuhalten?  
  Du bist das Glas deiner Mutter und sie in dir
  Ruft den schönen April ihrer Blüte zurück,
  So wirst du durch Fenster deines Alters sehen,
  Trotz des Blicks blickte s deine goldene Zeit.
    Aber wenn du nicht sein willst,
    Stirb mit dir, repariere das Bild.

Die letzten paar Zeilen sind zutiefst poetisch, wenn ich das selbst sage. Auch auf der Gettysburg-Adresse schneidet es überraschend gut ab.

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 to of rather us of advanced. It
is rather for us to be here dedicated to the who be it, vain who before us 
that from these honored dead we take increas be dead the the what use for which
they gave the last full measure of devotion  dead government The solve that
these dead shall not have died in vain that  the take nor world , 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.


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.

package stuff;

import java.io.File;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.Random;
import java.util.Scanner;
import java.util.Stack;

/**
 *
 * @author rohan
 */
public class PatchTheParagraph {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.println("File Name :");
        String[] text = getWordsFromFile(in.nextLine());
System.out.println("==ORIGINAL==");
        for(String s:text){
    System.out.println(s);
}
                    int lengthOfHole= 0;
        int rows = 0;
            for(String s: text){
                s = s.replaceAll("[^#]", "");

//      System.out.println(s);
                if(s.length()>0){
                    lengthOfHole = s.length();
                rows++;
                }
            }
            ArrayList<String> words = new ArrayList<>();
            words.add("I");
            for(String s:text){
                String[] w = s.replaceAll("#", " ").split(" ");
for(String a :w){
    words.add(a);
            }

            }
                        Iterator<String> j = words.iterator();
            while(j.hasNext()){
                String o;
                if((o = j.next()).equals("")){
                    j.remove();
                }
            }
            System.out.println(words);
            Stack<String> out = new Stack<>();
            String hashRow = "";
            for(int i = 0;i<lengthOfHole;i++){
                hashRow+="#";
            }

        for(int i = 0;i<rows;i++){
            int length = lengthOfHole-1; 
            String outPut = " ";
            while(length>2){
String wordAttempt = words.get(getRandom(words.size()-1));
while(wordAttempt.length()>length-1){
 wordAttempt = words.get(getRandom(words.size()-1));
}           
length -= wordAttempt.length()+1;
            outPut+=wordAttempt;
                outPut+=" ";
            }
        out.push(outPut);
    }
System.out.println("==PATCHED==");
        for(String s : text){
            if(s.contains(hashRow)){
                System.out.println(s.replaceAll(hashRow,out.pop()));
            }else{
                System.out.println(s);
            }
        }
                                    }
public static final Random r = new Random(42);
    public static int getRandom(int max){
    return (int) (max*r.nextDouble());
}
    /**
     *
     * @param fileName is the path to the file or just the name if it is local
     * @return the number of lines in fileName
     */
    public static int getLengthOfFile(String fileName) {
        int length = 0;
        try {
            File textFile = new File(fileName);
            Scanner sc = new Scanner(textFile);
            while (sc.hasNextLine()) {
                sc.nextLine();
                length++;
            }
        } catch (Exception e) {
System.err.println(e);
        }
        return length;
    }

    /**
     *
     * @param fileName is the path to the file or just the name if it is local
     * @return an array of Strings where each string is one line from the file
     * fileName.
     */
    public static String[] getWordsFromFile(String fileName) {
        int lengthOfFile = getLengthOfFile(fileName);
        String[] wordBank = new String[lengthOfFile];
        int i = 0;
        try {
            File textFile = new File(fileName);
            Scanner sc = new Scanner(textFile);
            for (i = 0; i < lengthOfFile; i++) {
                wordBank[i] = sc.nextLine();
            }
            return wordBank;
        } catch (Exception e) {
            System.err.println(e);
            System.exit(55);
        }
        return null;
    }
}


Der größte Teil von Shakespeares Gedichten ist gemeinfrei.

Rohan Jhunjhunwala
quelle
Kommentare sind nicht für längere Diskussionen gedacht. Diese Unterhaltung wurde in den Chat verschoben .
Dennis
3

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.

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from collections import defaultdict
import numpy

texts = [
"""'Twas brillig, and the slithy toves
Did gyre a######### in the wabe;
All mimsy #########borogoves,
And the mome raths outgrabe."""
]

class Patcher:
    def __init__(self):
        self.mapper = defaultdict(lambda: defaultdict(int))

    def add_mapping(self, from_value, to_value):
        self.mapper[from_value][to_value] += 1

    def get_patch(self, from_value):
        if from_value in self.mapper:
            sum_freq = sum(self.mapper[from_value].values())
            return numpy.random.choice(
                self.mapper[from_value].keys(),
                p = numpy.array(
                    self.mapper[from_value].values(),dtype=numpy.float64) / sum_freq)
        else:
            return None

def add_text_mappings(text_string, patcher = Patcher(), ignore_characters = ''):
    previous_letter = text_string[0]
    for letter in text_string[1:]:
        if not letter in ignore_characters:
            patcher.add_mapping(previous_letter, letter)
            previous_letter = letter
    patcher.add_mapping(text_string[-1], '\n')

def patch_text(text_string, patcher, patch_characters = '#'):
    result = previous_letter = text_string[0]
    for letter in text_string[1:]:
        if letter in patch_characters:
            result += patcher.get_patch(previous_letter)
        else:
            result += letter
        previous_letter = result[-1]
    return result

def main():
    for text in texts:
        patcher = Patcher()
        add_text_mappings(text, patcher, '#')
        print patch_text(text, patcher, '#')
        print "\n"

if __name__ == '__main__':
    main()

Beispielausgabe für das 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 conse Exe eut ccadamairure dolor in reprehenderit
in voluptate velit esse cilore indipserexepgiat nulla pariatur. Excepteur
sint occaecat cupidatat non upir alostat adin culpa qui officia deserunt
mollit anim id est laborum.

Eine extra poetische Zeile im Jabberwocky:

'Twas brillig, and the slithy toves
Did gyre and me the in the wabe;
All mimsy was
An inborogoves,
And the mome raths outgrabe.
wie auch immer
quelle
Welcher Beispieltext hat Unicode? Sie sollten alle gerade ASCII sein. Bitte lassen Sie es mich wissen und ich werde es korrigieren.
AdmBorkBork
Python beschwert sich im ersten Text über den Fehler und bezieht sich auf PEP 263 .
bis zum
Ah - merkte es nicht einmal. Ich habe das bearbeitet, um gerade ASCII zu sein. Danke für die Information!
AdmBorkBork
2

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), wobei fabnessdie Anzahl der folgenden Rückgaben berechnet curwirdlastfü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

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, that patches information outside of that patch. And it does a
quite good job, co the patch a is just a program. As a human, you can sometimes
see that something In a short it if you squeeze your eyes or just take a short
glance, the patch seems to fill in the gap quite well.

Jabberwocky

'Twas brillig, and the slithy toves
Did gyre and the in in the wabe;
All mimsy the mome borogoves,
And the mome raths outgrabe.

Dachs

Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Mushroom, mushroom, a-
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Mushroom, badger, badger
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!

_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

csc ParaPatch.cs
ParaPatch.exe infile outfile

Es gibt ziemlich viel davon. Das einzig entfernt interessante ist die FillMethode. Ich schließe die Heap-Implementierung ein, da .NET keine hat (WARUM MS WARUM ?!).

using System;
using System.Collections.Generic;
using System.Linq;

namespace ParaPatch
{
    class Program
    {
        private static string[] Filler = new string[] { "may", "will", "maybe", "rather", "perhaps", "reliably", "nineword?", "definitely", "elevenword?", "inexplicably" }; // adverbs
        private static char[] Breaking = new char[] { ' ', '\n', '\r', '\t' };
        private static char[] Punctuation = new char[] { ',', '.', '{', '}', '(', ')', '/', '?', ':', ';', '\'', '\\', '"', ',', '!', '-', '+', '[', ']', '£', '$', '%', '^', '—' };

        private static IEnumerable<string> TokenizeStream(System.IO.StreamReader reader)
        {
            System.Text.StringBuilder sb = new System.Text.StringBuilder();

            HashSet<char> breaking = new HashSet<char>(Breaking);
            HashSet<char> punctuation = new HashSet<char>(Punctuation);

            while (!reader.EndOfStream)
            {
                int ci = reader.Read();
                if (ci == -1) // sanity
                    break;

                char c = (char)ci;

                if (breaking.Contains(c))
                {
                    if (sb.Length > 0)
                        yield return sb.ToString();
                    sb.Clear();
                }
                else if (punctuation.Contains(c))
                {
                    if (sb.Length > 0)
                        yield return sb.ToString();
                    yield return ""+c;
                    sb.Clear();
                }
                else
                {

                    sb.Append(c);
                }
            }

            if (sb.Length > 0)
                yield return sb.ToString();
        }

        private enum DocTokenTypes
        {
            Known,
            LeftPartial,
            RightPartial,
            Unknown,
        }

        private class DocToken
        {
            public DocTokenTypes TokenType { get; private set; }
            public string StringPart { get; private set; }
            public int Length { get; private set; }

            public DocToken(DocTokenTypes tokenType, string stringPart, int length)
            {
                TokenType = tokenType;
                StringPart = stringPart;
                Length = length;
            }
        }

        private static IEnumerable<DocToken> DocumentTokens(IEnumerable<string> tokens)
        {
            foreach (string token in tokens)
            {
                if (token.Contains("#"))
                {
                    int l = token.IndexOf("#");
                    int r = token.LastIndexOf("#");

                    if (l > 0)
                        yield return new DocToken(DocTokenTypes.LeftPartial, token.Substring(0, l), l);

                    yield return new DocToken(DocTokenTypes.Unknown, null, r - l + 1);

                    if (r < token.Length - 1)
                        yield return new DocToken(DocTokenTypes.RightPartial, token.Substring(r + 1), token.Length - r - 1);
                }
                else
                    yield return new DocToken(DocTokenTypes.Known, token, token.Length);
            }
        }

        private class State : IComparable<State>
        {
            // missing readonly params already... maybe C#6 isn't so bad
            public int Remaining { get; private set; }
            public int Position { get; private set; }
            public State Prev { get; private set; }
            public string Token { get; private set; }
            public double H { get; private set; }
            public double Fabness { get; private set; }
            public string FullFilling { get; private set; }

            public State(int remaining, int position, Program.State prev, double fabness, double h, string token, string toAdd)
            {
                Remaining = remaining;
                Position = position;
                Prev = prev;
                H = h;
                Fabness = fabness;
                Token = token;

                FullFilling = prev != null ? prev.FullFilling + toAdd : toAdd;
            }

            public int CompareTo(State other)
            {
                return H.CompareTo(other.H);
            }
        }

        public static void Main(string[] args)
        {
            if (args.Length < 2)
                args = new string[] { "test.txt", "testout.txt" };

            List<DocToken> document;
            using (System.IO.StreamReader reader = new System.IO.StreamReader(args[0], System.Text.Encoding.UTF8))
            {
                document = DocumentTokens(TokenizeStream(reader)).ToList();
            }

            foreach (DocToken cur in document)
            {
                Console.WriteLine(cur.StringPart + " " + cur.TokenType);
            }

            // these are small docs, don't bother with more than 1 ply
            Dictionary<string, Dictionary<string, int>> FollowCounts = new Dictionary<string, Dictionary<string, int>>();
            Dictionary<string, Dictionary<string, int>> PreceedCounts = new Dictionary<string, Dictionary<string, int>>(); // mirror (might be useful)

            HashSet<string> knowns = new HashSet<string>(); // useful to have lying around

            // build counts
            DocToken last = null;
            foreach (DocToken cur in document)
            {
                if (cur.TokenType == DocTokenTypes.Known)
                {
                    knowns.Add(cur.StringPart);
                }

                if (last != null && last.TokenType == DocTokenTypes.Known && cur.TokenType == DocTokenTypes.Known)
                {
                    {
                        Dictionary<string, int> ltable;
                        if (!FollowCounts.TryGetValue(last.StringPart, out ltable))
                        {
                            FollowCounts.Add(last.StringPart, ltable = new Dictionary<string, int>());
                        }

                        int count;
                        if (!ltable.TryGetValue(cur.StringPart, out count))
                        {
                            count = 0;
                        }
                        ltable[cur.StringPart] = count + 1;
                    }


                    {
                        Dictionary<string, int> ctable;
                        if (!PreceedCounts.TryGetValue(cur.StringPart, out ctable))
                        {
                            PreceedCounts.Add(cur.StringPart, ctable = new Dictionary<string, int>());
                        }

                        int count;
                        if (!ctable.TryGetValue(last.StringPart, out count))
                        {
                            count = 0;
                        }
                        ctable[last.StringPart] = count + 1;
                    }
                }

                last = cur;
            }

            // build probability grid (none of this efficient table filling dynamic programming nonsense, A* all the way!)
            // hmm... can't be bothered
            Dictionary<string, Dictionary<string, double>> fabTable = new Dictionary<string, Dictionary<string, double>>();
            foreach (var k in FollowCounts)
            {
                Dictionary<string, double> t = new Dictionary<string, double>();

                // very naive
                foreach (var k2 in k.Value)
                {
                    t.Add(k2.Key, (double)k2.Value);
                }

                fabTable.Add(k.Key, t);
            }

            string[] knarr = knowns.ToArray();
            Random rnd = new Random("ParaPatch".GetHashCode());

            List<string> fillings = new List<string>();
            for (int i = 0; i < document.Count; i++)
            {
                if (document[i].TokenType == DocTokenTypes.Unknown)
                {
                    // shuffle knarr
                    for (int j = 0; j < knarr.Length; j++)
                    {
                        string t = knarr[j];
                        int o = rnd.Next(knarr.Length);
                        knarr[j] = knarr[o];
                        knarr[o] = t;
                    }

                    fillings.Add(Fill(document, fabTable, knarr, i));
                    Console.WriteLine(fillings.Last());
                }
            }

            string filling = string.Join("", fillings);

            int fi = 0;

            using (System.IO.StreamWriter writer = new System.IO.StreamWriter(args[1]))
            using (System.IO.StreamReader reader = new System.IO.StreamReader(args[0]))
            {
                while (!reader.EndOfStream)
                {
                    int ci = reader.Read();
                    if (ci == -1)
                        break;

                    char c = (char)ci;
                    c = c == '#' ? filling[fi++] : c;

                    writer.Write(c);
                    Console.Write(c);
                }
            }

//            using (System.IO.StreamWriter writer = new System.IO.StreamWriter(args[1], false, System.Text.Encoding.UTF8))
//            using (System.IO.StreamReader reader = new System.IO.StreamReader(args[0]))
//            {
//                foreach (char cc in reader.ReadToEnd())
//                {
//                    char c = cc;
//                    c = c == '#' ? filling[fi++] : c;
//                    
//                    writer.Write(c);
//                    Console.Write(c);
//                }
//            }

            if (args[0] == "test.txt")
                Console.ReadKey(true);
        }

        private static string Fill(List<DocToken> document, Dictionary<string, Dictionary<string, double>> fabTable, string[] knowns, int unknownIndex)
        {
            HashSet<char> breaking = new HashSet<char>(Breaking);
            HashSet<char> punctuation = new HashSet<char>(Punctuation);

            Heap<State> due = new Heap<Program.State>(knowns.Length);

            Func<string, string, double> fabness = (prev, next) =>
            {
                Dictionary<string, double> table;
                if (!fabTable.TryGetValue(prev, out table))
                    return 0; // not fab
                double fab;
                if (!table.TryGetValue(next, out fab))
                    return 0; // not fab
                return fab; // yes fab
            };

            DocToken mostLeft = unknownIndex > 2 ? document[unknownIndex - 2] : null;
            DocToken left = unknownIndex > 1 ? document[unknownIndex - 1] : null;
            DocToken unknown = document[unknownIndex];
            DocToken right = unknownIndex < document.Count - 2 ? document[unknownIndex + 1] : null;
            DocToken mostRight = unknownIndex < document.Count - 3 ? document[unknownIndex + 2] : null;

            // sum of empty space and partials' lengths
            int spaceSize = document[unknownIndex].Length
                + (left != null && left.TokenType == DocTokenTypes.LeftPartial ? left.Length : 0)
                + (right != null && right.TokenType == DocTokenTypes.RightPartial ? right.Length : 0);

            int l = left != null && left.TokenType == DocTokenTypes.LeftPartial ? left.Length : 0;
            int r = l + unknown.Length;

            string defaultPrev =
                left != null && left.TokenType == DocTokenTypes.Known ? left.StringPart :
                mostLeft != null && mostLeft.TokenType == DocTokenTypes.Known ? mostLeft.StringPart :
                "";

            string defaultLast =
                right != null && right.TokenType == DocTokenTypes.Known ? right.StringPart :
                mostRight != null && mostRight.TokenType == DocTokenTypes.Known ? mostRight.StringPart :
                "";

            Func<string, string> topAndTail = str =>
            {
                return str.Substring(l, r - l);
            };

            Func<State, string, double, bool> tryMove = (State prev, string token, double specialFabness) => 
            {
                bool isPunctionuation = token.Length == 1 && punctuation.Contains(token[0]);
                string addStr = isPunctionuation || prev == null ? token : " " + token;
                int addLen = addStr.Length;

                int newRemaining = prev != null ? prev.Remaining - addLen : spaceSize - addLen;
                int oldPosition = prev != null ? prev.Position : 0;
                int newPosition = oldPosition + addLen;

                // check length
                if (newRemaining < 0)
                    return false;

                // check start
                if (oldPosition < l) // implies left is LeftPartial
                {
                    int s = oldPosition;
                    int e = newPosition > l ? l : newPosition;
                    int len = e - s;
                    if (addStr.Substring(0, len) != left.StringPart.Substring(s, len))
                        return false; // doesn't match LeftPartial
                }

                // check end
                if (newPosition > r) // implies right is RightPartial
                {
                    int s = oldPosition > r ? oldPosition : r;
                    int e = newPosition;
                    int len = e - s;
                    if (addStr.Substring(s - oldPosition, len) != right.StringPart.Substring(s - r, len))
                        return false; // doesn't match RightPartial
                }

                if (newRemaining == 0)
                {
                    // could try to do something here (need to change H)
                }

                string prevToken = prev != null ? prev.Token : defaultPrev;
                bool isLastunctionuation = prevToken.Length == 1 && punctuation.Contains(prevToken[0]);

                if (isLastunctionuation && isPunctionuation) // I hate this check, it's too aggresive to be realistic
                    specialFabness -= 50;

                double fab = fabness(prevToken, token);

                if (fab < 1 && (token == prevToken))
                    fab = -1; // bias against unrecognised repeats

                double newFabness = (prev != null ? prev.Fabness : 0.0)
                    - specialFabness // ... whatever this is
                    - fab * addLen; // how probabilistic

                double h = newFabness; // no h for now

                State newState = new Program.State(newRemaining, newPosition, prev, newFabness, h, token, addStr);

//                Console.WriteLine((prev != null ? prev.Fabness : 0) + "\t" + specialFabness);
//                Console.WriteLine(newFabness + "\t" + h + "\t" + due.Count + "\t" + fab + "*" + addLen + "\t" + newState.FullFilling);

                due.Add(newState);
                return true;
            };

            // just try everything everything
            foreach (string t in knowns)
                tryMove(null, t, 0);

            if (left != null && left.TokenType == DocTokenTypes.LeftPartial)
                tryMove(null, left.StringPart, -1);

            while (!due.Empty)
            {
                State next = due.RemoveMin();

                if (next.Remaining == 0)
                {
                    // we have a winner!!
                    return topAndTail(next.FullFilling);
                }

                // just try everything
                foreach (string t in knowns)
                    tryMove(next, t, 0);
                if (right != null && right.TokenType == DocTokenTypes.RightPartial)
                    tryMove(next, right.StringPart, -5); // big bias
            }

            // make this a tad less stupid, non?
            return Filler.FirstOrDefault(f => f.Length == unknown.Length) ?? new String(' ', unknown.Length); // oh dear...
        }
    }

    //
    // Ultilities
    //

    public class Heap<T> : System.Collections.IEnumerable where T : IComparable<T>
    {
        // arr is treated as offset by 1, all idxes stored need to be -1'd to get index in arr
        private T[] arr;
        private int end = 0;

        private void s(int idx, T val)
        {
            arr[idx - 1] = val;
        }

        private T g(int idx)
        {
            return arr[idx - 1];
        }

        public Heap(int isize)
        {
            if (isize < 1)
                throw new ArgumentException("Cannot be less than 1", "isize");

            arr = new T[isize];
        }

        private int up(int idx)
        {
            return idx / 2;
        }

        private int downLeft(int idx)
        {
            return idx * 2;
        }

        private int downRight(int idx)
        {
            return idx * 2 + 1;
        }

        private void swap(int a, int b)
        {
            T t = g(a);
            s(a, g(b));
            s(b, t);
        }

        private void moveUp(int idx, T t)
        {
        again:
            if (idx == 1)
            {
                s(1, t);
                return; // at end
            }

            int nextUp = up(idx);
            T n = g(nextUp);
            if (n.CompareTo(t) > 0)
            {
                s(idx, n);
                idx = nextUp;
                goto again;
            }
            else
            {
                s(idx, t);
            }
        }

        private void moveDown(int idx, T t)
        {
        again:
            int nextLeft = downLeft(idx);
            int nextRight = downRight(idx);

            if (nextLeft > end)
            {
                s(idx, t);
                return; // at end
            }
            else if (nextLeft == end)
            { // only need to check left
                T l = g(nextLeft);

                if (l.CompareTo(t) < 0)
                {
                    s(idx, l);
                    idx = nextLeft;
                    goto again;
                }
                else
                {
                    s(idx, t);
                }
            }
            else
            { // check both
                T l = g(nextLeft);
                T r = g(nextRight);

                if (l.CompareTo(r) < 0)
                { // left smaller (favour going right if we can)
                    if (l.CompareTo(t) < 0)
                    {
                        s(idx, l);
                        idx = nextLeft;
                        goto again;
                    }
                    else
                    {
                        s(idx, t);
                    }
                }
                else
                { // right smaller or same
                    if (r.CompareTo(t) < 0)
                    {
                        s(idx, r);
                        idx = nextRight;
                        goto again;
                    }
                    else
                    {
                        s(idx, t);
                    }
                }
            }
        }

        public void Clear()
        {
            end = 0;
        }

        public void Trim()
        {
            if (end == 0)
                arr = new T[1]; // don't /ever/ make arr len 0
            else
            {
                T[] narr = new T[end];
                for (int i = 0; i < end; i++)
                    narr[i] = arr[i];
                arr = narr;
            }
        }

        private void doubleSize()
        {
            T[] narr = new T[arr.Length * 2];
            for (int i = 0; i < end; i++)
                narr[i] = arr[i];
            arr = narr;
        }

        public void Add(T item)
        {
            if (end == arr.Length)
            {
                // resize
                doubleSize();
            }

            end++;
            moveUp(end, item);
        }

        public T RemoveMin()
        {
            if (end < 1)
                throw new Exception("No items, mate.");

            T min = g(1);

            end--;
            if (end > 0)
                moveDown(1, g(end + 1));

            return min;
        }

        public bool Empty
        {
            get
            {
                return end == 0;
            }
        }

        public int Count
        {
            get
            {
                return end;
            }
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        public IEnumerator<T> GetEnumerator()
        {
            return (IEnumerator<T>)arr.GetEnumerator();
        }
    }
}
VisualMelon
quelle