Siła grawitacyjna jest siłą, która przyciąga dowolne dwa obiekty masą. W tym wyzwaniu naszymi obiektami będą Liczby, a ich masa będzie ich wartością. Aby to zrobić, nie dbamy o siłę siły, ale o jej kierunek.

Wyobraź sobie ten zestaw liczb

[1 6 9 4 6 9 7 6 4 4 9 8 7]

Każdy z nich tworzy siłę między sobą a sąsiednimi liczbami. W niektórych warunkach spowoduje to przyciągnięcie (przesunięcie) innej liczby w kierunku liczby. Gdy liczba jest większa niż sąsiednia, przyciąga ją. Rzućmy okiem na nasz poprzedni przykład:

[1 → 6 → 9 ← 4 6 → 9 ← 7 ← 6 ← 4 4 → 9 ← 8 ← 7]

Liczba 1nie jest wystarczająco duża, aby ją przenieść 6, ale liczba 6jest itd. Zasadniczo liczby są przenoszone do największej liczby sąsiedniej (również większej niż sama liczba). Jeśli obie sąsiednie liczby są równe, nie jest to przyciągane. Dzieje się tak również wtedy, gdy liczba i sąsiednie są równe.

Ma to jedynie na celu pokazanie atrakcji, ale co się potem stanie? Liczby, które kolidują z powodu przyciągania, są sumowane:

[20 32 28]

Zasadniczo więc wyzwaniem jest, biorąc pod uwagę zestaw liczb, wyprowadzić wynik przyciągniętego zestawu liczb.

Przykład 1

Input  => [10 15 20 10 20 10 10]
          [10 → 15 → 20 10 20 ← 10 10]
Output => [45 10 30 10]

Przykład 2

Input  => [9 9 9 9 8 1 8]
          [9 9 9 9 ← 8 1 8]
Output => [9 9 9 17 1 8]

Przykład 3

Input  => [1 6 9 4 6 9 7 6 4 4 9 8 7]
          [1 → 6 → 9 ← 4 6 → 9 ← 7 ← 6 ← 4 4 → 9 ← 8 ← 7]
Output => [20 32 28]

Przykład 4

Input  => [1 2 3 2 1]
          [1 → 2 → 3 ← 2 ← 1]
Output => [9]

Przykład 5

Input  => [1]
Output => [1]

Przykład 6

Input  => [1 1]
Output => [1 1]

Przykład 7

Input  => [2 1 4]
Output => [2 5]

Notatki

• Atrakcja dzieje się tylko raz
• Liczby nie są przyciągane do nieprzylegających liczb
• Zbiór liczb będzie zawierał wyłącznie liczby całkowite dodatnie

JavaScript (ES6),  106 104  100 bajtów

Zaoszczędzono 2 bajty dzięki @Shaggy

a=>a.filter(n=>n,[...a].map((v,i)=>a[a[p>v&(n=~~a[i+1])<p?k:i+(k=i,n>v&p<n)]+=x=a[i],p=v,i]-=x,p=0))

Wypróbuj online!

Skomentował

Najpierw aktualizujemy oryginalną tablicę wejściową, a[]wykonując iterację na jej kopii. Podczas tego kroku wszystkie wartości „przyciągane” przez inne są ustawiane na .$0$

Ponieważ tablica jest analizowana od lewej do prawej, możemy po prostu dodać do ilekroć wartość jest przyciągana przez jej prawego sąsiada.$a_i$$a_{i+1}$

Przykład: zamienia się w a następnie .$4\rightarrow5\rightarrow6$$[0,\color{red}9,6]$$[0,0,\color{red}{15}]$

Ale kiedy lewy sąsiad przyciąga kilka wartości z rzędu, musimy dodać do pierwszego atraktora tej sekwencji (z ) zamiast po prostu .$a_i$$a_k$$k<i$$a_{i-1}$

Przykład: zamienia się w a następnie .$6\leftarrow5\leftarrow4$$[\color{red}{11},0,4]$$[\color{red}{15},0,0]$

[...a]                 // create a copy of a[]
.map((v, i) =>         // for each value v in a[] at position i:
  a[                   //   this statement updates a[i]:
    a[                 //     this statement updates either a[i] or an adjacent value:
      p > v &          //       if the previous value p is greater than v
      (n = ~~a[i + 1]) //       and the next value n
      < p ?            //       is less than p (attraction to the left):
        k              //         use k (k is initially undefined, but this code cannot
                       //         be triggered during the first iteration)
      :                //       else:
        i + (          //         use either i or i + 1:
          k = i,       //           set k to i
          n > v &      //           use i + 1 if n is greater than v
          p < n        //           and p is less than n (attraction to the right)
        )              //
    ] += x = a[i],     //     add x = a[i] to the entry defined above
    p = v,             //     update the previous value to v
    i                  //     actual index to update a[i]
  ] -= x,              //   subtract x from a[i]
  p = 0                //   start with p = 0
)                      // end of map()

Następnie odfiltrowujemy wszystkie wpisy równe .$0$

a.filter(n => n)

Stax , 27 25 23 18 bajtów

«╥╦.ê§┘h!@ÆEÿ☺╜╫♥B

Uruchom i debuguj

Dane wyjściowe są oddzielone znakami nowej linii.

Ten program działa na sąsiednich parach w macierzy i określa, czy należy zastosować podział między nimi za pomocą tej procedury.

Rozważ jakieś arbitralne dane wejściowe [... w x y z ...]. Oto jak ustalić, czy powinien istnieć podział na xi y.

• Jeśli x == ytak, to tak.
• Jeśli x > y, to iff z >= x.
• Jeśli y > x, to iff w >= y.

Podsumowanie pozostawia się jako ćwiczenie.

Retina 0.8.2 , 64 bajty

\d+
$*
(?<=(1+)) ((?=(1+\1))(?<!\3 \1 )|(?!\1)(?!1+ \1))

1+
$.&

Wypróbuj online! Link zawiera pakiet testowy. Wyjaśnienie:

\d+
$*

Konwertuj na unary.

(?<=(1+)) ((?=(1+\1))(?<!\3 \1 )|(?!\1)(?!1+ \1))

Usuń separatory między przyciągniętymi liczbami. (?<=(1+))ustawia \1liczbę przed separatorem. Po separatorze występują dwa przypadki:

• Liczba po separatorze jest większa niż obie liczby przed separatorem
• Liczba przed separatorem jest większa niż obie liczby po separatorze

W takich przypadkach istnieje przyciąganie między dwiema liczbami, a usunięcie separatora powoduje zderzenie liczb, łącząc je ze sobą.

1+
$.&

Konwertuj na dziesiętny.

Galaretka , 23 bajty

Ø0jMÆmær0Ʋ3Ƥ×=4$o<ʋƝk⁸§

Wypróbuj online!

Monadyczny link, który przyjmuje listę liczb całkowitych jako argument i zwraca listę liczb całkowitych.

Wyjaśnienie

Ø0j                     | Join [0, 0] with input list
         Ʋ3Ƥ            | For each length 3 infix, do the following as a monad:
   M                    | - Indices of maximum
    Æm                  | - Mean
      ær0               | - Round to even (so the means of [1, 2, 3], [1, 2], [2, 3] and [1, 3] will all round to 2
                  ʋƝ    | For each neighbouring pair, do the following as a dyad:
            ×           | - Multiply
             =4$        | - Check if equal to 4
                o       | - Or
                 <      | - First number less than second
                    k⁸  | Split input after truthy values of the above
                      § | Sum, vectorised

Inspiracje zaczerpnięte z odpowiedzi Stax na @ recursive .

C (gcc) , 111 bajtów

a,b,c,s;P(){s=!printf("%d ",s);}f(int*v){for(b=s=0,c=*v;a=b,b=c;a<b|b<a&c<a||P(),s+=b,b<c&c<=a|!c&&P())c=*++v;}

Wypróbuj online!

Przyjmuje tablicę liczb całkowitych zakończonych zerem.

Wyjaśnienie

a,b,c,  // Three consecutive elements of input array
s;      // Accumulator for sum
P(){s=!printf("%d ",s);}  // Print and clear s
f(int*v){
    for(
        // Init
        b=s=0,
        c=*v;
        // Loop test
        a=b,  // Shift b into a
        b=c;  // Shift c into b, exit if zero
        // Post loop
        a<b|b<a&c<a||P(),  // Print if a==b || (b<a && a<=c)
        s+=b,  // Accumulate
        b<c&c<=a|!c&&P()   // Print if c==0 || (b<c && c<=a)
    )
        // Loop body
        c=*++v;  // Read next number into c
}

Python 2 , 162 bajty

l=input()
a=[(L<R>C)-(R<L>C)for L,C,R in zip([0]+l,l,l[1:]+[0])]
while any(a):
 i=0
 while a[i]==0:i+=1
 m=a.pop(i);x,y=[i,i+m][::m];l[x:y+1]=l[i]+l[i+m],
print l

Wypróbuj online!

J , 45 bajtów

+//.~0,[:+/\2(<+.1=*)/\3(>./1:/@I.@E.])\0,,&0

Wypróbuj online!

Zainspirowany oryginalną odpowiedzią Stax na rekurencyjne

R , 222 196 173 bajtów

Oto rozwiązanie z pewną pomocą Robin Ryder

n=length(d<-diff(y<-x<-scan()));l=c(1,sign(d[-n]+d[-1]),-1);m=!!l*n&c(d[1]>0,d[-1]>0|d[-n]<0,d[n]<0);for(t in 1:n){for(i in which(m))y[a]=y[a<-i+l[i]]+x[i];y=x=y-x*m};x[!m]

Wypróbuj online!

Krótki zestaw komentarzy

n=length(d<-diff(y<-x<-scan()));  #read input and compute pairwise differences
                    #d[-n]+d[-1]: compare left and right differences
l=c(1,sign(d[-n]+d[-1]),-1)                 #direction of attraction
m=!!l*n&                          #indices of attracted numbers
  c(d[1]>0,d[-1]>0|d[-n]<0,d[n]<0)  
                                   #!!l*n eliminates zeroes in l & the case n==0
for(t in 1:n){                   #excessive loop on transfers
 for(i in which(m))
   y[a]=y[a<-i+l[i]]+x[i]         #transfer right vs. left
 y=x=y-m*x}                        #complete transfer
x[!m]                             #output

Python, 114 112 bajtów

lambda a:eval('['+'+'.join(str(c)+',0'*((e<c>d)==(c<d>b))for b,c,d,e in zip([0]+a,a,a[1:]+[0],a[2:]+[0,0]))+']')

Wykorzystuje to fakt, że kierunek strzałki nie ma znaczenia i że obecność strzałki między [i] a [i + 1] można określić, patrząc na zakres czterech elementów a [i- 1: i + 3].

Edycja: Dziękuję Jo King za wyjaśnienie zasad

Perl 5 , 156 147 bajtów

$q='$F[$i';map{eval"\$i++while$q]$_"}"<$q+1]",">$q+1]&&$q]>$q+2]&&\$i<\@F"if eval"$q-1]-$q+1]||$q]>$q+1]";$\.=$".sum@F[$p..$i];($p=++$i)<@F&&redo}{

Wypróbuj online!

K (ngn / k) , 46 bajtów

{+/'x@.={x x}/(!#x)+{-/2=+/x<\:x 2 0}'3'0,x,0}

Wypróbuj online!

0,x,0 otaczaj argument zerami

3' trojaczki kolejnych pozycji

{ }' dla każdego

x 2 0zdobądź ostatni i pierwszy z obecnej trypletu - x[2]i x[0]. są to sąsiedzi x[1], na których trójka jest wyśrodkowana

x<\: porównaj używając mniej niż z każdym z obecnych trypletów

+/suma. wynikiem jest para odpowiadająca x[2]ix[0]

2=sprawdź, czy któryś z sąsiadów jest większy niż pozostałe 2 elementy x, zwróć parę boolanów 0 lub 1

-/odejmij je. wynik -1 oznacza x[1]przyciągnięcie w lewo, 1 w prawo, a 0 oznacza, że ​​pozostaje na miejscu

(!#x)+ dodaj 0 do pierwszego elementu, 1 do drugiego itd. To oblicza wskaźniki, do których przyciągane są przedmioty

{x x}/indeksować się do konwergencji. wynikiem są efektywne wskaźniki, do których ostatecznie przyciągany jest każdy przedmiot

x@.=grupa x(oryginalny argument) według tych. wynikiem jest lista list

+/' zsumuj każdy

Clojure , 299 252 bajtów

(fn[l](loop[o[0]m(vec(map-indexed(fn[i v](def f #(max(nth l(+ % i)0)v))(-(f -1)(f 1)))l))i 0](defn f[x](update o(-(count o)x)#(+(l i)%)))(cond(<=(count m)i)(pop o)(>(m i)0)(recur(f 2)m(inc i))(<(m i)0)(recur(f 1)m(inc i))1(recur(conj(f 1)0)m(inc i)))))

Wypróbuj online!

Wyjaśnienie:

(fn [l]
  (loop [o [0]
         m (vec(map-indexed (fn [i v] ; This maps each element l[i] of l to max(l[i-1], l[i]) - max(l[i+1], l[i])
                              (def f #(max (nth l (+ % i) 0) v))
                              (- (f -1) (f 1)))
                            l))       ; l[x] is zero when l[x] is out of bounds of the input vector l
         i 0]
    (defn f [x] (update o (- (count o) x) #(+ (l i) %)))
    ; Defines a function f(x) that returns the result of mapping the (x-1)th to last element of o over the function g(y) = l[i] + y

    (cond
      (<= (count m) i) (pop o) ; If the length of m is less than or equal to i, there are no more elements in m, so return all but the last element of o
      (> (m i) 0) (recur (f 2) m (inc i)) ; If m[i] is positive, l[i] is pulled toward to the previous element, so add l[i] to the 2nd to last element of o
      (< (m i) 0) (recur (f 1) m (inc i)) ; If m[i] is negative, l[i] is pulled toward the next element, so add l[i] to the last element of o
      1 (recur (conj (f 1) 0) m (inc i))))) ; 1 is truthy
      ; If the length of l is less than or equal to i, and m[i] is not positive or negative, we have m[i] = 0, so l[i] is not pulled toward any other element

APL (Dyalog Classic) , 52 51 bajtów

{+/(⊃∘⍵¨⊢)⌸{⍵[⍵]}⍣≡(⍳≢⍵)+{-/2=+⌿⍵∘.<1↓1⌽⍵}¨3,/∊0⍵0}

Wypróbuj online!

tłumaczenie mojej odpowiedzi k

05AB1E , 21 bajtów

0.øŒ3ùεZQXsÂU‚ÆZ≠}Å¡O

Wypróbuj online!