First puzzle from me, suggestions for improvement gladly received!
The scenario is; You work as a manager for a whitewater rafting company. Every morning, you are given a list of bookings, and you have to sort them into raft loads. Write a program or function in your chosen language that does this for you.
Each raft holds a maximum of
n clients, and each booking is for a group of between 1 and
n people (inclusive).
The following rules must be observed;
No groups may be split up. If they booked together, they must all be in the same raft.
The number of rafts must be minimised.
Subject to the two preceeding rules, the groups must be spread as equally as possible between the rafts.
n (you may assume that this is a positive integer), and the size of all the bookings. This may be an array, list or similar data structure if your language supports such things. All of these will be positive integers between 1 and
n. The order of the bookings is not defined, nor is it important.
Output. A list of the booking numbers, grouped into raft loads. The grouping must be indicated unambiguously, such as;
- a list, or array of arrays.
- a comma separated list for each raft. Newline between each raft.
How you implement the third rule is up to you, but this could involve finding the average raft occupancy, and minimising deviations from it as much as possible. Here are some test cases.
n Bookings Output 6 [2,5] , 4 [1,1,1,1,1] [1,1,1],[1,1] 6 [2,3,2] [2,2], 6 [2,3,2,3] [2,3],[2,3] 6 [2,3,2,3,2] [2,2,2],[3,3] 12 [10,8,6,4,2] ,[8,2],[6,4] 6 [4,4,4] ,, 12 [12,7,6,6] ,,[6,6]
Standard rules apply, shortest code wins. Have fun!
Edited; A suggested way to define as equally as possible for the third rule.
Once the number of rafts
r has been determined (subject to the second rule), the average occupancy
a can be calculated by summing over the bookings, and dividing by
r. For each raft, the deviation from the average occupancy can be found using
d(x) = abs(n(x)-a), where
n(x) is the number of people in each raft and
1 <= x <= r.
For some continuous, single-valued function
f(y), which is strictly positive and has a strictly positive first and non-negative second derivatives for all positive
y, we define a non-negative quantity
F, as the sum of all the
f(d(x)), 1 <= x <= r. Any choice of raft allocation that satisfies the first two rules, and where
F is equal to the global minimum will satisfy the third rule also.