18
\$\begingroup\$

In this challenge you will write a program that takes two newline-separated strings, s1 (the first line) and s2 (the second line), as input (STDIN or closest). You can assume that the length of s1 will always be smaller than 30 and bigger than the length of s2. The program should then output each step in the levenshtein distance from s1 to s2.

To clarify what each step in the levenshtein distance means, the program will print n strings, where n is the levenshtein distance between s1 and s2, and the levenshtein distance between two adjacent strings will always be one. The order doesn't matter. The output should be newline-separated and not include s1, only the in-betweens and s2. The program should also run in under one minute on a modern computer.

Examples:

Input:

Programming
Codegolf

Output:

rogramming
Cogramming
Coramming
Coamming
Codmming
Codeming
Codeging
Codegong
Codegolg
Codegolf

Input:

Questions
Answers

Output:

uestions
Aestions
Anstions
Ansions
Answons
Answens
Answers

Input:

Offline
Online

Output:

Ofline
Online

Input:

Saturday
Sunday

Output:

Sturday
Surday
Sunday

Here is a link to a python script that prints out the distance and the steps.

Additional rules:

This is code-golf so keep you code short; shortest code wins!

\$\endgroup\$
  • 1
    \$\begingroup\$ For my edit, I rather presumed that the input would be of the form s1(newline)s2, however, having looked over the question again, I am wondering if instead you intended for the program to select s1 and s2 based on the length of 2 inputed strings, coming in either order, would you mind clarifying this point? That is, do we assume the input is s1 followed by s2, or do we select s1 and s2 based on the length of the two inputs? \$\endgroup\$ – VisualMelon Jun 7 '15 at 17:25
  • \$\begingroup\$ Does an answer have to run in a reasonable amount of time? \$\endgroup\$ – KSab Jun 7 '15 at 18:30
  • \$\begingroup\$ Camper - Ampere, distance 2, the python script runs forever ... \$\endgroup\$ – edc65 Jun 9 '15 at 13:47
  • \$\begingroup\$ How strict is "take input from STDIN or closest"? Can I write a function that takes the input via function argument? The currently accepted answer does so. \$\endgroup\$ – nimi Mar 5 '16 at 23:57
4
\$\begingroup\$

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

Call with l("Programming","golf")

Codepen

Degolfed (and annotated) code (out of date but you get the idea):

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
  }
}
\$\endgroup\$
  • \$\begingroup\$ function l(a,b,d){s="slice";if(a!=b){if(a.length>b.length)a=a[s](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)}} \$\endgroup\$ – Dr. Pain Dec 30 '15 at 21:31
  • \$\begingroup\$ @nimi: If you call it with two arguments (e.g. l("programming","codegolf")) it works the same, so I suppose your point is null. \$\endgroup\$ – 9999years Mar 7 '16 at 3:05
  • \$\begingroup\$ Also, declaring s inside a=a[s](1) as a=a[s="slice"](1) saves some bytes. \$\endgroup\$ – Mama Fun Roll Mar 7 '16 at 5:20
  • 1
    \$\begingroup\$ According to the link to codepen, your program outputs 11 steps for "Programming" -> "Codegolf", but it should be 10. \$\endgroup\$ – nimi Mar 7 '16 at 17:16
10
\$\begingroup\$

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

Longer than expected. Maybe I can golf it down a little bit ...

Usage example:

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

It's a brute force that decides between changing and deleting if the initial characters differ.

\$\endgroup\$
  • \$\begingroup\$ How long does it take to run? \$\endgroup\$ – Loovjo Jun 9 '15 at 5:12
  • \$\begingroup\$ How can I test (maybe ideone)? \$\endgroup\$ – edc65 Jun 9 '15 at 13:49
  • \$\begingroup\$ @Loovjo: shorter strings like your examples are calculated instantly, worst case is about 1:30min. I've interpreted the "should" in "should run in under one minute" not as a strict limit (should vs. must). If this is a must, I can add a "performance pack" for about 20 bytes. \$\endgroup\$ – nimi Jun 9 '15 at 15:09
  • \$\begingroup\$ @edc65: yes, ideone, but it expects the function to be executed to be called "main". Try: ideone.com/CUgU8W \$\endgroup\$ – nimi Jun 9 '15 at 15:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.