Solution to the ghentfpg castles problem by Javache & me

castles.hs

import Data.Monoid
import Data.Ord (comparing)
import Data.List (sortBy, maximumBy)

import Data.Map (Map)
import qualified Data.Map as M

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

-- We use a 'Castle' structure to represent the nodes, and a simple 'Graph' type
-- to indicate the edges (roads). We give each castle a unique name (a 'Char')
-- in order to build a graph more easily.
--
-- So an input set consists of a
--
-- * 'World', which holds a number of castles by name
--
-- * 'Graph', which describes the roads between the castles

data Castle = Castle
    { castleNeeded      :: Int
    , castleCasualties  :: Int
    , castleLeaveBehind :: Int
    } deriving (Show)

type World = Map Char Castle
type Graph a = Map a [a]

-- | Auxiliary function: delete a node from a graph, also remove all edges
-- leading to/coming from the node
delete :: Ord a => a -> Graph a -> Graph a
delete c g = M.map (filter (/= c)) $ M.delete c g

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

-- We figures castles could be reduced to a simpler tuple (called 'Cost'),
-- which represents the cost to conquer a number of castles. It holds
--
-- * The number of soldiers needed to conquer the castles
--
-- * The number of soldiers we have left, after conquering those castles
--
-- We have a 'conquer' function which calculates the cost needed for one castle
-- using a simple formula.
--
-- A monoid is used in order to combine costs:
--
-- > cost1 `mappend` cost2
--
-- stands for the sequential conquering of (the castles represented by) @cost1@,
-- followed by the conquering of (the castles represented by) @cost2@

data Cost = Cost
    { costNeeded :: Int
    , costRemain :: Int
    } deriving (Show)

instance Monoid Cost where
    mempty = Cost 0 0
    mappend (Cost n1 r1) (Cost n2 r2) = Cost
        (n1 + max (n2 - r1) 0)
        (r2 + max (r1 - n2) 0)

conquer :: Castle -> Cost
conquer (Castle a b c) = Cost needed (needed - b - c)
  where
    needed = max a (b + c)

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

-- This is the actual solving algorithm. 'solve' is the entry method, it
-- finds the castle with the highest number of "remaining" soldiers after
-- capturing that castle, and starts our search algorithm with that node.
--
-- Our main algorithm, 'solveTree', recursively calls itself on all of it's
-- children (which are subtrees we can solve). It determines an optimal order
-- for it's children, and then sequentially conquers the root, followed by the
-- children (in the optimal order we calculated).

solve :: World -> Graph Char -> Int
solve w g = costNeeded $ solveTree w g start
  where
    start :: Char
    start = fst $ maximumBy (comparing $ costRemain . snd) $
        map (\k -> (k, conquer (w M.! k))) $
        M.keys g

solveTree :: World -> Graph Char -> Char -> Cost
solveTree w g c = conquer (w M.! c) `mappend` mconcat
    (reverse $ sortBy (comparing costRemain) children)
  where
    children = map (solveTree w g') (g M.! c)
    g' = delete c g

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

-- Below are example inputs

smallGraph :: Graph Char
smallGraph = M.fromList
    [ ('a', "bc")
    , ('b', "a")
    , ('c', "a")
    ]

smallWorld :: World
smallWorld = M.fromList
    [ ('a', Castle 5 1 1)
    , ('b', Castle 5 5 5)
    , ('c', Castle 10 5 5)
    ]

smallGraph' :: Graph Char
smallGraph' = M.fromList
    [ ('a', "bc")
    , ('b', "a")
    , ('c', "a")
    ]

smallWorld' :: World
smallWorld' = M.fromList
    [ ('a', Castle 110 0 100)
    , ('b', Castle 100 0 90)
    , ('c', Castle 100 0 0)
    ]

graph :: Graph Char
graph = M.fromList
    [ ('a', "b")
    , ('b', "adc")
    , ('c', "b")
    , ('d', "be")
    , ('e', "d")
    ]

world :: World
world = M.fromList
    [ ('a', Castle 20 10 5)
    , ('b', Castle 10 5 10)
    , ('c', Castle 5 5 5)
    , ('d', Castle 10 10 5)
    , ('e', Castle 20 0 10)
    ]

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

-- Example main code

main :: IO ()
main = print $ solve world graph

Im trying to do this in java