alloc.hs

module Alloc where

import Control.Arrow (first)
import Data.List (mapAccumL)

{-
given a stream of [[Int]] each sublist representing a day, each place representing people
each number representing the number of days they want to stay
We would like to get a list of rooms to check in on the day and rooms to check out on the day
and maximum number of occupied rooms.
-}

data Allocs = Allocs { checkouts :: [Int]
                     , checkins  :: [Int]
                     }
  deriving (Eq, Show)

data Rooms = Rooms { occupied :: [(Int, Int)] -- room no, remaining days
                   , free     :: [Int]        -- room no
                   }
  deriving (Eq, Show)

total :: Rooms -> Int
total rooms = (length . occupied) rooms + (length . free) rooms

alloc :: [[Int]] -> (Int, [Allocs])
alloc = first (length . free) . mapAccumL dailyActivity (Rooms [] [])

dailyActivity :: Rooms -> [Int] -> (Rooms, Allocs)
dailyActivity rooms arrivals = (rooms', Allocs checkedOutRooms (map fst ins))
  where
    rooms' = Rooms (roomsOccupiedAfterCheckOuts ++ ins) roomsFreeAfterCheckIns
    decrementedOccupied = map (\(n, d) -> (n, d-1)) $ occupied rooms
    checkedOutRooms = (map fst . filter lastDay) decrementedOccupied
    roomsFreeAfterCheckOuts = free rooms ++ checkedOutRooms
    ins = zip (roomsFreeAfterCheckOuts ++ [total rooms..]) arrivals
    roomsOccupiedAfterCheckOuts = filter (not . lastDay) decrementedOccupied
    roomsFreeAfterCheckIns = drop (length arrivals) roomsFreeAfterCheckOuts

lastDay :: (Int, Int) -> Bool
lastDay room = snd room == 0