In dieser Herausforderung schreiben Sie ein Programm, das zwei durch Zeilenumbrüche getrennte Zeichenfolgen, s1 (die erste Zeile) und s2 (die zweite Zeile), als Eingabe (STDIN oder am nächsten) verwendet. Sie können davon ausgehen, dass die Länge von s1 immer kleiner als 30 und größer als die Länge von s2 ist. Das Programm sollte dann jeden Schritt im Abstand von s1 bis s2 ausgeben.

Um zu verdeutlichen, was jeder Schritt in der Levenshtein-Entfernung bedeutet, gibt das Programm n Zeichenfolgen aus, wobei n die Levenshtein-Entfernung zwischen s1 und s2 ist und die Levenshtein-Entfernung zwischen zwei benachbarten Zeichenfolgen immer eins ist. Die Reihenfolge spielt keine Rolle. Die Ausgabe sollte durch Zeilenumbrüche getrennt sein und nicht s1, sondern nur die Zwischenschritte und s2 enthalten. Das Programm sollte auch auf einem modernen Computer in weniger als einer Minute ausgeführt werden.

Beispiele:

Eingang:

Programming
Codegolf

Ausgabe:

rogramming
Cogramming
Coramming
Coamming
Codmming
Codeming
Codeging
Codegong
Codegolg
Codegolf

Eingang:

Questions
Answers

Ausgabe:

uestions
Aestions
Anstions
Ansions
Answons
Answens
Answers

Eingang:

Offline
Online

Ausgabe:

Ofline
Online

Eingang:

Saturday
Sunday

Ausgabe:

Sturday
Surday
Sunday

Hier ist ein Link zu einem Python-Skript, das die Entfernung und die Schritte ausgibt.

Zusätzliche Regeln:

• Keine Nutzung des Internets
• Es gelten Standardlücken

Das ist Codegolf, also halten Sie den Code kurz. kürzester Code gewinnt!

Javascript, 167 161 154 Bytes

function l(a,b,d){if(a!=b){if(a[l="length"]>b[l])a=a[s="slice"](1),d=-1;else if(a[d]!=b[d])a=a[s](0,d)+b[d]+a[s](d+1);document.write(a+"<p>");l(a,b,++d)}}

Mit anrufen l("Programming","golf")

Codepen

Entgolfter (und kommentierter) Code (veraltet, aber Sie haben die Idee):

function l(a, b, d) {
  s = "substring"; //saving this to a string lets us call it with a[s] later
  if (a != b) { //if the strings aren't the same, continue
    if (a.length > b.length) { //if a is still greater than b we can delete characters
      a = a[s](1); //delete the first character from a
      d = -1 //when we start swapping characters, we'll need d to start at 0
    } else if (a[d] != b[d]) { //if the d'th character isn't the same, we can swap them
      a = a[s](0, d) + b[d] + a[s](d + 1) //swap the d'th character of b into a
    }
    document.write(a + "<p>"); //the first call to document.write overwrites the page but successive calls append the output 
    l(a, b, ++d) //increment d and recurse
  }
}

Haskell, 201 194 Bytes

l=length
g[]n u=map(\_->"")n
g(b:c)[]u=(u++c):g c[]u
g(b:c)n@(o:p)u|b==o=g c p(u++[o])|1<2=((u++o:c):g c p(u++[o]))!((u++c):g c n u)
a!b|l a<l b=a|1<2=b
p[a,n]=g a n""
f=interact$unlines.p.lines

Länger als erwartet. Vielleicht kann ich ein bisschen Golf spielen ...

Anwendungsbeispiel:

*Main> f                     -- call via f
Questions                    -- User input
Answers                      -- no newline after second line!
uestions                     -- Output starts here
Aestions
Anstions
Ansions
Answons
Answens
Answers

Es ist eine rohe Kraft, die zwischen Ändern und Löschen entscheidet, wenn sich die Anfangsbuchstaben unterscheiden.