rosetta/balanced_ternary.bruijn

:import std/Combinator .
:import std/Logic .
:import std/Pair .

# negative trit indicating coefficient of (-1)
t⁻ [[[2]]]

# positive trit indicating coefficient of (+1)
t⁺ [[[1]]]

# zero trit indicating coefficient of 0
t⁰ [[[0]]]

# shifts a negative trit into a balanced ternary number
↑⁻‣ [[[[[2 (4 3 2 1 0)]]]]]

# shifts a positive trit into a balanced ternary number
↑⁺‣ [[[[[1 (4 3 2 1 0)]]]]]

# shifts a zero trit into a balanced ternary number
↑⁰‣ [[[[[0 (4 3 2 1 0)]]]]]

# shifts a specified trit into a balanced ternary number
…↑… [[[[[[5 2 1 0 (4 3 2 1 0)]]]]]]

# negates a balanced ternary number
-‣ [[[[[4 3 1 2 0]]]]]

# increments a balanced ternary number (can introduce leading 0s)
++‣ [~(0 z a⁻ a⁺ a⁰)]
	z (+0) : (+1)
	a⁻ &[[↑⁻1 : ↑⁰1]]
	a⁺ &[[↑⁺1 : ↑⁻0]]
	a⁰ &[[↑⁰1 : ↑⁺1]]

# decrements a balanced ternary number (can introduce leading 0s)
--‣ [~(0 z a⁻ a⁺ a⁰)]
	z (+0) : (-1)
	a⁻ &[[↑⁻1 : ↑⁺0]]
	a⁺ &[[↑⁺1 : ↑⁰1]]
	a⁰ &[[↑⁰1 : ↑⁻1]]

# converts the normal balanced ternary representation into abstract form
→^‣ [0 z a⁻ a⁺ a⁰]
	z (+0)
	a⁻ [[[[[2 4]]]]]
	a⁺ [[[[[1 4]]]]]
	a⁰ [[[[[0 4]]]]]

# converts the abstracted balanced ternary representation back to normal
→_‣ y [[0 z a⁻ a⁺ a⁰]]
	z (+0)
	a⁻ [↑⁻(2 0)]
	a⁺ [↑⁺(2 0)]
	a⁰ [↑⁰(2 0)]

# adds two balanced ternary numbers (can introduce leading 0s)
…+… [[[c (0 z a⁻ a⁺ a⁰)] 1 →^0]]
	b⁻ [1 ↑⁺(3 0 t⁻) ↑⁰(3 0 t⁰) ↑⁻(3 0 t⁰)]
	b⁰ [1 ↑ (3 0 t⁰)]
	b⁺ [1 ↑⁰(3 0 t⁰) ↑⁻(3 0 t⁺) ↑⁺(3 0 t⁰)]
	a⁻ [[[1 (b⁻ 1) b⁻' b⁰ b⁻]]]
		b⁻' [1 ↑⁰(3 0 t⁻) ↑⁻(3 0 t⁰) ↑⁺(3 0 t⁻)]
	a⁺ [[[1 (b⁺ 1) b⁰ b⁺' b⁺]]]
		b⁺' [1 ↑⁺(3 0 t⁰) ↑⁰(3 0 t⁺) ↑⁻(3 0 t⁺)]
	a⁰ [[[1 (b⁰ 1) b⁻ b⁺ b⁰]]]
	z [[0 --(→_1) ++(→_1) →_1]]
	c [[1 0 t⁰]]

# subtracts two balanced ternary numbers (can introduce leading 0s)
…-… [[1 + -0]]

# multiplicates two balanced ternary numbers (can introduce leading 0s)
…⋅… [[1 z a⁻ a⁺ a⁰]]
	z (+0)
	a⁻ [↑⁰0 - 1]
	a⁺ [↑⁰0 + 1]
	a⁰ [↑⁰0]

# true if balanced ternary number is zero
=?‣ [0 true [false] [false] i]

# true if two balanced ternary numbers are equal
# → ignores leading 0s!
…=?… [[[0 z a⁻ a⁺ a⁰] 1 →^0]]
	z [=?(→_0)]
	a⁻ [[0 false [2 0] [false] [false]]]
	a⁺ [[0 false [false] [2 0] [false]]]
	a⁰ [[0 (1 0) [false] [false] [2 0]]]

main [[0]]

# --- tests/examples ---

:test ((-42) + (-1) =? (-43)) (true)
:test ((+1) + (+2) =? (+3)) (true)
:test ((-42) - (-1) =? (-41)) (true)
:test ((+1) - (+2) =? (-1)) (true)
:test ((-1) ⋅ (+42) =? (-42)) (true)
:test ((+3) ⋅ (+11) =? (+33)) (true)