W tym wyzwaniu musisz podzielić listę, gdzie partycje mają maksymalny rozmiar, minimalny rozmiar i preferowany rozmiar. Będę używał notacji (min,pref,max)
do wskazania rozmiarów w tym wyzwaniu.
Dla tych, którzy nie znają partycjonowania, poniższa lista została podzielona na części 3:
[0..9] -> [[0,1,2],[3,4,5],[6,7,8]]
Gdy lista nie jest podzielny, trzeba partycje być tak blisko do preferowanej wielkości, jak to możliwe: [0..10], (2,4,5) -> [[0,1,2,3],[4,5,6],[7,8,9]]
. Podział ten jest korzystniejszy niż [[0,1,2,3],[4,5,6,7],[8,9]]
, chociaż ten drugi ma większą preferowaną długość. Formalnie musimy zminimalizować sumę (partitionLength-preferredSize)^2
dla każdej partycji.
Kolejność długości partycji nie ma znaczenia: Dla [0..5], (2,3,3)
albo [[0,1,2],[3,4]]
albo [[0,1],[2,3,4]]
działa. Jeśli partycja jest możliwe powrót pustą tablicę: [0..7], (4,4,5) -> []
.
Możesz założyć, że 1<=min<=pref<=max
i przekazana do ciebie tablica jest niepustą tablicą liczb całkowitych. Tablica zawsze będzie pierwszym argumentem. Możesz zaakceptować min, max i pref w dowolnej kolejności i jako krotkę lub jako osobne argumenty.
Twój program musi działać w ciągu kilku sekund. Zasadniczo, iterowanie przez każdy możliwy rozmiar partycji w granicach jest niedozwolone.
Przypadki testowe:
[1], (1,3,4) -> [[1]]
[100], (1,2,3) -> [[100]]
[1,2], (1,1,2) -> [[1],[2]]
[1,2], (1,2,2) -> [[1,2]]
[1,2], (1,3,3) -> [[1,2]]
[1,2,3], (1,2,3) -> [[1,2],[3]] or [[1,2,3]]
[1,2,3,4], (1,3,4) -> [[1,2,3,4]]
[1,2,3,4,5], (3,3,4) -> []
[1,2,3,4,5], (2,2,2) -> []
[1,2,3,4,5], (3,3,5) -> [[1,2,3,4,5]]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49], (2,6,6) -> [[1,2,3,4,5,6],[7,8,9,10,11,12],[13,14,15,16,17,18],[19,20,21,22,23,24],[25,26,27,28,29],[30,31,32,33,34],[35,36,37,38,39],[40,41,42,43,44],[45,46,47,48,49]]
To jest golf golfowy , więc celuj w jak najmniejszą liczbę bajtów w swoim ulubionym języku!
źródło
[a..b]
zawieraa
i wykluczab
, prawda?Odpowiedzi:
Haskell, 152
Na każdej partycji, jeśli istnieją dwie listy o długościach różniących się o dwie lub więcej, zawsze korzystne będzie zmniejszenie większej listy i powiększenie mniejszej listy. dlatego musimy wziąć pod uwagę tylko partycje o tylko dwóch rozmiarach list, co upraszcza obliczenia.
następnie program działa na wszystkich możliwych listach na partycji. biorąc pod uwagę liczbę list w partycji, wynik jest jednoznacznie określony. program oblicza pasującą partycję i jej wynik.
następnie znajduje ogólne minimum i zwraca je.
Zastosowanie: input like
f [1,2,3,4,5] 1 3 4
(f
jest funkcją, która rozwiązuje wyzwanie)Chociaż możliwe jest obliczenie najlepszej opcji całkowicie numerycznie, a dopiero potem odpowiednie podzielenie listy na partycje, zajęło to zbyt wiele bajtów. jednak moja ostatnia wersja tego podejścia to:
źródło
CJam, 70
Wypróbuj online
Kod wyszukuje optymalną sekwencję rozmiarów partycji w oparciu o rozmiar listy, używając programowania dynamicznego (poprzez zapamiętaną rekurencję), a następnie przechodzi do podziału listy na partycje.
źródło