about summary refs log tree commit diff
path: root/users/sterni
diff options
context:
space:
mode:
authorsterni <sternenseemann@systemli.org>2022-12-20T19·01+0100
committerclbot <clbot@tvl.fyi>2022-12-20T19·08+0000
commitc3be4f6f591cfa8429b3ebffed800513675b72f4 (patch)
treea201b56160fafb414c8e509a0693c27ab1de3531 /users/sterni
parent68555896de3510c560587433acec3470e289c999 (diff)
feat(sterni/aoc/2022): day15 BQN solution r/5432
Part 2 is pretty slow, since we just reuse our fast solution for part 1.
This means we have to check 4000000 which could be reduced a bit by
using a loop. It is tolerably slow, so whatever. (Overall this problem
would have been more fun if the space to check was smaller.)

Change-Id: I1203330fe0364894cfe0318376e583868937b5bd
Reviewed-on: https://cl.tvl.fyi/c/depot/+/7603
Reviewed-by: sterni <sternenseemann@systemli.org>
Autosubmit: sterni <sternenseemann@systemli.org>
Tested-by: BuildkiteCI
Diffstat (limited to 'users/sterni')
-rw-r--r--users/sterni/exercises/aoc/2022/15/15.bqn18
1 files changed, 18 insertions, 0 deletions
diff --git a/users/sterni/exercises/aoc/2022/15/15.bqn b/users/sterni/exercises/aoc/2022/15/15.bqn
new file mode 100644
index 000000000000..e47355856bf8
--- /dev/null
+++ b/users/sterni/exercises/aoc/2022/15/15.bqn
@@ -0,0 +1,18 @@
+lib ← •Import "../../lib.bqn"
+
+F ← ¬∘('-'⊸=∨lib.IsAsciiNum)
+i ← ⌽˘˘∘‿2‿2⥊lib.ReadDec¨>(0⊸<⟜≠¨/⊢)∘((F ¯1˙⍟⊣¨(+`F))⊔⊢)¨ •FLines "input"
+
+ssp ← 4000000
+
+sds ← (⊏˘∾˘(+´˘(|(-˝))˘)) i
+
+# _fix is needed to deal with e.g. ⟨0‿15, 5‿8, 12‿23⟩
+MergeRanges ← ((⊑∾⊑∘⌽)∘∧∘∾)¨∘(+`∘((<∞‿∞)⊸»{<´1‿2⊏𝕨∾𝕩}¨⊢)⊔⊢) lib._fix
+
+Range ← {cky 𝕊 y‿x‿d: x+¯1‿1×d-|cky-y}
+RangesY ← {<˘∧𝕩(⊣Range˘({cky 𝕊 y‿·‿d: d≥|y-cky}˘/⊢))sds}
+OutRangeY ← {(1<≠)◶⟨0˙,𝕩⊸+∘(ssp⊸×⟜(+⟜1))∘(1⊸⊑)∘∾⟩ MergeRanges ssp⌊0⌈RangesY 𝕩}
+
+•Out "day15.1: "∾•Fmt +´-˜´¨MergeRanges RangesY 2÷˜ssp
+•Out "day15.2: "∾•Fmt +´OutRangeY¨↕ssp