Podział na rosnące podsekwencje

16

Specyfikacja

Wyzwanie to jest łatwe do stwierdzenia: dane wejściowe to niepusta tablica nieujemnych liczb całkowitych, a Twoim zadaniem jest podzielenie ich na jak najmniej rosnących podsekwencji. Bardziej formalnie, jeśli tablica wejściowa jest A, to dane wyjściowe to tablica tablic Btakich, że:

  • Każda tablica Btworzy podział Ana rozłączne (niekoniecznie ciągłe) podsekwencje. Indukcyjnie oznacza to, że albo Bzawiera tablicę singletonów A, albo pierwszy element Bjest podsekwencją, Aa reszta tworzy partycję Az usuniętą podsekwencją.
  • Każda tablica Brośnie (niekoniecznie ściśle).
  • Liczba tablic Bjest minimalna.

Zarówno dane wejściowe, jak i wyjściowe mogą być pobierane w rodzimym formacie tablicowym Twojego języka. Pamiętaj, że może istnieć kilka poprawnych wyników.

Przykład

Rozważ tablicę wejściową A = [1,2,1,2,5,4,7,1]. Jednym z możliwych wyników jest B = [[1],[1,2,4,7],[1,2,5]]. Warunki partycji są widoczne na tym schemacie:

A    1 2 1 2 5 4 7 1
B[0]               1
B[1] 1 2       4 7
B[2]     1 2 5

Z każdą kolejną tablicą Brośnie. Wreszcie, Anie można podzielić na dwa rosnące podsekwencje, więc długość Bjest również minimalna. Dlatego jest to poprawny wynik.

Zasady i punktacja

Możesz napisać funkcję lub pełny program. Wygrywa najniższa liczba bajtów, a standardowe luki są niedozwolone. Nie ma ograniczenia czasowego, ale powinieneś ewakuować swoje rozwiązanie na wszystkich testowych przypadkach przed jego przesłaniem.

Przypadki testowe

Wyświetlane jest tylko jedno możliwe wyjście, ale może istnieć kilka prawidłowych opcji. W szczególności kolejność tablic w wyniku nie ma znaczenia (ale każda pojedyncza tablica powinna być w kolejności rosnącej).

[0] -> [[0]]
[3,5,8] -> [[3,5,8]]
[2,2,2,2] -> [[2,2,2,2]]
[1154,1012,976,845] -> [[845],[976],[1012],[1154]]
[6,32,1,2,34,8] -> [[1,2,8],[6,32,34]]
[1,12,1,12,1,13] -> [[1,1,1,13],[12,12]]
[6,4,6,13,18,0,3] -> [[0,3],[4,6,13,18],[6]]
[1,2,3,2,3,4,7,1] -> [[1,1],[2,2,3,4,7],[3]]
[0,9,2,7,4,5,6,3,8] -> [[0,2,3,8],[4,5,6],[7],[9]]
[7,1,17,15,17,2,15,1,6] -> [[1,1,6],[2,15],[7,15,17],[17]]
[4,12,2,10,15,2,2,19,16,12] -> [[2,2,2,12],[4,10,15,16],[12,19]]
[10,13,9,2,11,1,10,17,19,1] -> [[1,1],[2,10,17,19],[9,11],[10,13]]
[3,7,3,8,14,16,19,15,16,2] -> [[2],[3,3,8,14,15,16],[7,16,19]]
[15,5,13,13,15,9,4,2,2,17] -> [[2,2,17],[4],[5,9],[13,13,15],[15]]
Zgarb
źródło
3
Reguły wydają się zezwalać na takie rozwiązania [0,5,2,0] -> [[0,5],[0,2]](np. Recykling pierwszego zera zamiast korzystania z każdego z nich raz). Czy to celowe?
feersum
@feersum To nie było celowe, dobry haczyk. Przepisałem warunki B, mam nadzieję, że są teraz jaśniejsze.
Zgarb,

Odpowiedzi:

3

Haskell, 54 bajty

n#[]=[[n]]
n#(l:c)|[n]<=l=(n:l):c|1<2=l:n#c
foldr(#)[]

Przykład użycia: foldr(#)[] [4,12,2,10,15,2,2,19,16,12]->[[2,2,2,12],[4,10,15,16],[12,19]]

Jak to działa: przejrzyj listę danych wejściowych, zaczynając od prawego końca. Zbuduj listę wyjściową (list), przygotowując bieżący element ndo pierwszej podlisty, lgdzie njest mniejsza lub równa główce l. Jeśli nie ma, utwórz nową listę singletonów nna końcu listy wyników.

nimi
źródło
1

Pyth, 20 bajtów

fTu&ahfSI+THGHGQm[)Q

Wypróbuj online: pakiet demonstracyjny lub testowy

Chciwe podejście. Tworzę len(input)puste listy. Następnie iteruję każdą liczbę na liście inputwyboru pierwszej, która nadal jest sortowana po dodaniu liczby.

Wyjaśnienie:

fTu&ahfSI+THGHGQm[)Q   implicit: Q = input list
                m[)Q   create a list of empty lists and assign to G
  u            Q       iterate over all numbers H in input:
      f     G             filter for lists T in G, which satisfy:
         +TH                 create a new list out of T and H
       SI                    and check if it is sorted
     h                    take the first such list T
    a        H            and append H
   &          G           logical and with G (so that u doesn't overwrite G)
fT                     remove all empty lists
Jakube
źródło
@ThomasKwa Testowałem teraz całkiem sporo dodatkowych przypadków testowych. Nie udało się znaleźć ani jednego, co daje zły wynik. Jestem całkiem pewien, że Chciwy zawsze zwraca poprawny wynik.
Jakube,
@ThomasKwa Och, ten kontrprzykład dotyczy innej chciwej strategii (znajdź najdłużej rosnącą podsekwencję, usuń ją i powtórz). Nie mogę też znaleźć przypadku testowego, dla którego to przesłanie się nie powiedzie ...
Zgarb,
Cóż, myślę, że na spoczywającym na odbiorcy spoczywa ciężar udowodnienia, że ​​działa. Będę głosować, jeśli okaże się to prawdą.
lirtosiast