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,4został zawalony 8w 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 0w 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]

JavaScript (Node.js) , 237 221 213 186 bajtów

f=a=>a.map(b=>{for(i=1;~b%2;b/=2)i*=2;return Array(i).fill(b)}).reduce((t,c,i,s)=>{b=c.slice();if(i)r=2*s[--i].length,b.length>=r&&b[0]==s[i][0]?b[r-2]+=b.pop():b;return t.concat(b)},[])

Wypró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:

• Blokowanie zgniatania należy umieścić tylko wtedy, gdy poprzednia liczba rozciągnięta jest równa bieżącej i jeśli bieżąca sekwencja rozciągnięta jest większa niż poprzednia. Na przykład, [2, 4]wymaga blokowania zgniatanie (rozciągnięty liczba 1, powtarzające się i [1, 1]jest krótsza niż [1,1,1,1]), ale [4, 2]i [2, 6]nie wymagają jednego
• jeśli wywołamy npoprzednią rozciągniętą sekwencję i jeśli powyższy warunek zostanie zweryfikowany, to bieżąca sekwencja jest powtórzeniem nsekwencji. Aby przerwać sekwencję zgniatania poprzedniego numeru, musimy umieścić blokadę zgniatania na końcu drugiej nsekwencji 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) + ...]

Galaretka , 42 bajty

ṪḤ,⁼?⁹⁸;µ/Ḋ$¹L’$?ÐĿċ³
ṗЀ⁸ẎS⁼¥Ðfµ€ŒpẎ€ÇÐfṪ

Wypróbuj online!

Pełny program Niezwykle nieefektywny, ale działa.

Python 2 , 230 228 226 bajtów

Dział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 iffunkcję główną

Edytuj: -2 bajty, usuwając dwa niepotrzebne nawiasy kwadratowe

lambda x:max((c(z[:],x),len(z),z)for z in b(sum(x)))[2]
def c(x,y):
 i=e=1
 while x[i:]:
	if x[~-i]==x[i]:del x[i];i-=1;x[i]*=2;e=2
	i+=1
 return x==y or~-e and c(x,y)
b=lambda s:[z+[-~i]for i in range(s)for z in b(s+~i)]+[[]]

Wypróbuj online!

Wyjaśnienie

Główna funkcja, odpowiedzialna za znalezienie wszystkich możliwych rozwiązań i wybór najdłuższego

lambda x:max((c(z[:],x),len(z),z)for z in b(sum(x)))[2]

Funkcja zmiażdżenia, która sprawdza, czy y jest równe jednemu ze zmiażdżeń.

def c(x,y):
 i=e=1
 while x[i:]:
	if x[~-i]==x[i]:del x[i];i-=1;x[i]*=2;e=2
	i+=1
 return x==y or~-e and c(x,y)

Wygeneruj wszystkie możliwe permutacje z podaną sumą

b=lambda s:[z+[-~i]for i in range(s)for z in b(s+~i)]+[[]]

05AB1E , 41 37 bajtów

vy[DÉ#2÷]DYQX©NoDU‹&sDV¸X∍sić·®·Íǝ}»,

Wypróbuj online!

Port mojego rozwiązania JavaScript.

Objaśnienia:

vy                   for each member of the list
[DÉ#2÷]              divide by 2 until odd: stack = stretched value, N = iterations
DYQ                  stetched value equal to the previous one?
X©NoDU‹              previous size < current one? (+store the new size in X)
&                    AND on the 2 previous tests
sDV¸X∍s              build a list of the new stretched value repeated X times
                      (+store the new stetched value in Y)
ić·®·Íǝ}             if the previous tests are true:
                       reduce the result list size by 1
                       multiply by 2 the number at the crush block position
»,                   join by newline + print the list