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