RSS

EPI 6.18 – Run-length Encoding

27 Feb

Problem:

Implement functions to run length encode a string and decode the RLE value of an encoded string.

For example “aaaabcccaa” should be encoded to “4a1b3c2a”, while “3e4f2e” would be decoded to “eeeffffee”.

Solution:

Encoding is straight forward:

run_length_encode :: [Char] -> [Char]
run_length_encode xs = run_length_encode' 0 '|' xs
    where
        run_length_encode' 0 _ [] = []
        run_length_encode' 0 _ (x:xs) = run_length_encode' 1 x xs
        run_length_encode' count curr_ch [] = (show count) ++ [curr_ch]
        run_length_encode' count curr_ch (x:xs)
            | curr_ch == x = run_length_encode' (count + 1) curr_ch xs
            | otherwise = (show count) ++ [curr_ch] ++ run_length_encode' 1 x xs

Decoding is also fairly straightforward, except we just need to accumulate the “count” before that many characters can be output:

run_length_decode :: [Char] -> [Char]
run_length_decode xs = run_length_decode' 0 xs
    where
        run_length_decode' _ [] = []
        run_length_decode' count (x:xs)
            | isDigit x = run_length_decode' ((count * 10) + (digitToInt x)) xs
            | otherwise = (replicate count x) ++ run_length_decode' 0 xs
About these ads
 

Tags: , , , ,

One response to “EPI 6.18 – Run-length Encoding

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
Follow

Get every new post delivered to your Inbox.

%d bloggers like this: