Smooth a line graph

Question

Given an input of an integer n and a list of positive integers m₁, m₂, ..., output a list of integers m₁', m₂', ... where m_x' is defined as the average of m_x-n through m_x+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 m_x (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 code-golf, 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

Answer 1

MATL, 30 28 26 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

Answer 2

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

Answer 3

CJam, 31 30 bytes

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.

Answer 4

Pyth, 20 bytes

m.O:vzeS,0-dQh+dQUvz

Test suite

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

Answer 5

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.

Answer 6

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

Answer 7

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.

Answer 8

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>

Answer 9

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>');

Answer 10

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}
ć                                  Head extract (get n)
 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
                  ¦                remove head (first element)
                   ©               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 :)

Answer 11

Wolfram Language (Mathematica), 46 bytes

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

Try it online!