12
\$\begingroup\$

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

\$\endgroup\$
2

8 Answers 8

7
\$\begingroup\$

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 
\$\endgroup\$
4
  • 1
    \$\begingroup\$ I had R underdot in place of U and last-3-dyad instead of chain separator. Essentially the same thing. \$\endgroup\$ Commented Aug 18, 2021 at 3:39
  • \$\begingroup\$ @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 \$\endgroup\$ Commented Aug 18, 2021 at 3:44
  • \$\begingroup\$ ` 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. \$\endgroup\$ Commented Aug 19, 2021 at 9:52
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ Commented Aug 19, 2021 at 13:44
4
\$\begingroup\$

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 
\$\endgroup\$
1
  • \$\begingroup\$ Remove the function prelude for 41 \$\endgroup\$ Commented Aug 18, 2021 at 1:47
3
\$\begingroup\$

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!

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

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. 
\$\endgroup\$
1
\$\begingroup\$

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) 
\$\endgroup\$
0
\$\begingroup\$

Charcoal, 20 bytes

FA«⊞υιUMυΣ…⮌υ⊕λI✂υ±¹ 

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✂υ±¹ 

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

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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) 
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.