Wcześniej zdefiniowałem proces zgniatania tablicy
W sympatii czytamy tablicę od lewej do prawej. Jeśli w pewnym momencie napotkamy dwa takie same elementy w rzędzie, usuwamy pierwszy i podwajamy drugi.
Na przykład tutaj jest proces zgniatania następującej tablicy
[5,2,2,4]
^
[5,2,2,4]
^
[5,2,2,4]
^
[5,4,4]
^
[5,4,4]
^
[5,8]
^
Pamiętaj, że ten sam element można zwinąć wiele razy. W przykładzie 2,2,4
został zawalony 8
w jednym przejściu.
Teraz miażdżenie tablic jest łatwe, a trudne jest ich niszczenie. Twoim zadaniem jest pobranie tablicy dodatnich liczb całkowitych jako danych wejściowych i wyprowadzenie największej tablicy, która może tworzyć dane wejściowe po wielokrotnym zmiażdżeniu. Na przykład układ [4]
jest tworzony przez kruszenie, [2,2]
które z kolei jest tworzone przez kruszenie [1,1,1,1]
. Ponieważ nie możemy mieć wartości niecałkowitych, [1,1,1,1]
nie można już dalej rozwalać, dlatego nasza odpowiedź jest taka.
Nigdy nie otrzymasz znaku 0
w tablicy wejściowej, ponieważ takie tablice można rozszerzać w nieskończoność. Nigdy też nie otrzymasz skrzynki z dwoma takimi samymi liczbami nieparzystymi obok siebie, takie skrzynki nie mogą być wynikiem zmiażdżenia.
To jest golf golfowy, więc odpowiedzi będą oceniane z wielkością ich źródła mierzoną w bajtach, przy czym mniej bajtów jest lepszych.
Zanim zaczniesz udzielać odpowiedzi, chcę tylko powiedzieć, że to wyzwanie jest znacznie trudniejsze, niż się wydaje. Sprawdź swoją intuicję i upewnij się, że Twoja odpowiedź przeszła wszystkie przypadki testowe.
Przypadki testowe
[] -> []
[5] -> [5]
[6] -> [3,3]
[8] -> [1,1,1,1,1,1,1,1]
[4,8] -> [1,1,1,1,1,1,1,1,1,1,2]
[2,8] -> [1, 1, 1, 1, 2, 1, 1, 1, 1]
[4,4] -> [1,1,1,1,1,1,1,1]
źródło
[1,1,1,1,1,1,1,1,1,1,2]
produkować[4, 8]
zamiast[8, 4]
? powinno to być[1,>1,1,1,1,1,1,1,1,1,2]
,[2,1,>1,1,1,1,1,1,1,2]
,[2,>2,1,1,1,1,1,1,2]
,[4,1,>1,1,1,1,1,2]
,[4,2,1,>1,1,1,2]
,[4,2,>2,1,1,2]
,[4,>4,1,1,2]
,[8,1,>1,2]
,[8,2,>2]
,[8,4]
?[1,>1,1,1,1,1,1,1,1,1,2]
,[2,>1,1,1,1,1,1,1,1,2]
,[2,1,>1,1,1,1,1,1,1,2]
,[2,2,>1,1,1,1,1,1,2]
,[2,2,1,>1,1,1,1,1,2]
,[2,2,2,>1,1,1,1,2]
,[2,2,2,1,>1,1,1,2]
,[2,2,2,2,>1,1,2]
,[2,2,2,2,1,>1,2]
,[2,2,2,2,2,>2]
,[2,2,2,2,4>]
, drugi przebieg:[2,>2,2,2,4]
,[4,>2,2,4]
,[4,2,>2,4]
,[4,4,>4]
,[4,8>]
. Mam nadzieję, że to wyjaśnia. Jeśli chcesz, aby jakiś kod spojrzał na poprzednie pytanie, ma odpowiedzi, które implementują funkcję kruszenia.[4, 4]
powinien zostać usunięty, ponieważ nigdy nie możemy uzyskać tej tablicy po sekwencji zgniatania =>, ponieważ zakończy się to[8]
Odpowiedzi:
JavaScript (Node.js) ,
237221213186 bajtówWypróbuj online!
Algorytm oblicza optymalne rozciągnięte tablice, rozciągając każdą liczbę do maksimum, a następnie, jeśli to konieczne, miażdży parę liczb we właściwym miejscu, skutecznie tworząc „blokadę zgniatania”, przerywając sekwencję zgniatania z poprzedniej liczby.
Na przykład:
[1, 1, 1, 1, 1, 1]
daje[4,2]
raz zmiażdżony, ale[1, 1, 1, 1, 2]
skutkuje[2, 4]
Wyzwanie polega na ustaleniu, gdzie dokładnie należy umieścić blokadę zgniatania, aby zmiażdżenie powstałej tablicy dało właściwy wynik:
[2, 4]
wymaga blokowania zgniatanie (rozciągnięty liczba1
, powtarzające się i[1, 1]
jest krótsza niż[1,1,1,1]
), ale[4, 2]
i[2, 6]
nie wymagają jednegon
poprzednią rozciągniętą sekwencję i jeśli powyższy warunek zostanie zweryfikowany, to bieżąca sekwencja jest powtórzeniemn
sekwencji. Aby przerwać sekwencję zgniatania poprzedniego numeru, musimy umieścić blokadę zgniatania na końcu drugiejn
sekwencji bieżącej liczby, aby ją rozciągnąć. Przykład:[2, 8] => [(1, 1)=n, (1, 1) + (2) + (1, 1) + ...]
lub[4, 8] => [(1, 1, 1, 1)=n, (1, 1, 1, 1) + (1, 1, 2) + ...]
źródło
Galaretka , 42 bajty
Wypróbuj online!
Pełny program Niezwykle nieefektywny, ale działa.
źródło
Python 2 ,
230228226 bajtówDziała poprzez iterowanie wszystkich możliwych list z taką samą sumą jak wejściowa. Usunięcie tych, które nie są równe tablicy wejściowej w stanie zgniatania, wybierając najdłuższy.
Edytuj: -2 bajty, usuwając
if
funkcję głównąEdytuj: -2 bajty, usuwając dwa niepotrzebne nawiasy kwadratowe
Wypróbuj online!
Wyjaśnienie
Główna funkcja, odpowiedzialna za znalezienie wszystkich możliwych rozwiązań i wybór najdłuższego
Funkcja zmiażdżenia, która sprawdza, czy y jest równe jednemu ze zmiażdżeń.
Wygeneruj wszystkie możliwe permutacje z podaną sumą
źródło
05AB1E ,
4137 bajtówWypróbuj online!
Port mojego rozwiązania JavaScript.
Objaśnienia:
źródło