A coding impromptu

This is a very efficient procedure that finds prefix strings in linear time. The imperative implementation reads:

ZI ← {𝕊s:
  l‿r‿z ← 0⚇0 0‿0‿s
  z ⊣ {
    v ← r(⊢1⊸+•_while_{(𝕩+𝕨)<≠s ? =´⟨𝕩,𝕩+𝕨⟩⊑¨<s ; 0}<◶({z⊑˜𝕩-l}⌊-+1)‿0)𝕩
    r <◶@‿{𝕊: l↩𝕩-v+1 ⋄ r↩𝕩} 𝕩+v-1
    z v⌾(𝕩⊸⊑)↩
  }¨ ↕≠s
}
ZI "abacabadabacaba"

⟨ 15 0 1 0 3 0 1 0 7 0 1 0 3 0 1 ⟩

Two algorithmic improvements can be made here, namely only iterate over indices where the character found is equal to the first character, and only search to extend the count if it goes up to the end of r:

ZFun ← {𝕊s:
  CountEq ← { 1⊸+•_while_((≠𝕨)⊸≤◶⟨⊑⟜𝕨≡⊑⟜𝕩,0⟩) 0 }
  l←r←0 ⋄ Ulr ← {(r⌈↩𝕨+𝕩)>r ? l↩𝕨 ⋄ 𝕩; 𝕩}
  SearchEq ← ⊣ Ulr ⊢ + + CountEq○(↓⟜s) ⊢
  Set ← {i𝕊𝕩: ((r-i) (i SearchEq 0⌈⊣)⍟≤ (i-l)⊑𝕩)⌾(i⊸⊑) 𝕩 }
  (⌽1↓/⊑⊸=s) Set´˜ ↑˜≠s
}

I came up with two array versions, with quadratic and cubic time complexities respectively:

ZAQ ← ¯1↓↓(+´·∧`⊣=≠⊸↑)¨<
ZAC ← (+´∧`)¨<=↕∘≠{«⍟𝕨𝕩}⌜<
(ZAQ≡ZAC)◶@‿ZAC "abacabadabacaba"

⟨ 15 0 1 0 3 0 1 0 7 0 1 0 3 0 1 ⟩

With further refinements, the earlier solutions can be transformed into:

ZAQ‿ZAC ← {(+´∧`)¨𝕏}¨ ⟨≠↑↓=⌽∘↑, <=«⍟(↕∘≠)⟩

This problem can be solved in \(O(n\log n)\) using dynamic programming. Here is an imperative implementation which is quadratic, but can be optimized:

LISI ← {
  k‿dp ← ¯1‿(∞¨𝕩)
  {i ← ∧´◶(⊑⊐⟜0)‿{𝕊:k+↩1} dp<𝕩 ⋄ dp 𝕩⌾(i⊸⊑)↩}¨ 𝕩
  +´∞>dp
}
LISI¨ ⟨0‿1‿0‿3‿2‿3, 10‿9‿2‿5‿3‿7‿101‿18, 7‿7‿7‿7‿7⟩

⟨ 4 4 1 ⟩

A more elegant array solution is:

LISA ← +´∞≠∞¨{𝕨⌾((⊑𝕩⍋𝕨-1)⊸⊑)𝕩}´⌽
LISA¨ ⟨0‿1‿0‿3‿2‿3, 10‿9‿2‿5‿3‿7‿101‿18, 7‿7‿7‿7‿7⟩

⟨ 4 4 1 ⟩

Let's )explain this optimized version, so we can truly appreciate its beauty:

 +´∞≠∞¨{𝕨⌾((⊑𝕩⍋𝕨-1)⊸⊑)𝕩}´⌽ 
 │ │ │ ││    │ │ │  │ │  │ 
 │ │ │ {┼────┼─┼─┼──┼─┼─´│ 
 │ │ ∞¨ │    │ │ │  │ │ ││ 
 │ │  └─┼────┼─┼─┼──┼─┼─┼⌽ 
 │ ∞≠───┼────┼─┼─┼──┼─┼─┘  
 +´ │   │    │ │ │  │ │    
  └─┘   │    │ │ │  │ │    
        │    │ 𝕨-1  │ │    
        │    𝕩⍋─┘   │ │    
        │   ⊑─┘     │ │    
        │   └──────⊸⊑ │    
        𝕨⌾─────────┘  │    
         ├────────────𝕩    
╶────────┘

The full expression is structured as a two-train: we sum all finite entries from the result of the rightmost three-train. The three-train is a right fold over the reversed input, with an initial array of ∞ and the same length as the input. In each step of the fold, we modify the right argument using under: we perform a binary search with strict comparison to find where the next element should go. The element is either placed at the end of the unfilled region, or it replaces the first element that is greater than 𝕨. Since BQN uses a based array model, we pick the enclosed atom from this operation's result. So it goes³.

This problem is the archetypal example of backtracking. Initially, I tried to solve it using a function to place the queens in the full board, hoping that it would lead to a more array oriented solution:

8 {((∨⌜´0⊸=)∨(0=-⌜´)∨0=+⌜´) 𝕩-¨<↕𝕨} 2‿3

┌─                 
╵ 0 1 0 1 0 1 0 0  
  0 0 1 1 1 0 0 0  
  1 1 1 1 1 1 1 1  
  0 0 1 1 1 0 0 0  
  0 1 0 1 0 1 0 0  
  1 0 0 1 0 0 1 0  
  0 0 0 1 0 0 0 1  
  0 0 0 1 0 0 0 0  
                  ┘

This resulted in a more complicated algorithm, so I decided to go for the classical Wirth implementation:

NQ ← {𝕊n:
  V‿P ← {⊣𝕏(⊢∾-⋈+)´∘⊢}¨ ⟨∨´⊑¨˜, {1⌾(𝕩⊸⊑)𝕨}¨⟩
  {n≠𝕩 ? +´(𝕨V⊢)◶⟨(𝕩+1)𝕊˜𝕨P⊢,0⟩∘(𝕩⋈⊢)¨ ↕n ; 1
  }˜´ (0⋈0×·↕¨⊢∾·⋈˜+˜)n 
}

Which nicely compares with the OEIS sequence:

a000170 ← 1‿0‿0‿2‿10‿4‿40‿92
a000170 ≡ NQ¨ 1+↕8

1

And of course, in the implementation above I could have used a single array instead of three, but I find the resulting validation and position functions very aesthetic the way they are.

The Boyer–Moore algorithm allows for finding the majority element (element that appears more than ⌊𝕩÷2 times in the array) in linear time. If such element exists, then it is equal to the mode of the data, and for this task we have a nice array solution. The original implementation could be expressed as:

BM ← {v←0 ⋄ I←⊢⊣=◶{𝕊:v+↩1}‿{𝕊:v-↩1} ⋄ 0{𝕊:v=0}◶⟨I,I˜⊣⟩´𝕩}
BM 6‿1‿3‿1‿3‿3‿4‿3‿3‿5

3

The previous fold tracks the majority element as state, a more elegant approach maintains the number of votes:

BM ← {e←@ ⋄ 0{𝕩=0 ? e↩𝕨⋄1 ; 𝕩+¯1⋆e≢𝕨}´𝕩 ⋄ e}
BM 6‿1‿3‿1‿3‿3‿4‿3‿3‿5

3

Some time ago, while working on performance optimization of linear algebra operations with Boolean arrays, I encountered an interesting summation property for an array \(a\) of length \(n\):

It turns out that the RHS can be elegantly transformed into a scan, giving rise to a beautiful identity that applies to all natural numbers, not just Booleans as I initially thought:

(+`≡·+´/≤⟜<⊒˜) •rand.Range˜ 1e3

1

This identity holds because ⊒˜ represents the indices i of the list, and since +´(/𝕩)=i ←→ i⊑𝕩, the fold sums all the elements in 𝕩 up to i, for i in the range of the length of the list. Ergo, a scan.

Studying tree algorithms in APL, I learned about the depth vector representation. If the nested object in consideration is a string, the best approach is using boolean masks. However, when dealing with a BQN list, recursion becomes necessary to determine the depth of nested elements. Here’s how it can be implemented:

{=◶⟨⋈0, 1+·∾𝕊¨⟩𝕩} ⟨1, ⟨2, ⟨3⟩, ⟨4, ⟨5, ⟨6, 7⟩⟩⟩⟩, 1⟩

⟨ 1 2 3 3 4 5 5 1 ⟩

This metric is one of the reasons for the deplorable state of modern academia, and the headaches for outsiders trying to get in. Consider that Peter Higgs has an estimated h-index of only 12. By contrast, a random professor nowadays boasts an h-index ten times as high, and exponentially less impact. Enough of ranting, let's concentrate on finding an elegant way to implement this useless thing:

HL ← (+´∘«⊒˜≤+`⌾⌽)·/⁼≠⊸⌊
HS ← +´∨≥1+⊒˜
(HL≡HS)◶@‿HL 14‿14‿11‿9‿5‿5‿1‿1‿1‿1‿0

5

If someone ever published that much, sorting will eventually be slower:

HL‿HS {𝕎•_timed𝕩}¨< 1e8 •rand.Range 1e3

⟨ 0.083824959 0.21801262700000001 ⟩

A testament to the idea that the simplest solution in BQN is often the most efficient: I initially clip my citations array with {≠¨⊔≠∘𝕩¨⌾(≥⟜≠∘𝕩⊸/)𝕩}, which is just /⁼≠⊸⌊.