OpenEuphoria

Credit: Kat

include sort.e 
include misc.e 
 
integer maxErrors, bestScore 
sequence bestMatch 
 
procedure update( integer score, sequence x ) 
    if score > bestScore then 
        bestScore = score 
        bestMatch = x 
        puts( 1, bestMatch & '\n' ) 
    end if 
end procedure 
 
procedure diff0( sequence s1, sequence s2, sequence x, integer score ) 
 
    integer char1, char2 
 
    -- exceeds max errors or can't exceed high score? 
    if score < -maxErrors 
    or score + length(s1) < bestScore then 
        return 
    end if 
 
    -- process each character 
    while 1 do 
        -- both empty? 
        if length( s1 ) = 0 
        and length( s2 ) = 0 then 
            update( score, x ) 
            return 
 
        -- first string empty? 
        elsif length( s1 ) = 0 then 
            -- lose one point for each remaining char 
            score -= length( s2 ) 
            x &= repeat( '_', length(s2) ) 
            update( score, x ) 
            return 
 
        -- second string empty? 
        elsif length( s2 ) = 0 then 
            -- lose one point for each remaining char 
            score -= length( s1 ) 
            x &= repeat( '_', length(s1) ) 
            update( score, x ) 
            return 
        else 
            -- pop the first char off each string 
            char1 = s1[1] 
            char2 = s2[1] 
 
            s1 = s1[2..length(s1)] 
            s2 = s2[2..length(s2)] 
 
            -- equal? 
            if char1 = char2 then 
                -- remove and keep looping 
                x &= char1 
                score += 1 
            else 
                -- assume first char in string 1 is noise 
                diff0( char1 & s1, s2, x & '_', score-1 ) 
 
                -- assume first char in string 2 is noise 
                diff0( s1, char2 & s2, x & "_", score-1 ) 
 
                -- assume both chars are noise 
                diff0( s1, s2, x & "_", score-1 ) 
 
                -- try swapping letters in first string 
                if length( s1 ) 
                and char2 = s1[1] then 
                    diff0( s1[1] & char1 & s1[2..length(s1)], 
                            char2 & s2, x, score-3 ) 
                end if 
 
                -- try swapping letters in second string 
                if length( s2 ) 
                and char1 = s2[1] then 
                    diff0( char1 & s1, s2[1] & char2 & s2[2..length(s2)], 
                        x, score-3 ) 
                end if 
 
                return 
 
            end if 
        end if 
    end while 
 
end procedure 
 
procedure diff( sequence s1, sequence s2 ) 
 
    for i = floor( length( s1 ) / 2 ) to length( s1 ) do 
        bestScore = -1000 
        bestMatch = repeat( '_', length(s1) ) 
        maxErrors = i 
        diff0( s1, s2, "", 0 ) 
        if bestScore != -1000 then 
            return 
        end if 
    end for 
 
end procedure 
 
 
-- Kat's test code modified by _tom 
 
sequence s1, s2 
 
s1 = "aaarrrggg" 
s2 = "arrgggg" 
    puts(1, s1 & "\n" ) 
    puts(1, s2 & "\n" ) 
diff( s1, s2 ) 
    printf( 1, "best guess, score of %d: %s", {bestScore, bestMatch} ) 
 
puts(1, "\n--------------\n" ) 
 
s1 = "foo NOISEY bar" 
s2 = "foo noise barr" 
    puts(1, s1 & "\n" ) 
    puts(1, s2 & "\n" ) 
diff( s1, s2 ) 
    printf( 1, "best guess, score of %d: %s", {bestScore, bestMatch} )