10
\$\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\$
1
  • \$\begingroup\$ A new Bubbler avatar! \$\endgroup\$
    – Jonah
    Aug 18 at 2:35
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\$
    – Bubbler
    Aug 18 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\$
    – hyper-neutrino
    Aug 18 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\$
    – justhalf
    Aug 19 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\$
    – hyper-neutrino
    Aug 19 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\$
    – Razetime
    Aug 18 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\$
    – emanresu A
    Aug 18 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\$

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.