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])
+ }
+}
+