13
\$\begingroup\$

If we have a list, say the list [9, 2, 4, 4, 5, 5, 7], we can do a moving average across it.

Taking a window of say, 3 elements, each element is replaced by a window like such: [[9], [9, 2], [9, 2, 4], [2, 4, 4], [4, 4, 5], [4, 5, 5], [5, 5, 7]], and then taking averages, we get [9.0, 5.5, 5.0, 3.3333333333333335, 4.333333333333333, 4.666666666666667, 5.666666666666667].

Pretty simple so far. But one thing you can notice about this is that taking a moving average "smooths out" the list. So this begs the question: how many times does one have to take a moving average to make the list "smooth enough"?

Your task

Given a list of floats, an integer window size, and a float, output how many times one has to take the moving average to get the standard deviation less than that float. For those that don't know, standard deviation measures how un-smooth a set of data is and can be calculated by the following formula:

stddev

For example, using our earlier list and a max stddev of .5, we get 8 iterations that look like this:

[9.0, 5.5, 5.0, 3.3333333333333335, 4.333333333333333, 4.666666666666667, 5.666666666666667]
[9.0, 7.25, 6.5, 4.6111111111111116, 4.2222222222222223, 4.1111111111111107, 4.8888888888888893]
[9.0, 8.125, 7.583333333333333, 6.1203703703703702, 5.1111111111111107, 4.3148148148148149, 4.4074074074074074]
[9.0, 8.5625, 8.2361111111111107, 7.2762345679012341, 6.2716049382716044, 5.1820987654320989, 4.6111111111111107]
[9.0, 8.78125, 8.5995370370370363, 8.024948559670781, 7.2613168724279831, 6.2433127572016458, 5.3549382716049374]
[9.0, 8.890625, 8.7935956790123466, 8.4685785322359397, 7.9619341563786001, 7.1765260631001366, 6.2865226337448554]
[9.0, 8.9453125, 8.8947402263374489, 8.7175997370827627, 8.4080361225422955, 7.8690129172382264, 7.141660951074531]
[9.0, 8.97265625, 8.9466842421124824, 8.8525508211400705, 8.6734586953208357, 8.3315495922877609, 7.8062366636183507]

and end with a stdev of 0.40872556490459366. You just output 8.

But there's a catch:

The answer does not have to be nonnegative! If the initial list already satisfies the maximum stddev, you have to see how many iterations you can "go backwards" and undo the moving average and still have the list satisfy the max stddev. Since we are truncating the windows for the initial n data points and not dropping those, there is enough data to reverse a moving average.

For example, if we start with the list [9.0, 8.99658203125, 8.9932148677634256, 8.9802599114806494, 8.9515728374598496, 8.8857883675880771, 8.7558358356689627] (taken from our earlier example with 3 more moving averages done to it) and the same window size and max stddev, you will output -3 because you can reverse the moving average at most 3 times.

Any reasonable I/O format is fine.

This is so shortest code in bytes wins!

Test Cases

[9, 2,  4,  4,  5,  5,  7], 3, .5 -> 8
[9, 2,  4,  4,  5,  5,  7], 3, .25 -> 9
[9.0, 8.99658203125, 8.9932148677634256, 8.9802599114806494, 8.9515728374598496, 8.8857883675880771, 8.7558358356689627], 3, .5 -> -3
[1000, 2,  4,  4,  5,  5,  7], 7, .25 -> 13
[1000.0, 999.98477172851563, 999.96956668760447, 999.95438464397, 999.90890377378616, 999.83353739825293, 999.69923168916694], 4, 7 -> -6
\$\endgroup\$
1
\$\begingroup\$

Wolfram - 236

Pretty clunky right now, but at least it works.

f[x_,w_,c_]:=Module[{l=Length,d=Sqrt@CentralMoment[#,2]&,n,a,b,t,r},n=Length@x;a=Normalize/@LowerTriangularize@Array[Boole[Abs[#1-#2]<w]&,{n,n}]^2;{b,t,r}=If[d@x>c,{a,d@#>c&,l@#-1&},{Inverse@a,d@#<c&,-l@#+2&}];r@NestWhileList[b.#&,x,t]]
\$\endgroup\$
  • \$\begingroup\$ 236 bytes, f[x_,w_,c_]:=Module[{l=Length,d=Sqrt@CentralMoment[#,2]&,n,a,b,t,r},n=Length@x;a=Normalize/@LowerTriangularize@Array[Boole[Abs[#1-#2]<w]&,{n,n}]^2;{b,t,r}=If[d@x>c,{a,d@#>c&,l@#-1&},{Inverse@a,d@#<c&,-l@#+2&}];r@NestWhileList[b.#&,x,t]] \$\endgroup\$ – CalculatorFeline Mar 14 '16 at 1:06

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.