- Published on
- Fri Jan 24, 2014
EPI 5.9 - Elias Encoding and Decoding
Problem ¶
Elias encoded version of an integer X = X in binary PREPENDED by number of zeroes in the binary representation minus 1.
So Elias of encoding of 13 (binary = 1101) would be 000 1101 (3 zeroes as length of 1101 = 4).
Solution ¶
elias_encode_int :: Int -> [Char]
elias_encode_int x = (take (len - 1) (repeat '0')) ++ xbase2
where
xbase2 = intToString 2 x
len = (length xbase2)
elias_decode_str :: Int -> [Char] -> Int
elias_decode_str size xs = stringToInt 2 (take size xs)
elias_encode :: [Int] -> [Char]
elias_encode xs = concat (map elias_encode_int xs)
elias_decode_helper :: Int -> [Char] -> [Int]
elias_decode_helper nzeroes [] = []
elias_decode_helper nzeroes (f:fs)
| f == '0' = elias_decode_helper (1 + nzeroes) fs
| otherwise = (elias_decode_str (1 + nzeroes) (f:fs)) : (elias_decode_helper 0 (drop nzeroes fs))
elias_decode = elias_decode_helper 0