From: Aaron Taylor Date: Wed, 5 May 2021 10:17:13 +0000 (-0700) Subject: In chapter-1 experiments, continued writing a program to breed numbers. X-Git-Url: http://git.subgeniuskitty.com/surreal-numbers/.git/commitdiff_plain/eaa1dbf5d3a89a2276ec7ac84db03ab61e8a9a70 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 --- 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 - // 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 { @@ -35,12 +40,57 @@ 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:]...) +// } + } } } @@ -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 { @@ -120,19 +183,84 @@ func main() { 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]) + } +} +