module Main where

-- Hauptprogramm
main  :: IO ()
main   
  = do putStrLn "COUNTDOWN NUMBERS GAME SOLVER"
       putStrLn "-----------------------------"
       putStr "\nEnter the source numbers (list of positive ints): "
       lns <- getLine
       let ns = read lns
       putStr "Enter the target number (positive integer): "
       ln  <- getLine
       let n = read ln
       display (solutions ns n)

-- Definition von Operatoren und Ausdruecken
data Op   = Add | Sub | Mul | Div     
data Expr = Val Int | App Op Expr Expr 

-- Applikation von Operatoren auf Werte
apply         :: Op -> Int -> Int -> Int
apply Add x y =  x+y
apply Sub x y =  x-y
apply Mul x y =  x*y
apply Div x y =  x `div` y

-- --------------------------------
-- Ein-/Ausgabefunktion  (2 Punkte) 
-- --------------------------------
-- Ausgabe des ersten Listenelementes, falls vorhanden.
-- Weitere Elemente sollen nur nach Eingabe der Returntaste ('\n') 
-- ausgegeben werden. Bei Betaetigung einer anderen Eingabetaste 
-- oder, falls keine (weiteren) L"osungen existieren, soll das 
-- Programm stoppen.
display         :: [Expr] -> IO ()
display _ = error "display muss noch definiert werden!"

-- -------------------------------
-- Kernaufgabe: Loesungssuche   --
-- -------------------------------
solutions      :: [Int] -> Int -> [Expr]
solutions ns n =  [ e | ns' <- subbags ns, e <- exprs ns', 
                        eval e == [n]]

-- Teilaufgaben hierzu: 
-- (A) subbags    :: [a]   -> [[a]]
-- (B) exprs      :: [Int] -> [Expr]
-- (C) eval       :: Expr  -> [Int]

-- -------------------
-- Teilaufgabe (A)  --
-- -------------------
-- Bestimme die Liste aller Permutationen
-- aller Teillisten einer gegebenen Liste.
subbags    :: [a] -> [[a]]
subbags xs =  [ys | xs' <- potenzmenge xs, ys <- perms xs' ]

-- Potenzmengenbestimmung 
potenzmenge        :: [a] -> [[a]]
potenzmenge []     =  [[]]
potenzmenge (x:xs) =  potxs ++ [x:ys | ys <- potxs]  
                    where potxs = potenzmenge xs

-- -----------------------------------
-- Permutationsbestimmung   (2 Punkte)
-- -----------------------------------
-- Bestimme zu einer Liste die Liste aller moeglichen Permutationen 
-- der Listenelemente
-- Beispiel: perms [1,2,3] =>*
--           [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
perms         :: [a] -> [[a]]
perms _ = error "perms muss noch definiert werden!"




-- -------------------
-- Teilaufgabe (B)  -- 
-- -------------------
-- --------------------------------
-- Ausdrucksbestimmung   (3 Punkte)
-- -------------------------------- 
-- Bilde zu einer Zahlenliste ns die Liste aller 
-- Ausdruecke e, fuer die gilt  values e == ns
exprs      :: [Int] -> [Expr]
exprs _ = error "exprs muss noch definiert werden!"


-- Bestimmt die Liste aller in einem Ausdruck 
-- vorkommenden ganzen Zahlen
-- wird nur für Spezifikation von exprs verwendet
values              :: Expr -> [Int]
values (Val x)      =  [x]
values (App op l r) =  values l ++ values r


-- -------------------
-- Teilaufgabe (C)  -- 
-- -------------------
-- -------------------------------------
-- Auswertung von Ausdruecken (1 Punkt) 
-- -------------------------------------
-- eval bestimmt zu einem arithmetischen Ausdruck seinen Wert
-- in einer einelementigen Liste. Falls der Ausdruck keine 
-- positive ganze Zahl ergibt oder ein Zwischenergebnis keine 
-- positive ganze Zahl ist, liefert die Funktion die leere Liste 
-- als Resultat.
eval              :: Expr -> [Int]
eval _ = error "eval muss noch definiert werden!"


-- ------------------
-- Hilfsfunktionen --
-- ------------------
-- zum Testen 
test :: IO()
test = putStr ( unlines (map show 
                   (solutions [1,3,7,10,25,30] 765)))


-- Anzeigefunktionen
instance Show Expr where 
  show = showExpr 
  
showExpr              :: Expr -> String
showExpr (Val n)      =  show n
showExpr (App op l r) =  "(" ++ showExpr l ++ showOp op ++ showExpr r ++ ")"


instance Show Op where
  show = showOp 
  
showOp     :: Op -> String
showOp Add = "+"
showOp Sub = "-"
showOp Mul = "*"
showOp Div = "/"