Recently I've been looking for a job and as usual in the IT field, I got lots of tests and programming quizz (more on this in another post). Since I wanted to flex my haskell muscles, I tried to solve one of the problem I got with it.
Count harmonic slices
Here's the problem:
Given an array
A of integer count the number of harmonic slices in this array.
An harmonic array is an array where all consecutive elements differ only by the same constant. For example
[-1, 1, 3] is harmonic as well as
[-1, -1, -1] but
[-1, 1, 1] is not. If the array's length is less than 2, it's defined as non harmonic.
An harmonic slice is a sub array:
So for example, the array
A = [-1, 1, 3, 3, 3, 2, 1, 0] has 5 harmonic slices defined by the indices:
(0, 2) (2, 4) (4, 6) (4, 7) (5, 7).
I'll not spoil the solution here, but it fairly easy to come up with a
O(n) time complexity, and
O(1) space complexity. And btw, the platform used for the test did not allow haskell anyway.
I first started to replicate the classical solution using Haskell. While it would have lead to a more efficient algorithm, it was not very educational in learning Haskell. So I switched to a very declarative approach:
Get all potential slices
First, given a list of
Int, return all the potential slices for this list. This is easily achieved with list comprehension:
subLists :: [Int] -> [[Int]] subLists xs = [(take a) . (drop b) $ xs | a <- [3..n], b <- [0..n], a+b <= n ] where n = length xs
Check if a slice is harmonic
This one had me thinking a lot. I tried various approach using recursion or
foldl trying to replicate a
for loop approach I would've used in other languages but with limited success.
A declarative approach is actually easier. The trick is to zip the list with itself (minus the first element) to be able to compare an element with the next one.
isHarmonic :: [Int] -> Bool isHarmonic xs | length xs < 3 = False | otherwise = allEqual $ zipWith (-) xs $ drop 1 xs -- takes a list and return true iff all elements are equals allEqual :: [Int] -> Bool allEqual xs = and $ zipWith (==) xs $ drop 1 xs
Putting it all together
The end result is given by the length of the filtered list:
countHarmonicSlices :: [Int] -> Int countHarmonicSlices = length $ filter isHarmonic $ subLists
Which gives in ghci:
λ: countHarmonicSlices [-1, 1, 3, 3, 3, 2, 1, 0] 5
Reasoning about space complexity in Haskell is very hard because of lazyness. For the same reason, time complexity is also harder to evaluate. I would tend to think though that this algorithm is vastly less efficient and most surely not
O(n) since I'm actually evaluating all possible slices.
I'm not convinced "regular" Haskell is a good tool for this kind of task, but that wasn't the point of the exercise anyway.