fork(1) download
copy 
  1.  
  2. module leveshtein.Main
  3.  
  4. open System
  5. open System.Collections.Generic 
  6.  
  7. let chars = [|'a'..'z'|]
  8.  
  9. let Levenshtein (a: array<char>) (b: array<char>) =
  10.     let cache = Dictionary<_, _>()
  11.     let rec lev i j =
  12.         if cache.ContainsKey(i, j) then cache.[i, j]
  13.         else
  14.             let x =
  15.                 match i, j with
  16.                 | 0, j -> j
  17.                 | i, 0 -> i
  18.                 | _, _ -> min (min (lev (i - 1) j + 1) (lev i (j - 1) + 1)) (lev (i - 1) (j - 1) + (if a.[i - 1] = b.[j - 1] then 0 else 1))
  19.             cache.Add((i, j), x)
  20.             x
  21.     in lev a.Length b.Length
  22.  
  23. let add i c a = Seq.concat [Seq.take i a; Seq.singleton c; Seq.skip i a] |> Seq.toArray
  24.  
  25. let delete i a = Seq.concat [Seq.take i a; Seq.skip (i + 1) a] |> Seq.toArray
  26.  
  27. let change i c a = Seq.concat [Seq.take i a; Seq.singleton c; Seq.skip (i + 1) a] |> Seq.toArray
  28.  
  29. type Tree<'a> = Nil | Tree of 'a * list<Tree<'a>>
  30.  
  31. /// Creates a tree with all the Levenshtein minimum paths from a to b
  32. let EditChain a b =
  33.     let rec generate a =
  34.         let d = Levenshtein a b
  35.         let gens = seq {
  36.             for i in 0..(a.Length - 1) do
  37.                 let c1 = delete i a
  38.                 if (Levenshtein c1 b) < d then yield c1 else ()
  39.                 for c in chars do
  40.                     let c2 = change i c a
  41.                     if (Levenshtein c2 b) < d then yield c2 else ()
  42.             for i in 0..(a.Length) do
  43.                 for c in chars do
  44.                     let c3 = add i c a
  45.                     if (Levenshtein c3 b) < d then yield c3 else ()
  46.         }
  47.         gens
  48.         |> Seq.map (fun g -> Tree(g, generate g)) |> Seq.toList    
  49.     let c = generate a
  50.     in Tree(a, c) 
  51.  
  52. /// Flattens a Tree giving a list of all the paths from the root to the leaves
  53. let rec Flatten = function
  54.     | Nil -> [[]]
  55.     | Tree(a, []) -> [[a]]
  56.     | Tree(a, ts) ->
  57.         let ts2 = ts |> List.map (fun t -> Flatten t) |> List.concat
  58.         in ts2 |> List.map (fun t -> a::t)
  59.  
  60. /// Prints the edit chain paths given by Flatten
  61. let PrettyPrint (t: char array list list) =
  62.     let pca (a: char array) = new System.String(a)
  63.     t |> List.iter (fun cw ->
  64.         printf "%s" (pca (List.head cw))
  65.         (List.tail cw) |> List.iter (fun w -> printf " -> %s" (pca w))
  66.         printfn "")
  67.  
  68. [<EntryPoint>]
  69. let main args =
  70.     let a = Console.ReadLine().ToCharArray() 
  71.     let b = Console.ReadLine().ToCharArray()
  72.     PrettyPrint (Flatten (EditChain a b))   
  73.     0
Success #stdin #stdout 0.45s 12688KB
comments (?)
stdin
copy 
media
vida
stdout
copy 
media -> vedia -> vidia -> vida
media -> vedia -> veda -> vida
media -> midia -> vidia -> vida
media -> midia -> mida -> vida
media -> meda -> veda -> vida
media -> meda -> mida -> vida
https://ideone.com/5JFixw
language:
F# (mono 4.1)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!