Boustrophedon transform

Question

Related: Boustrophedonise, Output the Euler Numbers (Maybe a new golfing opportunity?)

Background

Boustrophedon transform (OEIS Wiki) is a kind of transformation on integer sequences. Given a sequence \$a_n\$, a triangular grid of numbers \$T_{n,k}\$ is formed through the following procedure, generating each row of numbers in the back-and-forth manner:

$$ \swarrow \color{red}{T_{0,0}} = a_0\\ \color{red}{T_{1,0}} = a_1 \rightarrow \color{red}{T_{1,1}} = T_{1,0}+T_{0,0} \searrow \\ \swarrow \color{red}{T_{2,2}} = T_{1,0}+T_{2,1} \leftarrow \color{red}{T_{2,1}} = T_{1,1}+T_{2,0} \leftarrow \color{red}{T_{2,0}} = a_2 \\ \color{red}{T_{3,0}} = a_3 \rightarrow \color{red}{T_{3,1}} = T_{3,0} + T_{2,2} \rightarrow \color{red}{T_{3,2}} = T_{3,1} + T_{2,1} \rightarrow \color{red}{T_{3,3}} = T_{3,2} + T_{2,0} \\ \cdots $$

In short, \$T_{n,k}\$ is defined via the following recurrence relation:

$$ \begin{align} T_{n,0} &= a_n \\ T_{n,k} &= T_{n,k-1} + T_{n-1,n-k} \quad \text{if} \; 0<k\le n \end{align} $$

Then the Boustrophedon transform \$b_n\$ of the input sequence \$a_n\$ is defined as \$b_n = T_{n,n}\$.

More information (explicit formula of coefficients and a PARI/gp program) can be found in the OEIS Wiki page linked above.

Task

Given a finite integer sequence, compute its Boustrophedon transform.

Standard code-golf rules apply. The shortest code in bytes wins.

Test cases

[10] -> [10]
[0, 1, 2, 3, 4] -> [0, 1, 4, 12, 36]
[0, 1, -1, 2, -3, 5, -8] -> [0, 1, 1, 2, 7, 15, 78]
[1, -1, 1, -1, 1, -1, 1, -1] -> [1, 0, 0, 1, 0, 5, 10, 61]

Brownie points for beating or matching my 10 bytes in ngn/k or 7 bytes in Jelly.

Answer 1

Jelly, 7 bytes

;Uĵ\Ṫ€

Try It Online!

Given the previous row, we can reverse it, append it to the next element in the source list, and cumulatively sum. (Reverse + append-to is the same as append + reverse)

Therefore:

;Uĵ\Ṫ€    Main Link
    \      Cumulatively reduce the source list; each time, with the
           last row as the left and the next element as the right:
;          Append the element to the last row
 U         Reverse the whole thing
  Ä        Cumulative sum
     Ṫ€    Get the last element of each

Answer 2

K (oK), 47 42 41 bytes

f:{i{$[y;o[x;y-1]+o[x-1;x-y];a x]}'i:!#a:x}

Try it online!

A function taking an array of numbers. -5 thanks to ngn. -1 thanks to Razetime.

{                          // A function returning...
  {                        // A function, returning
    $[                     // A switch statemnet
      y;                   // If y (second arg) is nonzero
      o[x;y-1]+o[x-1;x-y]; // Do a recursive call
      a x                  // Else index x into a
    ]       
  }'i:                     // Call with the first argument as both arguments
  '!#a:x}                    // Map this over a range of the same length as the input, which we also assign to a for later use

Answer 3

JavaScript (ES6), 56 bytes

a=>a.map(g=(k,n,x)=>x?g(n,n):k?g(k-1,n)+g(n-k,n-1):a[n])

Try it online!

Answer 4

JavaScript (Node.js), 59 bytes

a=>a.map((_,i)=>(T=(n,k)=>k?T(n,k-1)+T(n-1,n-k):a[n])(i,i))

Try it online!

Copying the formula described in the question.

a => a.map(                           // Map a
  (_, i) =>                           // By index, we don't care about the content of a, just that it's the right length
  ( T = (n, k) =>                     // Declare a function T, taking n and k
      k ?                             // If k is nonzero...
        T(n, k - 1) + T(n - 1, n - k) // Do a recursive call
      : a[n]                          // Else index n into a
  )(i, i))                            // Call this function with i,i as arguments.

Answer 5

Jelly, 22 bytes

’1ŀ_+1ŀ’}¥ð‘ị³ðṛ?
J’Ç€

Try it online!

Horrible recursive definition, I'm sure there's a better approach. Full program. Here's a modified version to run as a test suite.

How it works

We just implement

$$T(n,k) = \begin{cases} a_n & \text{if } k = 0 \\ T(n-1,n-k) + T(n, k-1) & \text{otherwise} \end{cases}$$

then calculate \$T(i,i)\$ for each index \$i\$ of \$a\$

The first line defines \$T(n,k)\$, and the second calculates \$T(i,i)\$ for each index \$i\$.

’1ŀ_+1ŀ’}¥ð‘ị³ðṛ? - Helper link. T(n,k).
               ṛ? - If k:
          ð       -   Then:
’                 -     n-1
   _              -     n-k
 1ŀ               -     T(n-1, n-k)
         ¥        -     Last two links as a dyad g(n,k):
       ’}         -       k-1
     1ŀ           -       T(n, k-1)
    +             -     T(n-1, n-k) + T(n, k-1)
              ð   -   Else:
           ‘      -     n+1 (due to Jelly's 1 indexing)
            ị³    -     Index into a

J’Ç€ - Main link. Takes a on the left
J    - Indices of a
 ’   - Decrement to 0 index
   € - Over each index i:
  Ç  -   Yield T(i,i)

Answer 6

Charcoal, 20 bytes

ＦＡ«⊞υιＵＭυΣ…⮌υ⊕λＩ✂υ±¹

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

ＦＡ«

Loop over the input list.

⊞υι

Push the current input value to the Boustrophedon list.

ＵＭυΣ…⮌υ⊕λ

Take the sums of all the nontrivial suffixes of the list to produce the new list.

Ｉ✂υ±¹

Output the last member of the new list on its own line.

Answer 7

Ruby, 62 bytes

->l{l.size.times.map &g=->n,k=n{k<1?l[n]:g[n,k-1]+g[n-1,n-k]}}

Try it online!

Answer 8

05AB1E, 9 bytes

Å»ª.sO}€θ

Port of @hyper-neutrino♦'s Jelly answer, so make sure to upvote him!

Try it online or verify all test cases.

Explanation:

Å»      # Cumulative left-reduce the (implicit) input-list by:
  ª     #  Appending the current item to the list
   .s   #  Get the suffices of this list
     O  #  Sum each inner list together
 }€θ    # After the reduce, only leave the last element of each inner list
        # (after which the list is output implicitly as result)