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”.
Encoding is straight forward:
run_length_encode :: [Char] -> [Char]
run_length_encode xs = run_length_encode' 0 '|' xs
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
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
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.
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)
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.