Pozwala zdefiniować proces zgniatania tablicy liczb. 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,3]
 ^
[5,2,2,3]
   ^
[5,2,2,3]
     ^
[5,4,3]
   ^
[5,4,3]
     ^

Ten sam element może być wielokrotnie zwinięty, na przykład [1,1,2]staje się [4]po zmiażdżeniu.

Nazwiemy tablicę niezniszczalną, gdy proces zmiażdżenia tej tablicy nie zmieni jej. Na przykład [1,2,3]wciąż jest [1,2,3]po zmiażdżeniu.

Twoim zadaniem jest wziąć tablicę i określić liczbę zmiażdżeń wymaganych, aby uczynić ją niemożliwą do zniszczenia. Potrzebujesz tylko liczb całkowitych z zakresu od 0 do 2 ³² -1

To jest golf golfowy, więc odpowiedzi będą liczone w bajtach, przy czym mniej bajtów będzie lepszych.

Przypadki testowe

[1] -> 0
[1,1] -> 1
[2,1,1] -> 2
[4,2,1,1] -> 3
[2,2,2,1,1] -> 3
[0,0,0,0] -> 1
[4,0,0,0,4] -> 1
[4,0,0,0,0,4] -> 1
[] -> 0

Zestaw x86 (64-bitowy), 66 65 bajtów

31 c0 57 59 56 51 56 5f 4d 31 c0 48 83 c6 08 48
83 e9 01 76 1b fc f2 48 a7 75 15 48 d1 67 f8 51
56 57 f3 48 a5 5f 5e 59 fd 48 a7 49 ff c0 eb e5
59 5e 4c 29 c1 48 ff c2 4d 85 c0 75 c7 48 ff c8
c3

Pomocne były instrukcje strunowe. Konieczność poprawiania pojedynczych błędów w środowisku 64-bitowym nie była.

W pełni skomentowany kod źródłowy:

.globl crush
crush:
/* return value */
xor %eax, %eax
/* save our length in rcx */
push %rdi
pop %rcx
pass:
/* save the start of the string and the length */
push %rsi
push %rcx
/* this is the loop */
/* first copy source to dest */
push %rsi
pop %rdi
/* and zero a variable to record the number of squashes we make this pass */
xor %r8, %r8
/* increment source, and decrement ecx */
add $8,%rsi
sub $1,%rcx
/* if ecx is zero or -1, we're done (we can't depend on the code to take care of this
automatically since dec will leave the zero flag set and cmpsq won't change it) */
jbe endpass
compare:
/* make sure we're going forward */
cld
/* compare our two values until we find two that are the same */
repne cmpsq
/* if we reach here, we either found the end of the string, or
we found two values that are the same. check the zero flag to
find out which */
jne endpass
/* okay, so we found two values that are the same. what we need
to do is double the previous value of the destination, and then
shift everything leftwards once */
shlq $1, -8(%rdi)
/* easiest way to shift leftwards is rep movsq, especially since
our ecx is already right. we just need to save it and the rsi/rdi */
push %rcx
push %rsi
push %rdi
rep movsq
pop %rdi
pop %rsi
pop %rcx
/* problem: edi and esi are now one farther than they should be,
since we can squash this dest with a different source. consequently
we need to put them back where they were. */
std
cmpsq
/* we don't need to put ecx back since the list is now one shorter
than it was. */
/* finally, mark that we made a squash */
inc %r8
/* okay, once we've reached this point, we should have:
 edi and esi: next two values to compare
 ecx: number of comparisons left
so we just jump back to our comparison operation */
jmp compare
endpass:
/* we reached the end of the string. retrieve our old ecx and esi */
pop %rcx
pop %rsi
/* rsi is accurate, but rcx is not. we need to subtract the number of squashes
that we made this pass. */
sub %r8, %rcx
/* record that we performed a pass */
inc %rax
/* if we did make any squashes, we need to perform another pass */
test %r8, %r8
jnz pass
/* we reached the end; we've made as many passes as we can.
decrement our pass counter since we counted one too many */
dec %rax
/* and finally return it */
ret

Mogę spróbować zrobić to w wersji 32-bitowej, choćby dla zabawy, ponieważ te prefiksy REX naprawdę mnie zabiły.

Edycja: zgoliłem jeden bajt, zastępując lodsq przez add,% rdx przez% rax i zwijając dwa cld w jeden.

Pyth , 22 bajty

tl.uu?&GqeGH+PGyH+GHN[

Sprawdź wszystkie przypadki testowe.

Haskell , 66 bajtów

f(a:b:x)|a==b=f$a+a:x|1>0=a:f(b:x)
f x=x
g x|f x==x=0|1>0=1+g(f x)

Wypróbuj online!

Wyjaśnienie

fto funkcja miażdżąca listę. Wykonuje zgniatanie, jak opisano w pytaniu. gto funkcja zliczająca liczbę zmiażdżeń. Jeśli f x==x, g x=0w przeciwnym razie g x=1+g(f x).

Paradoc (v0.2.10), 16 bajtów (CP-1252)

{—1\ε=k+x}]»}IL(

Wypróbuj online! / z nagłówkiem / stopką, które sprawdzają wszystkie przypadki testowe

Pobiera listę na stosie i daje liczbę na stosie.

Całkiem prosta implementacja, szczerze mówiąc. Miażdży listę, zaczynając od wartownika -1, zapętlając listę, popychając każdy element i dodając go do elementu pod nim, jeśli są równe. Na koniec odcinamy -1. Zmiażdżymy tylko równe liczby razem, a wszystkie liczby problemów są nieujemne, więc wartownik -1 nie wpłynie na proces kruszenia. Po wdrożeniu funkcji kruszenia wystarczy tylko policzyć iteracje do ustalonego punktu.

Wyjaśnienie:

{            }I  .. Iterate this block: repeatedly apply it until a fixed
                 .. point is reached, and collect all intermediate results
 —1              ..   Push -1 (note that that's an em dash)
   \             ..   Swap it under the current list of numbers
    ε    }       ..   Execute this block for each element in the list:
     =           ..     Check if it's equal to the next element on the stack...
      k          ..       ... while keeping (i.e. not popping either of) them
       +         ..     Add the top two elements of the stack...
        x        ..       ... that many times (so, do add them if they were
                 ..       equal, and don't add them if they weren't)
          ]      ..   Collect all elements pushed inside the block that
                 ..     we're iterating into a list
           »     ..   Tail: take all but the first element (gets rid of the -1)
              L  .. Compute the length of the number of intermediate results
               ( .. Subtract 1

Gdybyśmy mogli założyć, że dane wejściowe są niepuste, nie potrzebowalibyśmy wartownika i moglibyśmy ogolić 2 bajty: {(\ε=k+x}]}IL(

Kolejny fajny fakt: tracimy tylko 2 bajty, jeśli zmuszamy się do używania tylko ASCII: {1m\{=k+x}e]1>}IL(

JavaScript (ES6), 86 bajtów

f=a=>a.length>eval("for(i=0;a[i]>-1;)a[i]==a[++i]&&a.splice(--i,2,a[i]*2);i")?1+f(a):0

Nieoznakowany i wyjaśniony

f=a=>                           // function taking array a
    a.length > eval("           // if a.length > the result of the following...
        for(i=0; a[i]>-1;)      //   loop from 0 until the current value is undefined (which is not > -1)
            a[i] == a[++i] &&   //     if the current value equals the next one...
                a.splice(--i,   //       splice the array at the first index of the pair...
                    2,          //       by replacing 2 items...
                    a[i]*2);    //       with the current item * 2
                                //       this also decrements the counter, which means the current value is now the next
    i")                         //   return the counter, which is new a.length
        ? 1+f(a)                // if that was true, the array was crushed. add 1 and recur with the new array
        : 0                     // otherwise just return 0

Testy

f=a=>a.length>eval("for(i=0;a[i]>-1;)a[i]==a[++i]&&a.splice(--i,2,a[i]*2);i")?1+f(a):0

;[ [1], [1,1], [2,1,1], [4,2,1,1], [2,2,2,1,1], [0,0,0,0], [4,0,0,0,4], [4,0,0,0,0,4], []
].forEach(x=>console.log( JSON.stringify(x) + " -> " + f(x) ))

.as-console-wrapper{max-height:100%!important}

JavaScript, 67 bajtów

f=a=>a.map(a=>k[k[d-1]!=a?d++:(a*=z=2,d-1)]=a,k=d=[z=0])&&z&&f(k)+1

Wypróbuj online!

Brain-Flak , 144 bajty

([])({<{}>(<(([][()]){[{}]<({}[({})]<(())>){({}<{}>({})<>)((<>))}>{}{{}(<(({}){})>)}{}([][()])})>{()(<{}>)}{}{}<><([]){{}({}<>)<>([])}>{}<>)}<>)

Wypróbuj online!

Wyjaśnienie

([])                                                                 Push stack height (starts main loop if list nonempty)
     {                                                       }       Do while the last iteration involved at least one crush:
      <{}>                                                           Remove crush indicator
           <(...)>                                                   Do a crush iteration
                  {()(<{}>)}                                         Evaluate to 1 if list was changed
                            {}{}                                     Remove zeroes
                                <>                        <>         On other stack:
                                  <([]){{}        ([])}>{}           Do while stack is nonempty:
                                          ({}<>)<>                   Move to first stack
          (                                                 )        Push 1 if crush worked, 0 otherwise
    (                                                         <>)    Push sum of results on other stack and implicitly print

Funkcja zgniatania ocenia liczbę par elementów, które zostały zmiażdżone razem:

([][()]){[{}]                                                            ([][()])}    Do while stack height isn't 1:
              ({}[({})]      )                                                        Calculate difference between top two elements
                       <(())>                                                         Push a 1 below difference
                              {                    }                                  If difference was nonzero (don't crush this pair)
                               ({}    ({})<>)                                         Reconstruct top element and place on other stack
                                  <{}>       ((<>))                                   Push zeros to exit this conditional and skip next
             <                                      >{}                               Evaluate as zero
                                                       {              }{}             If difference was zero (crush this pair):
                                                        {}                            Evaluate as previously pushed 1
                                                          (<(({}){})>)                Double top of stack

Java 8, 120 bajtów

Lambda od List<Long>do Integer. Lista danych wejściowych musi zostać zaimplementowana remove(int)(np ArrayList.). Przypisz do Function<List<Long>, Integer>.

l->{int c=-1,i,f=1;for(;f>0;c++)for(f=i=0;++i<l.size();)if(l.get(i)-l.get(i-1)==0)l.set(i-=f=1,2*l.remove(i));return c;}

Wypróbuj online

Niegolfowana lambda

l -> {
    int
        c = -1,
        i,
        f = 1
    ;
    for (; f > 0; c++)
        for (f = i = 0; ++i < l.size(); )
            if (l.get(i) - l.get(i - 1) == 0)
                l.set(i -= f = 1, 2 * l.remove(i));
    return c;
}

czlicza do tej pory liczbę zmiażdżeń, ijest indeksem na liście i fwskazuje, czy kontynuować miażdżenie listy po zakończeniu iteracji. Wewnątrz pętli porównywana jest każda sąsiednia para. ijest bezwarunkowo zwiększany, więc jeśli element zostanie usunięty przez zmiażdżenie, inajpierw jest zmniejszany, aby anulować przyrost. Poprzedni element zostanie usunięty z listy.

Podziękowanie

• Bugfix dzięki Olivier Grégoire: test równości w pudełku

Perl 5 , 96 bajtów

94 kod, 2 dla -pa

do{$\++;$l=@F;for($i=0;++$i<@F;){$F[$i]==$F[$i-1]&&splice@F,$i,2,$F[$i--]*2}}while$l!=@F}{$\--

Wypróbuj online!

JavaScript (ES6), 70 bajtów

f=(a,j=m=0,t=[])=>a.map(e=>t[e==t[j-1]?(e*=m=2,j-1):j++]=e)&&m&&1+f(t)

Wyjaśnienie:

f=(
  a,                  //the input
  j=m=0,              //j is the index into t; m starts out falsey
  t=[]                //t will hold the crushed array
)=>
  a.map(e=>           //for each element in the array
    t[e==t[j-1] ?     //if the element repeats:
      (e*=m=2,        //... multiply it by two, set m to truthy,
       j-1) :         //... and index the previous element of t.
      j++             //else append to t, and increment its index.
    ]=e               //set this index of t to the current value of e
  ) &&                //map is always truthy
  m &&                //if m is falsey, return 0
  1+f(t)              //else return 1 plus the recurse on t

Przypadki testowe:

f=(a,j=m=0,t=[])=>a.map(e=>t[e==t[j-1]?(e*=m=2,j-1):j++]=e)&&m&&1+f(t)

console.log(f([1])) // 0
console.log(f([1,1])) // 1
console.log(f([2,1,1])) // 2
console.log(f([4,2,1,1])) // 3
console.log(f([2,2,2,1,1])) // 3
console.log(f([0,0,0,0])) // 1
console.log(f([4,0,0,0,4])) // 1
console.log(f([4,0,0,0,0,4])) // 1
console.log(f([])) // 0

Python 2 , 112 110 108 107 105 100 bajtów

Edycja: zapisano 2 bajty, usuwając orinstrukcję return

Edycja: zapisano 2 bajty ijako indeks drugiego z dwóch elementów, które mają być dostępne

Edycja: zapisano 1 bajt dzięki @ Mr.Xcoder

Edycja: zapisano 7 bajtów dzięki @jferard

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

Wypróbuj online!

JavaScript (ES6), 83 bajty

f=([x,y,...a],b=[],c)=>1/x?x==y?f([x+y,...a],b,1):f([y,...a],[...b,x],c):c?1+f(b):0

Objaśnienie: Elementy są rekurencyjnie wyodrębniane z oryginalnej tablicy i dołączane są unikalne wartości, ba while cjest flagą wskazującą, czy tablica została pomyślnie zgnieciona.

J, 54 bajty

[:<:@#[:".@":@(,`(+:@[,}.@])@.({.@]=[))/^:a:@".@":_,|.

Wypróbuj online!

Pod żadnym względem nie mój najlepszy golf. Z pewnością musi istnieć lepszy sposób konwersji listy z jednym elementem na atom.

Wyjaśnienie

crush =. ,`(+:@[ , }.@])@.({.@] = [)/
times =. <:@# [: ".@":@crush^:a:@".@": _ , |.

zmiażdżyć

To raz zmiażdży tablicę. Trzeba podać tablicę w odwrotnej kolejności, ponieważ wstawka J działa od prawej do lewej (czego nauczyłem się dzisiaj). Nie ma to szczególnego znaczenia, ponieważ wszystko, czego potrzebujemy, to ile razy możemy zmiażdżyć tablicę.

,`(+:@[ , }.@])@.({.@] = [)/
                           /  Fold/reduce from the right
                  {.@] = [    Head of the running array equals the left argument?
   +:@[ ,                     If so, prepend double the argument to 
          }.@]                the array minus its head
,                             Else, prepend the left argument.

czasy

Jest to dość proste: zastosuj crush do tablicy, dopóki nasz wynik nie zbiegnie się, ale jest kilka problemów, z którymi musiałem sobie poradzić, uzyskując znacznie więcej kodu, niż się spodziewałem.

Po pierwsze, gdy zgniatanie ogranicza się do jednego elementu, element ten faktycznie znajduje się na liście jednego elementu (tzn. Nie jest anatomiczny), więc funkcja jest ponownie stosowana, co powoduje przeliczenie. Aby to naprawić, użyłem hacka, który wymyśliłem, aby zredukować listę pojedynczych elementów do atomu, który jest ".@":(przekonwertować na ciąg, a następnie ocenić).

Po drugie, crushbłędy na pustej liście. Myślę , że możesz zdefiniować, jak funkcja powinna zachowywać się po otrzymaniu pustych danych wejściowych za pomocą insert ( /), ale nie mogłem znaleźć niczego po pobieżnym spojrzeniu, więc używam innego obejścia. To obejście polega na dodawaniu _(nieskończoności) do listy, ponieważ nigdy nie wpłynie to na liczbę zmiażdżenia tablicy ( _ > 2^64). Jednakże , skutkuje to jedną listę składającą się z elementów _, gdy ze względu na pustą listę, więc trzeba przekonwertować do atomu znowu przed zgnieceniem.

<:@# [: ".@":@crush^:a:@".@": _ , |.
                                  |.  Reverse input
                              _ ,     Prepend infinity
                        ".@":         Convert single-element list to atom
              crush                   Crush the list and after
        ".@":                         Convert single-element list to atom 
                   ^:a:               until it converges, storing each 
                                      iteration in an array
<:@#                                  Length of the resulting list minus 1

Galaretka , 21 bajtów

ṪḤ,⁼?⁹⁸;µ/Ḋ$¹L’$?ÐĿL’

Wypróbuj online!

R , 142 bajty

f=function(l,r=l,k=0,T=1)"if"(sum(l|1)<2,k,{while(T<sum(r|1))"if"(r[T]-r[T+1],T<-T+1,{r<-r[-T]
r[T]<-2*r[T]})
"if"(all(r==l),k,f(r,r,k+1,1))})

Przerażające, jestem pewien, że jest bardziej sprytny sposób.

Liczby całkowite R są w rzeczywistości co najwyżej wszystkie 2^31-1.

Wypróbuj online!