Smooth a line graph
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
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
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.