| 1 | // (c) 2020 Aaron Taylor <ataylor at subgeniuskitty dot com> |
| 2 | // See LICENSE.txt file for copyright and license details. |
| 3 | |
| 4 | package main |
| 5 | |
| 6 | import ( |
| 7 | "flag" |
| 8 | "fmt" |
| 9 | "log" |
| 10 | ) |
| 11 | |
| 12 | // ============================================================================= |
| 13 | |
| 14 | // TODO: Anywhere we do simple comparisons for number equality testing, we need |
| 15 | // to upgrade to dual-LEQ comparisons. |
| 16 | |
| 17 | // ============================================================================= |
| 18 | |
| 19 | type surrealUniverse struct { |
| 20 | // TODO: Note that the elements of this array are maintained in order |
| 21 | // w.r.t. Axiom 2. Maybe I should just rename number -> numberLine? |
| 22 | numbers []surrealNumber |
| 23 | nextUniqueID int |
| 24 | } |
| 25 | |
| 26 | func (u *surrealUniverse) getIndex(num surrealNumber) (exists bool, index int) { |
| 27 | // TODO: After I implement a LEQ comparison function, the fact that |
| 28 | // u.numbers[] is ordered by that comparison will allow me to greatly |
| 29 | // shorten the search. |
| 30 | for i := 0; i < len(u.numbers); i++ { |
| 31 | if num.number == u.numbers[i].number { |
| 32 | return true, i |
| 33 | } |
| 34 | } |
| 35 | return false, 0 |
| 36 | } |
| 37 | |
| 38 | func (u *surrealUniverse) cardinality() int { |
| 39 | return len(u.numbers) |
| 40 | } |
| 41 | |
| 42 | func (u *surrealUniverse) insert(num surrealNumber) { |
| 43 | exists, _ := u.getIndex(num) |
| 44 | if !exists { |
| 45 | num.metadata.identifier = u.nextUniqueID |
| 46 | u.nextUniqueID++ |
| 47 | // Find spot to insert based on ordering defined in Axiom 2. |
| 48 | // TODO: Insert some comments explaining the basic algorithm. |
| 49 | for i := 0; i < len(u.numbers); i++ { |
| 50 | |
| 51 | // if num.number.leftSet != nil { |
| 52 | // // By assumption, everything is in reduced form by this point, |
| 53 | // // thus there is precisely one element at this time. |
| 54 | // _, leftIndex := u.getIndex(num.number.leftSet[0]) |
| 55 | // _, rightIndex := u.getIndex(u.numbers[i]) |
| 56 | // if leftIndex >= rightIndex { |
| 57 | // // num is NOT LEQ to u.numbers[i] |
| 58 | // } |
| 59 | // } |
| 60 | // if u.numbers[i].rightSet != nil { |
| 61 | // // TODO: How do I check if the second number's rightSet is less |
| 62 | // // than or equal to the first number? After all, the first |
| 63 | // // number isn't on the numberline yet. |
| 64 | // } |
| 65 | |
| 66 | // ================================================================================================= |
| 67 | //// Algorithm |
| 68 | //foreach u.numbers as oldNum, in increasing order: |
| 69 | // if newNum <= oldNum: |
| 70 | // if oldNum <= newNum: |
| 71 | // // the number are the same, just in a different reduced form. |
| 72 | // else: |
| 73 | // // Insert newNum immediately before oldNum |
| 74 | // else: |
| 75 | // if more oldNums exist: |
| 76 | // // loop and try the next oldNum |
| 77 | // else: |
| 78 | // // Found a new largest number? |
| 79 | // ================================================================================================= |
| 80 | |
| 81 | // if !lessThanOrEqual(num, u.numbers[i]) { |
| 82 | // if i+1 < len(u.numbers) { |
| 83 | // // There are still more entries to check. |
| 84 | // continue |
| 85 | // } else { |
| 86 | // // New largest number. Append to numberline. |
| 87 | // u.numbers = append(u.numbers, num) |
| 88 | // } |
| 89 | // } else { |
| 90 | // // Found insertion spot between two existing numbers. |
| 91 | // u.numbers = append(u.numbers[:i], num, u.numbers[i:]...) |
| 92 | // } |
| 93 | } |
| 94 | } |
| 95 | } |
| 96 | |
| 97 | func (u *surrealUniverse) remove(num surrealNumber) { |
| 98 | for i := 0; i < len(u.numbers); i++ { |
| 99 | if num.number == u.numbers[i].number { |
| 100 | u.numbers = append(u.numbers[:i], u.numbers[i+1:]...) |
| 101 | } |
| 102 | } |
| 103 | } |
| 104 | |
| 105 | // TODO: Note that this is only for numbers already in the universe, not for |
| 106 | // new numbers constructed FROM the universe. To determine where a new number |
| 107 | // goes, insert it into the universe. |
| 108 | func (u *surrealUniverse) lessThanOrEqual(left, right surrealNumber) bool { |
| 109 | _, leftIndex := u.getIndex(left) |
| 110 | _, rightIndex := u.getIndex(right) |
| 111 | if leftIndex <= rightIndex { |
| 112 | return true |
| 113 | } else { |
| 114 | return false |
| 115 | } |
| 116 | } |
| 117 | |
| 118 | // ============================================================================= |
| 119 | |
| 120 | type surrealNumber struct { |
| 121 | number surrealValue |
| 122 | metadata surrealMetadata |
| 123 | } |
| 124 | |
| 125 | // TODO: Note that this is split from the metadata so we can do direct |
| 126 | // comparisons when numbers are in reduced form. |
| 127 | type surrealValue struct { |
| 128 | leftSet *surrealSet |
| 129 | rightSet *surrealSet |
| 130 | } |
| 131 | |
| 132 | type surrealMetadata struct { |
| 133 | identifier int |
| 134 | generation int |
| 135 | } |
| 136 | |
| 137 | // ============================================================================= |
| 138 | |
| 139 | type surrealSet struct { |
| 140 | members []surrealNumber |
| 141 | } |
| 142 | |
| 143 | func (s *surrealSet) isMember(num surrealNumber) bool { |
| 144 | for i := 0; i < len(s.members); i++ { |
| 145 | if num.number == s.members[i].number { |
| 146 | return true |
| 147 | } |
| 148 | } |
| 149 | return false |
| 150 | } |
| 151 | |
| 152 | func (s *surrealSet) cardinality() int { |
| 153 | return len(s.members) |
| 154 | } |
| 155 | |
| 156 | func (s *surrealSet) insert(num surrealNumber) { |
| 157 | if !s.isMember(num) { |
| 158 | s.members = append(s.members, num) |
| 159 | } |
| 160 | } |
| 161 | |
| 162 | func (s *surrealSet) remove(num surrealNumber) { |
| 163 | for i := 0; i < len(s.members); i++ { |
| 164 | if num.number == s.members[i].number { |
| 165 | s.members[i] = s.members[len(s.members)-1] |
| 166 | s.members = s.members[:len(s.members)-1] |
| 167 | } |
| 168 | } |
| 169 | } |
| 170 | |
| 171 | // ============================================================================= |
| 172 | |
| 173 | func main() { |
| 174 | // Obtain termination conditions from user. |
| 175 | remainingGenerations := flag.Int("generations", 2, "Number of generations of surreal numbers to breed.") |
| 176 | flag.Parse() |
| 177 | if *remainingGenerations < 1 { |
| 178 | log.Fatal("ERROR: The argument to '-generations' must be greater than zero.") |
| 179 | } |
| 180 | |
| 181 | // Build a universe to contain all the surreal numbers we breed. |
| 182 | // Seed it by hand with the number zero as generation-0. |
| 183 | var universe surrealUniverse |
| 184 | universe.insert(surrealNumber{surrealValue{nil, nil}, surrealMetadata{0, 0}}) |
| 185 | |
| 186 | for generation := 1; generation <= *remainingGenerations; generation++ { |
| 187 | potentialNumbers := permuteExistingNumbers(generation, universe) |
| 188 | validNumbers := pruneInvalidNumbers(potentialNumbers, universe) |
| 189 | addNumbersToUniverse(validNumbers, &universe) |
| 190 | } |
| 191 | |
| 192 | // TODO: These are just for checking progress. How do I want to render the |
| 193 | // final generation vs magnitude chart? |
| 194 | fmt.Println("Total Numbers:", len(universe.numbers)) |
| 195 | fmt.Println(universe.numbers) |
| 196 | } |
| 197 | |
| 198 | // ============================================================================= |
| 199 | |
| 200 | // We will only build permutations with 0 or 1 elements in each of the left and |
| 201 | // right sets. This covers all the reduced form permutations. Any longer |
| 202 | // permutations will be similar to one of the reduced forms. |
| 203 | func permuteExistingNumbers(generation int, universe surrealUniverse) []surrealNumber { |
| 204 | var numbers []surrealNumber |
| 205 | |
| 206 | // First build permutations with 1 element in each set. |
| 207 | for i := 0; i < universe.cardinality(); i++ { |
| 208 | for j := 0; j < universe.cardinality(); j++ { |
| 209 | var leftSet, rightSet surrealSet |
| 210 | leftSet.insert(universe.numbers[i]) |
| 211 | rightSet.insert(universe.numbers[j]) |
| 212 | newSurrealNumber := surrealNumber{surrealValue{&leftSet,&rightSet},surrealMetadata{0,generation}} |
| 213 | numbers = append(numbers, newSurrealNumber) |
| 214 | } |
| 215 | } |
| 216 | // Now build permutations with one empty set and one 1-element set. |
| 217 | for i := 0; i < universe.cardinality(); i++ { |
| 218 | var tempSet surrealSet |
| 219 | tempSet.insert(universe.numbers[i]) |
| 220 | newSurrealNumber := surrealNumber{surrealValue{&tempSet,nil},surrealMetadata{0,generation}} |
| 221 | numbers = append(numbers, newSurrealNumber) |
| 222 | newSurrealNumber = surrealNumber{surrealValue{nil,&tempSet},surrealMetadata{0,generation}} |
| 223 | numbers = append(numbers, newSurrealNumber) |
| 224 | } |
| 225 | |
| 226 | return numbers |
| 227 | } |
| 228 | |
| 229 | func pruneInvalidNumbers(candidates []surrealNumber, universe surrealUniverse) []surrealNumber { |
| 230 | var numbers []surrealNumber |
| 231 | for i := 0; i < len(candidates); i++ { |
| 232 | if isValidSurrealNumber(candidates[i], universe) { |
| 233 | numbers = append(numbers, candidates[i]) |
| 234 | } |
| 235 | } |
| 236 | return numbers |
| 237 | } |
| 238 | |
| 239 | // Although a non-reduced-form number is technically valid, for the purposes of |
| 240 | // this program we're declaring it invalid. |
| 241 | func isValidSurrealNumber(candidate surrealNumber, universe surrealUniverse) bool { |
| 242 | // Is the number in reduced form per Definition 3? |
| 243 | if candidate.number.leftSet.cardinality() > 1 || candidate.number.rightSet.cardinality() > 1 { |
| 244 | return false |
| 245 | } |
| 246 | |
| 247 | // Is the number valid per Axiom 1? |
| 248 | if candidate.number.leftSet != nil && candidate.number.rightSet != nil { |
| 249 | // TODO: This needs to be beefed up since <|> = <-1|1>. |
| 250 | if candidate.number.leftSet == candiate.number.rightSet { |
| 251 | return false |
| 252 | } |
| 253 | if !universe.lessThanOrEqual(candidate.number.leftSet[0], candidate.number.rightSet[0]) { |
| 254 | return false |
| 255 | } |
| 256 | } |
| 257 | |
| 258 | return true |
| 259 | } |
| 260 | |
| 261 | func addNumbersToUniverse(numbers []surrealNumber, universe *surrealUniverse) { |
| 262 | for i := 0; i < len(numbers); i++ { |
| 263 | universe.insert(numbers[i]) |
| 264 | } |
| 265 | } |
| 266 | |