# Rafting Problem (Knapsack variant)

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.

Inputs. The number 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]          [5],[2]
4  [1,1,1,1,1]    [1,1,1],[1,1]
6  [2,3,2]        [2,2],[3]
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]   [10],[8,2],[6,4]
6  [4,4,4]        [4],[4],[4]
12 [12,7,6,6]     [12],[7],[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.

• For future reference you can post to our sandbox to get feedback on a challenge before you post. Feb 12, 2017 at 3:17
• Welcome to Programming Puzzles & Code Golf! This looks like a nice challenge, knowing that its your first challenge. Next time, however, it might be better to post the challenge in the Sandbox first, so people can give suggestions there. Then when you think the challenge is done, you can post it on the main site. Thank you for reading, and have a nice day! Feb 12, 2017 at 3:24
• How is as equally as possible measured? Feb 12, 2017 at 5:50
• @Dennis; I will put a suggested way to define this in an edit. However if you have a different method, and can justify it for your answer, that is fine.
– Gwyn
Feb 12, 2017 at 6:11
• Leaving things up to the implementation is fine, as long as it's clear what is valid and what not, and your latest edit achieves that imo. I'm a bit surpised that we can't use g(y) = y (second derivate zero) or g(y) = y² (first derviate zero when y = 0) though. Feb 12, 2017 at 6:52

import Data.List
o=map
u=sum
p=foldr(\x t->o([x]:)t++[(x:y):r|(y:r)<-t>>=permutations])[[]]
m x=foldl(\[m,n]x->[m+(x-m)/(n+1),n+1])[0,0]x!!0
a!z=abs$u z-a s t=(length t,u$o((m$o u t)!)t) a n=head.sortOn s.filter(all$(<=n).u).p


Or ungolfed

partition' :: [a] -> [[[a]]]
partition' [] = [[]]
partition' (x:xs) = [[x]:ps     | ps <- partition' xs]
++ [(x:p):rest | ps <- partition' xs, (p:rest) <- permutations ps]

-- from Data.Statistics
mean :: [Double] -> Double
mean xs = fst $foldl (\(m, n) x -> (m+(x-m)/n+1, n+1)) (0, 0) xs diff :: Double -> [Double] -> Double diff avg xs = abs$ sum xs - avg

rawScore :: [[Double]] -> Double
rawScore xs = sum . map (diff avg) $xs where avg = mean . map sum$ xs

score :: [[Double]] -> (Int, Double)
score xs = (length xs, rawScore xs)

-- from Data.Ord
comparing :: (Ord b) => (a -> b) -> a -> a -> Ordering
comparing p x y = compare (p x) (p y)

candidates :: Double -> [Double] -> [[[Double]]]
candidates n xs = filter (all (\ ys -> sum ys <= n)) . partition' $xs answer :: Double -> [Double] -> [[Double]] answer n xs = minimumBy (comparing score)$ candidates n xs


With some test cases

import Text.PrettyPrint.Boxes

testCases :: [(Double, [Double])]
testCases = [(6 , [2,5])
,(4 , [1,1,1,1,1])
,(6 , [2,3,2])
,(6 , [2,3,2,3])
,(6 , [2,3,2,3,2])
,(12, [10,8,6,4,2])
,(6 , [4,4,4])
,(12, [12,7,6,6])]

runTests tests = transpose
$["n", "Bookings", "Output"] : map (\(n, t) -> [ show . floor$ n
, show . map floor $t , show . map (map floor)$ a n t]) tests

test = printBox
. hsep 3 left . map (vcat top) . map (map text) . runTests $testCases  Where test yields n Bookings Output 6 [2,5] [[2],[5]] 4 [1,1,1,1] [[1,1],[1,1,1]] 6 [2,3,2] [[2,2],[3]] 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] [[10],[8,2],[6,4]] 6 [4,4,4] [[4],[4],[4]] 12 [12,7,6,6] [[12],[7],[6,6]]  ## Edit Thanks to @flawr and @nimi for advice. Squashed p a bit. Shaved off a couple bytes. • You could set s=sum and then use s instead of sum, and perhaps you could also replace fst$ ... with ...!!0. Feb 12, 2017 at 10:18
• You can replace minimumBy(c s) with head.sortOn s and remove function c. Also: \t->sum t<=n is (<=n).sum.
– nimi
Feb 12, 2017 at 10:31
• @flawr, good suggestion, thanks! Feb 12, 2017 at 11:00

# Perl 6, 163 158 bytes

{[grep $^n>=*.all.sum,map ->\p{|map {p[0,|$_ Z..^|$_,p]},(1..^p).combinations},$^s.permutations].&{.grep: .map(+*).min}.min({.map((*.sum-$s.sum/$_)**2).sum})}


Try it online!

### How it works

• map ->\p{|map {p[0,|$_ Z..^|$_,p]},(1..^p).combinations},$^s.permutations Generates all possible partitions of all permutations of the input array. • grep$^n>=*.all.sum,

Filters the ones where no raft is overbooked.

• .&{.grep: .map(+*).min}

Filters the ones where the number of rafts is minimal.

• .min({.map((*.sum-$s.sum/$_)**2).sum})}

Gets the first one with minimal ∑(nx-a)2.

-4 bytes thanks to @Pietu1998

• Do you need to do .abs if you square the result? Feb 12, 2017 at 14:39
• @Pietu1998: I don't, good catch.
– smls
Feb 12, 2017 at 15:05

# Python3, 224 bytes

def p(c):
if len(c)==1:yield[c];return
for s in p(c[1:]):
for n,u in enumerate(s):yield s[:n]+[[c[0]]+u]+s[n+1:]
yield[[c[0]]]+s
s=sum
r=lambda n,b:min(p(b),key=lambda c:s(abs(s(x)-s(b)/(s(b)//n+1))for x in c))


With testcases:

tc = [[6,[2,5]],[4,[1,1,1,1,1]],[6,[2,3,2]],[6,[2,3,2,3]],[6,[2,3,2,3,2]],[12,[10,8,6,4,2]],[6,[4,4,4]],[12,[12,7,6,6]]]
for case in tc:
print(str(case[0]).ljust(3),str(case[1]).ljust(16),"|",r(*case))


## How does it work?

The p function simply generates all partitions of a given list (all possible ways to divide it up into sublists). s=sum simply renames the sum function, so the last line does all the work.

r=lambda n,b:min(p(b),key=lambda c:s(abs(s(x)-s(b)/(s(b)//n+1))for x in c))
r=lambda n,b:                                                               Initialize the lambda
p(b)                                                       Calculate all possible raft arrangements
,key=lambda c:                                         Map the following lambda onto the list:
s(b)/(s(b)//n+1)              Calculate the ideal average amount of people per raft
abs(s(x)-                )             Calculate how close is the current raft
for x in c   For each raft in the partition
s(                                    )  Sum it (the sum is a score of how close to ideal the function is),
min(                                                         ) And find the lowest valued partition.


I'm certain that this can be golfed further, especially the p function, but I worked on this for hours already, so here you go.