1 
{-
  2 
 
  3 
Pearl 3: Improving on Saddleback search
  4 
 
  5 
Definitions:
  6 
Given function f(x,y) -> z , where x,y,z are Natural numbers.
  7 
f( , ) is strictly increasing in both it's arguments.
  8 
 
  9 
Problem:
 10 
Write the function invert which returns all the pairs (x,y) such that
 11 
f(x,y)=z
 12 
 
 13 
Solution:
 14 
 
 15 
Two methods: One that 'kind off' goes along a 'line' from top-left to bottom right, walking on the 'iso-line'.
 16 
The second is based on binary search, with the right limits, on different rows/columns
 17 
 
 18 
-}
 19 
module P3 where
 20 
 
 21 
-- Test function
 22 
f (x,y) = x+2*y
 23 
--f (x,y) = 3*x+27*y+y^2
 24 
--f (x,y) = x^2+y^2+x+y
 25 
 
 26 
 
 27 
-- Brute force
 28 
-- Requires (z+1)^2 evaluations of f
 29 
invert1 f z = [(x,y) | x<-[0..z],y<-[0..z],f (x,y) == z]
 30 
 
 31 
-- Saddleback search
 32 
-- Going from the top left to the bottom right, but moving to the right
 33 
-- in smart way, so NOT searching the whole triangle. More like searching
 34 
-- along a line.
 35 
invert2 f z = find2 (0,m) f z n
 36 
                where
 37 
                    -- determine boundaries of 'box' to search"
 38 
                    -- m on the y-axis, n on the x
 39 
                    -- we will search in the (0,0) (m,n) box
 40 
                    m = bsearch (\y->f(0,y)) (-1,z+1) z
 41 
                    n = bsearch (\x->f(x,0)) (-1,z+1) z 
 42 
 
 43 
find2 (u,v) f z n
 44 
    | u > n || v < 0    =    []                            -- if we are out of the box: Stop
 45 
    | z'<  z            =     find2 (u+1,v) f z n            -- we started from the TOP on the y-axis in every column
 46 
                                                        -- so if we stepped down on the column and didn't find it,
 47 
                                                        -- move one column to the right
 48 
    | z'== z            =     (u,v) : find2 (u+1,v-1) f z n-- We found one!! go to the right
 49 
    | z'>  z             =    find2 (u,v-1) f z n            -- Keep going down this column. we are still too large.
 50 
    where
 51 
        z' = f(u,v)
 52 
 
 53 
 
 54 
 
 55 
-- regular binary search
 56 
bsearch g (a,b) z
 57 
    | a+1 == b         = a                 -- no more 'segment' left
 58 
    | g m <= z        = bsearch g (m,b) z -- look at the top segment
 59 
    | otherwise     = bsearch g (a,m) z -- look at the bottom segment
 60 
    where
 61 
        m = (a + b) `div` 2
 62 
 
 63 
 
 64 
-- Binary search-2D, full swing
 65 
invert3 f z =     find3 (0,m) (n,0) f z
 66 
                where
 67 
                    m = bsearch (\y->f(0,y)) (-1,z+1) z
 68 
                    n = bsearch (\x->f(x,0)) (-1,z+1) z 
 69 
 
 70 
find3 (u,v) (r,s) f z
 71 
    | u > r || v < s     = []    -- out of bounderies
 72 
    | v-s <= r-u         = rfind (bsearch (\x->f(x,q)) (u-1,r+1) z)    -- Rows are longer than columns: search along row
 73 
    | otherwise         = cfind (bsearch (\y->f(p,y)) (s-1,v+1) z)    -- Column search
 74 
    where
 75 
        p         = (u+r) `div` 2
 76 
        q        = (v+s) `div` 2
 77 
        rfind p = (if f (p,q) == z     then (p,q): find3 (u,v) (p-1,q+1) f z     -- Top-Left Rectangle
 78 
                                    else find3 (u,v) (p,q+1) f z ) ++
 79 
                    find3 (p+1,q-1) (r,s) f z                                -- Bottom-Right rectangle
 80 
 
 81 
        cfind q = find3 (u,v) (p-1,q+1) f z ++                                -- Top-Left
 82 
                  (if f (p,q) == z     then (p,q): find3 (p+1,q-1) (r,s) f z    -- Bottom-Right
 83 
                                    else find3 (p+1,q) (r,s) f z ) 
 84 
                    
 85 
 
 86 
 
 87 
-- Main
 88 
 
 89 
main = do
 90 
    putStr "Brute force       : " 
 91 
    print $ invert1 f 18
 92 
    putStr "Saddleback search : " 
 93 
    print $ invert2 f 18
 94 
    putStr "Binary 2D search  : " 
 95 
    print $ invert3 f 18