# How wavy is an array?

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 an uncommon justification, so the shortest answer wins.

# APL (Dyalog Unicode), 3433 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), 34 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" ⊥⍨.

• I know 33 is without it, but you might want to remove g← from the leading one. – Ven Oct 21 at 9:09

# 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, where $$\M_i\$$ is the matrix formed by replacing the $$\i\$$-th column of $$\W_n\$$ with the input vector.

Example:

For the 5th 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
)                          // 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()


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