How wavy is an array?

Question

A wave of power \$k\$ is an infinite array that looks like \$1,2,\dots,k,k-1,\dots,1,\dots,k,\dots,1,\dots\$, and so on. For example, a wave of power 3 starts with \$1,2,3,2,1,2,3,2,1,...\$, and repeats indefinitely. A wave of power 1 is an infinite array of ones. They happen to be beautifully expressed as $$w_k[t] = k - |(t - 1)\bmod(2k - 2) - k + 1|\text{, 1-indexed}$$

In this challenge, all waves are trimmed to their first \$n\$ elements, where \$n\$ is the length of the input array.

A decomposition of an array into waves is an array of coefficients of length \$n\$ such that the original array equals the sum of the waves multiplied by their corresponding coefficients. Formally, if the original array is \$A\$, the decomposition is an array \$B\$ such that for any \$i\$ (\$1 \le i \le n\$) the following equality holds: $$A[i] = \sum_{j=1}^\infty B[j] \cdot w_j[i]\text{, 1-indexed}$$

The waviness of an array is the index of the last non-zero value in its decomposition into waves.

The task is, given a positive integer array of length \$n\$, to calculate its waviness. Note that the decomposition can still include non-integer and negative numbers.

Test cases

All test cases below are 1-indexed. Your solution may use 0-indexing instead.

[1, 1, 1] -> 1                 (decomposition: [1, 0, 0])
[1, 2, 1] -> 2                 (decomposition: [0, 1, 0])
[1, 2, 3] -> 3                 (decomposition: [0, 0, 1])
[1, 1, 2] -> 3                 (decomposition: [1, -0.5, 0.5])
[1, 3, 3, 3, 1] -> 3           (decomposition: [-1, 1, 1, 0, 0])
[1, 2, 2, 4] -> 4              (decomposition: [0, 0.5, -0.5, 1]
[4, 6, 9, 1, 4, 3, 5] -> 7     (decomposition: [2, -0.5, 5, -5, 6.5, -1, -3]
[4, 6, 9, 1, 4, 3, 5, 7] -> 8  (decomposition: [2, -0.5, 5, -5, 6.5, -1, -10.5, 7.5])

This is tagged code-golf ^{an uncommon justification}, so the shortest answer wins.

Answer 1

JavaScript (ES6),  172 171  169 bytes

The output is 0-indexed.

a=>a.map((_,i)=>(D=m=>+m||m.reduce((s,[v],i)=>s+(i&1?-v:v)*D(m.map(([,...r])=>r).filter(_=>i--)),0))(a.map((v,y)=>a.map((_,x)=>x-i?x-~-Math.abs(y%(2*x)-x):v)))&&(j=i))|j

Try it online!

How?

This is essentially an implementation of Cramer's rule, except that the denominator is not computed.

Given the input vector of length \$n\$, we define \$W_n\$ as the matrix holding the waves, stored column-wise.

Example:

$$W_5=\begin{pmatrix} 1&1&1&1&1\\ 1&2&2&2&2\\ 1&1&3&3&3\\ 1&2&2&4&4\\ 1&1&1&3&5\end{pmatrix}$$

We compute all values \$v_i=\det(M_i)\$ with \$0\le i<n\$, where \$M_i\$ is the matrix formed by replacing the \$i\$-th column of \$W_n\$ with the input vector.

Example:

For the 5^th test case and \$i=3\$, this gives:

$$v_3=\det(M_3)=\begin{vmatrix} 1&1&1&\color{red}1&1\\ 1&2&2&\color{red}3&2\\ 1&1&3&\color{red}3&3\\ 1&2&2&\color{red}3&4\\ 1&1&1&\color{red}1&5\end{vmatrix}=0$$

We return the highest index \$j\$ such that \$v_j\neq0\$.

Commented

The helper function \$D\$ uses Laplace expansion to compute the determinant:

D = m =>                     // m[] = matrix
  +m ||                      // if the matrix is a singleton, return it
  m.reduce((s, [v], i) =>    // otherwise, for each value v at (0, i):
    s                        //   take the previous sum s
    + (i & 1 ? -v : v)       //   based on the parity of i, add either v or -v
    * D(                     //   multiplied by the result of a recursive call:
      m.map(([, ...r]) => r) //     pass m[] with the 1st column removed
      .filter(_ => i--)      //     and the i-th row removed
    ),                       //   end of recursive call
    0                        //   start with sum = 0
  )                          // end of reduce()

The matrix \$M_i\$ is computed with:

a.map((v, y) =>         // for each value v at position y in the input vector a[]:
  a.map((_, x) =>       //   for each value at position x in the input vector a[]:
    x - i ?             //     if this is not the i-th column:
      x -               //       compute the wave of power x+1 at position y:
      ~-Math.abs(       //         x - (|y mod (2*x) - x| - 1)
        y % (2 * x) - x //         (where y mod 0 is coerced to 0)
      )                 //
    :                   //     else:
      v                 //       append the value a[y] of the input vector
  )                     //   end of inner map()
)                       // end of outer map()

Answer 2

APL (Dyalog Unicode), ^{34 33} 27 bytes

⊢{⊢/⍋0≠⍺⌹⍉↑(1+⍵⍴⍳,⊢-⍳)¨⍳⍵}≢

Try it online!

Lots of golfing thanks to ngn.

How it works

g←⊢{⊢/⍋0≠⍺⌹⍉↑(1+⍵⍴⍳,⊢-⍳)¨⍳⍵}≢  Accept a vector V of length N
  ⊢{                       }≢  Call the inner function with ⍺=V, ⍵=N
                         ⍳⍵    Make 0..N-1
             (    ⍳,⊢-⍳)¨      For each i of above, make 0..i-1,i..1 and
              1+⍵⍴               repeat/truncate to length N and +1
         ⍺⌹⍉↑                  Reform above as matrix and solve equations
       0≠                      Test nonzero on each item (nonzero→1, zero→0)
    ⊢/⍋                        Find the last index of 1

---

APL (Dyalog Unicode), ³⁴ 33 bytes

⍴-0(⊥⍨=)⊢⌹∘⍉∘↑1+⍴⍴¨(⊢,1+⌽)∘⍳¨∘⍳∘⍴

Try it online!

Uses ⎕IO←0 and an alternative way to generate the matrix W.

g←⍴-0(⊥⍨=)⊢⌹∘⍉∘↑1+⍴⍴¨(⊢,1+⌽)∘⍳¨∘⍳∘⍴  Accept a vector of length n
                                ⍳∘⍴  Make a vector 0..n-1
                     (⊢,1+⌽)∘⍳¨      For each k of above, chain 0..k-1 and k..1
                  ⍴⍴¨                  and repeat or truncate to length n
                                     The first row has 0 elements, repeat gives n zeros
                1+                   Increment all elements
  ⍴-0(⊥⍨=)⊢⌹∘⍉∘↑                     The rest is the same as the previous answer

---

APL (Dyalog Unicode), 34 bytes

⍴-0(⊥⍨=)⊢⌹∘⍉∘↑⍴⍴¨(⊢,1↓¯1↓⌽)∘⍳¨∘⍳∘⍴

Try it online!

A monadic train that accepts a numeric vector.

How it works

g←⍴-0(⊥⍨=)⊢⌹∘⍉∘↑⍴⍴¨(⊢,1↓¯1↓⌽)∘⍳¨∘⍳∘⍴  Accept a vector of length n
                                 ⍳∘⍴  Make a vector 1..n
                   (⊢,1↓¯1↓⌽)∘⍳¨      For each k of the above, generate one unit of wave of power k (1..k..2)
                ⍴⍴¨                   Repeat or truncate each row to length n (result is nested vector)
             ⍉∘↑                      Convert nested vector to matrix, and transpose it
          ⊢⌹                          Solve the linear equation
    0(⊥⍨=)                            Count trailing zeros
  ⍴-                                  Subtract from n

Basically, this solution uses the same W matrix as Arnauld's submission, solves the linear equation, and then finds the index of the last nonzero entry using the good old "count trailing ones" ⊥⍨.

Answer 3

MATLAB, 111 bytes

function w=f(A)
n=length(A)
W=ones(n,1)
for k=2:n
W(1:n,k)=k-abs(mod(0:n-1,2*k-2)-k+1)
end
w=max(find(W\A))
end

I'm new to this, do MATLAB answers have to be in a function, or can we assume A is set implicitly?

The code is straight-forward. The sum in the OP can be replaced with a simple matrix multiplication, A = W*B. The code computes B = inv(W)*A and finds the index of the last non-zero entry in B. mod(x,0) isn't well-defined, so the first row has to be set manually.