53
\$\begingroup\$

The gravitational force is a force that attracts any two objects with mass. In this challenge our objects will be Numbers and their mass will be their value. To do so, we don't care about the strength of the force but the direction of it.

Imagine this set of numbers

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

Each of them creates a force between itself and it's adjacent numbers. Under some conditions, this will cause another number to be attracted (moved) toward a number. When the number is bigger than the adjacent, it attracts it. Lets take a look at our previous example:

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

The number 1 is not big enough to move 6, but the number 6 is, etc... Basically, numbers are moved to the biggest adjacent number (also bigger than the number itself). If both of the adjacent numbers are equal it is not attracted then. It also happens when the number and it adjacent are equal.

This is only to show the attraction, but what happens after? Numbers that collide due to attraction are summed up:

[20 32 28]

So basically the challenge is, Given a set of numbers, output the result of the attracted set of numbers.


Example 1

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

Example 2

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

Example 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]

Example 4

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

Example 5

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

Example 6

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

Example 7

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

Notes

  • Attraction only happens once
  • Numbers are not attracted to non-adjacent Numbers
  • The set of numbers will only contain positive integers
\$\endgroup\$
8
  • 1
    \$\begingroup\$ Suggest adding a test case that collapses to a single integer. \$\endgroup\$
    – Shaggy
    May 20, 2019 at 18:25
  • 2
    \$\begingroup\$ [1 3 5 4 2] = 15? \$\endgroup\$ May 20, 2019 at 20:10
  • \$\begingroup\$ @MagicOctopusUrn Yes \$\endgroup\$ May 20, 2019 at 20:11
  • 14
    \$\begingroup\$ 1 is not big enough to attract the number 6 This wording bothers the physicist in me. (Well so do some of the other rules, but this one might be fixable by changing the wording without changing the problem definition). The attraction force between two bodies, G*M*m / r^2, is equal for both bodies. The lighter one moves more than the heavier one because of momentum, not because of a lack of attraction. Maybe say "1 is not big enough to move 6". \$\endgroup\$ May 21, 2019 at 9:33
  • 4
    \$\begingroup\$ But really you're defining "attract" as "pulled toward", rather than "creates a force", which conflicts with the earlier sentence "Each of them creates an attraction force to it's adjacent numbers". So maybe rework that opening to say "each of them creates a force between itself and it's adjacent numbers. Under some conditions, this will cause another number to be attracted (moved) toward a number." I know this is just a terminology nitpick, and this model of gravitation is only vaguely similar to real physics, but it bothered me enough to want to write this comment. \$\endgroup\$ May 21, 2019 at 9:36

14 Answers 14

15
\$\begingroup\$

JavaScript (ES6),  106 104  100 bytes

Saved 2 bytes thanks to @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))

Try it online!

Commented

We first update the original input array a[] by iterating on a copy of it. During this step, all values 'attracted' by other ones are set to \$0\$.

Because the array is parsed from left to right, we can just add \$a_i\$ to \$a_{i+1}\$ whenever a value is attracted by its right neighbor.

Example: \$4\rightarrow5\rightarrow6\$ is turned into \$[0,\color{red}9,6]\$ and then \$[0,0,\color{red}{15}]\$.

But when several values in a row are attracted by their left neighbor, we need to add \$a_i\$ to the first attractor \$a_k\$ of this sequence (with \$k<i\$) rather than simply \$a_{i-1}\$.

Example: \$6\leftarrow5\leftarrow4\$ is turned into \$[\color{red}{11},0,4]\$ and then \$[\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()

We then filter out all entries equal to \$0\$.

a.filter(n => n)
\$\endgroup\$
3
  • \$\begingroup\$ From your explanation, it sounds like your code would fail for [1,3,5,3,1,2,1] and output [14,2], but it actually works correctly and outputs [13,3]. \$\endgroup\$ May 21, 2019 at 18:58
  • \$\begingroup\$ @EriktheOutgolfer I've rephrased the part which -- I think -- was misleading. Is that better? \$\endgroup\$
    – Arnauld
    May 22, 2019 at 7:02
  • 2
    \$\begingroup\$ Now it does mention the "first attractor" instead of just the "highest previous value", so I can understand what you mean. \$\endgroup\$ May 22, 2019 at 8:48
9
\$\begingroup\$

Stax, 27 25 23 18 bytes

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

Run and debug it

Output is separated by newlines.

This program operates on adjacent pairs in the array, and determines whether there should be a split between them using this procedure.

Consider some arbitrary input [... w x y z ...]. Here is how to determine if there should be a split between x and y.

  • If x == y, then yes.
  • If x > y, then iff z >= x.
  • If y > x, then iff w >= y.

The summing is left as an exercise.

\$\endgroup\$
0
8
\$\begingroup\$

Retina 0.8.2, 64 bytes

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

1+
$.&

Try it online! Link includes test suite. Explanation:

\d+
$*

Convert to unary.

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

Remove the separators between attracted numbers. (?<=(1+)) sets \1 to the number before the separator. After the separator, there are then two cases:

  • The number after the separator is greater than both of the numbers before the separator
  • The number before the the separator is greater than both of the numbers after the separator

In these cases there is an attraction between the two numbers and deleting the separator causes the numbers to collide, adding them together.

1+
$.&

Convert to decimal.

\$\endgroup\$
6
\$\begingroup\$

Jelly, 23 bytes

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

Try it online!

A monadic link which takes a list of integers as its argument and returns a list of integers.

Explanation

Ø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

Some inspiration taken from @recursive’s Stax answer.

\$\endgroup\$
4
\$\begingroup\$

C (gcc), 111 bytes

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;}

Try it online!

Takes a zero-terminated array of integers.

Explanation

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
}
\$\endgroup\$
3
\$\begingroup\$

Python 2, 162 bytes

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

Try it online!

\$\endgroup\$
3
\$\begingroup\$

J, 45 bytes

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

Try it online!

Inspired by recursive's original Stax answer

\$\endgroup\$
3
\$\begingroup\$

R, 222 196 173 bytes

Here is a solution with some help from 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]

Try it online!

A short set of comments

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
\$\endgroup\$
4
  • 1
    \$\begingroup\$ -4 bytes with sign(e) instead of (e>0)-(e<0) \$\endgroup\$ May 24, 2019 at 12:26
  • 1
    \$\begingroup\$ also the {} in the for loop are unnecessary since there is only one instruction in the loop. \$\endgroup\$ May 24, 2019 at 12:31
  • 1
    \$\begingroup\$ 189 bytes with the above 2 comments + moving the definition of y. \$\endgroup\$ May 24, 2019 at 12:41
  • 1
    \$\begingroup\$ 179 bytes using the fact that m is a boolean \$\endgroup\$ May 24, 2019 at 13:36
3
\$\begingroup\$

Python, 114 112 bytes

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]))+']')

This uses the fact that the direction of the arrow doesn't actually matter, and that the presence of an arrow between a[i] and a[i+1] can be determined by looking at the range of four elements a[i-1:i+3].

Edit: Thank you to Jo King for the rule clarification

\$\endgroup\$
0
2
\$\begingroup\$

Perl 5, 156 147 bytes

$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}{

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Clojure, 299 252 bytes

(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)))))

Try it online!


Explanation:

(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
\$\endgroup\$
2
\$\begingroup\$

K (ngn/k), 47 bytes

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

Try it online!

0,x,0 surround the argument with 0s

3': triplets of consecutive items

{ }' for each do

x 2 0 get last and first of the current triplet - x[2] and x[0]. they are the neighbours of x[1], on which the triplet is centred

x<\: compare using less-than against each of the current triplet

+/ sum. the result is a pair corresponding to x[2] and x[0]

2= check if either neighbour is greater than the other 2 elements from x, return a pair of 0-or-1 booleans

-/ subtract them. a result of -1 means x[1] is attracted to the left, 1 to the right, and 0 means it stays in place

(!#x)+ add 0 to the first item, 1 to the second, etc. this computes the indices towards which items are attracted

{x x}/ index with itself until convergence. the result are the effective indices to which each item is ultimately attracted

x@.= group x (the original argument) by those. the result is a list of lists

+/' sum each

\$\endgroup\$
1
\$\begingroup\$

APL (Dyalog Classic), 52 51 bytes

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

Try it online!

translation of my k answer

\$\endgroup\$
1
\$\begingroup\$

05AB1E, 21 bytes

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

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.