Skip to content

Instantly share code, notes, and snippets.

@metric-space

metric-space/interleave.hs

Created December 11, 2022 09:41
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save metric-space/9e9ddc0cf1d41f63802d92300762f702 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save metric-space/9e9ddc0cf1d41f63802d92300762f702 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. metric-space created this gist Dec 11, 2022.
    18 changes: 18 additions & 0 deletions interleave.hs
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,18 @@
    import Data.Map qualified as M
    import Data.List qualified as L

    is_interleaved :: String -> String -> String -> Bool
    is_interleaved a b inte = let alen = length a
    blen = length b
    k x y
    | (x == alen) = drop y b == drop (x+y) inte
    | (y == blen) = drop x a == drop (x+y) inte
    | otherwise = ((a L.!! x == dest_elem) && ds M.! (x + 1,y)) || ((b L.!! y == dest_elem) && ds M.! (x ,y + 1))
    where dest_elem = inte L.!! (x+y)
    ds = M.fromList [((x,y),k x y) | x <- [0..alen], y <-[0..blen]]
    in k 0 0

    testCases :: [(String, String, String)]
    testCases = [("al","pha", "alpha"), ("banana", "ananas", "bananaananas"), ("dynamic", "programming", "prodgyrnamammiincg")]

    main = putStrLn . show . map (\(x,y,z) -> is_interleaved x y z) $ testCases