12
\$\begingroup\$

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 so the shortest code in bytes wins
\$\endgroup\$
6
  • \$\begingroup\$ I feel like there's a better mathematical way to doing this than just the straightforward method... \$\endgroup\$ – hyper-neutrino May 12 '17 at 1:54
  • \$\begingroup\$ My program is slightly off for the longer test cases due to floating point issues. Is that acceptable? \$\endgroup\$ – hyper-neutrino May 12 '17 at 2:04
  • \$\begingroup\$ That's acceptable for me! @HyperNeutrino \$\endgroup\$ – Graviton May 12 '17 at 2:10
  • 2
    \$\begingroup\$ How do you get the number 0.8978052126200274 from [-1, 0.057384545038866065, 0.4963420210333791, 0.058756287151348875]? \$\endgroup\$ – Luis Mendo May 12 '17 at 9:22
  • \$\begingroup\$ Yeah, the result should be 0.903120713306 \$\endgroup\$ – mbomb007 May 12 '17 at 13:32

14 Answers 14

6
\$\begingroup\$

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

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!

\$\endgroup\$
4
  • \$\begingroup\$ This is also 101 bytes but doesn't work since [ screws up. Maybe you can take some inspiration from it. \$\endgroup\$ – Giuseppe Feb 19 at 23:00
  • \$\begingroup\$ Though I guess you can get the -3 bytes from mean(x)-x rather than mean(x)-x[1]. \$\endgroup\$ – Giuseppe Feb 19 at 23:01
  • 1
    \$\begingroup\$ @Giuseppe - Thanks! I love it when 'there were 50 or more warnings...'! I also had the [ problem, and drop=F made that approach too long... \$\endgroup\$ – Dominic van Essen Feb 19 at 23:44
  • 1
    \$\begingroup\$ You can get to 95 bytes using c(y,y) instead of c(y,y[1]) but I found a 90 byter :-) \$\endgroup\$ – Giuseppe Feb 20 at 21:14
3
\$\begingroup\$

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

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!

\$\endgroup\$
2
  • \$\begingroup\$ My algorithm to produce the examples were slightly wrong, yours works perfectly fine for all inputs now! \$\endgroup\$ – Graviton May 12 '17 at 3:16
  • \$\begingroup\$ @Graviton Oh, that's interesting, I thought mine were off! Thanks! :P \$\endgroup\$ – hyper-neutrino May 12 '17 at 3:16
2
\$\begingroup\$

Mathematica, 83 bytes

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

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

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

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.

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

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

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

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

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
}
\$\endgroup\$
4
  • 1
    \$\begingroup\$ ⊃⍵-(+/÷≢)⍵⊃⍵-⍵⌹=⍨⍵ for -2 bytes. \$\endgroup\$ – Adám Feb 15 at 9:52
  • \$\begingroup\$ @Adám Using ⌹ is pretty smart! I need to look up how that works \$\endgroup\$ – user Feb 15 at 16:12
  • 1
    \$\begingroup\$ Think of it as finding the best fit \$x\$ for the over-determined equation system \$\begin{matrix} x=\omega_1\\ x=\omega_2\\ x=\omega_3\\ ⋮=⋮\\ x=\omega_n \end{matrix}\$ or actually \$\begin{align} [\omega_1=\omega_1]x=\omega_1\\ [\omega_3=\omega_2]x=\omega_2\\ [\omega_3=\omega_3]x=\omega_3\\ ⋮=⋮\\ [\omega_n=\omega_n]x=\omega_n \end{align}\$. \$\endgroup\$ – Adám Feb 15 at 16:43
  • \$\begingroup\$ @Adám Ah, I think I understand now (at least the vector version). This is a pretty interesting primitive! \$\endgroup\$ – user Feb 15 at 17:24
2
\$\begingroup\$

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.

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

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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