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.

• Jonah: A new Bubbler avatar!
• alephalpha: The Euler number used in the Boustrophedon transform is not OEIS A122045 (codegolf.stackexchange.com/q/107558/9288), but OEIS A000111 (codegolf.stackexchange.com/q/248143/9288)

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

• Bubbler: I had R underdot in place of U and last-3-dyad instead of chain separator. Essentially the same thing.
• hyperneutrino: @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
• justhalf: ` 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.
• hyperneutrino: @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.

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

• Razetime: Remove the function prelude for 41

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!

• emanresu A: Oh, using the same function for map and recurse. That's very clever.

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

’1l·_+1l·’}\ð‘ị3ðṛ?
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\$.

’1l·_+1l·’}\ð‘ị3ðṛ? - Helper link. T(n,k).
 ṛ? - If k:
 ð - Then:
’ - n-1
 _ - n-k
 1l· - T(n-1, n-k)
 \ - Last two links as a dyad g(n,k):
 ’} - k-1
 1l· - T(n, k-1)
 + - T(n-1, n-k) + T(n, k-1)
 ð - Else:
 ‘ - n+1 (due to Jelly's 1 indexing)
 ị3 - 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

FA«⊞υιUMυΣ...⮌υ⊕λI✂υ±1

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

FA«

Loop over the input list.

⊞υι

Push the current input value to the Boustrophedon list.

UMυΣ...⮌υ⊕λ

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

I✂υ±1

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

Å»a.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:
 a # 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)