Primer acertijo mío, ¡sugerencias de mejora recibidas con gusto!

El escenario es; Trabajas como gerente de una empresa de rafting en aguas bravas. Todas las mañanas, se le da una lista de reservas, y debe clasificarlas en cargas de balsa. Escriba un programa o función en el idioma elegido que haga esto por usted.

Cada balsa tiene un máximo de nclientes, y cada reserva es para un grupo de entre 1 y npersonas (inclusive). Deben observarse las siguientes reglas;

• No se pueden dividir grupos. Si reservaron juntos, todos deben estar en la misma balsa.

• Se debe minimizar el número de balsas.

• Sujeto a las dos reglas anteriores, los grupos deben distribuirse lo más equitativamente posible entre las balsas.

Entradas. El número n(puede suponer que es un número entero positivo) y el tamaño de todas las reservas. Esto puede ser una matriz, una lista o una estructura de datos similar si su idioma admite tales cosas. Todos estos serán enteros positivos entre 1 y n. El orden de las reservas no está definido, ni es importante.

Salida. Una lista de los números de reserva, agrupados en cargas de balsa. La agrupación debe indicarse sin ambigüedades, como;

• una lista o matriz de matrices.
• una lista separada por comas para cada balsa. Nueva línea entre cada balsa.

La forma en que implemente la tercera regla depende de usted, pero esto podría implicar encontrar la ocupación promedio de la balsa y minimizar las desviaciones de ella tanto como sea posible. Aquí hay algunos casos de prueba.

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]

Se aplican reglas estándar, gana el código más corto. ¡Que te diviertas!

Editado; Una forma sugerida de definir lo más equitativamente posible para la tercera regla.

Una vez que rse ha determinado el número de balsas (sujeto a la segunda regla), la ocupación promedio ase puede calcular sumando las reservas y dividiendo por r. Para cada balsa, se puede encontrar la desviación de la ocupación promedio d(x) = abs(n(x)-a), donde n(x)es el número de personas en cada balsa y 1 <= x <= r. Para alguna función continua de un solo valor f(y), que es estrictamente positiva y tiene una primera derivada estrictamente positiva y una segunda derivada no negativa para todas las positivas y, definimos una cantidad no negativa F, como la suma de todas las f(d(x)), 1 <= x <= r. Cualquier elección de asignación de balsa que satisfaga las dos primeras reglas, y donde Fsea ​​igual al mínimo global, también satisfará la tercera regla.

Perl 6 , 163158 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})}

Pruébalo en línea!

Cómo funciona

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

  Genera todas las particiones posibles de todas las permutaciones de la matriz de entrada.

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

  Filtra los que no tienen exceso de balsa.

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

  Filtra aquellos donde el número de balsas es mínimo.

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

  Obtiene el primero con mínimo ∑ (n _x -a) ² .

-4 bytes gracias a @ Pietu1998

Haskell 226 228 234 268 bytes

Respuesta ingenua en 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

O sin golf

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

Con algunos casos de prueba

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

Donde testrinde

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

Editar

Gracias a @flawr y @nimi por sus consejos.

Aplastado pun poco.

Afeitado un par de bytes.

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

Con estuches de prueba:

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

¿Como funciona?

La pfunción simplemente genera todas las particiones de una lista dada (todas las formas posibles de dividirla en sublistas). s=sumsimplemente cambia el nombre de la función de suma, por lo que la última línea hace todo el trabajo.

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.

Estoy seguro de que esto se puede jugar más, especialmente la pfunción, pero ya trabajé en esto durante horas, así que aquí tienes.