More samples and definitions

author: Marvin Borner 2024-03-25 16:21:54 +0100
committer: Marvin Borner 2024-03-25 16:21:54 +0100
commit: f8398804d351667a7b887b89f6f70c7d5c407d22 (patch)
tree: d33df8e6bbe60640beb9e99c778eb27b1aa77995
parent: 7bfc78b122ad9cbb65eed16f7de4d4021547c2a8 (diff)
12 files changed, 88 insertions, 29 deletions
diff --git a/docs/samples.template b/docs/samples.template
index 80e92b1..e686d34 100644
--- a/docs/samples.template
+++ b/docs/samples.template
@@ -8,7 +8,8 @@
 	</head>
 	<body>
 		<h1>bruijn samples</h1>
-These are some code samples written in the bruijn programming language. Most of the examples are copies of our solutions on <a href="https://rosettacode.org/wiki/Category:Bruijn">Rosetta Code</a>. All examples are written by bruijn's contributors and may be used according to the <a href="https://en.wikipedia.org/wiki/GNU_Free_Documentation_License">GNU FDL license</a>.
+<p>These are some code samples written in the bruijn programming language. Most of the examples are copies of our solutions on <a href="https://rosettacode.org/wiki/Category:Bruijn">Rosetta Code</a>. All examples are written by bruijn's contributors and may be used according to the <a href="https://en.wikipedia.org/wiki/GNU_Free_Documentation_License">GNU FDL license</a>.</p>
+<p>While solutions to the Project Euler puzzles should not be published in general, we may provide bruijn's solutions to the first 100 puzzles for introductory purposes. This is <a href="https://projecteuler.net/about">tolerated by the creators</a>.</p>
 		<ul>
 			LINKS
 		</ul>
diff --git a/samples/euler/009.bruijn b/samples/euler/009.bruijn
index be21d9e..c789719 100644
--- a/samples/euler/009.bruijn
+++ b/samples/euler/009.bruijn
@@ -12,6 +12,6 @@ solve [head <#> lst] → head → tail
 		a 1 - 0
 		b (+2) ⋅ 3 ⋅ 2
 		c 1 + 0
-	lst concat-map [map [check] ({ (+1) → --0 })] ({ (+2) → (sqrt 0) })
+	lst [[check] <$> ({ (+1) → --0 })] <++> ({ (+2) → (sqrt 0) })
 
 main [solve (+1000)]
diff --git a/samples/euler/013-input.bruijn b/samples/euler/013-input
index 43b568e..43b568e 100644
--- a/samples/euler/013-input.bruijn
+++ b/samples/euler/013-input
diff --git a/samples/euler/048.bruijn b/samples/euler/048.bruijn
new file mode 100644
index 0000000..e4f2cbb
--- /dev/null
+++ b/samples/euler/048.bruijn
@@ -0,0 +1,11 @@
+# TODO: also very slow
+
+:import std/Combinator .
+:import std/String .
+:import std/Math .
+
+solve [∑ (+1) → 0 | [pow-mod 0 0 (+10000000000)]]
+
+:test ((solve (+10)) =? (+405071317)) ([[1]])
+
+main [solve (+1000)]
diff --git a/samples/euler/063.bruijn b/samples/euler/063.bruijn
new file mode 100644
index 0000000..eb54a65
--- /dev/null
+++ b/samples/euler/063.bruijn
@@ -0,0 +1,5 @@
+:import std/Combinator .
+:import std/Math .
+:import std/List .
+
+main [∑([y [[0 =? ++(log (+10) (2 ** 0)) (1 ++0) --0]] (+1)] <$> ({ (+1) → (+9) }))]
diff --git a/samples/readme.md b/samples/readme.md
index 57332c1..237dae7 100644
--- a/samples/readme.md
+++ b/samples/readme.md
@@ -4,3 +4,8 @@ Most of the examples are copies of our solutions on [Rosetta
 Code](https://rosettacode.org/wiki/Category:Bruijn). All examples are
 written by bruijn's contributors and may be used according to the GNU
 FDL license (see `license.md`).
+
+While solutions to the Project Euler puzzles should not be published in
+general, we may provide bruijn's solutions to the first 100 puzzles for
+introductory purposes. This is [tolerated by the
+creators](https://projecteuler.net/about).
diff --git a/samples/rosetta/de_bruijn_sequence.bruijn b/samples/rosetta/de_bruijn_sequence.bruijn
index 1012223..967fa72 100644
--- a/samples/rosetta/de_bruijn_sequence.bruijn
+++ b/samples/rosetta/de_bruijn_sequence.bruijn
@@ -2,8 +2,8 @@
 
 :import std/Combinator .
 :import std/Char C
-:import std/Math .
 :import std/List .
+:import std/Math .
 
 # very slow but elegant
 de-bruijn y [[[C.?infix? (take 0 1) ~1 case-end case-rec]]]
diff --git a/std/Math.bruijn b/std/Math.bruijn
index 82a787d..3dcb23b 100644
--- a/std/Math.bruijn
+++ b/std/Math.bruijn
@@ -86,6 +86,13 @@ pow […!!… (iterate (…⋅… 0) (+1))] ⧗ Number → Number → Number
 
 :test (((+2) ** (+3)) =? (+8)) (true)
 
+# modulo exponentiation
+pow-mod [[[(f (2 % 0) 1 (+1)) % 0]]] ⧗ Number → Number → Number → Number
+	f y [[[[=?1 0 rec]]]]
+		rec 3 (2 ⋅ 2 % 4) /²1 (=²?1 0 (2 ⋅ 0 % 4))
+
+:test ((pow-mod (+2) (+3) (+5)) =? (+3)) (true)
+
 # power function using ternary exponentiation (TODO: fix, wrong..)
 pow* z [[[rec]]] ⧗ Number → Number → Number
 	rec =?0 case-end case-pow
@@ -172,6 +179,7 @@ sqrt [z [[[[rec]]]] (+1) 0 0] ⧗ Number → Number
 :test ((sqrt (+9)) =? (+3)) (true)
 
 # integer logarithm
+# TODO: could we somehow use the change-of-base rule and efficient log3?
 log z [[[[rec]]]] (+1) ⧗ Number → Number → Number
 	rec [((3 ≤? 1) ⋀? (1 <? 0)) case-end case-rec] (2 ⋅ 1)
 		case-end (+0)
@@ -185,21 +193,21 @@ log z [[[[rec]]]] (+1) ⧗ Number → Number → Number
 :test ((log (+2) (+48)) =? (+5)) (true)
 
 # iterated logarithm
-# note that log* 1 is defined as 1
-log* [z [[rec]] --0] ⧗ Number → Number
+# note that log! 1 is defined as 1
+log! [z [[rec]] --0] ⧗ Number → Number
 	rec (0 ≤? (+1)) case-end case-rec
 		case-end (+1)
 		case-rec ++(1 (log (+2) 0))
 
-:test ((log* (+1)) =? (+1)) (true)
-:test ((log* (+2)) =? (+1)) (true)
-:test ((log* (+3)) =? (+2)) (true)
-:test ((log* (+4)) =? (+2)) (true)
-:test ((log* (+5)) =? (+3)) (true)
-:test ((log* (+16)) =? (+3)) (true)
-:test ((log* (+17)) =? (+4)) (true)
-:test ((log* (+65536)) =? (+4)) (true)
-:test ((log* (+65537)) =? (+5)) (true)
+:test ((log! (+1)) =? (+1)) (true)
+:test ((log! (+2)) =? (+1)) (true)
+:test ((log! (+3)) =? (+2)) (true)
+:test ((log! (+4)) =? (+2)) (true)
+:test ((log! (+5)) =? (+3)) (true)
+:test ((log! (+16)) =? (+3)) (true)
+:test ((log! (+17)) =? (+4)) (true)
+:test ((log! (+65536)) =? (+4)) (true)
+:test ((log! (+65537)) =? (+5)) (true)
 
 # pascal triangle
 # TODO: something is wrong in here
diff --git a/std/Number.bruijn b/std/Number.bruijn
index 25a1f6c..a99bc19 100644
--- a/std/Number.bruijn
+++ b/std/Number.bruijn
@@ -9,10 +9,10 @@
 # the following functions are only here because of recursive imports of list/ternary
 
 # converts number to list of its digits
-number→list [=?0 {}(+0) <~>(z [[[rec]]] empty 0)] ⧗ Number → (List Number)
+number→list [=?0 {}(+0) (z [[[rec]]] empty 0)] ⧗ Number → (List Number)
 	rec =?0 case-end case-rec
 		case-rec &[[4 (0 : 3) 1]] (quot-rem 0 (+10))
-		case-end empty
+		case-end 1
 
 :test (number→list (+0)) ({}(+0))
 
diff --git a/std/Number/Bruijn.bruijn b/std/Number/Bruijn.bruijn
index 585d3bc..e4d0b36 100644
--- a/std/Number/Bruijn.bruijn
+++ b/std/Number/Bruijn.bruijn
@@ -5,7 +5,7 @@
 # very sad indeed
 
 # increments de Bruijn numeral
-inc [[[2 1]]]
+inc [[[2 1]]] ⧗ Bruijn → Bruijn
 
 ++‣ inc
 
@@ -13,9 +13,18 @@ inc [[[2 1]]]
 :test (++(+5d)) ((+6d))
 
 # decrements de Bruijn numeral
-dec [[1 0 0]]
+dec [[1 0 0]] ⧗ Bruijn → Bruijn
 
 --‣ dec
 
 :test (--(+1d)) ((+0d))
 :test (--(+5d)) ((+4d))
+
+# multiplies de Bruijn numeral with unary number
+mul [[1 0]] ⧗ Unary → Bruijn → Bruijn
+
+…⋅… mul
+
+:test ((+5u) ⋅ (+5d)) ((+25d))
+:test ((+0u) ⋅ (+5d)) ((+0d))
+:test ((+5u) ⋅ (+0d)) ((+0d))
diff --git a/std/Number/Ternary.bruijn b/std/Number/Ternary.bruijn
index 3695740..4eaaf5a 100644
--- a/std/Number/Ternary.bruijn
+++ b/std/Number/Ternary.bruijn
@@ -456,16 +456,16 @@ div² [z [[[[rec]]]] (+0) 0 0] ⧗ Number → Number
 :test (/³*(-6) =? (-2)) (true)
 :test (/³*(+5) =? (+1)) (true)
 
-# ceiled integer log3 by counting number of trits
+# ceiled integer log₃ by counting number of trits
 # also counts leading 0s
-log3* [0 (+0) inc inc inc] ⧗ Number → Number
+log₃* [0 (+0) inc inc inc] ⧗ Number → Number
 
-# ceiled integer log3 by counting number of trits
-log3 log3* ∘ strip ⧗ Number → Number
+# ceiled integer log₃ by counting number of trits
+log₃ log₃* ∘ strip ⧗ Number → Number
 
-:test (log3 (+0)) ((+0))
-:test (log3 (+5)) ((+3))
-:test (log3 (+42)) ((+5))
+:test (log₃ (+0)) ((+0))
+:test (log₃ (+5)) ((+3))
+:test (log₃ (+42)) ((+5))
 
 # returns the smallest number in a range such that a predicate is true
 binary-search z [[[[rec]]]] ⧗ (Number → Boolean) → Number → Number → Number
@@ -487,10 +487,10 @@ ternary-search z [[[[rec]]]] ⧗ (Number → Number) → Number → Number → N
 :test ((ternary-search [-((0 - (+3)) ⋅ (0 - (+3)))] (+0) (+5)) =? (+3)) (true)
 
 # pads a ternary number with 0s until it's as long a another ternary number
-pad y [[[(log3* 0) <? (log3* 1) (2 1 →⁰0) 0]]] ⧗ Number → Number → Number
+pad y [[[(log₃* 0) <? (log₃* 1) (2 1 →⁰0) 0]]] ⧗ Number → Number → Number
 
 # forces number to be exactly n trits long (either pad/trim)
-force [[[0 <? 2 pad trim] (log3* 0)]] ⧗ Number → Number
+force [[[0 <? 2 pad trim] (log₃* 0)]] ⧗ Number → Number
 	pad z [[[=?1 0 (2 --1 →⁰0)]]] (2 - 0) 1
 	trim z [[[=?1 0 (2 --1 ←0)]]] (0 - 2) 1
 
@@ -502,10 +502,10 @@ double-shift [[[[[left : right]] (force 2 1) (force 2 0)]]]
 
 # "efficient" quotient/remainder implementation for balanced ternary
 # technique by Douglas W. Jones
-# algorithm originally intended for fixed-width numbers (=> ugly hacks with force+log3)
+# algorithm originally intended for fixed-width numbers (=> ugly hacks with force+log₃)
 # TODO: remove the final `huh` correction step (probably some off-by-one bug?)
 # TODO: not actually that efficient right now
-quot-rem [[[[[z [[[[rec]]]] 1 (+0) 4]]] <?0 (max (log3 1) (log3 0)) 0]] ⧗ Number → Number → (Pair Number Number)
+quot-rem [[[[[z [[[[rec]]]] 1 (+0) 4]]] <?0 (max (log₃ 1) (log₃ 0)) 0]] ⧗ Number → Number → (Pair Number Number)
 	rec =?2 huh (double-shift 5 1 0 [[compare-case eq gt lt 1 (+0)]])
 		huh (>?1 ⋀? 6) ⋁? (<?1 ⋀? \6) (--0 : (1 + 7)) (0 : 1)
 		eq 5 --4 1 0
diff --git a/std/Number/Unary.bruijn b/std/Number/Unary.bruijn
index 5041614..3b58ceb 100644
--- a/std/Number/Unary.bruijn
+++ b/std/Number/Unary.bruijn
@@ -173,6 +173,26 @@ mod* [[1 &[[(0 ⋀? (2 ≤? 1)) case-rec case-end]] (1 : true) k]] ⧗ Unary →
 	case-rec (1 - 3) : true
 	case-end 1 : false
 
+# returns true if the number is even (remainder mod 2 == 0)
+even? [=?(0 % (+2u))] ⧗ Unary → Boolean
+
+=²?‣ even?
+
+:test (=²?(+0u)) (true)
+:test (=²?(+1u)) (false)
+:test (=²?(+41u)) (false)
+:test (=²?(+42u)) (true)
+
+# returns true if the number is odd (remainder mod 2 == 1)
+odd? ¬‣ ∘ even? ⧗ Unary → Boolean
+
+≠²?‣ odd?
+
+:test (≠²?(+0u)) (false)
+:test (≠²?(+1u)) (true)
+:test (≠²?(+41u)) (true)
+:test (≠²?(+42u)) (false)
+
 # exponentiates two unary number
 # doesn't give correct results for x^0
 pow* [[1 0]] ⧗ Unary → Unary → Unary
author	Marvin Borner	2024-03-25 16:21:54 +0100
committer	Marvin Borner	2024-03-25 16:21:54 +0100
commit	f8398804d351667a7b887b89f6f70c7d5c407d22 (patch)
tree	d33df8e6bbe60640beb9e99c778eb27b1aa77995
parent	7bfc78b122ad9cbb65eed16f7de4d4021547c2a8 (diff)