A* implementation in BQN

astar.bqn

Heap ⇐ {𝕤
 items ← ⟨⟩
 Lt ← 1+2×⊢ ⋄ Rt ← 2×1+⊢ ⋄ Up ← (⌊÷⟜2)-(¬2⊸|)
 Swap ← {items (⌽⌾(𝕨‿𝕩⊸⊏))↩ ⋄ 𝕩}
 SiftUp ← Swap⟜Up •_while_ {𝕩>0?<○(⊑⊑⟜items)⟜Up 𝕩;0}
 MinChild ← {(Rt𝕩)<≠items? {Lt⊸(<○(⊑⊑⟜items))⟜Rt 𝕩? Lt𝕩; Rt𝕩}𝕩; Lt𝕩}
 SiftDown ← {𝕊:Swap⟜MinChild•_while_{(Lt𝕩)<≠items?>○(⊑⊑⟜items)⟜MinChild 𝕩;0} 0}
 Add ⇐ {items ∾↩ ⟨𝕨‿𝕩⟩ ⋄ SiftUp (≠items)-1 ⋄ @}
 PopMin ⇐ {𝕊: t←⊑items ⋄ 0 Swap ¯1 ⋄ items↓˜↩¯1 ⋄ SiftDown@ ⋄ t}
 Empty ⇐ {𝕊:⟨⟩≡items}
 𝕨 Add¨ 𝕩
}

_path_ ⇐ {
 Moves _𝕣_ Goal s0: 3=•Type goal? Moves _𝕣_ Goal‿0 s0;
 Moves _𝕣_ Goal‿H s0:
 cost‿from‿open ← ⟨⟨s0⟩ •HashMap ⟨0⟩, ⟨⟩ •HashMap ⟨⟩, ⟨0⟩ Heap ⟨s0⟩⟩
 end ← {𝕤
   s ← 1⊑open.PopMin@
   {n‿c:
     d ← c+cost.Get s, 
     {d<∞ cost.Get n? n cost.Set d ⋄ n from.Set s ⋄ (d + H n) open.Add n; @} 
   }˘ (1==)◶⟨⊢,≍⟜1˘⟩ Moves s
   s
 } •_while_ {¬(open.Empty@)∨Goal 𝕩} s0
 {Goal end? (cost.Get end) ⋈ from.Get∘⊑⊸∾ •_while_ (from.Has∘⊑) ⟨end⟩}
}