In chapter-1 experiments, continued writing a program to breed numbers.

Still non-functional.

diff --git a/chapter-1-experiments/ch1-breeding-numbers.go b/chapter-1-experiments/ch1-breeding-numbers.go
index d063cdd..b990361 100644 (file)
--- a/chapter-1-experiments/ch1-breeding-numbers.go
+++ b/chapter-1-experiments/ch1-breeding-numbers.go
@@ -11,23 +11,28 @@ import (
 
 // =============================================================================
 
 
 // =============================================================================
 

+// 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
 type surrealUniverse struct {
     // TODO: Note that the elements of this array are maintained in order

-    // w.r.t. Axiom 2.
+    // w.r.t. Axiom 2. Maybe I should just rename number -> numberLine?

     numbers []surrealNumber
     nextUniqueID int
 }
 
     numbers []surrealNumber
     nextUniqueID int
 }
 

-func (u *surrealUniverse) exists(num surrealNumber) bool {
+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 {
     // 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
+            return true, i

         }
     }
         }
     }

-    return false
+    return false, 0

 }
 
 func (u *surrealUniverse) cardinality() int {
 }
 
 func (u *surrealUniverse) cardinality() int {


@@ -35,12 +40,57 @@ func (u *surrealUniverse) cardinality() int {
 }
 
 func (u *surrealUniverse) insert(num surrealNumber) {
 }
 
 func (u *surrealUniverse) insert(num surrealNumber) {

-    if !u.exists(num) {
+    exists, _ := u.getIndex(num)
+    if !exists {

         num.metadata.identifier = u.nextUniqueID
         u.nextUniqueID++
         num.metadata.identifier = u.nextUniqueID
         u.nextUniqueID++

-        // TODO: Need a LEQ function before I can insert in the correct order.
-        // For now, just append to the end.
-        u.numbers = append(u.numbers, num)
+        // 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:]...)
+//            }
+        }

     }
 }
 
     }
 }
 


@@ -52,6 +102,19 @@ func (u *surrealUniverse) remove(num surrealNumber) {
     }
 }
 
     }
 }
 

+// 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 {
 // =============================================================================
 
 type surrealNumber struct {


@@ -120,19 +183,84 @@ func main() {
     var universe surrealUniverse
     universe.insert(surrealNumber{surrealValue{nil, nil}, surrealMetadata{0, 0}})
 
     var universe surrealUniverse
     universe.insert(surrealNumber{surrealValue{nil, nil}, surrealMetadata{0, 0}})
 

-    // TODO: Describe the basic algorithm.

     for generation := 1; generation <= *remainingGenerations; generation++ {
     for generation := 1; generation <= *remainingGenerations; generation++ {

-// TODO: Continue here next time.
-// Rough Plan:
-//        allSymbols := buildAllSymbolCombinations(generation)
-//        validNumbers := pruneInvalidSymbolCombinations(allSymbols)
-//        addNumbersToUniverse(validNumbers)
+        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
     }
 
     // TODO: These are just for checking progress. How do I want to render the

-    // final generations vs magnitude chart?
+    // final generation vs magnitude chart?

     fmt.Println("Total Numbers:", len(universe.numbers))
     fmt.Println(universe.numbers)
 }
 
 // =============================================================================
     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])
+    }
+}
+