14
\$\begingroup\$

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

For more information, see the Wikipedia page on Bernoulli numbers.

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
\$\endgroup\$
  • \$\begingroup\$ "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 \$\endgroup\$ – ASCII-only Apr 17 '18 at 23:07
  • \$\begingroup\$ Can the rows be outputted always sorted from small to large? \$\endgroup\$ – Angs Apr 17 '18 at 23:15
  • \$\begingroup\$ @ASCII-only Changed to match C++'s maximum int \$\endgroup\$ – Bolce Bussiere Apr 17 '18 at 23:18
  • \$\begingroup\$ @Angs No, the rows should be ordered as shown \$\endgroup\$ – Bolce Bussiere Apr 17 '18 at 23:19
  • \$\begingroup\$ @ASCII-only That's a default loophole (although IMO it's a bit poorly worded as it depends on what people would consider "reasonable") \$\endgroup\$ – user202729 Apr 17 '18 at 23:40
7
\$\begingroup\$

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
}<>
\$\endgroup\$
4
\$\begingroup\$

JavaScript (SpiderMonkey), 67 bytes

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

Rows are 0-indexed.

f=(n,a=[1],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 = [1],                //   a[] = current row, initialized to [1]
  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[]
\$\endgroup\$
  • \$\begingroup\$ What spider-monkey specific feature does this use? \$\endgroup\$ – Downgoat Apr 18 '18 at 3:50
  • \$\begingroup\$ @Downgoat It's taking advantage of the specific implementation of sort() in this engine. I've added an explanation. \$\endgroup\$ – Arnauld Apr 18 '18 at 7:57
4
\$\begingroup\$

Perl 6, 52 bytes

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

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Haskell, 89 87 82 bytes

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

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

Jelly, 12 bytes

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ You could remove the first \$\endgroup\$ – Jonathan Allan Apr 18 '18 at 18:18
2
\$\begingroup\$

Python 3, 98 91 bytes

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

Try it online!

Switching to 0-based row numbering saved 7 bytes.

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

Julia 0.6, 85 bytes

r(l,n=cumsum(l))=[n...,n[end]]
w=reverse
f(n)=n<2?[1]: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 [1]
    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=[1])=(for i=2:n l=r(l,i)end;l)
\$\endgroup\$
1
\$\begingroup\$

Python 2, 103 97 bytes

f=lambda n,r=[1],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!

Non-recursive version (easier to read):

Python 2, 106 bytes

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

Try it online!

Surely, better is possible!

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

Python 3, 91 bytes

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

Try it online!

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

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.