# Seidel Triangle

The Seidel Triangle is a mathematical construction similar to Pascal's Triangle, and is known for it's connection to the Bernoulli numbers.

The first few rows are:

      1
1  1
2  2  1
2  4  5  5
16 16 14 10 5
16 32 46 56 61 61


Each row is generated as follows:

If the row number is even (1-indexed):

• Bring down the first item of the previous row

• Every next item is the sum of the previous item and the item above it

• Duplicate the last item

If the row number is odd:

• Bring down the last item of the previous row

• Going backwards, each item is the sum of the previous item and the item above it

• Duplicate what is now the first item.

Basically, we construct the triangle in a zig-zag pattern:

    1
v
1 > 1
v
2 < 2 < 1
v
2 > 4 > 5 > 5


### The Challenge:

Given n, either as a function argument or from STDIN, print or return either the nth row of the Seidel triangle or the first n rows. You may use either 0 or 1 indexing.

You do not need to handle negative or non-integer input (nor 0, if 1-indexed). You do not have to handle outputs larger than 2147483647 = 2^31 - 1

As this is code-golf, do this in as few bytes as possible.

### Examples:

In these examples the return value is the nth row, 0-indexed.

Input   ->  Output

0           1
1           1 1
2           2 2 1
6           272 272 256 224 178 122 61
13          22368256 44736512 66750976 88057856 108311296 127181312 144361456 159575936 172585936 183194912 191252686 196658216 199360981 199360981

• "You do not have to handle outputs larger than your language's default int type" makes this trivial for languages with only 1-bit ints – ASCII-only Apr 17 '18 at 23:07
• Can the rows be outputted always sorted from small to large? – Angs Apr 17 '18 at 23:15
• @ASCII-only Changed to match C++'s maximum int – Bolce Bussiere Apr 17 '18 at 23:18
• @Angs No, the rows should be ordered as shown – Bolce Bussiere Apr 17 '18 at 23:19
• @ASCII-only That's a default loophole (although IMO it's a bit poorly worded as it depends on what people would consider "reasonable") – user202729 Apr 17 '18 at 23:40

# Brain-Flak, 66 bytes

<>(())<>{({}[()]<(()[{}]<<>{(({}<>{}))<>}>)>)}{}{{}<>{({}<>)<>}}<>


Try it online!

Row is 0-indexed.

# Push 1 (the contents of row 0) on other stack; use implicit zero as parity of current row
<>(())<>

# Do a number of times equal to input:
{({}[()]<

# Subtract the row parity from 1
(()[{}]<

# For each entry in old row:
<>{

# Add to previous entry in new row and push twice
(({}<>{}))<>

}

>)

>)}{}

# If row parity is odd:
{{}

# Reverse stack for output
<>{({}<>)<>}

# Switch stacks for output
}<>


# JavaScript (SpiderMonkey), 67 bytes

This code abuses the sort() method and doesn't work on all engines.

Rows are 0-indexed.

f=(n,a=,r)=>n--?f(n,[...a.map(n=>k+=n,k=0),k].sort(_=>n|r),!r):a


Try it online!

### How?

We conditionally reverse an array by using the sort() method with a callback function that ignores its parameters and returns either 0 or a positive integer. Don't try this at home! This only works reliably on SpiderMonkey.

let A = [1,2,3,4,5] and B = [1,2,3,4,5,6,7,8,9,10,11]

| SpiderMonkey (Firefox)  | V8 (Chrome)             | Chakra (Edge)
-------------+-------------------------+-------------------------+------------------------
A.sort(_=>0) | 1,2,3,4,5               | 1,2,3,4,5               | 1,2,3,4,5
A.sort(_=>1) | 5,4,3,2,1               | 5,4,3,2,1               | 1,2,3,4,5
B.sort(_=>0) | 1,2,3,4,5,6,7,8,9,10,11 | 6,1,3,4,5,2,7,8,9,10,11 | 1,2,3,4,5,6,7,8,9,10,11
B.sort(_=>1) | 11,10,9,8,7,6,5,4,3,2,1 | 6,11,1,10,9,8,7,2,5,4,3 | 1,2,3,4,5,6,7,8,9,10,11


Note that V8 is probably using different sort algorithms depending on the length of the array (less or more than 10 elements).

### Commented

f = (                     // f = recursive function taking:
n,                      //   n   = row counter
a = ,                //   a[] = current row, initialized to 
r                       //   r   = 'reverse' flag, initially undefined
) =>                      //
n-- ?                   // decrement n; if it was not equal to zero:
f(                    //   do a recursive call with:
n,                  //     - the updated value of n
[ ...a.map(n =>     //     - a new array:
k += n, k = 0   //       - made of the cumulative sum of a[]
), k              //         with the last value appended twice
].sort(_ => n | r), //       - reversed if n is not equal to 0 or r is set
!r                  //     - the updated flag r
)                     //   end of recursive call
:                       // else:
a                     //   stop recursion and return a[]

• What spider-monkey specific feature does this use? – Downgoat Apr 18 '18 at 3:50
• @Downgoat It's taking advantage of the specific implementation of sort() in this engine. I've added an explanation. – Arnauld Apr 18 '18 at 7:57

# Perl 6, 52 bytes

{(1,{[[\+] |.reverse,0]}...*)[$_].sort((-1)**$_*-*)}


Try it online!

(cycle[r,id]!!)<*>s
r=reverse
s 0=
s n=let a=zipWith(+)(0:a)$(r.s$n-1)++in a


Just s prints the lines in the zig-zag order, the anonymous function on the first row reverses half of the rows.

Thanks to @nimi for saving 5 bytes!

Try it online!

# Jelly, 12 bytes

1;0SƤUƊ⁸¡U⁸¡


Try it online!

• You could remove the first ⁸ – Jonathan Allan Apr 18 '18 at 18:18

# Python 3, 98 91 bytes

from itertools import*
f=lambda n:n and[*accumulate(f(n-1)[::n&1or-1]+)][::n&1or-1]or


Try it online!

Switching to 0-based row numbering saved 7 bytes.

# Julia 0.6, 85 bytes

r(l,n=cumsum(l))=[n...,n[end]]
w=reverse
f(n)=n<2?:n%2<1?r(f(n-1)):w(r(w(f(n-1))))


Try it online!

This is a recursive solution in Julia. Note that it has 1-based indexing. Hence the tests.

Ungolfed version, to understand the logic:

function new_row(last_row)
new_row = cumsum(last_row)
push!(new_row, new_row[end])
return new_row
end

function triangle(n)
if n == 1
return 
elseif mod(n,2) == 0
return new_row(triangle(n-1))
else
return reverse(new_row(reverse(triangle(n-1))))
end
end


Asa bonus, here's a non-recursive version, but this is longer:

w=reverse;c=cumsum
r(l,i)=i%2<1?c([l...,0]):w(c(w([0,l...])))
f(n,l=)=(for i=2:n l=r(l,i)end;l)


# Python 2, 103 97 bytes

f=lambda n,r=,k=2:n and f(n-1,[sum(r[-2::-1][:i],r[-1])for i in range(k)],k+1)or r[::-(-1)**k]


Try it online!

# Python 2, 106 bytes

def f(n,r=,j=1):
while n:
a=r[-2::-1];r=r[-1:];n-=1;j=-j
for x in a+:r+=[r[-1]+x]
return r[::-j]


Try it online!

Surely, better is possible!

# Python 3, 91 bytes

from numpy import *
s=lambda n:n and cumsum(s(n-1)[::n%2*2-1]+).tolist()[::n%2*2-1]or


Try it online!

• You can remove the space between import and * – 12Me21 Apr 18 '18 at 13:36