28
\$\begingroup\$

Ken Iverson, 1920–2020
(0,x)-(x,0)

Let's implement his favourite expression:

Given a row of Pascal's triangle, compute the next row.

This can for example be computed by taking the input padded with a zero on the left, and the input padded with a zero on the right, and then adding the two element-by-element.

Test cases

[1] → [1,1]

[1,1] → [1,2,1]

[1,2,1] → [1,3,3,1]

[1,10,45,120,210,252,210,120,45,10,1] → [1,11,55,165,330,462,462,330,165,55,11,1]

[1,50,1225,19600,230300,2118760,15890700,99884400,536878650,2505433700,10272278170,37353738800,121399651100,354860518600,937845656300,2250829575120,4923689695575,9847379391150,18053528883775,30405943383200,47129212243960,67327446062800,88749815264600,108043253365600,121548660036300,126410606437752,121548660036300,108043253365600,88749815264600,67327446062800,47129212243960,30405943383200,18053528883775,9847379391150,4923689695575,2250829575120,937845656300,354860518600,121399651100,37353738800,10272278170,2505433700,536878650,99884400,15890700,2118760,230300,19600,1225,50,1] → [1,51,1275,20825,249900,2349060,18009460,115775100,636763050,3042312350,12777711870,47626016970,158753389900,476260169700,1292706174900,3188675231420,7174519270695,14771069086725,27900908274925,48459472266975,77535155627160,114456658306760,156077261327400,196793068630200,229591913401900,247959266474052,247959266474052,229591913401900,196793068630200,156077261327400,114456658306760,77535155627160,48459472266975,27900908274925,14771069086725,7174519270695,3188675231420,1292706174900,476260169700,158753389900,47626016970,12777711870,3042312350,636763050,115775100,18009460,2349060,249900,20825,1275,51,1]

Improve this question
\$\endgroup\$

28 Answers 28

Active Oldest Votes
9
\$\begingroup\$

Python 2, 34 bytes

lambda l:map(sum,zip(l+[0],[0]+l))

Try it online!

37 bytes

lambda l:map(int.__add__,l+[0],[0]+l)

Try it online!

Python 2, 38 bytes

p=0
for x in input()+[0]:print x+p;p=x

Try it online!

Python 3.8 (pre-release), 37 bytes

lambda l,p=0:[p+(p:=x)for x in l]+[1]

Try it online!

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Pre-release? Python 3.8 was released last year, and Python 3.9 was released a couple of months ago. \$\endgroup\$ – chepner Dec 17 '20 at 23:43
  • \$\begingroup\$ @chepner The version on TIO is the pre-release, so that is correct... \$\endgroup\$ – ASCII-only Dec 19 '20 at 1:02
7
\$\begingroup\$

APL (Dyalog Unicode), 7 bytes

+∘⌽⍨0,⊢

Try it online!

Prepend a zero, and add the mirrored array:

1 4 6 4 1
→ 0 1 4 6 4 1 + 1 4 6 4 1 0
→ 1 5 10 10 5 1

APL (Dyalog Unicode), 7 bytes

0∘,+,∘0

Try it online!

Just realized that the straightforward translation of Iverson's expression is short enough.

APL (Dyalog Extended), 5 bytes

…⍤≢!≢

Try it online!

Ignore the content, take the length (n) and evaluate all binomials from nC0 to nCn. In APL, nCk is k!n, and …n gives 0..n.

Improve this answer
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Oh wow, that Extended solution is clever! \$\endgroup\$ – Adám Dec 17 '20 at 8:54
7
\$\begingroup\$

Jelly, 2 bytes

Ż+

A monadic Link accepting a list of integers which yields a list of integers.

Try it online!

How?

Pretty simple in Jelly to go with the method given in the OP, although we do not need to right-pad with a zero since it is implicit in vectorised addition:

Ż+ - Link: list, R           e.g. [ 1, 4, 6, 4, 1]
Ż  - prepend a zero (to R)        [ 0, 1, 4, 6, 4, 1]
 + - addition (vectorises)        [ 1, 5,10,10, 5, 1]
Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ I believe the Ż character is 2 bytes, thus the whole code is 3 bytes, not 2. \$\endgroup\$ – lisyarus Dec 19 '20 at 7:12
  • 2
    \$\begingroup\$ @lisyarus Follow the “bytes” link in the answer header; TLDR, Jelly (and other golfing languages) often use custom code pages to encode their programs. In hex, this program is D2 2B (2 bytes), but Jelly uses the “multi byte” characters to represent the code in a more “readable” format, and so the commands “make sense” (for example, Ż is “prepend zero”) \$\endgroup\$ – caird coinheringaahing Dec 19 '20 at 14:52
  • 1
    \$\begingroup\$ @cairdcoinheringaahing I see, thank you for the explanation! \$\endgroup\$ – lisyarus Dec 19 '20 at 15:38
6
\$\begingroup\$

05AB1E, 5 4 bytes

0šÂ+

Try it online or verify all test cases.

Or alternatively (5 4 bytes):

0š+Ć

-1 byte thanks to @ovs.

Try it online or verify all test cases.

Or yet another alternative (5 bytes):

ü+X.ø

Try it online or verify all test cases.

Explanation:

      # (example input: [1,2,1])

0š    # Prepend a 0 to the (implicit) input-list
      #  STACK: [0,1,2,1]
  Â   # Bifurcate the list; short for Duplicate & Reverse copy
      #  STACK: [0,1,2,1], [1,2,1,0]
   +  # Add the values at the same positions in the two lists together
      #         [0+1,1+2,2+1,1+0]
      #  STACK: [1,3,3,1]
      # (after which the result is output implicitly)

0š    # Prepend a 0 to the (implicit) input-list
      #  STACK: [0,1,2,1]
  +   # Add the values at the same positions in the two lists together, where the second
      # list is the (implicit) input (because the two lists are of different lengths,
      # the trailing item is ignored)
      #         [0+1,1+2,2+1]
      #  STACK: [1,3,3]
   Ć  # Enclose; append its own first item as additional trailing item
      #  STACK: [1,3,3,1]
      # (after which the result is output implicitly)

ü     # For each overlapping pair of the (implicit) input-list:
 +    #  Sum them together
      #         [1+2,2+1]
      #  STACK: [3,3]
  X.ø # Then surround the resulting list with leading/trailing 1
      #  STACK: [1,3,3,1]
      # (after which the result is output implicitly)
Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Your last 5 byter can be 0š+Ć, making use of implicit input \$\endgroup\$ – ovs Dec 17 '20 at 9:16
  • \$\begingroup\$ @ovs Ah smart, thanks! :) \$\endgroup\$ – Kevin Cruijssen Dec 17 '20 at 9:39
5
\$\begingroup\$

Factor, 27 bytes

[ 0 suffix dup reverse v+ ]

Try it online!

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

(Unwrapping) brain, 41 bytes

>>>,[>>,]<<[<<]>>[[-<+>>+<]>>]<[<<]>>[.>>]

Takes input as character codepoints.

Unfortunately, control characters are currently cancelled on most PC's, so I cannot give a legitimate test case in TIO or any other implementation of brain. : /

How?

>>,[>>,]<<[<<]                                  # Store the input on every other cell
               >>[       ]>>]                   # For every number in the input
                  -<+>>+<                       # Distribute the number to adjacent cells                                                                                                          Nothing here...
                             <[<<]>>[.>>]       # Output each sum

Probably my last post of 2020.

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

K (oK), 8 6 bytes

-2 bytes thanks to Adám!

+':|0,

Try it online!

J, 9 7 bytes

-2 bytes thanks to xash!

0&,+,&0

Try it online!

Both translated from Bubbler's APL solution - don't forget to upvote it!

Improve this answer
\$\endgroup\$
4
  • 1
    \$\begingroup\$ oK -2: +':|0, \$\endgroup\$ – Adám Dec 17 '20 at 11:58
  • 2
    \$\begingroup\$ The other 2 in J, both 7 bytes: 0&,+,&0, #!~0,#\ \$\endgroup\$ – xash Dec 17 '20 at 12:00
  • \$\begingroup\$ @Adám Of course! Thank you! \$\endgroup\$ – Galen Ivanov Dec 17 '20 at 12:02
  • \$\begingroup\$ @xash Thank you, this is nice, symmetrical and shorter :) \$\endgroup\$ – Galen Ivanov Dec 17 '20 at 12:06
4
\$\begingroup\$

PowerShell, 30 27 bytes

-3 bytes thanks to mazzy

($x=$args+0)|%{$_+$x[--$i]}

Explanation:

 ($x=$args+0)|%{$_+$x[--$i]}
 ($x=                          #assign to $x
     $args+0)                  #the input array with a 0 appended
             |                 #pipe the result of the assignment
              %{           }   #for each item in the piped input
                $_+            #add to that item
                   $x[    ]    #the item of x
                      --$i     #with index equal to the decrement of i.
                               #negative indices in powershell index from
                               #the end of the array, so -1 is the last item
                               #in the array, -2 is second to last, etc.

                               #implicitly output
Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Thanks! Very nice. The [0] is redundant. Try it online! \$\endgroup\$ – mazzy Dec 17 '20 at 18:03
  • \$\begingroup\$ @mazzy thanks! I couldn't figure out how on earth to pass the array correctly on my PC, but tinkered with it after seeing your TIO and finally figured it out. \$\endgroup\$ – Zaelin Goodman Dec 17 '20 at 18:19
4
\$\begingroup\$

Haskell, 26 25 bytes

o l=zipWith(+)(0:l)l++[1]

Try it online!

  • Saved 1 thanks to @ovs
  • New approach, it essentially do this:
 0[1,2,1] +
[1,2,1]    =
[1,3,3] + 1

Previous version 30 bytes

o=(0#)
x#(v:w)=x+v:v#w
x#_=[x]

Try it online!

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ It needs to be zipWith(+)(0:l)$l++[0], otherwise you append 0 to the result, not the final argument to zipWith. \$\endgroup\$ – chepner Dec 17 '20 at 23:47
  • \$\begingroup\$ @chepner thanks! fixed \$\endgroup\$ – AZTECCO Dec 18 '20 at 6:20
  • \$\begingroup\$ You can remove the $ again and append a 1 instead of a 0: o l=zipWith(+)(0:l)l++[1] \$\endgroup\$ – ovs Dec 18 '20 at 10:03
3
\$\begingroup\$

JavaScript (ES6), 29 bytes

Returns a comma-separated string.

a=>a.map(v=>p+(p=v),p=0)+[,1]

Try it online!

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Jelly, 4 bytes

Ż+Ṛ$

Try it online!

Rip off Translation of Razetime's Husk solution, so be sure to send some upvotes his way.

Improve this answer
\$\endgroup\$
3
  • 2
    \$\begingroup\$ This works exactly like my APL solution +∘⌽⍨0,⊢: 0,⊢ (prepend zero) maps to Ż and +∘⌽⍨ (add reverse to self) maps to +Ṛ$. \$\endgroup\$ – Bubbler Dec 17 '20 at 8:57
  • 2
    \$\begingroup\$ -2 lol \$\endgroup\$ – Razetime Dec 17 '20 at 10:37
  • \$\begingroup\$ @Razetime ...how do I always forget how dyadic vectorization handles mismatches \$\endgroup\$ – Unrelated String Dec 17 '20 at 21:32
3
\$\begingroup\$

R, 21 bytes

c(0,x<-scan())+c(x,0)

Try it online!

Improve this answer
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Same byte count \$\endgroup\$ – Giuseppe Dec 17 '20 at 19:26
  • \$\begingroup\$ @Giuseppe - yeah, but yours is somehow cooler because it exploits a property of 'real' Pascal's triangle rows... Nice! \$\endgroup\$ – Dominic van Essen Dec 17 '20 at 19:51
2
\$\begingroup\$

MATL, 4 bytes

TTY+

Try it online!

How it works

This convolves the input with [1, 1].

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Husk, 4 bytes

Sż+Θ

Try it online!

Explanation

Sz+Θ
S     take the input
   Θ  and itself with 0 prepended
 ż+   and zip with addition, preserving elements
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Really like how this uses the guarantee that the input is, in fact, a row of Pascal's triangle--making it necessarily a palindrome \$\endgroup\$ – Unrelated String Dec 17 '20 at 8:40
2
\$\begingroup\$

Jelly, 4 bytes

LcŻ$

Try it online!

Same length as Unrelated String’s answer but uses a different method

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Red, 37 bytes

func[c][alter c 0 c + reverse copy c]

Try it online!

Takes the input as a vector!

Instead of inserting/appending a zero to the list, I use alter (for -1 byte) - it appends the value to the list if not present and removes it if present - the zero is guaranteed to not be in the list.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Scala 3, 26 bytes

x=>(0::x)zip(x:+0)map(_+_)

Try it online!

Pretty much a literal translation of the original APL expression, albeit more verbose.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Kakoune, 20 bytes

A,0<esc>x_S,
y<a-)>a+<c-r>"<esc>|bc

asciicast

Takes the input in the default buffer, as a sequence of comma-separated list of numbers. Has a trailing newline at the end.

Explanation:

A  <esc>                       *A*ppend the following to the end of the line:
 ,0                            Literal ,0
        x                      Select the whole line, including the newline
         _                     Trim the selection, removing the newline
          S,<ret>              Split the selection on every comma
y                              Copy the contents of every selection to the default "-register
 <a-)>                         Rotate the contents of the selections rightwards
      a       <esc>            Append to every selection:
       +                       Literal +
        <c-r>"                 The contents of the "-register
                   |bc<ret>    Pipe every selection into bc, evaluating it
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 25 bytes (or 14, if phrased as suggested by @att in the comments below)

Prepend[#,0]+Append[#,0]&

And below is a more "Mathematica-like" solution, in that it uses a mathematical primitive most other languages lack. It requires more bytes than the solution above (which is how most Mathematica programmers would probably solve this in the real world anyway).

(n=Length[#];Table[Binomial[n,k],{k,0,n}])&
Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ You can use infix notation for -2 bytes and Join instead of Prepend for -1. Input as a sequence instead for 14 bytes. \$\endgroup\$ – att Dec 18 '20 at 5:16
  • \$\begingroup\$ @att that is beautiful. For those without Mathematica handy, he/she points out that my first solution can be written as {##,0}+{0 ##}&, which is 14 bytes. This expression can then be applied (@@, in Mathematica) to a list of integers representing any row of Pascal's triangle and it will return the next row. \$\endgroup\$ – Michael Stern Dec 18 '20 at 5:24
  • \$\begingroup\$ I'm disappointed that the best Wolfram solution apparently doesn't involve a built-in for the Pascal triangle (or binomial coefficients). \$\endgroup\$ – ceased to turn counterclockwis Dec 19 '20 at 21:28
2
\$\begingroup\$

Wolfram Language (Mathematica), 29 bytes

Tr/@Partition[#,2,1,{2,1},0]&

Try it online!

-3 bytes from @att

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ BlockMap can be used here instead of Partition, but making use of Partition's 4th/5th arguments is shorter still: 29 bytes \$\endgroup\$ – att Dec 18 '20 at 5:20
  • 1
    \$\begingroup\$ Binomial[#,0~Range~#]&[#[[2]]+1]& is 33, but amusing in that it just ignores most of the input and computes the answer from scratch. \$\endgroup\$ – Greg Martin Dec 18 '20 at 20:27
  • 2
    \$\begingroup\$ @GregMartin Unfortunately that fails for an input of {1}, but Binomial[l=Tr[1^#],0~Range~l]& is even shorter at 30 bytes and handles it correctly. \$\endgroup\$ – att Dec 20 '20 at 21:15
1
\$\begingroup\$

Ruby 2.7, 26 bytes

A port of Arnauld's answer in Ruby.

->a,i=0{a.map{i+i=_1}+[1]}

Try it online!

Ruby, 33 bytes

->a{(a+[0]).zip([0]+a).map &:sum}

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

MathGolf, 6 bytes

ê0▌_x+

Port of my 4-bytes 05AB1E program.

Try it online.

Explanation:

ê       # Push all inputs as integer array
 0▌     # Prepend a 0
   _    # Duplicate the list
    x   # Reverse this copy
     +  # Add the values at the same positions in the two lists together
        # (after which the entire stack joined together is output implicitly as result)
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 12 bytes

ＩＥ⊞Ｏθ⁰⁺ι§θ⊖κ

Try it online! Link is to verbose version of code. Explanation:

    θ           Input array
  ⊞Ｏ ⁰          Append literal `0`
 Ｅ              Map over elements
       ι        Current element
      ⁺         Plus
        §θ⊖κ    Previous element (cyclic)
Ｉ               Cast to string
                Implicitly print

Alternative approach, relies on symmetry:

ＩＥ⮌⊞Ｏθ⁰⁺ι§θκ

Try it online! Link is to verbose version of code. Explanation:

     θ          Input array
   ⊞Ｏ ⁰         Append literal `0`
  ⮌             Reverse
 Ｅ              Map over elements
        ι       Current element
       ⁺        Plus
         §θκ    Element from unreversed list
Ｉ               Cast to string
                Implicitly print

In both of the above you can replace ⊞Ｏθ⁰ with θ and prefix ⊞θ⁰ to the start for the same effect.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Retina, 32 bytes

^|$
¶0¶
Lv$`¶\d+¶(\d+)¶
$.(*_$1*

Try it online! Takes each element on a separate line but header and footer of link convert to comma separated and also run a test suite according to the input number of iterations. Explanation:

^|$
¶0¶

Prefix and suffix a 0 to the list. The extra newlines make it easier to match the pairs of numbers.

Lv$`¶\d+¶(\d+)¶

Match each overlapping pair of numbers.

$.(*_$1*

Output the sum of each pair.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Japt, 6 bytes

p0 ä+0

Try it

p0      - appends 0 to input
   ä+0  - appends 0 and sums each consecutive
          pair of elements
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

C# (.NET Core), 98 bytes

IEnumerable<long> p(IEnumerable<long> l)=>l.Concat(new[]{0L}).Zip(new[]{0L}.Concat(l),(a,b)=>a+b);

Try it online!

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ tio.run/… (1 of 2) \$\endgroup\$ – user Dec 18 '20 at 21:58
  • \$\begingroup\$ IwD1qB86Dl3JAisKAUYgIjpwgtDCeQCAoqqOdVF7RNBpoGG4dKKe1FVYNYBCd9iiNstqeMKPQoAwAoXjGOgCkK5xASYqTgpL10Eq99U/yJ@UnzSfQJsAnY41nHu9jvKvRGkcLHq/@kpMLri4ofOX1heoX8s9q@C@OZ6WcRDNQcihI1CdVZyTBrqmr@bc29tUsXl@xq2KQ3yGn73D8Bw. 58 bytes with a lambda. (2 of 2) \$\endgroup\$ – user Dec 18 '20 at 21:58
1
\$\begingroup\$

SNOBOL4 (CSNOBOL4), 58 bytes

N	J =INPUT	:F(O)
	OUTPUT =I + J
	I =J	:(N)
O	OUTPUT =I
END

Try it online!

I/O as numbers separated by newlines.

N	J =INPUT	:F(O)	;* Read input. If none exists, goto O
	OUTPUT =I + J		;* Print I (initially 0) + J
	I =J	:(N)		;* Set I to J and goto N
O	OUTPUT =I		;* print I (always 1), and terminate the program
END
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

CJam, 8 bytes

{_0\+.+}

Anonymous block (equivalent to a function) that takes the input array from the stack and replaces it by the output array.

Try it online! Or verify all test cases.

How it works

{      }   e# Define code block
 _         e# Duplicate
  0        e# Push 0
   \       e# Swap
    +      e# Concatenate. Gives the original array with a 0 prepended
     .+    e# Vectorize addition. Works for arrays with unequal lengths
Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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