# Boustrophedon transform

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

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.

Given a finite integer sequence, compute its Boustrophedon transform.

Standard rules apply. The shortest code in bytes wins.

## Test cases

 -> 
[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.

# 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

• I had R underdot in place of U and last-3-dyad instead of chain separator. Essentially the same thing. Aug 18, 2021 at 3:39
• @Bubbler Ah, interesting. I usually just throw a µ in before the quick so I can do whatever I want in the link before without needing to worry about how many links to combine, and then can't be bothered to use the combining quick :P and also U is easier to type so I use it whenever there is no difference lol Aug 18, 2021 at 3:44
•  and also U is easier to type. Wait, Jelly coders actually type the code themselves? I thought they are using some other programs to convert them into the right symbols. Aug 19, 2021 at 9:52
• @justhalf usually people just copy-paste it off the wiki; on the JHT site (which I created) you can use alt-enter to combine characters, so for example, I can type R underdot by doing R. and then pressing alt-enter. I still end up copy-pasting a lot because I haven't memorized everything but for really common built-ins I can just type them. Some people also have keyboard layouts (US INTL specifically) that can type all of Jelly's characters. Aug 19, 2021 at 13:44

# K (oK), 4742 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

• Remove the function prelude for 41 Aug 18, 2021 at 1:47

# 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!

• Oh, using the same function for map and recurse. That's very clever. Aug 18, 2021 at 0:28

# 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.


# 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)


# 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.

# 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!

# 05AB1E, 9 bytes

Å»ª.sO}€θ


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

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)