7
\$\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 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
\$\endgroup\$
  • \$\begingroup\$ I feel like there's a better mathematical way to doing this than just the straightforward method... \$\endgroup\$ – HyperNeutrino 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\$ – HyperNeutrino 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
5
\$\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\$
1
\$\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\$
  • \$\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\$ – HyperNeutrino May 12 '17 at 3:16
1
\$\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\$
1
\$\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\$
0
\$\begingroup\$

Mathematica, 83 bytes

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

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.