CODEWITHSUNDEEP
algorithmfunctionhaskellfunctional-programmingocaml
Maciej Pk
Maciej Pk

Reputation: 123

Convert this algorithm into a procedure, that doesn't use recursion

Few weeks ago I had a task to accomplish and my way of thinking is correct, but the implementation I gave at that time was horrible. I have a chance to get some points but only if I provide a correct implementation. The problem is:

Consider a list of integers [x_1; x_2;...;x_n]. We'll call index i "a hole" if 1 < i < n, such as x_i < max(x_1,...,x_{i-1}) and x_i < max(x_{i+1},...,x_n). The depth of this hole is min(max(x_1,...,x_{i-1})-x_i, max(x_{i+1},...,x_n)-x_i).

Write procedure hole : int list -> int which for given list of integers find the max depth on this list. If there is no hole on the list, then the correct answer is 0. For example: hole [5;2;7;10;3;7] = 3, because for i=2, max on the left is 5, max on the right is 10, min (5 - 2, 10-2) = 3. hole [1;2;3;2;1] = 0, because there is no such index i, that matches our predicate.

Now, my procedure looks like this with using recursion:

let hole list =
   let rec aux maxL acc = function
    | [] -> (min_int, [])
    | x::xs ->
        let newMax = max maxL x in
        let (maxR, aclist) = aux newMax acc xs
        in
            if maxL > x && x < maxR then (max maxR x,(min (maxL-x) (maxR-x))::aclist)
            else (max maxR x, aclist)
in fold_left max 0 (snd (aux min_int [] list))

but I have to make it without using recursion, while I'm able to use high order functions. I wanted to use something called "function accumulation", but I can't get any idea on how to do it (been thinking about this problem for over 7 hours now).

Any code given in Haskell/OCaml is welcome. The only problem is that you CANNOT use recursion.

Upvotes: 1

Views: 213

Answers (1)

mdunsmuir
mdunsmuir

Reputation: 492

Here is code that may do what I think you are looking for, i.e. find the depth of the deepest 'hole' in a list of integers according to your description of a 'hole'. It zips up left and right scans for max with a list of the 'middle' values, which could be described with the word 'accumulating' if you want.

Not the most efficient implementation, I'm sure, but I think it is better than the obvious brute force solution. Where no hole is found, it returns Nothing.

deepestHole' :: [Int] -> Maybe Int
deepestHole' xs 
  | length xs < 3 = Nothing
  | maxHole < 1 = Nothing
  | otherwise = Just maxHole
  where
    lMaxes = scanl1 max $ take (length xs - 2) xs
    rMaxes = scanr1 max (drop 2 xs)
    middles = tail $ init xs
    holeDepth lMax mid rMax = min lMax rMax - mid
    maxHole = maximum $ zipWith3 holeDepth lMaxes middles rMaxes

Upvotes: 1

Related Questions