Pierwsze puzzle ode mnie, chętnie otrzymałem sugestie dotyczące ulepszeń!
Scenariusz jest następujący; Pracujesz jako kierownik firmy raftingowej. Każdego ranka dostajesz listę rezerwacji i musisz posortować je na ładunki tratwowe. Napisz program lub funkcję w wybranym języku, który to zrobi za Ciebie.
Każda tratwa może pomieścić maksymalnie n
klientów, a każda rezerwacja dotyczy grupy od 1 do n
osób (włącznie). Należy przestrzegać następujących zasad;
Żadne grupy nie mogą być podzielone. Jeśli zarezerwowali razem, wszyscy muszą być na tej samej tratwie.
Liczba tratw musi zostać zminimalizowana.
Z zastrzeżeniem dwóch powyższych zasad, grupy muszą być rozmieszczone tak równo, jak to możliwe między tratwami.
Wejścia
Liczba n
(możesz założyć, że jest to dodatnia liczba całkowita) i wielkość wszystkich rezerwacji. Może to być tablica, lista lub podobna struktura danych, jeśli Twój język obsługuje takie rzeczy. Wszystkie będą dodatnimi liczbami całkowitymi od 1 do n
. Kolejność rezerwacji nie jest zdefiniowana ani nie jest ważna.
Wynik. Lista numerów rezerwacji pogrupowanych w ładunki tratwowe. Grupowanie musi być jednoznacznie wskazane, takie jak;
- lista lub tablica tablic.
- oddzielona przecinkami lista dla każdej tratwy. Nowa linia między każdą tratwą.
To, jak wdrożysz trzecią zasadę, zależy od ciebie, ale może to obejmować znalezienie średniego obłożenia tratwy i zminimalizowanie odchyleń od niej w jak największym stopniu. Oto kilka przypadków testowych.
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]
Obowiązują standardowe zasady, najkrótszy kod wygrywa. Baw się dobrze!
Edytowane; Sugerowany sposób zdefiniowania tak równo, jak to możliwe trzeciej zasady .
Po ustaleniu liczby tratw r
(zgodnie z drugą zasadą), średnie obłożenie a
można obliczyć, sumując rezerwacje i dzieląc r
. Dla każdej tratwy można znaleźć odchylenie od przeciętnego obłożenia za pomocą d(x) = abs(n(x)-a)
, gdzie n(x)
jest liczba osób w każdej tratwie i 1 <= x <= r
. Dla pewnej ciągłej funkcji o pojedynczej wartości f(y)
, która jest ściśle dodatnia i ma ściśle dodatnią pierwszą i nieujemną drugą pochodną dla wszystkich dodatnich y
, definiujemy wielkość nieujemną F
jako sumę wszystkich f(d(x)), 1 <= x <= r
. Każdy wybór przydziału tratw, który spełnia dwie pierwsze reguły i gdzie F
jest równy globalnemu minimum, spełni również trzecią zasadę.
źródło
g(y) = y
(drugiej pochodnej zero) lubg(y) = y²
(pierwszej obniżenia zera kiedyy = 0
).Odpowiedzi:
Perl 6 ,
163158 bajtówWypróbuj online!
Jak to działa
Generuje wszystkie możliwe partycje wszystkich permutacji tablicy wejściowej.
Filtruje te, w których żadna tratwa nie jest przepełniona.
Filtruje te, w których liczba tratw jest minimalna.
Pobiera pierwszy z minimalnym ∑ (n x -a) 2 .
-4 bajty dzięki @ Pietu1998
źródło
.abs
jeśli wyrównasz wynik?Haskell 226
228234268bajtówNaiwna odpowiedź w Haskell
Lub bez golfa
Z niektórymi przypadkami testowymi
Gdzie
test
dajeEdytować
Dzięki @flawr i @nimi za poradę.
p
Trochę zgnieciony .Ogoliłem kilka bajtów.
źródło
s=sum
, a następnie użyćs
zamiastsum
, a być może także zastąpićfst$ ...
z...!!0
.minimumBy(c s)
zhead.sortOn s
i usunąć funkcjęc
. Także:\t->sum t<=n
jest(<=n).sum
.Python3, 224 bajty
Z walizkami testowymi:
Jak to działa?
p
Funkcja po prostu generuje wszystkie partycje z danej listy (we wszystkich możliwych sposobów, aby podzielić go na podlist).s=sum
po prostu zmienia nazwę funkcji sumy, więc ostatni wiersz wykonuje całą pracę.Jestem pewien, że można dalej grać w golfa, zwłaszcza
p
funkcję, ale pracowałem nad tym już od wielu godzin, więc proszę bardzo.źródło