--h = number of humans on the left
--g = number of giants on the left
--s = side (left/right)
 
left = 0
right = 1
 
valid_state (h, g, s) =
    if (h >= 0) && (h <= 3) && (g >= 0) && (g <= 3)                --number of people valid?
    then not (((g > h) && (h>0)) || ((3-g > 3-h) && (3-h > 0)))    --num of giant <= num of human
    else False
 
change (h, g, s) (hd, gd) =         -- create a new state based on hd (human diff), gd (giant diff)
    if s == left 
    then (h-hd, g-gd, right)
    else (h+hd, g+gd, left)
 
possible_states (h, g, s) = filter valid_state [change(h,g,s) (x,y) |
                            (x,y) <- [(1,0), (0,1), (1,1), (2, 0), (0, 2)]]
                                    --  H      G     HG     HH       GG
solve x 0 = []                      -- reached max depth
solve [] depth = []                 -- no more sibling node to traverse
solve (x:xs) depth =
    let (h, g, s) = x;
        z = solve (possible_states(h,g,s)) (depth-1)
    in  if (h == 0) && (g == 0) && (s == 1)
        then [(h,g,s)]
        else
            if length z > 0        --if child got answer
            then [(h,g,s)]++z   
            else solve xs depth    --otherise return siblings' answer
 
iter_dpn depth =                --Iterative deepening depth-first search
    let ans = solve [(3,3,left)] depth
    in if length ans > 0
       then ans
       else iter_dpn (depth+1)
 
-- run "iter_dpn 0" to find answer