// (c) 2020 Aaron Taylor <ataylor at subgeniuskitty dot com>
// See LICENSE.txt file for copyright and license details.
// =============================================================================
// This program recognizes four types of numbers:
// - Surreal symbols, like those generated by Axiom 1.
// - Surreal numbers, like those selected by Axiom 2.
// - Reduced form numbers, per Definition 7.
// - Named form numbers, which are the equivalence classes induced by
// Definition 6, represented by the first representative reduced
// form number encountered at runtime.
// Although the surrealNumber type can represent any of these four types of
// numbers, the surrealUniverse contains only named form numbers.
// All equality tests (e.g. eq, geq, leq) in this program actually test for
// similarity per Definition 6.
// =============================================================================
type surrealUniverse
struct {
// The elements in this slice are stored in order according to Axiom 3.
// Thus, numbers[0] < numbers[1] < ... < numbers[n].
func (u
*surrealUniverse
) getIndex(num surrealNumber
) int {
for i
:= 0; i
< len(u
.numbers
); i
++ {
if num
.identifier
== u
.numbers
[i
].identifier
{
return -1 // This should be unreachable.
func (u
*surrealUniverse
) cardinality() int {
func (u
*surrealUniverse
) insert(num surrealNumber
) {
// Before we can insert a number into the universe, we must first determine
// if it is newly discovered. We do this by looking at its ancestors, all
// guaranteed to be on the number line by construction, finding three
// 1. There are zero ancestors.
// We have rediscovered 0 and can abort the insertion unless creating
// 2. There is one ancestor.
// If the number extends the number line, it is new, otherwise it will
// be similar to a form with two ancestors and should be ignored since
// the two ancestor form is a better visual representation.
// 3. There are two ancestors.
// The number is only new if both ancestors are side-by-side on the
ancestorCount
:= num
.leftSet
.cardinality() + num
.rightSet
.cardinality()
if u
.cardinality() == 0 {
num
.identifier
= u
.nextUniqueID
u
.numbers
= append(u
.numbers
, num
)
if num
.leftSet
.cardinality() == 1{
index
:= u
.getIndex(num
.leftSet
.members
[0])
num
.identifier
= u
.nextUniqueID
if index
+1 == u
.cardinality() {
u
.numbers
= append(u
.numbers
, num
)
index
:= u
.getIndex(num
.rightSet
.members
[0])
num
.identifier
= u
.nextUniqueID
u
.numbers
= append(u
.numbers
[:1], u
.numbers
...)
leftIndex
:= u
.getIndex(num
.leftSet
.members
[0])
rightIndex
:= u
.getIndex(num
.rightSet
.members
[0])
if leftIndex
+1 == rightIndex
{
num
.identifier
= u
.nextUniqueID
u
.numbers
= append(u
.numbers
[:rightIndex
+1], u
.numbers
[rightIndex
:]...)
u
.numbers
[rightIndex
] = num
// =============================================================================
// Note: The following comparison functions apply only to numbers already in
// the universe, not to new numbers constructed from the universe. To
// determine where a (potentially) new number goes, first insert it into the
// This function implements Axiom 3 and is the root of all other comparisons.
func (u
*surrealUniverse
) isRelated(numA
, numB surrealNumber
) bool {
// By construction, no number in this program will ever have more than one
// element in its right or left sets, nor will those elements be of a form
// other than that 'registered' with the universe. That allows direct
// comparisons using the surrealNumber.identifier field via u.getIndex().
// ---------------------------------
// First we implement the check "no member of the first number's left set
// is greater than or equal to the second number".
if numA
.leftSet
.cardinality() == 1 {
if u
.getIndex(numA
.leftSet
.members
[0]) >= u
.getIndex(numB
) {
// Now we implement the check "no member of the second number's right set
// is less than or equal to the first number".
if numB
.rightSet
.cardinality() == 1 {
if u
.getIndex(numB
.rightSet
.members
[0]) <= u
.getIndex(numA
) {
func (u
*surrealUniverse
) isSimilar(numA
, numB surrealNumber
) bool {
if u
.isRelated(numA
, numB
) && u
.isRelated(numB
, numA
) {
func (u
*surrealUniverse
) equal(left
, right surrealNumber
) bool {
return u
.isSimilar(left
, right
)
func (u
*surrealUniverse
) lessThanOrEqual(left
, right surrealNumber
) bool {
return u
.isRelated(left
, right
)
func (u
*surrealUniverse
) lessThan(left
, right surrealNumber
) bool {
return u
.lessThanOrEqual(left
, right
) && !u
.equal(left
, right
)
func (u
*surrealUniverse
) greaterThanOrEqual(left
, right surrealNumber
) bool {
return !u
.lessThan(left
, right
)
func (u
*surrealUniverse
) greaterThan(left
, right surrealNumber
) bool {
return !u
.isRelated(left
, right
)
// =============================================================================
type surrealNumber
struct {
func (s
*surrealSet
) isMember(num surrealNumber
, u surrealUniverse
) bool {
for i
:= 0; i
< len(s
.members
); i
++ {
if u
.equal(num
, s
.members
[i
]) {
func (s
*surrealSet
) cardinality() int {
func (s
*surrealSet
) insert(num surrealNumber
, u surrealUniverse
) {
s
.members
= append(s
.members
, num
)
func (s
*surrealSet
) remove(num surrealNumber
, u surrealUniverse
) {
for i
:= 0; i
< len(s
.members
); i
++ {
if u
.equal(num
, s
.members
[i
]) {
s
.members
[i
] = s
.members
[len(s
.members
)-1]
s
.members
= s
.members
[:len(s
.members
)-1]
// =============================================================================
// Obtain termination conditions from user.
totalGenerations
:= flag
.Int("generations", 2, "Number of generations of surreal numbers to breed.")
if *totalGenerations
< 1 {
log
.Fatal("ERROR: The argument to '-generations' must be greater than zero.")
remainingGenerations
:= *totalGenerations
- 1
// Build a universe to contain all the surreal numbers we breed.
// Seed it by hand with the number zero as generation-0.
var universe surrealUniverse
universe
.nextUniqueID
= 0
universe
.insert(surrealNumber
{surrealSet
{}, surrealSet
{}, 0, 0})
// Breed however many generations of numbers were requested by the user and
// add them all to the universe.
for generation
:= 1; generation
<= remainingGenerations
; generation
++ {
// First generate all possible reduced form symbols per Axiom 1.
potentialNumbers
:= permuteExistingNumbers(generation
, universe
)
// Now prune out any symbols which are NOT valid numbers per Axiom 2.
validNumbers
:= pruneInvalidNumbers(potentialNumbers
, universe
)
// Attempt to add the new numbers to the universe. Any duplicates will
// be weeded out in the attempt.
addNumbersToUniverse(validNumbers
, &universe
)
// Print the number line with generation on the horizontal axis and
// magnitude on the vertical axis.
for i
:= 0; i
< universe
.cardinality(); i
++ {
printlnNumber(universe
.numbers
[i
])
fmt
.Println("After", *totalGenerations
, "generations, the universe contains", len(universe
.numbers
), "numbers.")
fmt
.Println("If output looks poor, ensure tabstop is eight spaces and that output doesn't wrap.")
// =============================================================================
// We will only build permutations with 0 or 1 elements in each of the left and
// right sets. This covers all the reduced form permutations. Any longer
// permutations will be similar to one of the reduced forms.
func permuteExistingNumbers(generation
int, universe surrealUniverse
) []surrealNumber
{
var numbers
[]surrealNumber
// First build permutations with 1 element in each set.
for i
:= 0; i
< universe
.cardinality(); i
++ {
for j
:= 0; j
< universe
.cardinality(); j
++ {
var leftSet
, rightSet surrealSet
leftSet
.insert(universe
.numbers
[i
], universe
)
rightSet
.insert(universe
.numbers
[j
], universe
)
newSurrealNumber
:= surrealNumber
{leftSet
,rightSet
,0,generation
}
numbers
= append(numbers
, newSurrealNumber
)
// Now build permutations with one empty set and one 1-element set.
for i
:= 0; i
< universe
.cardinality(); i
++ {
tempSet
.insert(universe
.numbers
[i
], universe
)
newSurrealNumber
:= surrealNumber
{tempSet
,surrealSet
{},0,generation
}
numbers
= append(numbers
, newSurrealNumber
)
newSurrealNumber
= surrealNumber
{surrealSet
{},tempSet
,0,generation
}
numbers
= append(numbers
, newSurrealNumber
)
func pruneInvalidNumbers(candidates
[]surrealNumber
, universe surrealUniverse
) []surrealNumber
{
var numbers
[]surrealNumber
for i
:= 0; i
< len(candidates
); i
++ {
if isValidSurrealNumber(candidates
[i
], universe
) {
numbers
= append(numbers
, candidates
[i
])
// Although a non-reduced-form number is technically valid, for the purposes of
// this program we're declaring it invalid.
func isValidSurrealNumber(candidate surrealNumber
, universe surrealUniverse
) bool {
// Is the number in reduced form?
if candidate
.leftSet
.cardinality() > 1 || candidate
.rightSet
.cardinality() > 1 {
// Is the number valid per Axiom 2?
if candidate
.leftSet
.cardinality() != 0 && candidate
.rightSet
.cardinality() != 0 {
for i
:= 0; i
< candidate
.leftSet
.cardinality(); i
++ {
for j
:= 0; j
< candidate
.leftSet
.cardinality(); j
++ {
// Since candidates are drawn from the universe, this comparison is allowed.
if universe
.greaterThanOrEqual(candidate
.leftSet
.members
[i
], candidate
.rightSet
.members
[j
]) {
func addNumbersToUniverse(numbers
[]surrealNumber
, universe
*surrealUniverse
) {
for i
:= 0; i
< len(numbers
); i
++ {
universe
.insert(numbers
[i
])
// Pretty print a number, indenting to indicate generation.
func printlnNumber(num surrealNumber
) {
for i
:= 0; i
< num
.generation
; i
++ {
fmt
.Printf("%s = ", toBase26(num
.identifier
))
if num
.leftSet
.cardinality() == 0 {
fmt
.Printf("%s", toBase26(num
.leftSet
.members
[0].identifier
))
if num
.rightSet
.cardinality() == 0 {
fmt
.Printf("%s", toBase26(num
.rightSet
.members
[0].identifier
))
// This function is a total hack, intended only to avoid printing identifiers
// as actual numbers since we don't want to imply any particular association to
// specific 'real' numbers yet. Instead, print them with [a-z] as base-26
func toBase26(num
uint) (base26String
[]byte) {
// For alignment reasons, we never print more than three digits. Thus, any
// number greater than (26^3)-1 is out of range.
base26String
= []byte("xxx")
var firstByte
, secondByte
, thirdByte
byte
thirdByte
= byte((num
% 26) + uint('a'));
secondByte
= byte((num
% 26) + uint('a'));
firstByte
= byte((num
% 26) + uint('a'));
base26String
= append(base26String
, firstByte
)
base26String
= append(base26String
, secondByte
)
base26String
= append(base26String
, thirdByte
)