Since you're looking for a starting point and not a solution, I'll walk through a brute force way that you could use to think about solving this functionally, but which is not computationally practical.
Emphasis again: this is not a practical solution, and even as brute force solutions go, you can probably do better
I'm also going to try to solve for the 1 week version of this, with the assumption that the 1 week schedule will repeat indefinitely. Note that this assumption doesn't necessarily have to be true (it's possible that there's a solution that would require 2 weeks in order to allocate). If we accept that assumption, one of your constraints will say that people who have 2 days off can't have both Monday and Friday off.
I'll use a really simplified version of your data model.
data Location = Home | Office deriving (Eq, Show)
Let's ignore the workers that are always in the office. They always consume the same number of chairs every day. In practical terms, if you have 41 chairs, and 10 employees that are there every day, you have 31 chairs left for your employees that have flexible schedules.
For your employees who are home once a week, their weekly schedule will be one of the permutations of
[Home, Office, Office, Office, Office]
and your employees who are at home twice a week will be one of the permutations of
[Home, Home, Office, Office, Office]
but you'll exclude the [Home,Office,Office,Office,Home]
since that would violate your constraint.
Let's name some types and grossly abuse lists to make things simple:
type WorkerSchedule = [Location] -- a schedule for an individual worker
type PossibleSchedule = [WorkerSchedule] -- a list of possible schedules for a worker
type FullSchedule = [WorkerSchedule] -- represents a list of workers with the schedule that they will work
type WorkerSchedules = [PossibleSchedule] -- represents the brute force pool of schedules
type ChairCount = Int
Here's a dumb, brute force algorithm:
- For each of your workers, create a
PossibleSchedule
that represents all of the possible ways that worker can be scheduled in a given week.
- Create a list of your workers' possible schedules (7 of one type, 49 of the other)
- Create a list of chairs that you have available every day [31,31,31,31,31]
- Start at the beginning of the worker list, with the first possible schedule for the first worker, with all of the chairs available.
- Find a way to solve for the rest of the workers, but with one fewer chair on each of the days that the worker will be in the office.
a. If there's a solution, then we just take our schedule and jam it onto the solution we found for the rest of the workers.
b. If there's no solution, then try again using the next possible schedule for that first worker. If there are no more possible schedules, then there is no solution.
You might end up with something that looks like:
findSchedule :: [ChairCount] -> WorkerSchedules -> Maybe Fullschedule
findSchedule chairs [] = Just [] --Nobody left to schedule!
findSchedule chairs ([]:xss) = Nothing --No other schedules I can try for this worker
findSchedule chairs ((x:xs):xss) =
case buildChairCountAfterWorker chairs x of
Nothing -> findSchedule chairs (xs:xss) --Try next schedule
Just newChairs -> case findSchedule newChairs xss of
Nothing -> findSchedule chairs (xs:xss) --Try next schedule
Just sched -> Just (x:sched) --Return solution
In this case, buildChairCountAfterWorker
is a helper function that takes a list of chairs, a proposed schedule for the worker, and returns a Maybe [ChairList]
which will be nothing if there are not sufficient chairs on one of the days, or otherwise provides the number of chairs remaining for everyone else.
So....this is functional and "correct", but not practical. Let's assume that your employees are fixed (you have the 56 employees as described in the problem).
*Constraints> findSchedule [5,5,5,5,5] allEmployees
Nothing
(0.07 secs, 43,830,416 bytes)
Ok - that's reasonable. We clearly can't fit all those people into 5 chairs.
*Constraints> findSchedule [51,51,51,51,51] allEmployees
Just <schedule removed for clarity>
(0.13 secs, 35,608,720 bytes)
Awesome. When we have a lot of room to find a solution, we don't have to explore the solution space very far.
*Constraints> findSchedule [6,6,6,6,6] allEmployees
Nothing
(0.49 secs, 373,728,960 bytes)
*Constraints> findSchedule [7,7,7,7,7] allEmployees
Nothing
(13.56 secs, 9,336,407,864 bytes)
*Constraints> findSchedule [8,8,8,8,8] allEmployees
Nothing
(328.77 secs, 250,233,745,768 bytes)
Uh - that doesn't look good. If we constrain ourselves to 8 chairs, it still takes 5 minutes to get far enough down the solution space to confirm that we don't have a solution.
Closing in on more constrained solution from the top isn't any better:
*Constraints> findSchedule [47,47,47,47,47] allEmployees
(149.57 secs, 112,385,139,968 bytes)
You can almost certainly do better than this algorithm, but the takeaway is probably that you should be using a specialized solver as discussed in the comments to your original post. Dumb brute force is always going to run into an exponential problem that looks a lot like 9**(number of employees).
schedules :: Int -> Workers -> [Schedule]
that generates all imaginable schedules of N weeks, starting with those where nobody is at the office any day at all to those where everybody comes in every day. Thenschedule = head . filter isValidSchedule . schedule 2
– Bergi Apr 8 at 2:15:sat
in the cryptol repl will ask a solver for an assignment that meets the constraints. – Daniel Wagner Apr 8 at 2:40sbv
Haskell library. I really enjoy using for solving problems like this. – arrowd Apr 8 at 6:05