23
\$\begingroup\$

This problem is "inspired" from a question that was originally asked on Quora (not for code golfing). I just want to make it a challenge for you guys (and my first problem submission here).

Given an array of integer elements v and an integer d (we assume that d is lower or equal to the array's length), consider all the sequences of d consecutive elements in the array. For each sequence, compute the difference between the maximum and minimum value of the elements in that sequence and name it the deviation.

Your task is to write a program or function that computes the maximum value among all deviations of all the sequences considered above, and return or output that value.

Worked-through Example:

v: (6,9,4,7,4,1)
d: 3

The sequences of length 3 are:
6,9,4 with deviation 5
9,4,7 with deviation 5
4,7,4 with deviation 3
7,4,1 with deviation 6

Thus the maximal deviation is 6, so the output is 6.

This is code golf, so the shortest answer in bytes wins.

\$\endgroup\$
0

38 Answers 38

16
\$\begingroup\$

Dyalog APL, 7 bytes

⌈/⌈/-⌊/

Test it on TryAPL.

How it works

⌈/⌈/-⌊/  Dyadic chain. Left argument: d. Right argument: v

     ⌊/  Reduce v by d-wise minimum, yielding the minima of all slices of length d.
  ⌈/     Reduce v by d-wise maximum, yielding the maxima of all slices of length d.
    -    Subtract, yielding the ranges of all slices of length d.
⌈/       Take the maximum.
\$\endgroup\$
5
\$\begingroup\$

JavaScript (ES6), 73 bytes

with(Math)(v,d)=>max(...v.map((a,i)=>max(...a=v.slice(i,i+d))-min(...a)))
\$\endgroup\$
3
  • \$\begingroup\$ +1 for TIL that you can use with on an entire lambda function \$\endgroup\$ Oct 21, 2016 at 15:18
  • \$\begingroup\$ Actually, Uncaught SyntaxError: Unexpected token with. Can you post a working snippet? \$\endgroup\$ Oct 21, 2016 at 15:21
  • \$\begingroup\$ @BassdropCumberwubwubwub If you want to name the lambda you need to put the assignment after the with(Math), or use f=eval("with(Math)(v,d)=>max(...a)))"). \$\endgroup\$
    – Neil
    Oct 21, 2016 at 15:43
4
\$\begingroup\$

Python, 60 bytes

Saving 5 bytes thanks to Neil

f=lambda v,d:v and max(max(v[:d])-min(v[:d]),f(v[1:],d))or 0

My first recursive lambda!

Usage:

print f([6,9,4,7,4,1], 3)
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I think you can just use v and; the range isn't going up if you remove elements. \$\endgroup\$
    – Neil
    Oct 21, 2016 at 14:48
4
\$\begingroup\$

Perl, 48 bytes

Includes +5 for -0pi

Give the width after the -i option, give the elements as separate lines on STDIN:

perl -0pi3 -e '/(^.*\n){1,$^I}(?{\$F[abs$1-$&]})\A/m;$_=$#F'
6
9
4
7
4
1
^D

Just the code:

/(^.*\n){1,$^I}(?{\$F[abs$1-$&]})\A/m;$_=$#F

(use a literal \n for the claimed score)

\$\endgroup\$
7
  • \$\begingroup\$ I see a regex, and then I get lost. 0.0 What's going on here? \$\endgroup\$ Oct 21, 2016 at 19:09
  • \$\begingroup\$ @VTCAKAVSMoACE Basically I match 1 to width consecutive lines. $& will contain the whole match which will evaluate as the first number in arithmetic context. $1 will contain the last number. I then forcefully fail the regex with \A. So it will try all starting positions and lengths up to width. I use absolute value of the difference as an array index and see how big the array grows. Perl has no builtin max so I have to improvise \$\endgroup\$
    – Ton Hospel
    Oct 21, 2016 at 19:13
  • \$\begingroup\$ That's extremely clever. Any way you can put the -0pi3 -e into -0pi3e? Just an assumption about a possible reduction, I don't use perl (thus my question). \$\endgroup\$ Oct 21, 2016 at 19:16
  • \$\begingroup\$ @VTCAKAVSMoACE No unfortunately. -i eats everything after it as its value, including any e \$\endgroup\$
    – Ton Hospel
    Oct 21, 2016 at 19:18
  • \$\begingroup\$ And I'm assuming that -e has to go just before the code? Bummer. \$\endgroup\$ Oct 21, 2016 at 19:21
4
\$\begingroup\$

R, 63 62 56 bytes

Billywob has already provided a great R answer using only the base functions. However, I wanted to see if an alternative approach was possible, perhaps using some of R's extensive packages. There's a nice function rollapply in the zoo package designed to apply a function to a rolling window of an array, so that fits our purposes well. We use rollapply to find the max of each window, and we use it again to find the min of each window. Then we take the difference between the maxes and mins, which gives us the deviation for each window, and then return the max of those.

function(v,d)max((r=zoo::rollapply)(v,d,max)-r(v,d,min))
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Nice, I knew there was a function for generating the subsequences but couldn't find it. Also behind a proxy at work so can't use any external packages. \$\endgroup\$
    – Billywob
    Oct 21, 2016 at 15:25
  • 1
    \$\begingroup\$ Some googling informs me that there's also gtools::rolling, but that's one more byte and I'm not familiar with it. I'm always in two minds about using non-base packages: on the one hand, it feels like cheating when there's a simple solution; on the other hand, the packages (and the community) are one of R's strengths as a language, I think. \$\endgroup\$
    – rturnbull
    Oct 21, 2016 at 15:30
4
\$\begingroup\$

Husk, 13 7 bytes

▲m§-▼▲X

Try it online!

-6 bytes from Jo King.

Explanation

▲m§-▼▲X Slices of length n
 m      map to
  §-    difference between
    ▼▲  min and max
▲       take the maximum of that
   
\$\endgroup\$
1
  • \$\begingroup\$ @JoKing Imagine reading documentation \$\endgroup\$
    – Razetime
    Oct 6, 2020 at 10:01
3
\$\begingroup\$

R, 80 77 bytes bytes

Edit: Saved 3 bytes thanks to @rturnbull

function(s,d)max(sapply(d:sum(1|s)-d+1,function(i)diff(range(s[i:(i+d-1)]))))
\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can replace 1:(length(s)-d+1) with d:sum(1|s)-d+1. \$\endgroup\$
    – rturnbull
    Oct 21, 2016 at 14:44
  • \$\begingroup\$ @rturnbull Nice catch! \$\endgroup\$
    – Billywob
    Oct 21, 2016 at 14:47
3
\$\begingroup\$

Mathematica, 41 37 bytes

Max[MovingMap[MinMax,#,#2-1].{-1,1}]&
\$\endgroup\$
3
  • \$\begingroup\$ Couldn't you use the dot product with {-1,1} to avoid the Abs? \$\endgroup\$
    – miles
    Oct 21, 2016 at 19:16
  • \$\begingroup\$ @miles Thanks! Edited answer. \$\endgroup\$ Oct 22, 2016 at 2:55
  • \$\begingroup\$ @JHM One byte saved with Max[BlockMap[MinMax,#,#2,1].{-1,1}]&. \$\endgroup\$
    – user48818
    Oct 23, 2016 at 22:11
2
\$\begingroup\$

PowerShell v2+, 68 bytes

param($v,$d)($v|%{($x=$v[$i..($i+++$d-1)]|sort)[-1]-$x[0]}|sort)[-1]

Iterative solution. Loops through $v, but really we're just using that as a counter rather than actually going through the values. Each iteration, we're slicing $v by $i..($i+++$d-1), where $i defaults to 0. We |sort those elements, and store the result into $x. Then we take the biggest [-1] and subtract the smallest [0]. We then |sort those results and take the biggest [-1] of that. That number is left on the pipeline and output is implicit.

Examples

PS C:\Tools\Scripts\golfing> .\find-the-maximum-deviation.ps1 @(6,9,4,7,4,1) 3
6

PS C:\Tools\Scripts\golfing> .\find-the-maximum-deviation.ps1 @(1,2,3,4,5,6) 3
2

PS C:\Tools\Scripts\golfing> .\find-the-maximum-deviation.ps1 @(7,2,3,4,5,6) 3
5
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 12 10 bytes

Uses CP-1252 encoding.

Œù€{øÀ`-ÄZ

Try it online!

Explanation

Π             # sublists of v
 ù             # of length d
  €{           # sort each
    ø          # zip
     À         # rotate left (last 2 lists will be largest and smallest)
      `        # flatten (lists with smallest and largest item will be on top)
       -       # subtract largest from smallest
        Ä      # take absolute value (as we will have negatives after the previous step)
         Z     # take the largest
\$\endgroup\$
2
\$\begingroup\$

Scala, 48 bytes

(_:Seq[Int])sliding(_:Int)map(s=>s.max-s.min)max

Ungolfed:

(a:Seq[Int],d:Int)=>a.sliding(d).map(s=>s.max-s.min).max

Explanation:

(_:Seq[Int])   //define a function with a seq of ints as an argument
sliding(_:Int) //get the sequences with the length of an int argument
map(s=>        //map each sequence
  s.max-s.min    //to its deviation
)max           //and take the maximum value
\$\endgroup\$
2
\$\begingroup\$

Java 8, 140 128

Shaved a bunch off, in part thanks to VTCAKAVSMoACE.

int l(int[]a,int d){int x=0,i=0,f,j,k;for(;i<=a.length-d;i++)for(j=i;j<i+d;j++)for(k=i;k<i+d;)x=(f=a[j]-a[k++])>x?f:x;return x;}

Ungolfed

int l(int[]a,int d){
    int x=0,i=0,f,j,k;
    for(;i<=a.length-d;i++)
        for(j=i;j<i+d;j++)
            for(k=i;k<i+d;)
                x=(f=a[j]-a[k++])>x?f:x;
    return x;
}
\$\endgroup\$
6
  • \$\begingroup\$ You're missing a end bracket. ;) \$\endgroup\$ Oct 21, 2016 at 19:20
  • \$\begingroup\$ @VTCAKAVSMoACE oops. Copy and paste error :( \$\endgroup\$
    – dpa97
    Oct 21, 2016 at 19:26
  • 1
    \$\begingroup\$ 5 byte reduction: int l(int[]a,int d){int x=0,i=0,f,j,k;for(;i<=a.length-d;i++)for(j=i;j<i+d;j++)for(k=j;k<i+d;)x=(f=a[j]-a[k++])<0?-f:f>x?f:x;return x;} \$\endgroup\$ Oct 21, 2016 at 19:29
  • \$\begingroup\$ @VTCAKAVSMoACE I don't believe what you have will work- could be wrong. Try switching the 7 and the 1 in the test case. However, I can use it to shave a few off my new idea! \$\endgroup\$
    – dpa97
    Oct 21, 2016 at 19:41
  • 1
    \$\begingroup\$ I got rid of the need for abs (making the algo much worse in the process, of course) by starting k at i as well. Pretty nifty trick having x=(f=...) in the same line, thanks for that \$\endgroup\$
    – dpa97
    Oct 21, 2016 at 19:49
2
\$\begingroup\$

PowerShell, 70 bytes

(0..(-$d+$v.count)|%{$s=$v[$_..($_+$d-1)]|sort;$s[-1]-$s[0]}|sort)[-1]

Try it online!

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 8 bytes

ŒIùεW-}à

Inputs in the order \$v,d\$.

Try it online.

Explanation:

Π      # Get all sublists of the first (implicit) input-list `v`
 Iù     # Only keep those with a length equal to the second input-integer `d`
   ε    # Map over each d-sized sublist:
    W   #  Push the minimum of the current sublist (without popping the list)
     -  #  Subtract this minimum from each value in the list
   }à   # After the map: pop and push the flattened maximum
        # (which is output implicitly as result)

The map εW-} could alternatively be D€ß- for a vectorized subtraction.

\$\endgroup\$
1
\$\begingroup\$

Ruby, 45 bytes

->a,d{a.each_cons(d).map{|b|b.max-b.min}.max}

I feel like this could be a lot better.

\$\endgroup\$
1
\$\begingroup\$

MATLAB with Statistics and Image Processing Toolboxes, 33 bytes

@(v,d)max(range(im2col(v,[1 d])))

This defines an anonymous function. Example use:

>> f = @(v,d)max(range(im2col(v,[1 d])));
>> f([6,9,4,7,4,1], 3)
ans =
     6

You can also try it on Octave at Ideone (but Octave, unlike Matlab, requires explicitly loading the image package).

Explanation

im2col(v,[1 d]))   % Takes overlapping blocks of size d from v, and arranges them as
                   % columns of a matrix
range(...)         % Maximum minus minimum of each column. Gives a row vector
max(...)           % Maximum of the above row vector
\$\endgroup\$
1
\$\begingroup\$

Java 7,159 bytes

Java = expensive(i know it can be golfed much more)

int c(int[]a,int d){int[]b=new int[d];int i,j,s=0;for(i=-1;i<a.length-d;){for(j=++i;j<i+d;)b[i+d-1-j]=a[j++];Arrays.sort(b);s=(j=b[d-1]-b[0])>s?j:s;}return s;}

Ungolfed

static int c ( int []a , int d){
    int []b = new int[ d ];
    int i , j , s = 0 ;
    for ( i = -1 ; i < a.length - d ;) {
        for ( j = ++i ; j < i + d ;)
        b[ i + d - 1 - j ] = a[ j++ ] ;
        Arrays.sort( b ) ;
        s = ( j = b[ d - 1 ] - b[ 0 ] ) > s ? j : s ;
    }
    return s ;
    }
\$\endgroup\$
1
\$\begingroup\$

MATL, 10 bytes

YCS5LY)dX>

Try it online!

Explanation

Consider inputs [6,9,4,7,4,1], 3 as an example.

       % Implicitly take the two inputs: v, d
       % STACK: [6,9,4,7,4,1], 3
YC     % Matrix of overlapping d-blocks of v
       % STACK: [6 9 4 7
                 9 4 7 4
                 4 7 4 1]
S      % Sort each column
       % STACK: [4 4 4 1
                 6 7 4 4
                 9 9 7 7]
5LY)   % Keep first and last rows
       % STACK: [4 4 4 1
                 9 9 7 7]
d      % Differences along each column
       % STACK: [5 5 3 6]
X>     % Maximum
       % STACK: 6
       % Implicitly display
\$\endgroup\$
1
\$\begingroup\$

PHP, 89 87 bytes

for($i=1;$r=array_slice($argv,++$i,$argv[1]);$d=max($r)-min($r))$o=$d>$o?$d:$o;echo+$o;

Not particularly clever or pretty but it works. Use like:

php -r "for($i=1;$r=array_slice($argv,++$i,$argv[1]);$d=max($r)-min($r))$o=$d>$o?$d:$o;echo+$o;" 3 6 9 4 7 1

for v=6,9,4,7,4,1, d=3

Edit: 2 bytes saved thanks to Jörg Hülsermann

\$\endgroup\$
1
  • \$\begingroup\$ echo+$o; instead of echo$o?:0; \$\endgroup\$ Oct 23, 2016 at 11:46
1
\$\begingroup\$

Jelly, 8 bytes

ṡµṂ€ạṀ€Ṁ

Try it online!

Uses the same algorithm as Dyalog APL, but I figured this myself before looking at it.

Explanation:

ṡµṂ€ạṀ€Ṁ ḷ“Main link. Arguments: v d.”
ṡ        ḷ“Overlapping sublists of x of length y.”
 µ       ḷ“Start a new monadic chain.”
  Ṃ€ạṀ€  ḷ“Find the deviation of each of the elements of x.”
       Ṁ ḷ“Take the maximum of x.”

Note: x, y are left, right arguments respectively.

\$\endgroup\$
1
\$\begingroup\$

Brachylog, 10 bytes

s₎ᶠ⟨⌉-⌋⟩ᵐ⌉

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Arturo, 59 bytes

$[a,n][max map 0..-size a n'x[z:a\[x..x+n-1](max z)-min z]]

Try it

\$\endgroup\$
1
\$\begingroup\$

Factor + math.statistics, 32 bytes

[ clump [ range ] map supremum ]

Try it online!

  • clump Get the windows of [first input] of length [second input]
  • [ range ] map Map each window to its 'deviation' (which Factor calls range)
  • supremum Maximum element
\$\endgroup\$
1
\$\begingroup\$

Japt -h, 12 bytes

ãV mÍ®Ì-ZÎÃÍ

Try it

ãV     # subsequences of length V
mÍ     # sort each, ascending
®Ì-ZÎà # map each to last - first
Í      # sort, ascending
# -h flag prints the last element 
\$\endgroup\$
1
\$\begingroup\$

Desmos, 62 58 bytes

r=v[i-d+1...i]
f(v,d)=[r.max-r.minfori=[d...v.length]].max

Try it on Desmos!
-4 bytes thanks to Aiden Chow

\$\endgroup\$
3
  • \$\begingroup\$ 60 bytes \$\endgroup\$
    – Aiden Chow
    Mar 24 at 0:10
  • \$\begingroup\$ Wait actually 58 bytes \$\endgroup\$
    – Aiden Chow
    Mar 24 at 0:13
  • \$\begingroup\$ You didn't change the code box. It's still the same as your original answer. \$\endgroup\$
    – Aiden Chow
    Mar 24 at 7:45
1
\$\begingroup\$

Vyxal G, 12 bytes

ÞS'L⁰=;ƛG$g-

Try it Online!

Explanation

ÞS'L⁰=;ƛG$g-  # Implicit input
ÞS            # All sublists of the first input
  '   ;       # Filtered by the following:
   L          #  The length of the sublist
    ⁰=        #  Equals the second input
       ƛ      # Map over the filtered list:
        G     #  Push the maximum of the sublist
         $g   #  Swap and push the minimum
           -  #  Subtract to find the deviation
              # G flag gets the maximum of this list
              # Implicit output
\$\endgroup\$
0
\$\begingroup\$

CJam, 17 bytes

q~ew{$)\(\;-}%:e>

(Also q~ew:$z)\(\;.-:e>)

Try it online!

Explanation

q~                   e# Read the two inputs. Evaluate
  ew                 e# Overlapping blocks
    {       }%       e# For each block
     $               e# Sort
      )              e# Get last element (that is, maximum)
       \(            e# Swap, get first element (minimum)
         \;          e# Swap, delete rest of the block
           -         e# Subtract (maximum minus minimum)
              :e>    e# Maximum of array
\$\endgroup\$
0
\$\begingroup\$

Haskell, 56 bytes

_#[]=0 
d#l|m<-take d l=max(maximum m-minimum m)$d#tail l

Usage example: 3 # [6,9,4,7,4,1] -> 6.

Considering ranges less than d doesn't change the overall maximum, so we can run take d down to the very end of the list (i.e. also include the ranges with the last d-1, d-2, ... 0 elements). The recursion stops with the empty list where we set the deviation to 0.

\$\endgroup\$
0
\$\begingroup\$

Actually, 13 bytes

╗╜@V`;m@M-`MM

Try it online!

-6 bytes from the observation in nimi's Haskell answer, that slices shorter than d don't affect the maximum deviation.

Explanation:

╗╜@V`;m@M-`MM
╗              store d in register 0
 ╜@            push d, swap so v is on top
   V           push all slices of v whose length is in [1, d]
    `;m@M-`M   map (for each slice):
     ;m@M-       get minimum and maximum, subtract min from max
           M  get maximum of list of deviations
\$\endgroup\$
0
\$\begingroup\$

Java, 126 bytes

I got inspired by dpa97's answer and found this:

int f(int v[],int d){int m=0,i=0,j,t,l=v.length;for(;i<l;i++)for(j=i;j<l;j++)m=j-i<d&&(t=Math.abs(v[i]-v[j]))>m?t:m;return m;}

Expanded, golfed and example code

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.