-----------------------------------------------------------------------------
--   Problem 1
-----------------------------------------------------------------------------


type Variable = String
type TruthAssign = [Variable]

data Form = Var Variable
          | Disj Form Form
          | Conj Form Form
          | Imp Form Form
          | Neg Form
	    deriving (Eq)
--            deriving (Show, Eq)

exp1, exp2, exp3, exp4, exp5, exp6 :: Form

-- X
exp1 = Var "X"

-- ~Y
exp2 = Neg (Var "Y")

-- ~~Z
exp3 = Neg (Neg (Var "Z"))

-- X \/ ~Y
exp4 = Disj (Var "X") (Neg (Var "Y"))

-- W /\ (X \/ ~Y)
exp5 = Conj (Var "W") (Disj (Var "X") (Neg (Var "Y")))

-- ~(W => (X \/ ~Y))
exp6 = Neg (Imp (Var "W") (Disj (Var "X") (Neg (Var "Y"))))

instance Show Form where
    show (Var v) = v 
    show (Disj f1 f2) = "(" ++ (show f1) ++ "\\/" ++ (show f2) ++ ")"
    show (Conj f1 f2) = "FIX!!"
    show (Impl f1 f2) = "FIX!"
    show (Neg f1)     = "Fix!"
    -- Etc.

demorgan, negate :: Form -> Form

demorgan  (Var v)     = Var v
-- Etc.

negate (Var v)        = Neg (Var v)
-- Etc.


-----------------------------------------------------------------------------
--   Problem 2
-----------------------------------------------------------------------------

type Board = [Int]
type Move = Board -> Board
type Name = String
type Player = (Name, Move)

-- 
-- two simple strategies
--

delay, grab :: Move

delay (0:rest) = 0:(delay rest)
delay (n:rest) = (n-1):rest

grab (0:rest) = 0:(grab rest)
grab (n:rest) = 0: rest

-- 
-- one more involved strategy
--

-- This is based on pages 117-120 in ``An Introduction to the Theory
-- of Numbers, 5/e'' by G.H. Hardy and E.M. Wright, Oxford
-- Univ. Press, 1985.  Try and bet this guy.

smart :: Move
smart bd 
    | null goodPositions = delay bd
    | otherwise          = take i bd ++ [xor m x] ++ drop (i+1) bd
    where
      -- xor m n = the bit-wise exclusive-or of m and n
      xor :: Int -> Int -> Int
      xor 0 n = n
      xor m 0 = m
      xor m n = 2*((m `div` 2) `xor` (n `div` 2)) + ((m+n) `mod` 2)
      -- x = n1 `xor` n2 `xor` ... nk `xor` 0, where bd = [n1,...,nk]
      x :: Int 
      x = foldr xor 0 bd
      -- goodPositions = a list of good positions for a move
      goodPositions  = [(j,n) | (j,n) <- zip [0..] bd, x `xor` n < n]
      (i,m) = head goodPositions        

--------------------------------------------------------------------------
-- Call the first player Alice and the second player Bob and let
--  them play with a starting board: [3,5,7]. So
--      (nim grab delay) 
--  runs the game in which Alice plays the grab strategy and Bob
--  plays the delay strategy.

nim :: Move -> Move -> IO ()
nim m1 m2 = putStr (nimPlay ("Alice",m1) ("Bob",m2) [3,5,7] ++ " wins.\n")

-- A placeholder definition of nimPlay

nimPlay :: Player -> Player -> Board -> Name
nimPlay p1 p2 bd = "Mrs. Frisby"

--------------------------------------------------------------------------