Skip to content

Instantly share code, notes, and snippets.

@ap29600
Created June 5, 2024 11:39
Show Gist options
  • Save ap29600/635caa045da0e58aab3ba75bca29fe70 to your computer and use it in GitHub Desktop.
Save ap29600/635caa045da0e58aab3ba75bca29fe70 to your computer and use it in GitHub Desktop.
A solution to project euler 61 in BQN
n ← 6
k ← 4
d ← ↕n
poly ← (0.5×d+1)≍¨(-0.5×d-1)
limits ← ⌈{a‿b‿c: (2×a)÷˜-b-√(טb)-4×a×c}¨ poly ∾⌜ -10⋆k-1‿0
values ← poly {+´𝕨×(ט𝕩)‿𝕩}¨ {a‿b:<a+↕b-a}˘limits # the numbers to be tested
perm ← (n-1) ∾˘˜ (≍↕0){∾˝(0∾˘1+𝕩)⊸⊏˘⍒˘=⌜˜↕𝕨}´-⟜↕n-1 # distinct cycles of number class
{
x ← 𝕩
w ← / 0‿0 ⍉ ∨˝∘∧⎉1‿∞´ m ← x {(100|𝕨)=⌜⌊𝕩÷100}¨ 1⌽x # adjacency matrices of consecutive number classes
(×≠w)◶@‿{𝕩⋄ # is a cycle possible?
path ← ⟨⊑w⟩
reach ← (⊑w) ⊏˘¨ 1↓mc ← ∨˝∘∧⎉1‿∞˜`⌾⌽ m # progressive reachability
reach {path ∾↩ ⊑/𝕨∧(⊢´path)⊏𝕩}¨ ¯1↓m # find path backwards
•Show +´ path ⊑¨ x
} @
}¨ <˘perm⊏values
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment