Commit | Line | Data |
---|---|---|
24271b43 AT |
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 ( | |
3c02a58e | 7 | "flag" |
24271b43 | 8 | "fmt" |
3c02a58e | 9 | "log" |
24271b43 AT |
10 | ) |
11 | ||
3c02a58e AT |
12 | // ============================================================================= |
13 | ||
90f47767 AT |
14 | // This program recognizes four types of numbers: |
15 | // - Surreal symbols, like those generated by Axiom 1. | |
16 | // - Surreal numbers, like those selected by Axiom 2. | |
17 | // - Reduced form numbers, per Definition 7. | |
18 | // - Named form numbers, which are the equivalence classes induced by | |
19 | // Definition 6, represented by the first representative reduced | |
20 | // form number encountered at runtime. | |
21 | // | |
22 | // Although the surrealNumber type can represent any of these four types of | |
23 | // numbers, the surrealUniverse contains only named form numbers. | |
24 | // | |
25 | // All equality tests (e.g. eq, geq, leq) in this program actually test for | |
26 | // similarity per Definition 6. | |
eaa1dbf5 AT |
27 | |
28 | // ============================================================================= | |
29 | ||
3c02a58e | 30 | type surrealUniverse struct { |
90f47767 AT |
31 | // The elements in this slice are stored in order according to Axiom 3. |
32 | // Thus, numbers[0] < numbers[1] < ... < numbers[n]. | |
3c02a58e | 33 | numbers []surrealNumber |
90f47767 | 34 | nextUniqueID uint |
3c02a58e AT |
35 | } |
36 | ||
90f47767 | 37 | func (u *surrealUniverse) getIndex(num surrealNumber) int { |
3c02a58e | 38 | for i := 0; i < len(u.numbers); i++ { |
90f47767 AT |
39 | if num.identifier == u.numbers[i].identifier { |
40 | return i | |
3c02a58e AT |
41 | } |
42 | } | |
90f47767 | 43 | return -1 // This should be unreachable. |
3c02a58e AT |
44 | } |
45 | ||
46 | func (u *surrealUniverse) cardinality() int { | |
47 | return len(u.numbers) | |
48 | } | |
49 | ||
50 | func (u *surrealUniverse) insert(num surrealNumber) { | |
90f47767 AT |
51 | // Before we can insert a number into the universe, we must first determine |
52 | // if it is newly discovered. We do this by looking at its ancestors, all | |
53 | // guaranteed to be on the number line by construction, finding three | |
54 | // cases: | |
55 | // | |
56 | // 1. There are zero ancestors. | |
57 | // We have rediscovered 0 and can abort the insertion unless creating | |
58 | // a brand new universe. | |
59 | // | |
60 | // 2. There is one ancestor. | |
61 | // If the number extends the number line, it is new, otherwise it will | |
62 | // be similar to a form with two ancestors and should be ignored since | |
63 | // the two ancestor form is a better visual representation. | |
64 | // | |
65 | // 3. There are two ancestors. | |
66 | // The number is only new if both ancestors are side-by-side on the | |
67 | // number line. | |
68 | ||
69 | ancestorCount := num.leftSet.cardinality() + num.rightSet.cardinality() | |
70 | switch ancestorCount { | |
71 | case 0: | |
72 | if u.cardinality() == 0 { | |
73 | num.identifier = u.nextUniqueID | |
74 | u.nextUniqueID++ | |
75 | u.numbers = append(u.numbers, num) | |
76 | } | |
77 | case 1: | |
78 | if num.leftSet.cardinality() == 1{ | |
79 | index := u.getIndex(num.leftSet.members[0]) | |
80 | num.identifier = u.nextUniqueID | |
81 | u.nextUniqueID++ | |
82 | if index+1 == u.cardinality() { | |
83 | u.numbers = append(u.numbers, num) | |
84 | } | |
85 | } else { | |
86 | index := u.getIndex(num.rightSet.members[0]) | |
87 | num.identifier = u.nextUniqueID | |
88 | u.nextUniqueID++ | |
89 | if index == 0 { | |
90 | u.numbers = append(u.numbers[:1], u.numbers...) | |
91 | u.numbers[0] = num | |
92 | } | |
93 | } | |
94 | case 2: | |
95 | leftIndex := u.getIndex(num.leftSet.members[0]) | |
96 | rightIndex := u.getIndex(num.rightSet.members[0]) | |
97 | if leftIndex+1 == rightIndex { | |
98 | num.identifier = u.nextUniqueID | |
99 | u.nextUniqueID++ | |
100 | u.numbers = append(u.numbers[:rightIndex+1], u.numbers[rightIndex:]...) | |
101 | u.numbers[rightIndex] = num | |
102 | } | |
3c02a58e AT |
103 | } |
104 | } | |
105 | ||
90f47767 AT |
106 | // ============================================================================= |
107 | ||
108 | // Note: The following comparison functions apply only to numbers already in | |
109 | // the universe, not to new numbers constructed from the universe. To | |
110 | // determine where a (potentially) new number goes, first insert it into the | |
111 | // universe. | |
112 | ||
113 | // This function implements Axiom 3 and is the root of all other comparisons. | |
114 | func (u *surrealUniverse) isRelated(numA, numB surrealNumber) bool { | |
115 | // By construction, no number in this program will ever have more than one | |
116 | // element in its right or left sets, nor will those elements be of a form | |
117 | // other than that 'registered' with the universe. That allows direct | |
118 | // comparisons using the surrealNumber.identifier field via u.getIndex(). | |
119 | ||
120 | // --------------------------------- | |
121 | ||
122 | // First we implement the check "no member of the first number's left set | |
123 | // is greater than or equal to the second number". | |
124 | if numA.leftSet.cardinality() == 1 { | |
125 | if u.getIndex(numA.leftSet.members[0]) >= u.getIndex(numB) { | |
126 | return false | |
127 | } | |
128 | } | |
129 | ||
130 | // Now we implement the check "no member of the second number's right set | |
131 | // is less than or equal to the first number". | |
132 | if numB.rightSet.cardinality() == 1 { | |
133 | if u.getIndex(numB.rightSet.members[0]) <= u.getIndex(numA) { | |
134 | return false | |
3c02a58e AT |
135 | } |
136 | } | |
90f47767 AT |
137 | |
138 | return true | |
3c02a58e AT |
139 | } |
140 | ||
90f47767 AT |
141 | func (u *surrealUniverse) isSimilar(numA, numB surrealNumber) bool { |
142 | if u.isRelated(numA, numB) && u.isRelated(numB, numA) { | |
eaa1dbf5 | 143 | return true |
eaa1dbf5 | 144 | } |
90f47767 | 145 | return false |
eaa1dbf5 AT |
146 | } |
147 | ||
90f47767 AT |
148 | func (u *surrealUniverse) equal(left, right surrealNumber) bool { |
149 | return u.isSimilar(left, right) | |
150 | } | |
3c02a58e | 151 | |
90f47767 AT |
152 | func (u *surrealUniverse) lessThanOrEqual(left, right surrealNumber) bool { |
153 | return u.isRelated(left, right) | |
3c02a58e AT |
154 | } |
155 | ||
90f47767 AT |
156 | func (u *surrealUniverse) lessThan(left, right surrealNumber) bool { |
157 | return u.lessThanOrEqual(left, right) && !u.equal(left, right) | |
3c02a58e AT |
158 | } |
159 | ||
90f47767 AT |
160 | func (u *surrealUniverse) greaterThanOrEqual(left, right surrealNumber) bool { |
161 | return !u.lessThan(left, right) | |
162 | } | |
163 | ||
164 | func (u *surrealUniverse) greaterThan(left, right surrealNumber) bool { | |
165 | return !u.isRelated(left, right) | |
3c02a58e AT |
166 | } |
167 | ||
168 | // ============================================================================= | |
169 | ||
90f47767 AT |
170 | type surrealNumber struct { |
171 | leftSet surrealSet | |
172 | rightSet surrealSet | |
173 | identifier uint | |
174 | generation int | |
175 | } | |
176 | ||
3c02a58e AT |
177 | type surrealSet struct { |
178 | members []surrealNumber | |
179 | } | |
180 | ||
90f47767 | 181 | func (s *surrealSet) isMember(num surrealNumber, u surrealUniverse) bool { |
3c02a58e | 182 | for i := 0; i < len(s.members); i++ { |
90f47767 | 183 | if u.equal(num, s.members[i]) { |
3c02a58e AT |
184 | return true |
185 | } | |
186 | } | |
187 | return false | |
188 | } | |
189 | ||
190 | func (s *surrealSet) cardinality() int { | |
191 | return len(s.members) | |
192 | } | |
193 | ||
90f47767 AT |
194 | func (s *surrealSet) insert(num surrealNumber, u surrealUniverse) { |
195 | if !s.isMember(num, u) { | |
3c02a58e AT |
196 | s.members = append(s.members, num) |
197 | } | |
198 | } | |
199 | ||
90f47767 | 200 | func (s *surrealSet) remove(num surrealNumber, u surrealUniverse) { |
3c02a58e | 201 | for i := 0; i < len(s.members); i++ { |
90f47767 | 202 | if u.equal(num, s.members[i]) { |
3c02a58e AT |
203 | s.members[i] = s.members[len(s.members)-1] |
204 | s.members = s.members[:len(s.members)-1] | |
205 | } | |
206 | } | |
207 | } | |
208 | ||
209 | // ============================================================================= | |
210 | ||
24271b43 | 211 | func main() { |
3c02a58e | 212 | // Obtain termination conditions from user. |
90f47767 | 213 | totalGenerations := flag.Int("generations", 2, "Number of generations of surreal numbers to breed.") |
3c02a58e | 214 | flag.Parse() |
90f47767 | 215 | if *totalGenerations < 1 { |
3c02a58e AT |
216 | log.Fatal("ERROR: The argument to '-generations' must be greater than zero.") |
217 | } | |
90f47767 | 218 | remainingGenerations := *totalGenerations - 1 |
3c02a58e AT |
219 | |
220 | // Build a universe to contain all the surreal numbers we breed. | |
221 | // Seed it by hand with the number zero as generation-0. | |
222 | var universe surrealUniverse | |
90f47767 | 223 | universe.nextUniqueID = 0 |
1c22e97e | 224 | fmt.Println("Seeding generation 0 by hand.") |
90f47767 | 225 | universe.insert(surrealNumber{surrealSet{}, surrealSet{}, 0, 0}) |
3c02a58e | 226 | |
90f47767 AT |
227 | // Breed however many generations of numbers were requested by the user and |
228 | // add them all to the universe. | |
1c22e97e | 229 | fmt.Printf("Breeding Generation:") |
90f47767 | 230 | for generation := 1; generation <= remainingGenerations; generation++ { |
1c22e97e AT |
231 | if generation != 1 { |
232 | fmt.Printf(",") | |
233 | } | |
234 | fmt.Printf(" %d", generation) | |
90f47767 | 235 | // First generate all possible reduced form symbols per Axiom 1. |
eaa1dbf5 | 236 | potentialNumbers := permuteExistingNumbers(generation, universe) |
90f47767 | 237 | // Now prune out any symbols which are NOT valid numbers per Axiom 2. |
eaa1dbf5 | 238 | validNumbers := pruneInvalidNumbers(potentialNumbers, universe) |
90f47767 AT |
239 | // Attempt to add the new numbers to the universe. Any duplicates will |
240 | // be weeded out in the attempt. | |
eaa1dbf5 | 241 | addNumbersToUniverse(validNumbers, &universe) |
3c02a58e | 242 | } |
1c22e97e | 243 | fmt.Printf(".\n") |
3c02a58e | 244 | |
90f47767 AT |
245 | // Print the number line with generation on the horizontal axis and |
246 | // magnitude on the vertical axis. | |
247 | for i := 0; i < universe.cardinality(); i++ { | |
248 | printlnNumber(universe.numbers[i]) | |
249 | } | |
250 | fmt.Println("After", *totalGenerations, "generations, the universe contains", len(universe.numbers), "numbers.") | |
251 | fmt.Println("If output looks poor, ensure tabstop is eight spaces and that output doesn't wrap.") | |
24271b43 | 252 | } |
3c02a58e AT |
253 | |
254 | // ============================================================================= | |
eaa1dbf5 AT |
255 | |
256 | // We will only build permutations with 0 or 1 elements in each of the left and | |
257 | // right sets. This covers all the reduced form permutations. Any longer | |
258 | // permutations will be similar to one of the reduced forms. | |
259 | func permuteExistingNumbers(generation int, universe surrealUniverse) []surrealNumber { | |
260 | var numbers []surrealNumber | |
261 | ||
262 | // First build permutations with 1 element in each set. | |
263 | for i := 0; i < universe.cardinality(); i++ { | |
264 | for j := 0; j < universe.cardinality(); j++ { | |
265 | var leftSet, rightSet surrealSet | |
90f47767 AT |
266 | leftSet.insert(universe.numbers[i], universe) |
267 | rightSet.insert(universe.numbers[j], universe) | |
268 | newSurrealNumber := surrealNumber{leftSet,rightSet,0,generation} | |
eaa1dbf5 AT |
269 | numbers = append(numbers, newSurrealNumber) |
270 | } | |
271 | } | |
272 | // Now build permutations with one empty set and one 1-element set. | |
273 | for i := 0; i < universe.cardinality(); i++ { | |
274 | var tempSet surrealSet | |
90f47767 AT |
275 | tempSet.insert(universe.numbers[i], universe) |
276 | newSurrealNumber := surrealNumber{tempSet,surrealSet{},0,generation} | |
eaa1dbf5 | 277 | numbers = append(numbers, newSurrealNumber) |
90f47767 | 278 | newSurrealNumber = surrealNumber{surrealSet{},tempSet,0,generation} |
eaa1dbf5 AT |
279 | numbers = append(numbers, newSurrealNumber) |
280 | } | |
281 | ||
282 | return numbers | |
283 | } | |
284 | ||
285 | func pruneInvalidNumbers(candidates []surrealNumber, universe surrealUniverse) []surrealNumber { | |
286 | var numbers []surrealNumber | |
287 | for i := 0; i < len(candidates); i++ { | |
288 | if isValidSurrealNumber(candidates[i], universe) { | |
289 | numbers = append(numbers, candidates[i]) | |
290 | } | |
291 | } | |
292 | return numbers | |
293 | } | |
294 | ||
295 | // Although a non-reduced-form number is technically valid, for the purposes of | |
296 | // this program we're declaring it invalid. | |
297 | func isValidSurrealNumber(candidate surrealNumber, universe surrealUniverse) bool { | |
90f47767 AT |
298 | // Is the number in reduced form? |
299 | if candidate.leftSet.cardinality() > 1 || candidate.rightSet.cardinality() > 1 { | |
eaa1dbf5 AT |
300 | return false |
301 | } | |
302 | ||
90f47767 AT |
303 | // Is the number valid per Axiom 2? |
304 | if candidate.leftSet.cardinality() != 0 && candidate.rightSet.cardinality() != 0 { | |
305 | for i := 0; i < candidate.leftSet.cardinality(); i++ { | |
306 | for j := 0; j < candidate.leftSet.cardinality(); j++ { | |
307 | // Since candidates are drawn from the universe, this comparison is allowed. | |
308 | if universe.greaterThanOrEqual(candidate.leftSet.members[i], candidate.rightSet.members[j]) { | |
309 | return false | |
310 | } | |
311 | } | |
eaa1dbf5 AT |
312 | } |
313 | } | |
314 | ||
315 | return true | |
316 | } | |
317 | ||
318 | func addNumbersToUniverse(numbers []surrealNumber, universe *surrealUniverse) { | |
319 | for i := 0; i < len(numbers); i++ { | |
320 | universe.insert(numbers[i]) | |
321 | } | |
322 | } | |
323 | ||
90f47767 AT |
324 | // Pretty print a number, indenting to indicate generation. |
325 | func printlnNumber(num surrealNumber) { | |
326 | for i := 0; i < num.generation; i++ { | |
327 | fmt.Printf(".\t\t") | |
328 | } | |
329 | fmt.Printf("%s = ", toBase26(num.identifier)) | |
330 | fmt.Printf("<") | |
331 | if num.leftSet.cardinality() == 0 { | |
332 | fmt.Printf("---") | |
333 | } else { | |
334 | fmt.Printf("%s", toBase26(num.leftSet.members[0].identifier)) | |
335 | } | |
336 | fmt.Printf("|") | |
337 | if num.rightSet.cardinality() == 0 { | |
338 | fmt.Printf("---") | |
339 | } else { | |
340 | fmt.Printf("%s", toBase26(num.rightSet.members[0].identifier)) | |
341 | } | |
342 | fmt.Printf(">") | |
343 | fmt.Printf("\n") | |
344 | } | |
345 | ||
346 | // This function is a total hack, intended only to avoid printing identifiers | |
347 | // as actual numbers since we don't want to imply any particular association to | |
348 | // specific 'real' numbers yet. Instead, print them with [a-z] as base-26 | |
349 | // integers. | |
350 | func toBase26(num uint) (base26String []byte) { | |
351 | // For alignment reasons, we never print more than three digits. Thus, any | |
352 | // number greater than (26^3)-1 is out of range. | |
353 | if num >= 26*26*26 { | |
354 | base26String = []byte("xxx") | |
355 | } else { | |
356 | var firstByte, secondByte, thirdByte byte | |
357 | thirdByte = byte((num % 26) + uint('a')); | |
358 | num = num / 26; | |
359 | secondByte = byte((num % 26) + uint('a')); | |
360 | num = num / 26; | |
361 | firstByte = byte((num % 26) + uint('a')); | |
362 | num = num / 26; | |
363 | base26String = append(base26String, firstByte) | |
364 | base26String = append(base26String, secondByte) | |
365 | base26String = append(base26String, thirdByte) | |
366 | } | |
367 | return base26String | |
368 | } |