Dans ce défi, vous allez écrire un programme qui prend en entrée deux chaînes séparées par une nouvelle ligne, s1 (la première ligne) et s2 (la deuxième ligne) (STDIN ou la plus proche). Vous pouvez supposer que la longueur de s1 sera toujours inférieure à 30 et supérieure à la longueur de s2. Le programme doit ensuite sortir chaque étape dans la distance de levenshtein de s1 à s2.

Pour clarifier ce que signifie chaque étape de la distance levenshtein, le programme imprimera n chaînes, où n est la distance levenshtein entre s1 et s2, et la distance levenshtein entre deux chaînes adjacentes sera toujours une. L'ordre n'a pas d'importance. La sortie doit être séparée par des sauts de ligne et ne pas inclure s1, uniquement les entre-deux et s2. Le programme devrait également fonctionner en moins d'une minute sur un ordinateur moderne.

Exemples:

Contribution:

Programming
Codegolf

Production:

rogramming
Cogramming
Coramming
Coamming
Codmming
Codeming
Codeging
Codegong
Codegolg
Codegolf

Contribution:

Questions
Answers

Production:

uestions
Aestions
Anstions
Ansions
Answons
Answens
Answers

Contribution:

Offline
Online

Production:

Ofline
Online

Contribution:

Saturday
Sunday

Production:

Sturday
Surday
Sunday

Voici un lien vers un script python qui affiche la distance et les étapes.

Règles supplémentaires:

• Pas d'utilisation d'Internet
• Des échappatoires standard s'appliquent

C'est du code-golf, alors gardez votre code court; le code le plus court gagne!

Javascript, 167 161 154 octets

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)}}

Appeler avec l("Programming","golf")

Codepen

Code dégolfé (et annoté) (obsolète mais vous avez l'idée):

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 octets

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

Plus long que prévu. Peut-être que je peux jouer au golf un peu ...

Exemple d'utilisation:

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

C'est une force brute qui décide entre changer et supprimer si les caractères initiaux diffèrent.