# A history of APL in 50 functions
# But they're BQN functions
# Still about APL history though
# Also not all the functions are here yet
# https://www.jsoftware.com/papers/50/
# TODO: 13, 16, 18, 27, 28, 29, 30, 31, 32, 33, 35, 36, 37, 41
# Some of the above are purely speculative snippets on the website, and may not be added to this example.

# Utilities
Words ← (⊢-˜¬×+`)∘=⟜' '⊸⊔  # Split string on spaces
Rand ← •rand.Range

# 0
ArrayLogic ← (>-<)⟜0
! 1‿¯1‿0‿1 ≡ ArrayLogic 5‿¯2.7‿0‿6

# 1
Average ← +´÷≠
! 3 ≡ Average 2‿1‿6

# 2
# x⌹x=x is an alternate way to get the average of vector x.
# There's no reason to do it this way in BQN (or APL, really).

# 3
IndexOfSelfie ← ⊐˜
! 0‿1‿2‿3‿4‿1 ≡ IndexOfSelfie "Selfie"

# 4
BarChart ← ".⎕"⊏˜>⌜⟜(↕⌈´)
! {
  bc ← BarChart 3‿1‿4‿1‿5‿9
  bc ≡ 6‿9⥊"⎕⎕⎕......⎕........⎕⎕⎕⎕.....⎕........⎕⎕⎕⎕⎕....⎕⎕⎕⎕⎕⎕⎕⎕⎕"
}

# 5
ParenthesesNesting ← +`1‿¯1‿0⊏˜"()"⊐⊢
! {
  pn ← ParenthesesNesting "⍵((∇<S),=S,(∇>S))⍵⌷⍨?≢⍵"
  pn ≡ 0‿1‿2‿2‿2‿2‿1‿1‿1‿1‿1‿2‿2‿2‿2‿1‿0‿0‿0‿0‿0‿0‿0
}

# 6
PerfectShuffle ← ⊢⊏˜·⍋∘⍒≠⥊0‿1˙
! "IAJBKCLDMENFOGPHQ" ≡ PerfectShuffle "ABCDEFGHIJKLMNOPQ"

# 7
_quicksort ← {Cmp←𝔽 ⋄ S←{p←𝕩Cmp˜𝕩⊏˜Rand≠𝕩 ⋄ ∾1‿0‿1𝕩{S⍟𝕨𝕗/˜0𝕏p}¨<‿=‿>}⍟(1<≠)}
! 1‿2‿2‿3‿5‿7‿9‿10‿10‿10‿11‿14‿16 ≡ -_quicksort 2‿2‿7‿10‿10‿11‿3‿10‿14‿5‿9‿1‿16
! {
  Cmp ← ≢◶0‿(-´∘⍋∾○<)¨
  srt ← Words "Anna Fi JD Jay Jd John Morten Roger Scott Zeus"
  srt ≡ Cmp _quicksort Words "Fi Jay John Morten Roger JD Jd Anna Scott Zeus"
}

# 8
PascalsTriangle ← {>𝕩↑¨0(∾+∾˜)⍟(↕𝕩)⥊1}
! [1‿0‿0‿0⋄1‿1‿0‿0⋄1‿2‿1‿0⋄1‿3‿3‿1] ≡ PascalsTriangle 4
! 1‿1‿2‿3‿5‿8‿13‿21‿34‿55 ≡ { 𝕩 ↑ +´¨ (+⌜˜↕𝕩) ⊔○⥊ PascalsTriangle 𝕩 } 10

# 9
GoldenRatio ← +⟜÷´¨∘(1↓↑) ⥊⟜1
! 1e¯5 ∧´∘> | (GoldenRatio 16) - 1‿2‿1.5‿1.66667‿1.6‿1.625‿1.61538‿1.61905‿1.61765‿1.61818‿1.61798‿1.61806‿1.61803‿1.61804‿1.61803‿1.61803

# 10
NewtonsMethod ← (2 ÷˜ ⊢ + ÷)´¨∘(1↓↑) ⥊
! 1e¯5 ∧´∘> | (7 NewtonsMethod 2) - 2‿1.5‿1.41667‿1.41422‿1.41421‿1.41421‿1.41421

# 11
InnerProduct ← +˝∘×⎉1‿2
! [2‿3⋄4‿1] ≡ [1‿0⋄¯1‿1] InnerProduct [2‿3⋄6‿4]

# 12
CayleysTheorem ← {R←⥊⊐⊢ ⋄ (R𝕩) ≡ R ⊏˜⌜˜ <˘R𝕩}
! {
  t ← 2‿2⊸⥊¨ (⌽2|⌊∘÷⟜2⍟(↕4))¨ 9‿6‿7‿11‿13‿14
  g ← ≠˝∘∧⎉1‿2⌜˜t
  CayleysTheorem g
}

# 14
IntervalIndex ← 1-˜≠∘⊣(⊣↓⊢⍋⊸⊏+`∘>)⍋∘∾  # Or ⍋, of course
! 0‿2‿3‿2‿4‿1‿0‿2‿¯1 ≡ ¯1‿2‿3‿7‿8.5 IntervalIndex 0‿4‿7‿6‿11‿2‿1‿3‿¯5
! 0‿1‿0‿¯1‿4‿4 ≡ "Fi Jay John Morten Roger" IntervalIndex○Words "JD Jd Geoff Anna Scott Zeus"

# 15
CentralLimit ← { 41 ↑ /⁼ (5×↕40) ⍋ +˝ Rand 𝕩⥊21 }
# 5‿8 ⥊ CentralLimit 10 1e3

# 17
SeventeenTwentyNine ← {F:
  c ← 3⋆˜1+↕200
  t ← (<⌜˜↕200) × +⌜˜c
  d ← ⍷⊸⊐⊸⊔ ⥊t
  ⌊´ ⊑¨ (2=≠¨)⊸/ d
}
# ! 1729 ≡ SeventeenTwentyNine⟨⟩  # slow

# 19
Permutations ← {𝕊0:1‿0⥊0; ∾˝(0∾˘1+𝕊𝕩-1)⊸⊏˘⍒˘=⌜˜↕𝕩}
! (6‿3⥊0‿1‿2‿0‿2‿1‿1‿0‿2‿1‿2‿0‿2‿0‿1‿2‿1‿0) ≡ Permutations 3

# 20
InversePermutation ← ⍋  # Or ⊐⟜(↕≠) or ∾∘⊔
! (↕10) ≡ InversePermutation⊸⊏ 1‿4‿5‿2‿6‿8‿3‿7‿0‿9

# 21
⟨IndexFromPermutation⇐Ifp,PermutationFromIndex⇐Pfi⟩ ← {
  Rfd ← ⊢+´∘>¨¯1↓↓
  Dfr ← (⍋∘⍋∾)´
  Ifp ⇐ {𝕊⁼:𝕨Pfi𝕩; (⌽×`1+»↕≠𝕩) +´∘× Rfd𝕩}
  Pfi ⇐ {𝕊⁼:𝕨Ifp𝕩; w𝕊𝕩: Dfr (1+↕w) (⌽⊣|¯1↓·⌊∘÷`∾˜) 𝕩}
}
! {
  p ← 1‿3‿0‿7‿6‿5‿4‿9‿8‿2
  ! p ≡ 10 PermutationFromIndex i ← IndexFromPermutation p
  ! p ≡ ⊢⌾(10⊸IndexFromPermutation) p
  ! i ≡ ⊢⌾(10⊸PermutationFromIndex) i
}

# 22
Combinations ← {𝕨(=∨0=⊣)◶⟨(0∾˘𝕊⌾(-⟜1))∾1+𝕊⟜(-⟜1), ≍∘↕⊣⟩𝕩}
! (3 Combinations 5) ≡ 10‿3⥊0‿1‿2‿0‿1‿3‿0‿1‿4‿0‿2‿3‿0‿2‿4‿0‿3‿4‿1‿2‿3‿1‿2‿4‿1‿3‿4‿2‿3‿4

# 23
⟨IndexFromCombination⇐Ic,CombinationFromIndex⇐Ci⟩ ← {
  C ← ((-˜+↕∘⊣)÷○(×´1⊸+)↕∘⊣)⚇0  # Combination function (APL's dyadic !)
  Ic ⇐ {
    𝕊⁼: 𝕨Ci𝕩;
    m‿n𝕊𝕩:
    ⊑-˝(m-↕m) +˝∘(C˘) n-(»1+𝕩)∾˘𝕩
  }
  Ci ⇐ {
    𝕊⁼: 𝕨Ic𝕩;
    0‿n𝕊𝕩: ⟨⟩;
    m‿n𝕊𝕩:
    v←+`(m-1)C(1-m)↓⌽↕n
    k←(v>𝕩)⊐1
    k∾(1+k)+(𝕨-1∾1+k)𝕊(𝕩-k⊏0∾v)
  }
}
! 11 ≡ 4‿6 IndexFromCombination 1‿2‿3‿5
! 1‿2‿3‿5 ≡ 4‿6 CombinationFromIndex 11
! 11 ≡ 4‿6 CombinationFromIndex⁼ 4‿6 CombinationFromIndex 11

# 24
SymmetricArray ← ⍉⊸≡ ∧ 1⊸⍉⊸≡
! SymmetricArray +⌜´ 3⥊<2‿3‿7‿11

# 25
NQueens ← {
  Arr ← {>(⊑⊸⊏⟜𝕩∾1⊸⊑)¨/○⥊⟜(↕≢)¬(↕𝕨)∊⎉1𝕩⥊∘+⎉1‿2(-⟜↕¯1⊑≢𝕩)×⌜¯1‿0‿1}
  𝕩 Arr⍟(𝕩-1) ≍˘↕𝕩
}
QueenCheck ← {
  ! 1=≠≢𝕩
  ! (↕≠𝕩)≡∧𝕩
  ! ∧´⥊(=⌜˜↕≠𝕩)≥(|-⌜˜𝕩)=|-⌜˜↕≠𝕩
}
QueenCheck˘ NQueens 8

# 26
KnightsTour ← {
  Kmoves ← {
    t ← (⥊↕𝕩‿𝕩)+⌜<˘8‿2⥊2‿1‿2‿¯1‿1‿2‿1‿¯2‿¯1‿2‿¯1‿¯2‿¯2‿1‿¯2‿¯1
    (∧˝⎉1(>t)∊↕𝕩) /¨○<˘ 𝕩{+⟜(𝕨⊸×)´⌽𝕩}¨t
  }
  m ← >↑˜¨⟜(⌈´≠¨) Kmoves 𝕩
  b ← (𝕩×𝕩)⥊1
  F ← {b↩0⌾(𝕩⊸⊑)b ⋄ (⊑⍋+˝˘(j⊏m)⊏b)⊑j←⊏⟜b⊸/𝕩⊏m}
  𝕩‿𝕩⥊⍋F⍟(↕𝕩⋆2) 0
}
! (KnightsTour 6) ≡ 6‿6⥊0‿9‿20‿35‿6‿11‿21‿32‿7‿10‿19‿26‿8‿1‿34‿25‿12‿5‿33‿22‿31‿16‿27‿18‿2‿15‿24‿29‿4‿13‿23‿30‿3‿14‿17‿28

# 34
_pow ← {𝔽´𝔽˜⍟(/2|⌊∘÷⟜2⍟(↕1+·⌊2⋆⁼⊢)𝕩)𝕨}
! 847288609443 ≡ 3 ×_pow 25

# 38
Hanoi ← {¯1↓(⥊⊢≍⎉0˜≠⥊⊑⊑⟨1‿5‿2⋄0‿3‿4⟩˙)⍟𝕩⥊1}
! 0‿1‿3‿0‿4‿5‿0 ≡ Hanoi 3

# 39
Ack ← {
  0 𝕊 𝕩: 1+𝕩;
  𝕨 𝕊 0: (𝕨-1) 𝕊 1;
  (𝕨-1) 𝕊 𝕨 𝕊 𝕩-1
}
! 9 ≡ 2 Ack 3
! 29 ≡ 3 Ack 2

# 40
# If _H solves the halting problem (𝔽 _H 𝕩 is 1 iff 𝔽𝕩 halts) then the
# following function causes a paradox.
# F←{𝕊 _H 𝕩 ? 𝕊 𝕩; ⟨⟩}

# 42
Minors ← {(/¨≠⟜<↕≠𝕩)(⍉⊏)⎉0‿∞ 𝕩}⎉2⍟2
Minors1 ← {𝕊 mat: >{mat ⍉∘{𝕩/˜¬𝕨=↕≠𝕩}´ ⌽𝕩}¨↕≢𝕩}
! (Minors ≡ Minors1) 3‿4⥊↕12
! (Minors ≡ Minors1) 4‿4⥊'A'+↕26

# 43
S1 ← {
  𝕊 0: ⋈1;
  (0∾t)+(t∾0)× 𝕩-1⊣t←𝕊 𝕩-1
}
S2 ← {
  𝕊 0: ⋈1;
  (0∾t)+(t∾0)×↕𝕩+1⊣t←𝕊 𝕩-1
}
! ⟨ 0, 6, 11, 6, 1 ⟩ ≡ S1 4
! ⟨ 0, 1,  7, 6, 1 ⟩ ≡ S2 4

# 44
XEA ← {(𝕨∾1‿0) {0=⊑𝕩 ? 𝕨; 𝕩 𝕊 𝕨-𝕩×⌊(⊑𝕨)÷⊑𝕩} (𝕩∾0‿1)}
CRT ← {
  m‿r 𝕊 n‿s:
  gcd‿a‿b ← m XEA n
  lcm ← m×n÷gcd
  c ← lcm|gcd÷˜(r×b×n)+(s×a×m)
  ! (r=m|c)∧(s=n|c)
  lcm∾c
}
! 2‿¯1‿1 ≡ 4 XEA 6
! 12‿9 ≡ 4‿1 CRT 6‿3

# 46
Sieve←{
  4≥𝕩 ? 𝕩⥊0‿0‿1‿1;
  𝕊 n:
  r←⌊√n
  p ← 2‿3‿5‿7‿11‿13‿17‿19‿23‿29‿31‿37‿41‿43
  p ↩ (1+(×`p)⊸⍋⌾<n-1)↑p
  b ← 0⌾(1⊸⊑) 1 {m←n⌊𝕨×≠𝕩 ⋄ (m⥊𝕩)>m⥊𝕨↑1}´ ⌽p
  {
    r≥q←b⊸⊐⌾<1 ?
    b 0¨⌾((q∾q×/b↑˜⌈n÷q)⊸⊏)↩
    𝕊 𝕩∾q
  ;
    b 1¨⌾(𝕩⊸⊏)↩
  }p
}
! 2‿3‿5‿7‿11‿13‿17‿19‿23‿29 ≡ /Sieve 30
! 78498 ≡ +´Sieve 1e6

# 47
Pg ← •rand.Deal{
  d ← 𝕩+𝕩
  s ← 𝕩×𝕩
  t ← 𝕩↑˘𝕩‿d⥊(¬d)↑'a'+𝕩𝔽26
  p ← ⍋(𝔽s)+s×/+`(¯1⊸⋆×𝕩-˜⌽)↕d
  (⌽↕𝕩) ⌽⟜{1↓⥊' '≍˘𝕩}˘ 𝕩‿𝕩⥊p⊏⥊t
}
#•Show Pg¨ 4‿5‿6‿7
TestPg ← {n𝕊p:
  ! (>(«∨»)⍟(↕n)1(⊢∾∾)0⥊˜n-1) ≡ ' '≠p
  rows ← (<' '⊸≠⊸/)˘p
  ! ∧´ (<"") (»(∧≡↕∘≠)∘⊒¨⊢) rows
  ! ∧´∊ ¯1⊑rows
}
TestPg⟜Pg¨ 4‿5‿6‿7

# 48
Stick ← {
 c ← 𝕩 •rand.Range 3         # where the car is hidden
 i ← 𝕩 •rand.Range 3         # your initial choice of door
 +´c=i                       # number of cars that you win
}
Change ← {
 c ← 𝕩 •rand.Range 3                      # where the car is hidden
 i ← 𝕩 •rand.Range 3                      # your initial choice of door
 j ← (c×i≠c)+(3|i+1+•rand.Range¨𝕩⥊2)×i=c  # your changed choice
 +´c=j                                    # number of cars that you win
}
#•Show Stick‿Change {𝕎𝕩}¨ 1e6

# 49
# +´(1+↕∞)⋆-s ←→ ×´÷1-(⍭↕∞)⋆-s