Find all strings at distance k
Scala 168 228

My first submission had a bug where it didn't consider multiple insertions at the same point in the input string.

After

val k = 1
val s = "1111011010"


The code that counts is:

def e(k:Int,s:String):Set[String]=if(k&lt;1)Set(s)else e(k-1,s).flatMap(e=&gt;"01"map(_+e))++(if(s=="")Set()else e(k,s.tail).map(s.head+_)++e(k-1,s.tail).flatMap(e=&gt;(Set("0","1","")-(s take 1))map(_+e)))
print(e(k,s))


To run, save both sections together as a file and run like:

$ scala distancek.scala
Set(111111010, 111101010, 1111001010, 11110011010, 1101011010, 11101011010, 111101101, 111101100, 11111011010, 1111011011, 1111011000, 11110101010, 1111010010, 11110110110, 11110110101, 111101110, 11110110010, 0111011010, 1110011010, 11110110100, 10111011010, 11011011010, 01111011010, 1011011010, 1111111010, 111011010, 11110111010, 1111011110)
$


Recursive function to build the edited strings. k is the number of edits remaining, s is the string to edit. Slightly ungolfed:

def e(k:Int,s:String):Set[String]=
  if(k&lt;1) Set(s)                           // No edits left
  else e(k-1,s).flatMap(e=&gt;"01"map(_+e))++ // Insert a character, consume an edit, continue from the same point
      (if(s=="") Set()                     // We're at the end of the string so only insertions are allowed
       else e(k,s.tail).map(s.head+_)++    // skip past this character, making no edit
       e(k-1,s.tail).flatMap(e=&gt;(Set("0","1","")-(s take 1))map(_+e))) // replace this character with its inverse or ""


Note that each step makes at least one of k, s smaller so we're guaranteed to terminate.



First submission (Incorrect)

print((0 to 10).permutations.flatMap{i=&gt;((s.map(_+""):+"")zip i).:\(Set("")){case((s,i),a)=&gt;a.flatMap{a=&gt;(if(i&lt;k)Set(1+s,0+s,"","0","1")-s else Set(s))map(_+a)}}}toSet)


We take the permutations of 0..10 and zip them with the word s + a terminal "" (for insertions at the end).
All the positions &lt; k are positions where an edit should occur. For each edit we replace the string at that position with

Set(1+s,0+s,"","0","1")-s # don't count substituting s for itself as an edit.


and finally convert to a set to remove duplicates.