-- Water jugs puzzle implemented with both 
-- Constrained Constructor and Incremental Solution patterns.
-- Sergio Antoy & Michael Hanus
-- Mon Oct  8 11:19:58 PDT 2001
-- Updated Mon Apr 18 09:03:37 PDT 2011

-- Two jugs can be filled from or poured into an unlimited supply
-- of water.  One jug can also be poured into the other until the
-- first is empty or the second is full.
-- The size of the jugs is given, e.g., 3 and 7 liters.
-- The goal is to obtained a given amout of water in a jug, e.g.,
-- for this program 1 liter in the small jug

import inc_search

-- The possible actions:
data Action = FillSmall | FillBig | PourSmall 
            | PourBig | SmallInBig | BigInSmall

-- A partial solution is described by (State s b n mvs) where
-- * s is the contents of the small jug
-- * b is the contents of the big jug
-- * n is the number of actions done so far
-- * mvs is the list of actions (in reverse order) done so far
data State = State Int Int Int [Action]

small = 3  -- the size of the small jug
big   = 7  -- the size of the big jug

-- Constrained constructor: only states compatible with
-- the physical constraints of the problem are created.
makeState s b ct mvs
   | 0 <= s && s <= small && 0 <= b && b <= big
   = State s b ct mvs

-- A partial solution is extended by performing a possible action:
extend :: State -> State
extend (State s b ct mvs) 
  = makeState small             b                   (ct+1) (FillSmall :mvs)
  ? makeState s                 big                 (ct+1) (FillBig   :mvs)
  ? makeState 0                 b                   (ct+1) (PourSmall :mvs)
  ? makeState s                 0                   (ct+1) (PourBig   :mvs)
  ? makeState (max (s-big+b) 0) (min big (b+s))     (ct+1) (SmallInBig:mvs)
  ? makeState (min small (b+s)) (max (b-small+s) 0) (ct+1) (BigInSmall:mvs)
  where max x y = if x > y then x else y
        min x y = if x < y then x else y

initState = State 0 0 0 []

smallOne (State s _ _ _) = s==1

fewerActions (State _ _ c1 _) (State _ _ c2 _) = c1 < c2

-- two partial solutions are equivalent if the contents of both jugs
-- are the same:
sameContents (State s1 b1 _ _) (State s2 b2 _ _) = s1==s2 && b1==b2


-- Tests ------------------------------------------------------------
-- best first search:
main1 = head (searchBestFirst extend initState smallOne fewerActions)

-- best first search with equivalence checking:
main2 = head
   (searchBestFirstNoEquiv extend initState smallOne fewerActions sameContents)