Erstes Puzzle von mir, Verbesserungsvorschläge gerne erhalten!

Das Szenario ist; Sie arbeiten als Manager für eine Wildwasser-Rafting-Firma. Jeden Morgen erhalten Sie eine Liste mit Buchungen, die Sie in Floßladungen sortieren müssen. Schreiben Sie ein Programm oder eine Funktion in der von Ihnen gewählten Sprache, die dies für Sie erledigt.

Jedes Floß hat ein Maximum an nKunden und jede Buchung ist für eine Gruppe von 1 bisn einschließlich Personen. Die folgenden Regeln müssen beachtet werden;

• Es dürfen keine Gruppen aufgeteilt werden. Wenn sie zusammen gebucht haben, müssen sie sich alle im selben Floß befinden.

• Die Anzahl der Flöße muss minimiert werden.

• Vorbehaltlich der beiden vorhergehenden Regeln müssen die Gruppen so gleichmäßig wie möglich auf die Flöße verteilt werden.

Eingänge. Die Nummern (Sie können davon ausgehen, dass dies eine positive Ganzzahl ist) und die Größe aller Buchungen. Dies kann ein Array, eine Liste oder eine ähnliche Datenstruktur sein, wenn Ihre Sprache solche Dinge unterstützt. All dies sind positive ganze Zahlen zwischen 1 und n. Die Reihenfolge der Buchungen ist nicht festgelegt und auch nicht wichtig.

Ausgabe. Eine Liste der Buchungsnummern, gruppiert nach Floßladungen. Die Gruppierung muss eindeutig angegeben werden, wie z.

• eine Liste oder ein Array von Arrays.
• eine durch Kommas getrennte Liste für jedes Floß. Newline zwischen jedem Floß.

Wie Sie die dritte Regel implementieren, bleibt Ihnen überlassen. Dies kann jedoch bedeuten, dass Sie die durchschnittliche Floßbelegung ermitteln und Abweichungen davon so gering wie möglich halten. Hier sind einige Testfälle.

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]

Es gelten Standardregeln, der kürzeste Code gewinnt. Habe Spaß!

Bearbeitet; Ein vorgeschlagener Weg, um so gleich wie möglich zu definieren die dritte Regel .

Nachdem die Anzahl der Flöße rbestimmt wurde (vorbehaltlich der zweiten Regel), kann die durchschnittliche Belegung aberechnet werden, indem die Buchungen summiert und durch dividiert werden r. Für jedes Floß kann die Abweichung von der durchschnittlichen Belegung findet Verwendung d(x) = abs(n(x)-a), wo n(x)die Zahl der Menschen in jedem Floß ist und 1 <= x <= r. Für eine kontinuierliche, einwertige Funktion f(y), die streng positiv ist und eine streng positive erste und eine nicht negative zweite Ableitung für alle positiven hat y, definieren wir eine nicht negative Größe Fals die Summe aller f(d(x)), 1 <= x <= r. Jede Wahl der Floßzuweisung, die die ersten beiden Regeln erfüllt und bei Fder das globale Minimum gleich ist, erfüllt auch die dritte Regel.

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})}

Probieren Sie es online!

Wie es funktioniert

• map ->\p{|map {p[0,|$_ Z..^|$_,p]},(1..^p).combinations},$^s.permutations

  Erzeugt alle möglichen Partitionen aller Permutationen des Eingabearrays.

• grep $^n>=*.all.sum,

  Filtert diejenigen, bei denen kein Floß überbucht ist.

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

  Filtert diejenigen, bei denen die Anzahl der Flöße minimal ist.

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

  Erhält das erste mit minimalem ∑ (n _x -a) ² .

-4 Bytes dank @ Pietu1998

Haskell 226 228 234 268 Bytes

Naive Antwort in Haskell

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

Oder 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

Mit einigen Testfällen

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

Woher test Erträge

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]]

Bearbeiten

Vielen Dank an @flawr und @nimi für den Rat.

Gequetscht p .

Ein paar Bytes abgeschabt.

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))

Mit Testfällen:

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))

Wie funktioniert es?

Die pFunktion generiert einfach alle Partitionen einer bestimmten Liste (alle Möglichkeiten, sie in Unterlisten aufzuteilen). s=sumbenennt einfach die Summenfunktion um, sodass die letzte Zeile die ganze Arbeit erledigt.

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.

Ich bin mir sicher, dass dies weiter verbessert werden kann, insbesondere die pFunktion, aber ich habe bereits stundenlang daran gearbeitet, also los geht's.