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 6.15 – Printing a 2D array in spiral order

Problem:

Given an nxm 2D array of integers, print it in spiral order.

Eg for a 3×3 matrix (with the following implicit values):

1 2 3
4 5 6
7 8 9

Would be printed as “1 2 3 6 9 8 7 4 5”

Solution:

The straight forward solution is to have 4 iterations, and in each iteration to print one of the two directions (horizontal and vertical) alternatively.

However a more intuitive solution is to use vectors to create a tour starting from the index (0,0) and incrementing the next point based on the current direction and position.

First we create the concept of directions along with a couple of helper functions:

data Direction = North | East | South | West
-- Return the clockwise direction of a given direction
clockwise_of North = East
clockwise_of East = South
clockwise_of South = West
clockwise_of West = North

-- Returns the vector representing the direction
vector_of North = (0, -1)
vector_of South = (0, 1)
vector_of East = (1, 0)
vector_of West = (-1, 0)

-- The primary coordinate that will be updated when traversing in a particular direction
primary_coord North = 1
primary_coord South = 1
primary_coord East = 0
primary_coord West = 0

-- Given a direction and point, returns the next and previous points in the direction.
next_pt dir (x,y) = ((x + fst (vector_of dir)),(y + snd (vector_of dir)))
prev_pt dir (x,y) = ((x - fst (vector_of dir)),(y - snd (vector_of dir)))

Now we simply use the above helpers to start and iterate through a tour:

print_spirally width height = print_spirally' East (0,0) 0 [width, height]
    where
        print_spirally' dir (x,y) t [w,h]
            | w == 0 || h == 0 = []
            | t < [w,h] !! curr_coord = (y * width + x + 1) : print_spirally' dir (next_pt dir (x,y)) (t+1) [w,h]
            | otherwise = print_spirally' next_dir (next_pt next_dir (prev_pt dir (x,y))) 0 [next_w,next_h]
            where 
                curr_coord = primary_coord dir
                dir_vector = vector_of dir
                next_dir = clockwise_of dir
                next_dir_vector = vector_of next_dir
                next_w = w - (abs (fst next_dir_vector))
                next_h = h - (abs (snd next_dir_vector))

Couple of things to note:

* w,h represent the “remaining” width and height in the spiral as each time there is a change in direction, the available coordinate size reduces by one (height if beginning vertically, width if beginning horizontally).
* t is the number of values printed in a given direction (when this value reaches “w” or “h” depending on the direction, direction is rotated and t is reset to 0).
* When the direction needs to change (in the otherwise) the “current” point is one beyond the last point in the direction. For this reason the next point is evaluted from the previous direction in the previous point.

EPI 6.13 – Rotate an array

Problem:

Given an Array of n elements, design an algorithm for rotating an Array right by i positions. Only O(1) additional storage is allowed.

Solution:

The natural solution is to start from position the value at index k to k + i, repeatedly n times. This will work well if GCD(n,i) is != 1. However a general solution is to perform m jumps of size i, l times, but each time starting from the next index.

The first helper function is to perform m jumps of “size” each starting from a given index, wrapping around if necessary. For example if A = [1,2,3,4,5,6,7,8,9,10],

m_rotations A 0 3 3

would cause the following jumps: 1 -> 4 -> 7, with A resulting in:

[1, 2, 3, 1, 5, 6, 4, 8, 9, 10]
m_rotations xs index size m = elems (m_rotations' (arrayFromList xs 0) index (xs!!index) size m)
    where
        len = length xs
        m_rotations' arr curr_index curr_value size numleft 
            | curr_index < 0 || size <= 0 || numleft <= 0 = arr
            | otherwise = m_rotations' (arr // [(next_index, curr_value)]) next_index next_value size (numleft - 1)
            where
                next_index = mod (curr_index + size) len
                next_value = arr!next_index

Now we create the actual rotator method that calls m_rotations k times, where k = gcd(|A|, j).

This is:

rotate_array xs j = rotate_array' xs 0
    where 
        lxs = length xs
        j' = mod j lxs
        gcd_lxs_j = greatest_common_divisor lxs j'
        numtimes = div lxs gcd_lxs_j
        rotate_array' xs start_index
            | start_index >= gcd_lxs_j = xs
            | otherwise = m_rotations ys (j' - (start_index + 1)) j' numtimes
            where
                ys = rotate_array' xs (start_index + 1)

A simpler algorithm to perform this is very similar to reversing words in a sentence:

rotate_array_simple xs j = reverse (take j rxs) ++ reverse (drop j rxs) 
        where rxs = reverse xs

EPI 5.10 – Greatest Common Divisor

Problem:

Design an algorithm for computing the GCD of two numbers without using multiplication, division or the modulus operator.

Solution:
The GCD of two numbers can be computed by recursively subtracting the smaller number from the larger until one of the numbers is 0, at which point the non-zero value is the GCD.

However this can be improved by “quickly” eliminating factors of two (by inspecting the least significant bits) and doubling and halving values (via left and right shifting by 1 respectively).

greatest_common_divisor x 0 = x
greatest_common_divisor 0 y = y
greatest_common_divisor x y
    | x_is_even && y_is_even = 2 * greatest_common_divisor (x `shiftR` 1) (y `shiftR` 1)
    | x_is_odd && y_is_even = greatest_common_divisor x (y `shiftR` 1)
    | x_is_even && y_is_odd = greatest_common_divisor (x `shiftR` 1) y
    | x  y = greatest_common_divisor (x - y) x
    | otherwise = x
    where
        x_is_even = (x .&. 1) == 0
        y_is_even = (y .&. 1) == 0
        x_is_odd = not x_is_even
        y_is_odd = not y_is_even

EPI 6.6 – Longest contiguous increasing subarray

Problem

An array is increasing if each element is less than its succeeding element except for the last element.

Given an array A of n elements return the beginning and ending indices of a longest increasing subarray of A.

Solution

Let S[i] be the longest increasing subarray between the indexes (0,i – 1).
Then

S[i] = a,b if A[i] > A[i – 1],
i,i otherwise
where a,b = S[i – 1]

In haskell this would be:

longest_contig_inc_subarray :: (Ord a) => [a] -> (Int, Int)
longest_contig_inc_subarray [] = (-1, -1)
longest_contig_inc_subarray (x:xs) = longest_contig_inc_subarray' (0, x, 0, x) xs
    where
    longest_contig_inc_subarray' (i,ai,j,aj) [] = (i,j)
    longest_contig_inc_subarray' (i,ai,j,aj) (x:xs) 
            | x >= aj = longest_contig_inc_subarray' (i,ai,j + 1,x) xs
            | otherwise = longest_contig_inc_subarray' (j + 1,x,j + 1,x) xs

A heuristic to improve the best case complexity (but does nothing in the worst case) is to realise that if the length of the longest subarray till i is L (and A[i + 1] < A[i] – indicating an end of the longest subarray), then a larger increasing subarray must contain *atleast* L elements. So we only need to start with L items in front and check backwards.

The code for this is (here the start index and the length of the subarray are returned instead):



-- Returns the size of the largest increasing "prefix" in an array
largest_inc_prefix [] = 0
largest_inc_prefix (x:[]) = 1
largest_inc_prefix (x:y:xs)
        | x = y = 1 + largest_dec_prefix (y:xs)
        | otherwise = 1

-- Returns the size of the largest decreasing "prefix" in an array
largest_dec_prefix [] = 0
largest_dec_prefix (x:[]) = 1
largest_dec_prefix (x:y:xs)
        | x >= y = 1 + largest_dec_prefix (y:xs)
        | otherwise = 1

lcisa :: (Ord a) => [a] -> (Int, Int)
lcisa [] = (-1,-1)
lcisa xs = lcisa' (0,1) 0 xs
    where 
        lcisa' (start,maxlen) i [] = (start,maxlen)
        lcisa' (start,maxlen) i xs
            | nextlen > maxlen = lcisa' nextbest
                                    (i + maxlen + inc_prefix)
                                    (drop inc_prefix rest)
            | otherwise = lcisa' (start,maxlen) (i + maxlen) rest
            where
                first_l = take maxlen xs
                rest = drop maxlen xs
                dec_prefix = largest_dec_prefix (reverse first_l)
                inc_prefix = largest_inc_prefix rest
                nextlen = inc_prefix + dec_prefix
                nextbest = (i + maxlen - dec_prefix, nextlen) 

EPI 6.19 – Reversing words in a sentence

Problem

Reverse the words in a sentence.

Solution

We can define a word as any substring separated by one or more spaces. To do this on constant space, simply reverse the entire sentence, and then reverse each word within.

In haskell, the recursive solution would be:

reverse_words :: [Char] -> [Char]
reverse_words [] = []
reverse_words xs = initial_spaces ++ (reverse after_spaces) ++ reverse_words remaining
    where
        initial_spaces = takeWhile isSpace xs
        spaces_dropped = dropWhile isSpace xs
        after_spaces = takeWhile (\x -> not (isSpace x)) spaces_dropped
        remaining = drop (length after_spaces) spaces_dropped

This is clearly not O(1) in space usage. The constant space solution would require maintaining array structures and swapping entries within the array.

EPI 6.5 – Subset summing to 0 mod n

Problem

Given an array A, a subset of S (i0, i1, i2… ik) of A such that Sum(S) mod n = 0. This is the 0 mod n subset problem.  Find this subset.

Solution

The general case of 0 mod k is NP complete however 0 mod n can be computed efficiently O(n) time and O(n) space.  Also in the case of n, there is always guaranteed to be a solution as seen below.

First create the array mod_till_k such that

mod_till_k[i] = Sum(A[0] .. A[i]) mod n

This is implemented below:

mod_till_k :: [Integer] -> [Integer]
mod_till_k xs = mod_till_k' 0 xs
    where
        n = length xs
        mod_till_k' :: Integer -> [Integer] -> [Integer]
        mod_till_k' _ [] = []
        mod_till_k' prev (x:xs) = curr : (mod_till_k' curr xs)
            where curr = mod (x + prev) (toInteger n)

Now if mod_till_k[x] == 0, then the subset [0,x] is a solution.
If there no x such that mod_till_k[x] == 0, then there WILL exist some a < b such that mod_till_k[a] == mod_till_k[b]. In this case the solution is [a + 1,b]

This search can done linearly with.

zero_mod_n_subset :: [Integer] -> (Integer, Integer)
zero_mod_n_subset xs = zero_mod_n_subset' 0 index_table (mod_till_k xs)
    where 
        n = length xs
        index_table = array (0, toInteger (n - 1)) [(toInteger i, -1) | i <- [0..n - 1]]
        zero_mod_n_subset' i index_table (x:xs)
            | x == 0 = (0,i)
            | index_table!x /= -1 = (index_table!x,i)
            | otherwise = zero_mod_n_subset' (i + 1) (index_table // [(toInteger x,toInteger i)]) xs

Here index_table, which is initialised to -1, keeps track of previous positions where a particular mod was last seen.

EPI 6.3 – Max Difference

A robot needs to travel along a path that includes several ascents and descents.  As it at ascends, it uses up energy stored in its battery.  As it descends it converts the potential energy to charge the battery.  Assume the conversion is perfect (ie descending X units restores as much as energy as was expended in an ascent of X units).  Also assume that the “distance” travelled is irrelevant and only the height determines the energy lost and gained.

Problem

Given a set of 3 dimensional coordinates which plot the ascents and descents during a robot’s path, compute the minimum battery capacity required.

Solution

The O(n^2) solution (for each index find the maximum “increase” is going forward and then find the index with the maximum increase) is:


third (a,b,c) = c

max_diff_nsquared xs = maximumBy (comparing third) 
                        [(i,j,xj - xi) | (i,xi) <- zip [0.. length xs - 1] xs, 
                                         (j,xj) <- zip [0.. length xs - 1] xs, i < j]

In the naive method, finding the maximum increase at an index is O(n^2). This can be brought down to a linear algorithm with O(n) space:

max_increase_from_index :: [Int] -> [(Int,Int)]
max_increase_from_index [] = []
max_increase_from_index (x:[]) = [(0,x)]
max_increase_from_index (x:xs)
    | x <= aj = (j,aj):max_inc_from_next
    | otherwise = (length max_inc_from_next, x) : max_inc_from_next
    where 
        max_inc_from_next = max_increase_from_index xs
        (j, aj) = head max_inc_from_next

This would return a list of triples (j,A[j]) such that for each index i. Note that the indexes of j will be in “reverse”.

To get the best i, j such that i < j and A[j] – A[i] is maximised:

lxs = length xs - 1
maximumBy (comparing third) [(i,lxs - j,aj-ai) | (i,ai,(j,aj))<- zip3 [0..((length ms) - 1)] ms ms2]

Giving the final solution of:

minimum_robot_battery :: [(Int,Int,Int)] -> (Int,Int,Int)
minimum_robot_battery xs = maximumBy (comparing third) [(i,lxs - j,aj-ai) | 
                            (i,ai,(j,aj)) <- zip3 [0..((length ms) - 1)] ms ms2]
    where 
        ms = map third xs
        ms2 = max_increase_from_index ms
        lxs = length xs - 1

Note that we dont actually have to compute the array of differences. We could have simply also passed and maintained in a “curr_max” variable which would have stored have returned the max difference at the completion of the call.

EPI 6.1 Dutch Flag Partition

Problem:

Write a function that taks an Array A and an index i into A, and rearranges the elements such that all elements less than A[i] appear first, followed by elements equal to A[i], followed by elements greater than A[i].

Solution:

First we define a couple of auxiliary helper functions to create haskell Arrays from haskell lists and a method to swap elements at two indexes in an Array:

import Data.Array

arrayFromList input startIndex = array bounds [(i + startIndex, x) | (i,x) <- (zip indexes input)]
            where
                bounds = (startIndex, startIndex + (length input) - 1)
                indexes = [0 .. length input]

swapItems xs a b = xs // [(b, xa)] // [(a, xb)]
            where
                xa = xs!a
                xb = xs!b

Now the algorithm. The core of the algorithm is to start with 4 partitions (with in the original Array):

smaller – All items smaller than the pivot element (originally A[i])
equal – All items equal to the pivot item
larger – All items larger than the pivot item
unclassified – Items that have not yet been classified into one of the above arrays.

Intuitively #unclassified = |A| – #smaller + #equal + #larger and this will become 0 at the end.

Initially #smaller, #equal and #larger = 0, 0 and |A| – 1 respectively. The following tail recursive solution updates one or more of these regions in each step as it iterates through the array (and stopping when the “equal” region “hits” the “larger” region).


dutch_flag_partition xs i = elems (dutch_flag_partition' arrayXS i 0 0 ((length xs) - 1))
    where
        arrayXS = (arrayFromList xs 0)
        pivot = arrayXS ! i
        dutch_flag_partition' xs i s e l
            | e > l = xs
            | (xs!e) < pivot = dutch_flag_partition' (swapItems xs s e) i (s + 1) (e + 1) l
            | (xs!e) == pivot = dutch_flag_partition' xs i s (e + 1) l
            | otherwise = dutch_flag_partition' (swapItems xs e l) i s e (l - 1)

A quick note. In this example (and others) we are using immutable collections. From an efficiency point of view using mutable collections would result in, well more efficiency. However we are striving for a balance between efficiency and reasonably simple code that is close enough to the guaranteed algorithmic complexities when these subtle differences (such as immutable vs mutable) are ignored.

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

EPI 5.8 – Spreadsheet Column Encoding

Problem:

Write a function that converts excel column IDs to corresponding integers with “A” corresponding to 1 and so on.

Solution:

We will modify the solution in EPI 5.6 slightly so that we have:

indexOf :: Eq a => a -> [a] -> Int
indexOf item xs
    | length firstMatched == 0 = -1
    | otherwise = fst (head firstMatched)
    where
        matchesItem x = snd x /= item
        firstMatched = dropWhile matchesItem 
                        (zip [0 .. (length xs) - 1] xs)
digitIndices :: [Char] -> [Int]
digitIndices digits = [ indexOf (chr i) digits | i <- [0 .. 255]]
spreadsheet_column_encoding :: [Char] -> [Int]
spreadsheet_column_encoding xs = 
        sum [ digit_to_value digit pos | (pos, digit) <- dig_positions xs]
    where
        reverse_indexes xs = [(length xs) - 1, (length xs) - 2 .. 0]
        dig_positions xs = zip  (reverse_indexes xs) xs
        symbols = ['A' .. 'Z']
        ourIndexes = digitIndices symbols
        digit_to_value digit pos = (1 + (ourIndexes !! (ord digit))) * 
                                    floor (26 ** fromIntegral pos)

EPI 5.7 – Generalised conversion between bases

Problem:

Continuing on from EPI 5.6, this problem is to convert an integer encoded as S1 in base b1, to S2 in base b2:

Solution:

The easiest way is to use the techniques in EPI 5.6 and simply do:

 base1ToBase2 b1 s1 b2 = intToString b2 (stringToInt b1 s1)

Anybody looking for a version without the intermediate conversion to base 10?

EPI 5.6 String to Integer inter conversion functions

Problem:

Implement the following methods, which convert (signed) integers to a string and vice versa respectively:

intToString x :: Int -> [Char]

stringToInt :: [Char] -> Int

Additionally invalid strings (when converting to Int) must return an error of some sort.

Solution:

Even though the question was specific to converting to and from base 10, this can be generalised to any base with *very* little changes.  The straightforward solution is:

intToString :: Int -> Int -> [Char]
intToString base x 
            | x < 0 = "-" ++ intToString base (-x)
            | x < base = [intToDigit x]
            | otherwise = (intToString base (div x base)) ++ [intToDigit (mod x base)]

stringToInt :: Int -> [Char] -> Int
stringToInt base (x:xs)
            | x == '-' = - (stringIntHelper base xs)
            | otherwise = stringIntHelper base (x:xs)
            where stringIntHelper base (x:xs)
                    | dx >= base = error ("Invalid digit: " ++ [x])
                    | length xs == 0 = digitToInt x
                    | otherwise = (dx * (floor (fromIntegral base ** fromIntegral digitsLeft))) + (stringIntHelper base xs)
                    where 
                        digitsLeft = (length xs)
                        dx = digitToInt x

Here is an alternative and more intuitive version of stringToIntHelper above:


stringToIntHelper2 base xs = 
            sum [ digit_to_value digit position |
                (position, digit) <- (zip dig_positions xs)]
    where 
        dig_positions = [(length xs) - 1, (length xs) - 2 .. 0]
        digit_to_value digit position = (digitToInt digit) * 
                            floor (base ** fromIntegral position)

This version does not check if each digit is between 0 and “base” but that is a trivial check to add via a “any” check in the original input (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.