X-Git-Url: http://git.subgeniuskitty.com/surreal-numbers/.git/blobdiff_plain/24271b43a4bb149a3904ad2a1e4fdf439d654ad0..eaa1dbf5d3a89a2276ec7ac84db03ab61e8a9a70:/chapter-1-experiments/ch1-breeding-numbers.go

diff --git a/chapter-1-experiments/ch1-breeding-numbers.go b/chapter-1-experiments/ch1-breeding-numbers.go
index 1e53fc3..b990361 100644
--- a/chapter-1-experiments/ch1-breeding-numbers.go
+++ b/chapter-1-experiments/ch1-breeding-numbers.go
@@ -4,9 +4,263 @@
 package main
 
 import (
+    "flag"
     "fmt"
+    "log"
 )
 
+// =============================================================================
+
+// TODO: Anywhere we do simple comparisons for number equality testing, we need
+// to upgrade to dual-LEQ comparisons.
+
+// =============================================================================
+
+type surrealUniverse struct {
+    // TODO: Note that the elements of this array are maintained in order
+    // w.r.t. Axiom 2. Maybe I should just rename number -> numberLine?
+    numbers []surrealNumber
+    nextUniqueID int
+}
+
+func (u *surrealUniverse) getIndex(num surrealNumber) (exists bool, index int) {
+    // TODO: After I implement a LEQ comparison function, the fact that
+    // u.numbers[] is ordered by that comparison will allow me to greatly
+    // shorten the search.
+    for i := 0; i < len(u.numbers); i++ {
+        if num.number == u.numbers[i].number {
+            return true, i
+        }
+    }
+    return false, 0
+}
+
+func (u *surrealUniverse) cardinality() int {
+    return len(u.numbers)
+}
+
+func (u *surrealUniverse) insert(num surrealNumber) {
+    exists, _ := u.getIndex(num)
+    if !exists {
+        num.metadata.identifier = u.nextUniqueID
+        u.nextUniqueID++
+        // Find spot to insert based on ordering defined in Axiom 2.
+        // TODO: Insert some comments explaining the basic algorithm.
+        for i := 0; i < len(u.numbers); i++ {
+
+//            if num.number.leftSet != nil {
+//                // By assumption, everything is in reduced form by this point,
+//                // thus there is precisely one element at this time.
+//                _, leftIndex := u.getIndex(num.number.leftSet[0])
+//                _, rightIndex := u.getIndex(u.numbers[i])
+//                if leftIndex >= rightIndex {
+//                    // num is NOT LEQ to u.numbers[i]
+//                }
+//            }
+//            if u.numbers[i].rightSet != nil {
+//                // TODO: How do I check if the second number's rightSet is less
+//                // than or equal to the first number? After all, the first
+//                // number isn't on the numberline yet.
+//            }
+
+// =================================================================================================
+//// Algorithm
+//foreach u.numbers as oldNum, in increasing order:
+//    if newNum <= oldNum:
+//        if oldNum <= newNum:
+//            // the number are the same, just in a different reduced form.
+//        else:
+//            // Insert newNum immediately before oldNum
+//    else:
+//        if more oldNums exist:
+//            // loop and try the next oldNum
+//        else:
+//            // Found a new largest number?
+// =================================================================================================
+
+//            if !lessThanOrEqual(num, u.numbers[i]) {
+//                if i+1 < len(u.numbers) {
+//                    // There are still more entries to check.
+//                    continue
+//                } else {
+//                    // New largest number. Append to numberline.
+//                    u.numbers = append(u.numbers, num)
+//                }
+//            } else {
+//                // Found insertion spot between two existing numbers.
+//                u.numbers = append(u.numbers[:i], num, u.numbers[i:]...)
+//            }
+        }
+    }
+}
+
+func (u *surrealUniverse) remove(num surrealNumber) {
+    for i := 0; i < len(u.numbers); i++ {
+        if num.number == u.numbers[i].number {
+            u.numbers = append(u.numbers[:i], u.numbers[i+1:]...)
+        }
+    }
+}
+
+// TODO: Note that this is only for numbers already in the universe, not for
+// new numbers constructed FROM the universe.  To determine where a new number
+// goes, insert it into the universe.
+func (u *surrealUniverse) lessThanOrEqual(left, right surrealNumber) bool {
+    _, leftIndex := u.getIndex(left)
+    _, rightIndex := u.getIndex(right)
+    if leftIndex <= rightIndex {
+        return true
+    } else {
+        return false
+    }
+}
+
+// =============================================================================
+
+type surrealNumber struct {
+    number surrealValue
+    metadata surrealMetadata
+}
+
+// TODO: Note that this is split from the metadata so we can do direct
+// comparisons when numbers are in reduced form.
+type surrealValue struct {
+    leftSet *surrealSet
+    rightSet *surrealSet
+}
+
+type surrealMetadata struct {
+    identifier int
+    generation int
+}
+
+// =============================================================================
+
+type surrealSet struct {
+    members []surrealNumber
+}
+
+func (s *surrealSet) isMember(num surrealNumber) bool {
+    for i := 0; i < len(s.members); i++ {
+        if num.number == s.members[i].number {
+            return true
+        }
+    }
+    return false
+}
+
+func (s *surrealSet) cardinality() int {
+    return len(s.members)
+}
+
+func (s *surrealSet) insert(num surrealNumber) {
+    if !s.isMember(num) {
+        s.members = append(s.members, num)
+    }
+}
+
+func (s *surrealSet) remove(num surrealNumber) {
+    for i := 0; i < len(s.members); i++ {
+        if num.number == s.members[i].number {
+            s.members[i] = s.members[len(s.members)-1]
+            s.members = s.members[:len(s.members)-1]
+        }
+    }
+}
+
+// =============================================================================
+
 func main() {
-    fmt.Println("Hello, World!")
+    // Obtain termination conditions from user.
+    remainingGenerations := flag.Int("generations", 2, "Number of generations of surreal numbers to breed.")
+    flag.Parse()
+    if *remainingGenerations < 1 {
+        log.Fatal("ERROR: The argument to '-generations' must be greater than zero.")
+    }
+
+    // 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.insert(surrealNumber{surrealValue{nil, nil}, surrealMetadata{0, 0}})
+
+    for generation := 1; generation <= *remainingGenerations; generation++ {
+        potentialNumbers := permuteExistingNumbers(generation, universe)
+        validNumbers := pruneInvalidNumbers(potentialNumbers, universe)
+        addNumbersToUniverse(validNumbers, &universe)
+    }
+
+    // TODO: These are just for checking progress. How do I want to render the
+    // final generation vs magnitude chart?
+    fmt.Println("Total Numbers:", len(universe.numbers))
+    fmt.Println(universe.numbers)
 }
+
+// =============================================================================
+
+// 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])
+            rightSet.insert(universe.numbers[j])
+            newSurrealNumber := surrealNumber{surrealValue{&leftSet,&rightSet},surrealMetadata{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++ {
+        var tempSet surrealSet
+        tempSet.insert(universe.numbers[i])
+        newSurrealNumber := surrealNumber{surrealValue{&tempSet,nil},surrealMetadata{0,generation}}
+        numbers = append(numbers, newSurrealNumber)
+        newSurrealNumber = surrealNumber{surrealValue{nil,&tempSet},surrealMetadata{0,generation}}
+        numbers = append(numbers, newSurrealNumber)
+    }
+
+    return numbers
+}
+
+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])
+        }
+    }
+    return numbers
+}
+
+// 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 per Definition 3?
+    if candidate.number.leftSet.cardinality() > 1 || candidate.number.rightSet.cardinality() > 1 {
+        return false
+    }
+
+    // Is the number valid per Axiom 1?
+    if candidate.number.leftSet != nil && candidate.number.rightSet != nil {
+        // TODO: This needs to be beefed up since <|> = <-1|1>.
+        if candidate.number.leftSet == candiate.number.rightSet {
+            return false
+        }
+        if !universe.lessThanOrEqual(candidate.number.leftSet[0], candidate.number.rightSet[0]) {
+            return false
+        }
+    }
+
+    return true
+}
+
+func addNumbersToUniverse(numbers []surrealNumber, universe *surrealUniverse) {
+    for i := 0; i < len(numbers); i++ {
+        universe.insert(numbers[i])
+    }
+}
+