# Smooth a line graph

Given an input of an integer n and a list of positive integers m1, m2, ..., output a list of integers m1', m2', ... where mx' is defined as the average of mx-n through mx+n.

When calculating these averages, ignore indices that are out of bounds (and adjust what you are dividing the sum by accordingly). n will always be ≥ 1 but never half of the length of m (rounded down) or more. This means that the minimum length of m is 4. The elements in m will be positive integers, but the output must be accurate to at least 3 decimal places.

The input / output elements that are lists may be either whitespace-/comma-separated strings or arrays/lists/etc. For input, if your solution is a function, you may additionally take a first argument of n and additional arguments as mx (this applies to command line arguments as well).

Here is a visual representation of n=1:

1 4 5 7 10
__/ | | |
L avg(1,4) = 2.5
| | |
\___/ | |
L avg(1,4,5) = 3.333
| |
\___/ |
L avg(4,5,7) = 5.333
|
\___/
L avg(5,7,10) = 7.333

\___
L avg(7,10) = 8.5

Final output: 2.5 3.333 5.333 7.333 8.5


Since this is , the shortest code in bytes wins.

Test cases (these were done manually; please notify me of any errors):

In                             Out
----------------------------------------------------------------------
n=1, m=12 6 3 9                9 7 6 6
n=1, m=1 4 5 7 10              2.5 3.333 5.333 7.333 8.5
n=1, m=1 3 3 7 4 2 4 2         2 2.333 4.333 4.666 4.333 3.333 2.666 3
n=2, m=1 3 5 9 10 14 15 16 23  3 4.5 5.6 8.2 10.6 12.8 15.6 17 18
n=3, m=1 1 1 1 1 1 1 1         1 1 1 1 1 1 1 1
n=3, m=1 2 3 4 5 6 7 8         2.5 3 3.5 4 5 5.5 6 6.5

• To be clear, this is the same as prepending and appending zeros and then calculating the means of each contiguous subsequence of length 3? – El'endia Starman Jan 11 '16 at 1:19
• @El'endiaStarman No. avg(0,1,2) is not the same as avg(1,2). For the "edge cases" (ha), you shouldn't be averaging as many elements of the input list. – Doorknob Jan 11 '16 at 1:20
• Ah, right, I see now. – El'endia Starman Jan 11 '16 at 1:20
• Related – Alex A. Jan 11 '16 at 2:13
• This would have been a better challenge without the restriction that the m_i are positive. – Peter Taylor Jan 11 '16 at 18:44

# Pyth, 20 bytes

m.O:vzeS,0-dQh+dQUvz


Test suite

Pretty straightforward, just slice the appropriate section out of the list, then average.

• @ThomasKwa I tried that, but it seems like you have to store E outside the map because it will keep trying to read a new value if it is inside. This makes it take the same number of bytes. – FryAmTheEggman Jan 11 '16 at 22:25

# MATL, 302826 24 bytes

2*1+:g2X53$X+1Mbgbb3$X+/


Tested on Matlab and on Octave. Uses current version (9.1.0) of the language/compiler.

Input is: first the number controlling window length, then the array with format [1 4 5 7 10].

EDIT (20 May 2016): Try it online! The code in the link has X+ replaced by Y+ to conform to version 18.0.0 of the language.

### Example

>> matl
> 2*1+:g2X53$X+1Mbgbb3$X+/
>
> 1
> [1 4 5 7 10]
2.5 3.333333333333333 5.333333333333333 7.333333333333333               8.5

>> matl
> 2*1+:g2X53$X+1Mbgbb3$X+/
>
> 2
> [1 3 5 9 10 14 15 16 23]
3               4.5               5.6 8.199999999999999              10.6               2.8              15.6        17                18


### Explanation

The equivalent Matlab code would be

n = 1; %// first input: number controlling window length
x = [1 4 5 7 10]; %// second input: array
result = conv(x,ones(1,2*n+1),'same')./conv(ones(size(x)),ones(1,2*n+1),'same');


The MATL code makes use of the recently added features of implicit input and automatic function-input clipboard:

2*1+          % get implicit input "n". Multipliy by 2 and add 1
:g            % create a vector of 2*n+1 "true" values (will act as "one" values)
2X5           % 'same' string literal
3$X+ % get implicit input "x" (array). Convolution using three inputs 1M % push all three inputs from last function bgbb % convert first input to "true" values. Will act as "one" values 3$X+          % convolution using three inputs
/             % divide element-wise. Implicitly print


# APL (Dyalog Unicode), 18 16 bytes

{⍵⌹×⍵}⌺(1+2×⎕)⊢⎕


Try it online!

@ngn suggested an average trick using ⌹, and I took it further to shorten it by two bytes, eliminating the need of ↓.

Since the input is positive integers and the Stencil's padding gives only zeros, it suffices to average the nonzero entries.

The default trick for average using ⌹ (matrix divide/solve linear equation/least squares fit) is "divide a vector by its all ones version", which solves the least squares of something like this:

1x = 1
1x = 3
1x = 5


where the least square solution is exactly the average. I modified it to ignore the zeros when calculating the average:

{⍵⌹×⍵}  Input: a vector of positive integers, possibly with zeros to ignore
×⍵   Signum of each number, which gives 1 for positives and 0 for zeros
⍵⌹     Matrix-divide the original vector by the above,
which gives the system of equations, e.g. for 0 0 1 3 5:
0x = 0
0x = 0
1x = 1
1x = 3
1x = 5
Then the zero-coefficient equations are ignored in the least squares,
which leads to the average of only positive entries.


Alternatively, Extended can do the same in 15 bytes, exploiting the fact that the left argument is always zero (as opposed to the "padding size" in regular Dyalog version):

# APL (Dyalog Extended), 15 bytes

(⊢⌹<)⌺(1+2×⎕)⊢⎕


Try it online!

# APL (Dyalog Unicode) 18.0, 18 bytes

(+/÷≢)⍤↓⌺(1+2×⎕)⊢⎕


Try an equivalent 17.x program online!

What a fitting challenge for Dyalog APL's Stencil ⌺.

The Stencil operator extracts the moving window over an array exactly as described in the challenge. Specifically, for odd window size, the window is centered over each element, padded with zeros outside the array as necessary, and then the amount of padding is given as an extra information so that single Drop ↓ will remove such padding. The rest is just specifying the right window size and taking average (+/÷≢) over each subarray.

### Illustration

Input array: 12 6 3 9
Input n: 1
Window size: 3 (1+2×n)
Arguments to left operand of Stencil:
Left  Right
1     0  12 6  ⍝ Zero padding 1 unit to the left; 1↓ drops 0 from the front
0     12 6  3
0     6  3  9
¯1    3  9  0  ⍝ Zero padding 1 unit to the right ¯1↓ drops 0 from the back


Matrix multiplication approach is also possible, but it is not short enough:

# APL (Dyalog Unicode), 21 bytes

{÷/⍵1+.×¨⊂⍺≥|∘.-⍨⍳≢⍵}


Try it online!

### How it works

{÷/⍵1+.×¨⊂⍺≥|∘.-⍨⍳≢⍵}  ⍝ Left:n, Right:m
⍳≢⍵   ⍝ 1..length of m
∘.-⍨      ⍝ Self outer product by difference
⍺≥|          ⍝ 1 if abs diff is at most n, 0 otherwise
⍝ which gives the band matrix
⍵1+.×¨⊂  ⍝ Inner product with m and all-one vector
÷/         ⍝ Divide left by right


ri_S*l~1$++\2*)ew{S-_:+\,d/}%  Input format is n [m1 m2 ... mx]. Run all test cases. (Automatically converts the test suite to the required input format.) This works by pre- and append n spaces, then taking all substrings of length 2n+1, and removing the spaces again before computing their means. # Julia, 57 bytes f(n,m)=[mean(m[max(1,i-n):min(end,i+1)])for i=1:endof(m)]  This is a function that accepts two integers and returns an array of floats. The approach here is very straightforward. We construct a new array by taking the mean of sections of the input array, truncating at the front and back. ## Haskell, 97 95 bytes import Data.List n#x|t<-2*n+1=[sum a/sum(1<$a)|a<-take t<$>take t(inits x)++tails x,length a>n]  Usage example: 2 # [1,3,5,9,10,14,15,16,23] -> [3.0,4.5,5.6,8.2,10.6,12.8,15.6,17.0,18.0]. How it works: t<-2*n+1 -- assign t to the maximum number of elements of a -- of sublist take t(inits x) -- build the sublists from t elements of the inits ++tails x -- of the input and the tails of the input, -- e.g. x=[1,2,3,4], t=3: -- [[],[1],[1,2]] ++ [[1,2,3,4],[2,3,4],[3,4],[4],[]] a<-take t<$>                -- take at most t elements from every sublist
,length a>n   -- keep those with a minimum length of n+1
sum a/sum(1<$a) -- calculate average, "sum(1<$a)" is the length of a


## Pyth, 22 bytes

.OMsM.:++J*]YKE]MQJhyK


Explanation:

.OM sM .: +               Means of flattens of sublists of length 2K+1 of
+ J *
] Y     J is E copies of [].
K E     Save E to a variable to use it later.
]MQ        the input
J             Put J on both sides of ]MQ.
h y K           2K+1


Try it here.

# JavaScript (ES6), 104

Running total / running sample size. In Javascript, reading a value outside the bounds of an array gives undefined, that can be converted to 0 using ~~

(l,n,p=0)=>l.map((v,i)=>(p+=~l[i-n-1]-~l[i+n])/(n+1+Math.min(n,l.length-1-i,i)),l.map((v,i)=>p+=i<n&&v))


Ungolfed

(l, n) => {
p = 0;
for (i = 0; i < n; i++) p += v;
r = [];
for (i = 0; i < l.length; i++) {
p += (l[i + n] || 0) - (i > n ? l[i - n - 1] : 0);
r.push(p / Math.min(n, l.length - i - 1, i);
}
return r;
}


Test

f=(n,l,p=0)=>l.map((v,i)=>(p+=~l[i-n-1]-~l[i+n])/(n+1+Math.min(n,l.length-1-i,i)),l.map((v,i)=>p+=i<n&&v))

console.log=x=>O.textContent+=x+'\n';

;[
[1,[12,6,3,9],[9,7,6,6]]
, [1,[1,4,5,7,10],[2.5,3.333,5.333,7.333,8.5]]
, [1,[1,3,3,7,4,2,4,2],[2,2.333,4.333,4.667,4.333,3.333,2.667,3]]
, [2,[1,3,5,9,10,14,15,16,23],[3,4.5,5.6,8.2,10.6,12.8,15.6,17,18]]
, [3,[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1]]
, [3,[1,2,3,4,5,6,7,8],[2.5,3,3.5,4,5,5.5,6,6.5]]
].forEach(t=>{
var n=t[0],l=t[1],x=t[2],r=f(n,l)
// verify (limited to 3 decimals)
var ok = r.every((v,i)=>v.toFixed(3)==x[i].toFixed(3))

console.log((ok?'OK   ':'Fail ')+n+' '+l+' -> '+r+' ('+x+')')
})
<pre id=O></pre>

# JavaScript (ES6), 82 bytes

code:

F=(n,a)=>a.map((e,i)=>(s=a.slice(i<n?0:i-n,i+n+1))&&s.reduce((l,c)=>l+c)/s.length)


test:

F=(n,a)=>a.map((e,i)=>(s=a.slice(i<n?0:i-n,i+n+1))&&s.reduce((l,c)=>l+c)/s.length)

document.write('<pre>' +
[
[1, [12, 6, 3, 9], [9, 7, 6, 6] ],
[1, [1, 4, 5, 7, 10], [2.5, 3.333, 5.333, 7.333, 8.5] ],
[1, [1, 3, 3, 7, 4, 2, 4, 2], [2, 2.333, 4.333, 4.667, 4.333, 3.333, 2.667, 3] ],
[2, [1, 3, 5, 9, 10, 14, 15, 16, 23], [3, 4.5, 5.6, 8.2, 10.6, 12.8, 15.6, 17, 18] ],
[3, [1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1] ],
[3, [1, 2, 3, 4, 5, 6, 7, 8], [2.5, 3, 3.5, 4, 5, 5.5, 6, 6.5] ]
].map(t => {
var [n, m, e] = t;
var r = F(n, m);
// verify to precision of 3 decimals
var test = r.every((v, i) => v.toPrecision(3) === e[i].toPrecision(3));

return 'F(' + n + ', [' + m + '])\t' + (test ? 'Pass' : 'Fail') +
'\n\t{' + r + '} ' + (test ? '=' : '≠') + ' {' + e + '}';
}).join('\n\n') +
'</pre>');

## 05AB1E, 30 bytes

ćU˜©ε®NX@iX·>£ÅAV®¦©YëN>X+£ÅA}


Input is: [n,[list_m]] Output is: [list_of_avgs]

Explanation

ćU˜©ε®NX@iX·>£ÅAV®¦©YëN>X+£ÅA}
U                                 Save in variable X
˜                                Flat the list
©                               Save the list in register c
ε                        }     Map
®                             Get the list from register c
NX@                          Is the iteration greater than or equal to n
i                         if true
ë             if false
X·>                      push (n*2)+1
£                     extract (n*2)+1 elements from head
ÅA                   Arithmetic mean
V                  Save the result in variable Y
®                 Push the list from register c again
©               save the new list in register c
Y              get variable Y (to apply on map returned value)
N>X+         push i+1+n  (i=iteration index, loop count)
£        extract i+1+n elements from head
ÅA      Arithmetic mean


Try it here :)

# Wolfram Language (Mathematica), 46 bytes

Mean/@N@Partition[#2,UpTo[2#+1],1,{-#-1,#+1}]&


Try it online!