Different Way Forward

Question

Given a list of integers produce a Forward Difference at a specified order/depth.

For the list of integers:

(10, 18, -12, 4, 8, -3, -5, 67, 9, 14)

The Forward Differences at the various orders/depths are:

0   10,   18,  -12,    4,    8,   -3,   -5,  67,  9,  14
1      8,  -30,   16,    4,  -11,   -2,   72, -58,  5
2       -38,   46,  -12,  -15,    9,   74, -130, 63
3           84,  -58,   -3,   24,   65, -204, 193
4            -142,   55,   27,   41, -269, 397
5               197,  -28,   14, -310, 666
6                 -225,   42, -324, 976
7                    267, -366, 1300
8                      -633, 1666
9                         2299

So with the input of

4, (10, 18, -12, 4, 8, -3, -5, 67, 9, 14)

You would return the list

(-142,   55,   27,   41, -269, 397)

Input

The input can be via STDIN or function parameters.

An integer specifying the depth to return. This will be 0 to the length of the list minus 1

A list of integers to calculate the forward difference for

Output

The output can be via STDOUT or returned by the function.

The forward differences for the specified depth as a list of integers

Rules

Built in and 3rd Party functions that do this directly are not allowed.

Standard loophole restrictions apply.

Shortest code wins

Answer 1

J, 15 9 7 bytes

Very easy. Takes depth and list as left and right arguments.

-~/\~&2

As an explicit definition without all the adverbial trickery, this reduces to

4 : '(2 -~/\ ])^:x y'

• -~/\~&2 y – The forwards difference of y.
• x -~/\~&2 y – The x-th forwards difference of y.

If I were to make a serious (i. e. non-golfed) definition of this function, I would probably do something like this:

(}. - }:) : ($:@[&0)

The monadic case computes the forward difference whereas the dyadic case computes the x-th forward difference.

Even simpler, but not exactly equal:

+/\inv

+/\ yields a vector of the sums of the prefixes of the argument. inv (defined as ^:_1) is a conjunction that inverses a verb. This works wherever J knows how to inverse a verb and for the case of +/\, J knows how to.

Answer 2

Python, 61 59 bytes

f=lambda n,L:n and f(n-1,[x-y for x,y in zip(L[1:],L)])or L

Here we perform the subtraction by zipping all but the last of the list with all but the first of the list. zip(L[1:],L) is equivalent to zip(L[1:],L[:-1]), due to zip's nature of taking the minimum length of the two lists:

>>> zip([1,2,3],[4,5])
[(1, 4), (2, 5)]

---

An alternative that's just as long (Python 2 only):

f=lambda n,L:n and f(n-1,map(int.__sub__,L[1:],L[:-1]))or L

Unfortunately Python 2 doesn't cut off the end of the list, so I can't do map(int.__sub__,L,L[1:]). Annoyingly, Python 3 does, but map no longer returns a list so this ends up being a byte more (60 bytes):

f=lambda n,L:n and f(n-1,list(map(int.__sub__,L[1:],L)))or L

However, if we allow the input to be the depth followed by the list like f(3, 2, 5, 6, 7, 5, 10, 25) (i.e. depth 3 and list [2, 5, 6, 7, 5, 10, 25]), then this is 56 bytes:

f=lambda n,*T:n and f(n-1,*map(int.__sub__,T[1:],T))or T

---

Here's another alternative that would really annoy anyone who saw this in production code (this one destroys the original list):

f=lambda n,L:n and f(n-1,[L[1]-L.pop(0)for _ in L[1:]])or L

Answer 3

Mathematica 23 57 23 bytes

Martin Büttner's suggestion, exploiting the listability of subtraction.

 Rest@#-Most@#&~Nest~##&

e.g.

Rest@# - Most@# &~Nest~## & @@ {{10, 18, -12, 4, 8, -3, -5, 67, 9, 14}, 4}

{-142, 55, 27, 41, -269, 397}

---

Rest@#-Most@# carries out the subtraction that yields differences.

Nest performs said operation the specified number of times, operating always on the most recent list.

Answer 4

Haskell, 40 34 bytes

n#l=iterate(zipWith(-)=<<tail)l!!n

Usage example: 4 # [10,18,-12,4,8,-3,-5,67,9,14] which outputs [-142,55,27,41,-269,397].

How it works: repeatedly calculate the difference between neighbor elements and store the intermediate results in a list. Take the nth element from this list.

Edit: @Zgarb found 6 bytes to save. Awesome!

Answer 5

JavaScript (ES6), 52 49 bytes

Simple recursive function, using map to scan the array and slice to drop the first element on each recursive call.

Edit 3 bytes saved, thanks @DocMax, really smart suggestion

F=(n,l)=>n?F(n-1,l.slice(1).map((a,k)=>a-l[k])):l

Test In Firefox/FireBug console

for(i=0;i<10;i++)console.log(F(i,[10, 18, -12, 4, 8, -3, -5, 67, 9, 14]))

[10, 18, -12, 4, 8, -3, -5, 67, 9, 14]
[8, -30, 16, 4, -11, -2, 72, -58, 5]
[-38, 46, -12, -15, 9, 74, -130, 63]
[84, -58, -3, 24, 65, -204, 193]
[-142, 55, 27, 41, -269, 397]
[197, -28, 14, -310, 666]
[-225, 42, -324, 976]
[267, -366, 1300]
[-633, 1666]
[2299]

Answer 6

CJam, 15 bytes

l~{{_@-\}*;]}*p

Takes input as a CJam-style array and then the depth:

[10 18 -12 4 8 -3 -5 67 9 14] 4

and prints the result as a CJam-style array.

Test it here.

Explanation

l~              "Read and eval input.";
  {         }*  "Repeat this block N times, which computes the forward differences.";
   {    }*      "Fold this block onto the list - this is quite an abuse of folding semantics.";
    _           "Duplicate the current element (for the use in the next difference).";
     @          "Pull up the other copy of the last element.";
      -         "Subtract.";
       \        "Swap the difference and the other copy of the current element.";
          ;     "Discard the last element.";
           ]    "Wrap everything in an array again.";

Answer 7

Java, 122 119 bytes

int[]a(int[]a,int b){if(b<1)return a;int e=a.length-1,c[]=new int[e],i=e;for(;i-->0;)c[i]=a[i+1]-a[i];return a(c,b-1);}

Example Usage: http://ideone.com/ALgYez

3 bytes thanks to Geobits :v )>

Answer 8

Python, 70 68 67 59 bytes

f=lambda x,n:n and f([x[1]-x.pop(0)for i in x[1:]],n-1)or x

Non-golfed version before I went recursive:

def f(x,n):
    for j in range(n):
        for i in range(len(x)-1):
            x[i]=x[i+1]-x[i]
    return x[:-n]

Answer 9

><> 53 50 bytes

l:[2-&\~~]r1-:?!vr
&}-@:$/!?&:-1
:;!? &&  lo*84n~<       

Usage: Prepopulate the stack (-v in python interpreter) with depth first, followed by the integers.

For example:

forward.fish -v 3 2 5 6 7 5 10 25

Returns

2 -3 10 3

Thanks to Sp3000 for the help.

Answer 10

Prelude, 95 92 79 78 bytes

?    (1-vv- # ) v  !
  ?     #   ^   #
?(1-)   1  (#)  1)(#)
  1   #(# ) 1  (#

Input format is

N
M
n_1
n_2
...
n_M

where N is the depth of the differences and M is the number of integers in the input. Adding M was necessary, because there's no way for Prelude to distinguish a 0 from the end of the input. Output is also as a newline separated list of integers. I had to assume the slightly adjusted Prelude spec we devised for this challenge, because standard Prelude reads integers as byte values, which makes it impossible to enter negative numbers. Essentially, this is the Python interpreter with an additional NUMERIC_INPUT flag.

For reference there are only 48 38 37 non-space characters - the rest was merely needed to align the code correctly.

Explanation

In Prelude, each line is a separate "voice" that operates on its own stack. The program is executed column by column, where the separate voices are taken to operate "in parallel". All commands are single characters, and parentheses are Brainfuck-like loops (which are entered and repeated whenever the top of the stack is non-zero). Note that the vertical position of the closing parenthesis is irrelevant - putting it in a different voice still counts as matching with the most recent opening parenthesis, and the stack that is checked for the loop condition is always the voice where the ( appeared. Now on to this program...

The program can basically be separated in into two parts. The bottom two lines are merely used for most of the loops in the program (except the main loop over N), passing 1s back and forth. The top two lines contain the main loop and actual differencing. The following annotation has the code transposed, so I can annotate the individual columns:

? ?   # Read two integers. Read instructions are processed top to bottom, so the first voice 
      # reads N and the third voice reads M.
  (   # Start a loop on the third voice. This loop will execute M times, reading the input list
      # and pushing M 1s onto the fourth voice - i.e. a unary representation of M.
 ?11  # Read an integer onto the second voice, push 1s onto the third and fourth voice.
  -   # Subtract the 1 from the third voice, decrementing M down to 0.
  )   # End of loop, if the third voice is not 0 yet, to back two columns.
(     # Start a loop on the first voice. This is the main loop and will execute N times. Each
      # iteration will compute the forward differences once and thereby shorten the list by one
      # element and also reduce the stack of 1s on the bottom voice by one.
1  #  # Push a 1 onto the first voice and pop a 1 from the last. Together with the next column,
      # this decrements both N and (the unary) M.
-  (  # Subtract the 1 from the first voice (decrementing N), and start a loop on the fourth 
      # voice over whatever is left of M (the length of the resulting difference list). Note 
      # that this column is *not* part of the loop, so the - on the first voice will only be 
      # executed once. This loop builds the differences in reverse order on the first voice.
v#1#  # Pop a 1 from the fourth voice and push a 1 onto the third. This loops over M while
      # shifting its unary representation to the other stack. In addition, shift the top stack
      # element from the second to the first voice.
v     # Copy the next element from the second voice to the first, without popping.
-  )  # Subtract the two elements on the first voice and end the loop if the fourth voice is 
      # empty. Note that his column *is* part of the loop.
  (   # Start a loop on the third voice. This is another loop over M, shifting the stack of 1s 
      # back to the fourth voice, and reversing the differences by shifting them onto the 
      # second.
#^#1  # As stated above, shift an element from the first to the second voice, a 1 from the
      # third to the fourth.
  )   # End the loop. After this point, we're back to the original situation, except that the
      # second voice has been replaced by its differences. The bottom stack element the
      # previous list is also still on that stack, but the decreasing loop lengths on the third
      # and fourth voices ensures that this element is never touched again.
)     # End the main loop when N has been reduced to 0.
   (  # Start another loop over the remaining list length, shifting and reversing the result.
v#1#  # Shift a 1 back to the third voice and an element from the second to the first voice.
  )   # End the loop. Note that this parenthesis is not on the same voice as the corresponding
      # opening parenthesis, but its exact position is irrelevant. Moving it to this voice
      # saves a byte.
  (   # Start one last loop over the length of the result.
! #   # Pop a 1 from the third voice while printing (and popping) one element of the result.
  )   # End the loop.

Answer 11

R, 48 39 46 44 bytes

Recursion!

function(x,y)if(x)Recall(x-1,diff(y)) else y

• x is the number of iterations to perform, and y is a vector of integers.
• if(x) is true as long as x>0.
• Recall calls the current function but with new arguments.
• Diff outputs the differences between consecutive list/vector elements.

Previous versions:

#does not work for x=0:
function(x,y){for(i in 1:x)y=diff(y);y}

#does not use diff function:
function(x,y){for(i in 1:x)y=y[-1]-head(y,-1);y}

y[-1]       is a list minus its first element
head(y,-1)  is a list minus its last element

Answer 12

Python, 92 87 86 bytes

def a(b,c):
 if c<1:return b
 d=[];e=b[0]
 for f in b[1:]:d+=f-e,;e=f
 return a(d,c-1)

This is my first Python golf. Any suggestions will be appreciated :)

5 6 bytes thanks to Sp3000 :D

Answer 13

c, 68 55 bytes

f(int *l){for(--l[-1]?f(l):0;*l;l++)*l=l[1]-*l;*--l=0;}

This might be taking liberties with the input spec a bit. An int array is constructed such that element 0 is the depth and elements 1 to (n+1) are the input list elements 0 to n. Then the address of element 1 is passed to the function.

The array must be zero terminated. The array is edited in place.

E.g:

#include <stdio.h>

f(int *l){for(--l[-1]?f(l):0;*l;l++)*l=l[1]-*l;*--l=0;}

int main (int argc, char **argv)
{
  int list[] = {4, 10, 18, -12, 4, 8, -3, -5, 67, 9, 14, 0};
  int *elem;

  f(list + 1);

  for (elem = list + 1; *elem; elem++) {
    printf("%d, ", *elem);
  }
}

http://ideone.com/m5PDgF

Answer 14

Japt -h, 17 5 bytes

12 bytes saved thanks to @Shaggy

VÆ=än

Try it online!

Answer 15

Powershell 115 111 bytes

$p={param($a, $b)0..($a-1)|%{$b=@($l=$b.length;for($i=0;$i-lt$l;$i++){$b[$i+1]-$b[$i]})[0..($l-2)]};$b-join','}

Execute as such:

.$p 4 @(10,18,-12,4,8,-3,-5,67,9,14)

Output:

-142,55,27,41,-269,397

Moving a curly brace to a different spot allows this to display every step to the answer.

8,-30,16,4,-11,-2,72,-58,5
-38,46,-12,-15,9,74,-130,63
84,-58,-3,24,65,-204,193
-142,55,27,41,-269,397

Answer 16

STATA, 126 bytes

di _r(a)_r(b)
token $b
gl $c=wordcount($b)
forv x=1/$a{
gl $c--
forv y=1/$c{
loc `y'=``y'+1'-``y''
}
}
forv z=1/$c{
di ``z''
}

Expects input as an integer representing the depth, followed by a space separated list of integers, both given via the standard prompt. Output is newline separated list of integers.

First it converts the list of integers (which it views as 1 long string) into a list of local variables whose names are 1,2,3,... Then it computes forward differences by setting the value of the yth local variable to be the value of the y+1th local variable minus the value of the yth local variable (i.e. 18-10=8), which overwrites existing values only after use. It does this $a (value of global variable a) times. Then it displays the value of each local variable, 1 at a time.

Answer 17

T-SQL, Too Many :)

When I first saw this problem, I wondered if there was a way to do this in a query. While trivial for most languages, it's not so much for SQL query.

The input goes into variables @ (for depth) and @L for the integer list. @L is a user defined table type

CREATE TYPE L AS TABLE(n INT IDENTITY(0,1),v INT)

Input setup

DECLARE @L L,@ INT=4
INSERT @L(v)values(10),(18),(-12),(4),(8),(-3),(-5),(67),(9),(14)

The query with some comments

WITH R AS( 
    -- Recursive query to calculate the level of a pascal triangle with alternating negatives
    -- For 4 this is 1 -4  6 -4  1  
    SELECT 1c,0g UNION ALL SELECT-c*(@-g)/(g+1),g+1FROM r WHERE g<@
    ),
    O AS( 
    --Multiple N values of list by reversed pascal triangle values
    --shifting the start for each iteration (list length) - N
    SELECT c*v v,F 
    FROM @L L 
        CROSS APPLY(
            SELECT TOP((SELECT COUNT(*)FROM @L)-@)ROW_NUMBER()OVER(ORDER BY(SELECT\))-1F FROM sys.all_views a,sys.all_views b)c 
        JOIN R ON N=F+@-G
    )
-- Sum the multiplied values
SELECT SUM(V)FROM o GROUP BY F ORDER BY F

Result

-142
55
27
41
-269
397

Answer 18

Clojure, 47 bytes

#(if(= 0 %)%2(recur(dec %)(map -(rest %2)%2))))

A simple recursion on anonymous function. You save 1 byte if the order of arguments is swapped as now %2 occurs more frequently than %.

Answer 19

Jelly, 2 bytes

I¡

Try it online!

Explanation

I¡  Main Link
 ¡  Repeat `n` times; this repeats the previous link by <right argument> times
I   Get forward differences

Very straightforward answer :P

Answer 20

SmileBASIC, 76 bytes

Finally a reason to use ARYOP!

DEF F L,D
IF!D THEN@R
DIM B[0]COPY B,L
T=SHIFT(L)ARYOP 1,L,L,B
F L,D-1@R
END

Answer 21

Japt, 7 bytes

A couple of alternatives I'd made available to Luis for his solution.

_än}gNÅ

Try it

10 bytes

ÏÄ<V}f@=än

Try it