9
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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), 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" ⊥⍨.

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

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

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.

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