add third exercise of lecture 8

1 files changed, 43 insertions, 0 deletions

diff --git a/lec08/Party.hs b/lec08/Party.hs
index 05b5e0e..7163eaf 100644
--- a/lec08/Party.hs
+++ b/lec08/Party.hs
@@ -24,3 +24,46 @@ moreFun gl1@(GL _ f1) gl2@(GL _ f2)
 
 treeFold :: (a -> [b] -> b) -> Tree a -> b
 treeFold f (Node l subs) = f l $ map (\t -> treeFold f t) subs
+
+-- Exercise 3
+
+-- This exercise has been more troublesome than many others I've done, so here's
+-- an explanation (for both myself and other readers).
+--
+-- We know that:
+-- - We want to maximize the fun.
+-- - All guests in a list have their fun added.
+-- - Inviting a boss automatically sets the fun to zero for all the invited
+--   employees immediately under that boss.
+-- - As a consequence, if we recursively invite all bosses at all levels of the
+--   company hierarchy, regardless of which other employees we also invite, then
+--   only the CEO is going to have fun.
+--
+-- One way of maximizing the fun is to only invite employees who are not bosses
+-- (the leaves in the tree of the company hierarchy) so that the fewest people
+-- are excluded and we get most people's fun. However, a sub-boss could have
+-- more fun than all of their immediate employees, which makes that sub-boss
+-- more suitable to be invited, unless that sub-boss also have the fun set to
+-- zero due to a boss immediately above being invited, in which case both the
+-- sub-boss and all their employees are going to have no fun at all.
+--
+-- What this function is supposed to do here is, given a boss and a list of
+-- guest list pairs for each level (whose first element includes the boss of
+-- that level while the second does not), to compute an output pair whose first
+-- element has the best guest list with the given boss while the second has the
+-- best guest list without the given boss.
+--
+-- This implementation of the function calculates the two values for the output
+-- pair as follows. Since we can't invite any sub-boss when we invite a boss,
+-- then the most obvious answer for the first element is to just invite the
+-- given boss and all lists with no bosses, which are the second of each pair.
+-- As for the second element, since we don't invite the current boss, we're free
+-- to choose whether or not to invite any sub-boss, which results in choosing
+-- the list that most maximizes the fun in each pair.
+--
+-- Thanks you, Giacomo Cavalieri, for helping me write the solution!
+nextLevel :: Employee -> [(GuestList, GuestList)] -> (GuestList, GuestList)
+nextLevel boss outcomes = (bestWith, bestWithout)
+  where
+    bestWith    = glCons boss $ mconcat $ map snd outcomes
+    bestWithout = mconcat $ map (uncurry max) outcomes