A coding impromptu

This post is a rolling collection of algorithms and computational ideas I like, implemented in BQN:

Table of Contents

Extrapolating Perlis' remark1, it's likely that a group of 50 individuals would devise 35 to 40 distinct solutions to even the simplest problem in BQN. Therefore, I will frequently juxtapose my implementations with those of seasoned BQNators, acknowledging their contributions in footnotes.

Z algorithm

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 were proposed2 for the function above, 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
}

An array version which I find more beautiful, but has quadratic time complexity is: 

ZAQ ← ¯1↓↓(+´·∧`⊣=≠⊸↑)¨<
ZAQ "abacabadabacaba"

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

I also came up with a cubic solution, but as we will see it can be made quadratic: 

ZAC ← (+´∧`)¨<=↕∘≠{«⍟𝕨𝕩}⌜<
ZAC "abacabadabacaba"

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

Further improvements where proposed by2, 3, rendering the above solutions into: 

ZAC ← (+´∧`)¨≠↑↓=⌽∘↑
ZAC ← (+´∧`)¨<=«⍟(↕∘≠)

Longest increasing sub-sequence

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 and tacit solution was crafted by2, 3: 

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 ⟩

In case you are wondering like I did, the minus one there is to make the bins comparison strictly increasing.

N-queens problem

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.

Footnotes:

1

Almost Perfect Artifacts Improve only in Small Ways: APL is more French than English, Alan J. Perlis (1978). From jsoftware's papers collection.

2

Marshall Lochbaum, the BQN creator.

3

dzaima, the CBQN developer.