Average an array until all numbers are (almost) equal

Question

Given an array of numbers, find out how many iterations of averaging* it takes for the average of every element to be no more than 1 higher or lower than the first element (absolute difference between the array's average and the first element is less than or equal to 1).

*Array averaging

To "average" a number in our array, we take the average of itself, the number behind it, and the number ahead of it. The last number of the array assumes the number ahead of it is the first number of the array (wrapping). Do this for all but the first number of the array, it needs to stay constant. The averages should all be applied at the same time (i.e. don't take the average of a number, put it back into the array, then average the next number).

Example:

ITERATION 0: [-1,4,3.5,7]
          1: [-1, 2.1666666666666665, 4.833333333333333, 3.1666666666666665]
          2: [-1, 2.0, 3.388888888888889, 2.3333333333333335]
          3: [-1, 1.462962962962963, 2.5740740740740744, 1.5740740740740742]
          4: [-1, 1.0123456790123457, 1.8703703703703705, 1.049382716049383]
          5: [-1, 0.6275720164609054, 1.3106995884773662, 0.6399176954732511]
          6: [-1, 0.31275720164609055, 0.8593964334705076, 0.3168724279835391]
          7: [-1, 0.057384545038866065, 0.4963420210333791, 0.058756287151348875]
abs(AVERAGE - FIRST_ELEMENT) = 0.903120713306 (IS LESS THAN 1)
OUTPUT: 7

Other I/O

INPUT >> OUTPUT
[-3, 9]  >>  2
[0, 0, 0, 0]  >>  0
[64, -66, -9, 78, -60]  >>  29
[9, 4, 5, 3, 3, 3, 10, 1, 1, 1]  >>  44
[-6, 5, -4, 3, -2, 1, -1, 2, -3, 4, -5, 6]  >>  70
[100000000, 2.11, 0.0, 16.88, 8.44, 6.33, 16.88, 100000000]  >>  348
[-8245, 6832, 9525, -3397, 5595, -9242, 1954, 6427, 36, -9647, -8887, 3062, -4424, -4806, -3803, 3608, -5115, -3725, -3308, -277]  >>  1038

Though not a part of the challenge; technically we are dealing with absolute values therefore complex numbers should also work. Your program does NOT need to handle complex numbers.:

[(20-1j), (5-4j), 7, (-0-100j)]  >>  15

Notes:

• Other mathematical methods are accepted
• You are to assume there are at least two elements in the array
• This is code-golf so the shortest code in bytes wins

Answer 1

Perl 6,  83  82 bytes

->\a(\b,|c){(c,{[(b,|$_,b).rotor(3=>-2).map: *.sum/3]}...{(b+.sum)/a~~b-1..b+1})-1}

Try it

->\a(\b,|c){(c,{[(b,|$_,b).rotor(3=>-2).map: *.sum/3]}...{1>abs (b+.sum)/a -b})-1}

Try it (also works for complex numbers

Expanded

->      # pointy block lambda

  \a    # the input array
  (
    \b, # the first value  
    |c  # all the rest of the values
  )

{
  (
    # generate a sequence

    c,                 # initialize the sequence starting with the second value

    {                  # bare block lambda with implicit parameter ｢$_｣

      [                # turn the result from a Seq into an array

        ( b, |$_, b )  # re-add the first element
                       # and add it to the end

        .rotor(3=>-2)  # grab 3 at a time, backing up 2

        .map: *.sum/3  # return the average for each sub sequence

      ]
    }

    ...                # keep calling that to generate values until

    {
      1 > abs ( b + .sum )/a - b     # they are almost equal
    }

  ) - 1 # count them and reduce by one (ignore initial value)
}

Answer 2

R, 107 101 98 95 bytes

Edit: -6 bytes thanks to Giuseppe (who has now outgolfed this with his own shorter answer)

function(x){while(abs(mean(x)-x)>1){for(j in seq(y<-x)[-1])x[j]=mean(c(y,y)[j+-1:1]);F=F+1};+F}

Try it online!

Answer 3

Jelly, 30 bytes

L‘ṁ@µ+3\÷3;@Ḣ
ǵS÷L_1ị$Ị¬µÐ¿L’

A monadic link taking the list and returning the number of iterations required.

Test suite at Try it online!

How?

L‘ṁ@µ+3\÷3;@Ḣ - Link 1, perform an iteration: list x
L             - length of x
 ‘            - incremented
  ṁ@          - mould with swapped @rguments (i.e.. [a,b,c,...] -> [a,b,c,...,a])
    µ         - monadic chain separation (call that v)
      3\      - three-wise reduce v with:
     +        -    addition (sum up the overlapping slices of 3)
        ÷3    - divide those by three (get the averages)
            Ḣ - head v (get the first element)
          ;@  - concatenate with swapped @rguments

ǵS÷L_1ị$Ị¬µÐ¿L’ - Main link: list a
 µ         µÐ¿   - collect results while loop
Ç                -   body: call last link as a monad
                 -   condition:
  S              -     sum
    L            -     length
   ÷             -     divide (average)
        $        -     last two links as a monad:
      1          -       literal one
       ị         -       index into (the first element)
     _           -     subtract
         Ị       -     insignificant (absolute value is less than or equal to 1)
          ¬      -     not
              L  - length (count the results)
               ’ - decrement (the first result is number zero)

Answer 4

Python 2, 130 bytes

x=map(float,input())
l=len(x)
q=0
while abs(x[0]-sum(x)/(l+.0))>=1:x=x[:1]+[sum((x+x)[i-1:i+2])/3for i in range(1,l)];q+=1
print q

Slightly off for the larger test cases Apparently not!

BONUS: Change float to complex and it will be able to handle complex numbers correctly (at a cost of two bytes).

Edited once ehhh.... I found a bug.... fixed now!

Answer 5

Mathematica, 83 bytes

(a=#;0//.n_/;Mean@a-First@a>=1:>(a={#&@@a,##}&@@Mean/@Partition[a,3,1,{1,2}];n+1))&

Answer 6

JavaScript (ES6), 106 bytes

f=(a,l=a.length,m=a.reduce((s,e)=>s+e-a[0],0))=>m>l|m<-l&&1+f(a.map((e,i)=>i?(a[i-1]+e+a[++i<l?i:0])/3:e))

Answer 7

Haskell, 81 bytes

g l@(a:_)|abs(sum l/sum(1<$l)-a)<1=0|1<2=1+g(a:[(x+y+z)/3|x:y:z:_<-scanr(:)[a]l])

Usage example: g [64,-66,-9,78,-60] -> 29. Try it online!

How it works

g l@(a:b)                -- function g takes a list l where the first element 
                         -- is bound to a
    |abs (      ) = 0    -- if the end condition is true, return 0
          sum(1<$l)      -- computes the length of l. The library function "length"
                         -- won't work, because it returns an "Int"
    | 1+g                -- else return 1 + a recursive call with one step of
                         -- averaging
  x:y:z:_<-scanr(:)[a]l  -- picks all 3 element sublists of l appended by a
                         -- the elements are bound to x, y and z   

Answer 8

Octave, 146 bytes

function k=f(a)n=numel(a);I=eye(n-1,n)/3;A=[resize(1,1,n);I+circshift(I,[0,1])+circshift(I,[0,2])];k=0;while(abs(mean(a)-a(1))>1)k++;a=A*a;end;end

Try it online!

Multi-line version:

function k = f(a)
    n = numel(a);
    I = eye(n - 1, n) / 3;
    A = [resize(1, 1, n);
         I + circshift(I, [0, 1]) + circshift(I, [0, 2])];
    k = 0;
    while(abs(mean(a) - a(1)) > 1)
        k++;
        a = A * a;
    end;
end

Pretty sure it's rather suboptimal.

Answer 9

Jelly, 22 bytes

;®Æm3Ƥ®;µḷ/©ạÆmỊ¬µÐ¿L’

Try it online!

How it works

;®Æm3Ƥ®;µḷ/©ạÆmỊ¬µÐ¿L’ - Main link. Takes an array A on the left
                  п   - While loop, collecting the results
                 µ     -   Condition:
         ḷ/            -     Get the first element of A
           ©           -     Save into the register R
             Æm        -     Get the mean of A
            ạ          -     Absolute difference
               Ị       -     Less than or equal to 1?
                ¬      -     Logical NOT
        µ              -   Body:
 ®                     -     Retrieve the first element of A
;                      -     Append to A
    3Ƥ                 -     Over overlapping windows of size 3:
  Æm                   -       Return the mean
      ®                -     Retrieve the first element of A
       ;               -     Prepend to the means
                    L  - Count the steps of the while loop
                     ’ - Decrement to account for the first iteration (A)

Answer 10

Husk, 18 bytes

←V§≈←A¡λ:←¹mAX3S:←

Try it online!

Explanation

←V§≈←A¡λ:←¹mAX3S:←
      ¡λ             Infinitely iterate the following function and build a list of results
               S:←   Append the first element to the list
             X3      Get all the contiguous sequences of 3 elements
           mA        Compute the average of each
        :←¹          Prepend the first element of the original list to this result
                     Now we have an infinite list with all the steps
 V§                  Find the index of the first position where:
     A                 the average
   ≈                   is similar (absolute difference <=1)
    ←                  to the first element
←                    Finally, subtract 1 (lists in Husk are 1-indexed)

Answer 11

05AB1E, 22 bytes

[¬UDÅAXα1›≠#Ćü3ÅAXš¼}¾

Try it online or verify all test cases.

Explanation:

[           # Start an infinite loop:
 ¬          #  Get the first item of the list (without popping the list itself)
            #  (which will use the implicit input-list in the first iteration)
  U         #  Pop and store this first item in variable `X`
 D          #  Duplicate the list
  ÅA        #  Pop and get the arithmetic mean
    Xα      #  Get the absolute difference with `X`
      1›≠   #  If this is NOT larger than 1 (thus it's <=1):
         #  #   Stop the infinite loop
  Ć         #  Enclose the list; append its own first item
   ü3       #  Create overlapping triplets
     ÅA     #  Get the arithmetic mean of each inner triplet
       Xš   #  Prepend `X` at the front of this list
 ¼          #  Increase the counter variable by 1 (0 by default)
}¾          # After the infinite loop: push the counter variable
            # (after which it is output implicitly as result)

Answer 12

APL (Dyalog Unicode), 35 33 bytes

Saved 2 bytes thanks to Adám (and would have saved 1 with a tip from Bubbler)

{1≥|⊃⍵-⍵⌹=⍨⍵:0⋄1+∇h,3÷⍨3+/⍵,h←⊃⍵}

Try it online!

A recursive function.

Adám's idea of using ⌹ to find the average is really cool. See their explanation in the comments. R is the result of X⌹Y, and it's chosen to minimize the square of the difference between X and the matrix product of R and Y. In this case, since Y is a vector of all 1s, the average of X minimizes that squared difference.

Explanation:

{
  1≥|⊃⍵-(+/÷≢)⍵: 0        ⍝ Base case: If it's the last iteration, return 0
         ⍵⌹=⍨⍵           ⍝ Average of ⍵ (the array)
            =⍨⍵           ⍝ Compare ⍵ to itself to create an array of 1s the same size as ⍵
         ⍵⌹               ⍝ ⍵ divided by that (matrix division)
       ⍵-                  ⍝ Subtract that from all elements of ⍵
      ⊃                    ⍝ Take only the first of those differences
     |                     ⍝ Absolute value
   1≥                      ⍝ Is it less than or equal to 1?
⋄1+∇h,3÷⍨3+/⍵,h←⊃⍵
               h←⊃⍵        ⍝ Assign the first element of ⍵ to h
            ⍵,             ⍝ Append to ⍵ (because of wrapping)
         3+/               ⍝ Take groups of 3 adjacent elements and sum each
      3÷⍨                  ⍝ Divide each sum by 3 (to get average)
    h,                     ⍝ Prepend h, which stays constant
   ∇                       ⍝ Call on this new iteration
 1+                        ⍝ Add 1 to that
}

Answer 13

Ruby, 88 bytes

f=->a{x,=a;(x-1.0*a.sum/a.size).abs>1?f[[x,*[*a,x].each_cons(3).map{|a|a.sum/3.0}]]+1:0}

Try it online!

Recursive lambda, works with complex numbers. As usual, 2 bytes can be saved in Ruby 2.7+ by using a numbered block parameter. If we can assume that array values will always be provided as floats, we can save some more by avoiding float conversions.

Answer 14

R, 90 bytes

function(l){while(abs(mean(l)-l)>1){l[-1]=colMeans(array(l,sum(l|1)+1:0)[1:3,])
F=F+1}
+F}

Try it online!

Test harness stolen from Dominic van Essen's answer.

Uses R's recycling to construct the appropriate neighbor-means to replace in the original array.