// =============================================================================
+// 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.
+ // w.r.t. Axiom 2. Maybe I should just rename number -> numberLine?
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 {
- return true
+ return true, i
}
}
- return false
+ return false, 0
}
func (u *surrealUniverse) cardinality() int {
}
func (u *surrealUniverse) insert(num surrealNumber) {
- if !u.exists(num) {
+ exists, _ := u.getIndex(num)
+ if !exists {
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:]...)
+// }
+ }
}
}
}
}
+// 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 {
var universe surrealUniverse
universe.insert(surrealNumber{surrealValue{nil, nil}, surrealMetadata{0, 0}})
- // TODO: Describe the basic algorithm.
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
- // final generations vs magnitude chart?
+ // 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])
+ }
+}
+