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 | ||
eaa1dbf5 AT |
14 | // TODO: Anywhere we do simple comparisons for number equality testing, we need |
15 | // to upgrade to dual-LEQ comparisons. | |
16 | ||
17 | // ============================================================================= | |
18 | ||
3c02a58e AT |
19 | type surrealUniverse struct { |
20 | // TODO: Note that the elements of this array are maintained in order | |
eaa1dbf5 | 21 | // w.r.t. Axiom 2. Maybe I should just rename number -> numberLine? |
3c02a58e AT |
22 | numbers []surrealNumber |
23 | nextUniqueID int | |
24 | } | |
25 | ||
eaa1dbf5 | 26 | func (u *surrealUniverse) getIndex(num surrealNumber) (exists bool, index int) { |
3c02a58e AT |
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 { | |
eaa1dbf5 | 32 | return true, i |
3c02a58e AT |
33 | } |
34 | } | |
eaa1dbf5 | 35 | return false, 0 |
3c02a58e AT |
36 | } |
37 | ||
38 | func (u *surrealUniverse) cardinality() int { | |
39 | return len(u.numbers) | |
40 | } | |
41 | ||
42 | func (u *surrealUniverse) insert(num surrealNumber) { | |
eaa1dbf5 AT |
43 | exists, _ := u.getIndex(num) |
44 | if !exists { | |
3c02a58e AT |
45 | num.metadata.identifier = u.nextUniqueID |
46 | u.nextUniqueID++ | |
eaa1dbf5 AT |
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 | } | |
3c02a58e AT |
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 | ||
eaa1dbf5 AT |
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 | ||
3c02a58e AT |
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 | ||
24271b43 | 173 | func main() { |
3c02a58e AT |
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 | ||
3c02a58e | 186 | for generation := 1; generation <= *remainingGenerations; generation++ { |
eaa1dbf5 AT |
187 | potentialNumbers := permuteExistingNumbers(generation, universe) |
188 | validNumbers := pruneInvalidNumbers(potentialNumbers, universe) | |
189 | addNumbersToUniverse(validNumbers, &universe) | |
3c02a58e AT |
190 | } |
191 | ||
192 | // TODO: These are just for checking progress. How do I want to render the | |
eaa1dbf5 | 193 | // final generation vs magnitude chart? |
3c02a58e AT |
194 | fmt.Println("Total Numbers:", len(universe.numbers)) |
195 | fmt.Println(universe.numbers) | |
24271b43 | 196 | } |
3c02a58e AT |
197 | |
198 | // ============================================================================= | |
eaa1dbf5 AT |
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 |