EPI 6.18 – Run-length Encoding

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

EPI 5.4: Closest integers with the same weight

Problem (EPI 5.4):

The weight, W(x) of an integer, x, is the number of bits set (to 1) in binary.

Given a 64 bit unsigned integer x (where W(x) != 0 and W(x) != 64) find y such that W(x) = W(y) and |x – y| is minimized.

Solution:

An example would make this clear, eg if

X = 4 (dec) = 0100 (bin)

The candiates are:

0001   –   Diff = 3

0010   –   Diff = 2

1000   –   Diff = 4

So Y = 010 (bin) = 2 (dec).

The solution to this is to start with X and find the first “01” or “10” starting from the LEFT and then swap the bits.

In haskell this is (assuming a 64 bit number)

import Data.Bits
closest_neighbour_by_weight x = closest_neighbour_by_weight_aux x 0
    where closest_neighbour_by_weight_aux x i 
            | two_digits /= 0 && two_digits /= 3 = xor x (shiftL 3 i)
            | otherwise = closest_neighbour_by_weight_aux x (i + 1)
              where two_digits = (x `shiftR` i) .&. 3

Essentially starting from the least significant bit (i = 0), we see if the bit at position i and the bit at position i + 1 are the same. If they are same, then we recursively continue with i + 1. If they are NOT the same then the bits are swapped (with the x ^ (3 << i) in the False case) and that is the solution. The xor with 3 is just a easy way to swap two consecutive bits.