One Away



In [1]:

    
oneAway :: String -> String -> Bool
oneAway "" "" = True
oneAway (x:xs) (y:ys)
    | x == y = oneAway xs ys
    | otherwise = xs == ys || (x:xs) == ys || xs == (y:ys)
oneAway "" [ys] = True
oneAway [xs] "" = True
oneAway _ _ = False



In [2]:

    
map (uncurry oneAway) [ ("pale", "ple")
                      , ("pales", "pale")
                      , ("pale", "bale")
                      , ("pale", "bake")
                      ]









    





[True,True,True,False]

Tests



In [3]:

    
data Edit = Remove | Insert Char | Replace Char deriving (Show)



In [4]:

    
applyEdit :: String -> Int -> Edit -> String
applyEdit "" _ (Insert c) = [c]
applyEdit "" _ _ = ""
applyEdit xs n edit =
    case edit of
        Remove -> ys ++ tail zs
        (Insert c) -> ys ++ c:zs
        (Replace c) -> ys ++ c:tail zs
    where
        n' = n `mod` length xs
        (ys, zs) = splitAt n' xs



In [5]:

    
applyEdit "abc" (-1) Remove
applyEdit "abc" (-2) (Insert 'z')
applyEdit "abc" 2 (Replace 'q')









    





"ab"






    





"azbc"






    





"abq"



In [6]:

    
import Test.QuickCheck



In [7]:

    
import Control.Applicative



In [8]:

    
instance Arbitrary Edit where
    arbitrary = oneof [ elements [Remove]
                      , Insert <$> (arbitrary :: Gen Char)
                      , Replace <$> (arbitrary :: Gen Char)
                      ]

Unfortunately, the following test doesn't check the last invariant, and, specifically, when the strings are two or more edits away, oneAway must return False. This invariant is not trivial to check, because if one arbitrary generates multiple Edits, they might end up compensating each other, or be collapsible into one Edit.

Apparently, it is not possible to evaluate the consequences of edits without knowing at least the length of the string, and then one would need to see if resulting strings are equal and/or the difference can be expressed as one edit. For now, we decided to leave this up to future generations.



In [9]:

    
testOneAway :: (String, Int, Edit) -> Bool
testOneAway (xs, n, edit) =
    oneAway xs xs &&
    oneAway xs (applyEdit xs n edit)



In [10]:

    
quickCheck testOneAway









    





+++ OK, passed 100 tests.