{-
  Examples of programming search algorithms using Haskell
  using the Maybe and List monads

  Pedro Vasconcelos <pbv@dcc.fc.up.pt>, 2017-2021
-}

import Data.List
import Control.Monad

{-
  Solve an arithmetic puzzles.

  "Find an assignment of distinct digits 0..9 to letters such that
   the following addition holds:
      SEND
    + MORE
   -------
   = MONEY

  A solutions using the list monad for backtracking search.

-}

type Solution = (Int, Int, Int)  -- (SEND, MORE, MONEY)

puzzle :: [Solution]
puzzle = do
  -- generate all possible assignments
  s <- [1..9]
  e <- [0..9] \\ [s]
  n <- [0..9] \\ [s,e]
  d <- [0..9] \\ [s,e,n]
  m <- [1..9] \\ [s,e,n,d]
  o <- [0..9] \\ [s,e,n,d,m]
  r <- [0..9] \\ [s,e,n,d,m,o]
  y <- [0..9] \\ [s,e,n,d,m,o,r]
  -- filter using the condition
  let send = number [s,e,n,d]
  let more = number [m,o,r,e]
  let money = number [m,o,n,e,y]
  guard (send + more == money)
  return (send,more,money)


number :: [Int] -> Int
number ds = foldl (\r d -> 10*r+d) 0 ds


-- Greedy algorithm: always choose the largest possible coin
-- search in the Maybe monad
greedy :: [Int] -> Int -> Maybe [Int]
greedy coins 0  = return []
greedy coins quant 
  | null lesseq = Nothing
  | otherwise = do
      let c = maximum lesseq
      cs <- greedy lesseq (quant-c)
      return (c:cs)
  where
    lesseq = filter (<=quant) coins   -- all usable coins


-- Exaustive solution: finds all possible decompositions
-- search in the list monad
exaustive :: [Int] -> Int -> [[Int]]
exaustive coins 0 = return []
exaustive coins quant
  | null lesseq = []
  | otherwise = do
      c <- lesseq
      cs <- exaustive lesseq (quant-c)
      return (c:cs)
  where
    lesseq = filter (<=quant) coins


eurocoins :: [Int]
eurocoins = [5,10,20,50,100,200]