]> git.scottworley.com Git - planeteer/blob - planeteer.go
Performance!
[planeteer] / planeteer.go
1 /* Planeteer: Give trade route advice for Planets: The Exploration of Space
2 * Copyright (C) 2011 Scott Worley <sworley@chkno.net>
3 *
4 * This program is free software: you can redistribute it and/or modify
5 * it under the terms of the GNU Affero General Public License as
6 * published by the Free Software Foundation, either version 3 of the
7 * License, or (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU Affero General Public License for more details.
13 *
14 * You should have received a copy of the GNU Affero General Public License
15 * along with this program. If not, see <http://www.gnu.org/licenses/>.
16 */
17
18 package main
19
20 import "flag"
21 import "fmt"
22 import "json"
23 import "os"
24 import "runtime/pprof"
25 import "strings"
26
27 var funds = flag.Int("funds", 0,
28 "Starting funds")
29
30 var start = flag.String("start", "",
31 "The planet to start at")
32
33 var flight_plan_string = flag.String("flight_plan", "",
34 "Your hyper-holes for the day, comma-separated.")
35
36 var end_string = flag.String("end", "",
37 "A comma-separated list of acceptable ending planets.")
38
39 var planet_data_file = flag.String("planet_data_file", "planet-data",
40 "The file to read planet data from")
41
42 var fuel = flag.Int("fuel", 16, "Hyper Jump power left")
43
44 var hold = flag.Int("hold", 300, "Size of your cargo hold")
45
46 var start_edens = flag.Int("start_edens", 0,
47 "How many Eden Warp Units are you starting with?")
48
49 var end_edens = flag.Int("end_edens", 0,
50 "How many Eden Warp Units would you like to keep (not use)?")
51
52 var cloak = flag.Bool("cloak", false,
53 "Make sure to end with a Device of Cloaking")
54
55 var drones = flag.Int("drones", 0, "Buy this many Fighter Drones")
56
57 var batteries = flag.Int("batteries", 0, "Buy this many Shield Batterys")
58
59 var drone_price = flag.Int("drone_price", 0, "Today's Fighter Drone price")
60
61 var battery_price = flag.Int("battery_price", 0, "Today's Shield Battery price")
62
63 var visit_string = flag.String("visit", "",
64 "A comma-separated list of planets to make sure to visit")
65
66 var cpuprofile = flag.String("cpuprofile", "", "write cpu profile to file")
67
68
69 var visit_cache []string
70 func visit() []string {
71 if visit_cache == nil {
72 if *visit_string == "" {
73 return nil
74 }
75 visit_cache = strings.Split(*visit_string, ",")
76 }
77 return visit_cache
78 }
79
80 var flight_plan_cache []string
81 func flight_plan() []string {
82 if flight_plan_cache == nil {
83 if *flight_plan_string == "" {
84 return nil
85 }
86 flight_plan_cache = strings.Split(*flight_plan_string, ",")
87 }
88 return flight_plan_cache
89 }
90
91 var end_cache map[string]bool
92 func end() map[string]bool {
93 if end_cache == nil {
94 if *end_string == "" {
95 return nil
96 }
97 m := make(map[string]bool)
98 for _, p := range strings.Split(*end_string, ",") {
99 m[p] = true
100 }
101 end_cache = m
102 }
103 return end_cache
104 }
105
106 type Commodity struct {
107 BasePrice int
108 CanSell bool
109 Limit int
110 }
111 type Planet struct {
112 BeaconOn bool
113 /* Use relative prices rather than absolute prices because you
114 can get relative prices without traveling to each planet. */
115 RelativePrices map[string]int
116 }
117 type planet_data struct {
118 Commodities map[string]Commodity
119 Planets map[string]Planet
120 p2i, c2i map[string]int // Generated; not read from file
121 i2p, i2c []string // Generated; not read from file
122 }
123
124 func ReadData() (data planet_data) {
125 f, err := os.Open(*planet_data_file)
126 if err != nil {
127 panic(err)
128 }
129 defer f.Close()
130 err = json.NewDecoder(f).Decode(&data)
131 if err != nil {
132 panic(err)
133 }
134 return
135 }
136
137 /* This program operates by filling in a state table representing the best
138 * possible trips you could make; the ones that makes you the most money.
139 * This is feasible because we don't look at all the possible trips.
140 * We define a list of things that are germane to this game and then only
141 * consider the best outcome in each possible game state.
142 *
143 * Each cell in the table represents a state in the game. In each cell,
144 * we track two things: 1. the most money you could possibly have while in
145 * that state and 2. one possible way to get into that state with that
146 * amount of money.
147 *
148 * A basic analysis can be done with a two-dimensional table: location and
149 * fuel. planeteer-1.0 used this two-dimensional table. This version
150 * adds features mostly by adding dimensions to this table.
151 *
152 * Note that the sizes of each dimension are data driven. Many dimensions
153 * collapse to one possible value (ie, disappear) if the corresponding
154 * feature is not enabled.
155 *
156 * The order of the dimensions in the list of constants below determines
157 * their layout in RAM. The cargo-based 'dimensions' are not completely
158 * independent -- some combinations are illegal and not used. They are
159 * handled as three dimensions rather than one for simplicity. Placing
160 * these dimensions first causes the unused cells in the table to be
161 * grouped together in large blocks. This keeps them from polluting
162 * cache lines, and if they are large enough, prevent the memory manager
163 * from allocating pages for these areas at all.
164 *
165 * If the table gets too big to fit in RAM:
166 * * Combine the Edens, Cloaks, and UnusedCargo dimensions. Of the
167 * 24 combinations, only 15 are legal: a 38% savings.
168 * * Reduce the size of the Fuel dimension to 3. We only ever look
169 * backwards 2 units, so just rotate the logical values through
170 * the same 3 physical addresses. This is good for an 82% savings.
171 * * Reduce the size of the Edens dimension from 3 to 2, for the
172 * same reasons as Fuel above. 33% savings.
173 * * Buy more ram. (Just sayin'. It's cheaper than you think.)
174 *
175 */
176
177 // The official list of dimensions:
178 const (
179 // Name Num Size Description
180 Edens = iota // 1 3 # of Eden warp units (0 - 2 typically)
181 Cloaks // 2 2 # of Devices of Cloaking (0 or 1)
182 UnusedCargo // 3 4 # of unused cargo spaces (0 - 3 typically)
183 Fuel // 4 17 Hyper jump power left (0 - 16)
184 Location // 5 26 Location (which planet)
185 Hold // 6 15 Cargo bay contents (a *Commodity or nil)
186 BuyFighters // 7 2 Errand: Buy fighter drones
187 BuyShields // 8 2 Errand: Buy shield batteries
188 Visit // 9 2**N Visit: Stop by these N planets in the route
189
190 NumDimensions
191 )
192
193 func bint(b bool) int {
194 if b {
195 return 1
196 }
197 return 0
198 }
199
200 func DimensionSizes(data planet_data) []int {
201 eden_capacity := data.Commodities["Eden Warp Units"].Limit
202 if *start_edens > eden_capacity {
203 eden_capacity = *start_edens
204 }
205 cloak_capacity := bint(*cloak)
206 dims := make([]int, NumDimensions)
207 dims[Edens] = eden_capacity + 1
208 dims[Cloaks] = cloak_capacity + 1
209 dims[UnusedCargo] = eden_capacity + cloak_capacity + 1
210 dims[Fuel] = *fuel + 1
211 dims[Location] = len(data.Planets)
212 dims[Hold] = len(data.Commodities) + 1
213 dims[BuyFighters] = bint(*drones > 0) + 1
214 dims[BuyShields] = bint(*batteries > 0) + 1
215 dims[Visit] = 1 << uint(len(visit()))
216
217 // Remind myself to add a line above when adding new dimensions
218 for i, dim := range dims {
219 if dim < 1 {
220 panic(i)
221 }
222 }
223 return dims
224 }
225
226 func StateTableSize(dims []int) int {
227 product := 1
228 for _, size := range dims {
229 product *= size
230 }
231 return product
232 }
233
234 type State struct {
235 value, from int
236 }
237
238 func EncodeIndex(dims, addr []int) int {
239 index := addr[0]
240 if addr[0] > dims[0] {
241 panic(0)
242 }
243 for i := 1; i < NumDimensions; i++ {
244 if addr[i] < 0 || addr[i] > dims[i] {
245 panic(i)
246 }
247 index = index*dims[i] + addr[i]
248 }
249 return index
250 }
251
252 func DecodeIndex(dims []int, index int) []int {
253 addr := make([]int, NumDimensions)
254 for i := NumDimensions - 1; i > 0; i-- {
255 addr[i] = index % dims[i]
256 index /= dims[i]
257 }
258 addr[0] = index
259 return addr
260 }
261
262 func InitializeStateTable(data planet_data, dims []int) []State {
263 table := make([]State, StateTableSize(dims))
264
265 addr := make([]int, NumDimensions)
266 addr[Fuel] = *fuel
267 addr[Edens] = *start_edens
268 addr[Location] = data.p2i[*start]
269 table[EncodeIndex(dims, addr)].value = *funds
270
271 return table
272 }
273
274 /* These four fill procedures fill in the cell at address addr by
275 * looking at all the possible ways to reach this cell and selecting
276 * the best one.
277 *
278 * The other obvious implementation choice is to do this the other way
279 * around -- for each cell, conditionally overwrite all the other cells
280 * that are reachable *from* the considered cell. We choose gathering
281 * reads over scattering writes to avoid having to take a bunch of locks.
282 */
283
284 func UpdateCell(table []State, here, there, value_difference int) {
285 possible_value := table[there].value + value_difference
286 if table[there].value > 0 && possible_value > table[here].value {
287 table[here].value = possible_value
288 table[here].from = there
289 }
290 }
291
292 func FillCellByArriving(data planet_data, dims []int, table []State, addr []int) {
293 my_index := EncodeIndex(dims, addr)
294 other := make([]int, NumDimensions)
295 copy(other, addr)
296
297 /* Travel here via a 2-fuel unit jump */
298 if addr[Fuel]+2 < dims[Fuel] {
299 other[Fuel] = addr[Fuel] + 2
300 for other[Location] = 0; other[Location] < dims[Location]; other[Location]++ {
301 if data.Planets[data.i2p[addr[Location]]].BeaconOn {
302 UpdateCell(table, my_index, EncodeIndex(dims, other), 0)
303 }
304 }
305 other[Location] = addr[Location]
306 other[Fuel] = addr[Fuel]
307 }
308
309 /* Travel here via a hyper hole */
310 if addr[Fuel]+1 < dims[Fuel] {
311 hole_index := (dims[Fuel] - 1) - (addr[Fuel] + 1)
312 if hole_index < len(flight_plan()) && addr[Location] == data.p2i[flight_plan()[hole_index]] {
313 other[Fuel] = addr[Fuel] + 1
314 for other[Location] = 0; other[Location] < dims[Location]; other[Location]++ {
315 UpdateCell(table, my_index, EncodeIndex(dims, other), 0)
316 }
317 other[Location] = addr[Location]
318 other[Fuel] = addr[Fuel]
319 }
320 }
321
322 /* Travel here via Eden Warp Unit */
323 if addr[Edens]+1 < dims[Edens] && addr[UnusedCargo] > 1 {
324 _, available := data.Planets[data.i2p[addr[Location]]].RelativePrices["Eden Warp Units"]
325 if !available {
326 other[Edens] = addr[Edens] + 1
327 other[UnusedCargo] = addr[UnusedCargo] - 1
328 for other[Location] = 0; other[Location] < dims[Location]; other[Location]++ {
329 UpdateCell(table, my_index, EncodeIndex(dims, other), 0)
330 }
331 other[Location] = addr[Location]
332 other[UnusedCargo] = addr[UnusedCargo]
333 other[Edens] = addr[Edens]
334 }
335 }
336 }
337
338 func FillCellBySelling(data planet_data, dims []int, table []State, addr []int) {
339 if addr[Hold] > 0 {
340 // Can't sell and still have cargo
341 return
342 }
343 if addr[UnusedCargo] > 0 {
344 // Can't sell everything and still have 'unused' holds
345 return
346 }
347 my_index := EncodeIndex(dims, addr)
348 other := make([]int, NumDimensions)
349 copy(other, addr)
350 planet := data.i2p[addr[Location]]
351 for other[Hold] = 0; other[Hold] < dims[Hold]; other[Hold]++ {
352 commodity := data.i2c[other[Hold]]
353 if !data.Commodities[commodity].CanSell {
354 // TODO: Dump cargo
355 continue
356 }
357 relative_price, available := data.Planets[planet].RelativePrices[commodity]
358 if !available {
359 continue
360 }
361 base_price := data.Commodities[commodity].BasePrice
362 absolute_price := float64(base_price) * float64(relative_price) / 100.0
363 sell_price := int(absolute_price * 0.9)
364
365 for other[UnusedCargo] = 0; other[UnusedCargo] < dims[UnusedCargo]; other[UnusedCargo]++ {
366
367 quantity := *hold - (other[UnusedCargo] + other[Cloaks] + other[Edens])
368 sale_value := quantity * sell_price
369 UpdateCell(table, my_index, EncodeIndex(dims, other), sale_value)
370 }
371 }
372 other[UnusedCargo] = addr[UnusedCargo]
373 }
374
375 func FillCellByBuying(data planet_data, dims []int, table []State, addr []int) {
376 if addr[Hold] == 0 {
377 // Can't buy and then have nothing
378 return
379 }
380 my_index := EncodeIndex(dims, addr)
381 other := make([]int, NumDimensions)
382 copy(other, addr)
383 planet := data.i2p[addr[Location]]
384 commodity := data.i2c[addr[Hold]]
385 if !data.Commodities[commodity].CanSell {
386 return
387 }
388 relative_price, available := data.Planets[planet].RelativePrices[commodity]
389 if !available {
390 return
391 }
392 base_price := data.Commodities[commodity].BasePrice
393 absolute_price := int(float64(base_price) * float64(relative_price) / 100.0)
394 quantity := *hold - (addr[UnusedCargo] + addr[Cloaks] + addr[Edens])
395 total_price := quantity * absolute_price
396 other[Hold] = 0
397 other[UnusedCargo] = 0
398 UpdateCell(table, my_index, EncodeIndex(dims, other), -total_price)
399 other[UnusedCargo] = addr[UnusedCargo]
400 other[Hold] = addr[Hold]
401 }
402
403 func FillCellByMisc(data planet_data, dims []int, table []State, addr []int) {
404 my_index := EncodeIndex(dims, addr)
405 other := make([]int, NumDimensions)
406 copy(other, addr)
407
408 /* Buy a Device of Cloaking */
409 if addr[Cloaks] == 1 && addr[UnusedCargo] < dims[UnusedCargo]-1 {
410 relative_price, available := data.Planets[data.i2p[addr[Location]]].RelativePrices["Device Of Cloakings"]
411 if available {
412 absolute_price := int(float64(data.Commodities["Device Of Cloakings"].BasePrice) * float64(relative_price) / 100.0)
413 other[Cloaks] = 0
414 if other[Hold] != 0 {
415 other[UnusedCargo] = addr[UnusedCargo] + 1
416 }
417 UpdateCell(table, my_index, EncodeIndex(dims, other), -absolute_price)
418 other[UnusedCargo] = addr[UnusedCargo]
419 other[Cloaks] = addr[Cloaks]
420 }
421 }
422
423 /* Silly: Dump a Device of Cloaking */
424
425 /* Buy Fighter Drones */
426 if addr[BuyFighters] == 1 {
427 relative_price, available := data.Planets[data.i2p[addr[Location]]].RelativePrices["Fighter Drones"]
428 if available {
429 absolute_price := int(float64(data.Commodities["Fighter Drones"].BasePrice) * float64(relative_price) / 100.0)
430 other[BuyFighters] = 0
431 UpdateCell(table, my_index, EncodeIndex(dims, other), -absolute_price * *drones)
432 other[BuyFighters] = addr[BuyFighters]
433 }
434 }
435
436 /* Buy Shield Batteries */
437 if addr[BuyShields] == 1 {
438 relative_price, available := data.Planets[data.i2p[addr[Location]]].RelativePrices["Shield Batterys"]
439 if available {
440 absolute_price := int(float64(data.Commodities["Shield Batterys"].BasePrice) * float64(relative_price) / 100.0)
441 other[BuyShields] = 0
442 UpdateCell(table, my_index, EncodeIndex(dims, other), -absolute_price * *batteries)
443 other[BuyShields] = addr[BuyShields]
444 }
445 }
446
447 /* Visit this planet */
448 var i uint
449 for i = 0; i < uint(len(visit())); i++ {
450 if addr[Visit] & (1 << i) != 0 && visit()[i] == data.i2p[addr[Location]] {
451 other[Visit] = addr[Visit] & ^(1 << i)
452 UpdateCell(table, my_index, EncodeIndex(dims, other), 0)
453 }
454 }
455 other[Visit] = addr[Visit]
456
457 }
458
459 func FillCellByBuyingEdens(data planet_data, dims []int, table []State, addr []int) {
460 my_index := EncodeIndex(dims, addr)
461 other := make([]int, NumDimensions)
462 copy(other, addr)
463
464 /* Buy Eden warp units */
465 eden_limit := data.Commodities["Eden Warp Units"].Limit
466 if addr[Edens] > 0 && addr[Edens] <= eden_limit {
467 relative_price, available := data.Planets[data.i2p[addr[Location]]].RelativePrices["Eden Warp Units"]
468 if available {
469 absolute_price := int(float64(data.Commodities["Eden Warp Units"].BasePrice) * float64(relative_price) / 100.0)
470 for quantity := addr[Edens]; quantity > 0; quantity-- {
471 other[Edens] = addr[Edens] - quantity
472 if addr[Hold] != 0 {
473 other[UnusedCargo] = addr[UnusedCargo] + quantity
474 }
475 if other[UnusedCargo] < dims[UnusedCargo] {
476 UpdateCell(table, my_index, EncodeIndex(dims, other), -absolute_price * quantity)
477 }
478 }
479 other[Edens] = addr[Edens]
480 other[UnusedCargo] = addr[UnusedCargo]
481 }
482 }
483 }
484
485 func FillStateTable2Iteration(data planet_data, dims []int, table []State,
486 addr []int, f func(planet_data, []int, []State, []int)) {
487 /* TODO: Justify the safety of the combination of this dimension
488 * iteration and the various phases f. */
489 for addr[Hold] = 0; addr[Hold] < dims[Hold]; addr[Hold]++ {
490 for addr[Cloaks] = 0; addr[Cloaks] < dims[Cloaks]; addr[Cloaks]++ {
491 for addr[UnusedCargo] = 0; addr[UnusedCargo] < dims[UnusedCargo]; addr[UnusedCargo]++ {
492 for addr[BuyFighters] = 0; addr[BuyFighters] < dims[BuyFighters]; addr[BuyFighters]++ {
493 for addr[BuyShields] = 0; addr[BuyShields] < dims[BuyShields]; addr[BuyShields]++ {
494 for addr[Visit] = 0; addr[Visit] < dims[Visit]; addr[Visit]++ {
495 f(data, dims, table, addr)
496 }
497 }
498 }
499 }
500 }
501 }
502 }
503
504 func FillStateTable2(data planet_data, dims []int, table []State,
505 addr []int, barrier chan<- bool) {
506 FillStateTable2Iteration(data, dims, table, addr, FillCellByArriving)
507 FillStateTable2Iteration(data, dims, table, addr, FillCellBySelling)
508 FillStateTable2Iteration(data, dims, table, addr, FillCellByBuying)
509 FillStateTable2Iteration(data, dims, table, addr, FillCellByMisc)
510 FillStateTable2Iteration(data, dims, table, addr, FillCellByBuyingEdens)
511 if barrier != nil {
512 barrier <- true
513 }
514 }
515
516 /* Filling the state table is a set of nested for loops NumDimensions deep.
517 * We split this into two procedures: 1 and 2. #1 is the outer, slowest-
518 * changing indexes. #1 fires off many calls to #2 that run in parallel.
519 * The order of the nesting of the dimensions, the order of iteration within
520 * each dimension, and where the 1 / 2 split is placed are carefully chosen
521 * to make this arrangement safe.
522 *
523 * Outermost two layers: Go from high-energy states (lots of fuel, edens) to
524 * low-energy state. These must be processed sequentially and in this order
525 * because you travel through high-energy states to get to the low-energy
526 * states.
527 *
528 * Third layer: Planet. This is a good layer to parallelize on. There's
529 * high enough cardinality that we don't have to mess with parallelizing
530 * multiple layers for good utilization (on 2011 machines). Each thread
531 * works on one planet's states and need not synchronize with peer threads.
532 */
533 func FillStateTable1(data planet_data, dims []int, table []State) {
534 barrier := make(chan bool, len(data.Planets))
535 eden_capacity := data.Commodities["Eden Warp Units"].Limit
536 work_units := (float64(*fuel) + 1) * (float64(eden_capacity) + 1)
537 work_done := 0.0
538 for fuel_remaining := *fuel; fuel_remaining >= 0; fuel_remaining-- {
539 /* Make an Eden-buying pass (Eden vendors' energy gradient
540 * along the Edens dimension runs backwards) */
541 for edens_remaining := 0; edens_remaining <= eden_capacity; edens_remaining++ {
542 for planet := range data.Planets {
543 if _, available := data.Planets[planet].RelativePrices["Eden Warp Units"]; available {
544 addr := make([]int, len(dims))
545 addr[Edens] = edens_remaining
546 addr[Fuel] = fuel_remaining
547 addr[Location] = data.p2i[planet]
548 FillStateTable2(data, dims, table, addr, nil)
549 }
550 }
551 }
552 for edens_remaining := eden_capacity; edens_remaining >= 0; edens_remaining-- {
553 /* Do the brunt of the work */
554 for planet := range data.Planets {
555 addr := make([]int, len(dims))
556 addr[Edens] = edens_remaining
557 addr[Fuel] = fuel_remaining
558 addr[Location] = data.p2i[planet]
559 go FillStateTable2(data, dims, table, addr, barrier)
560 }
561 for _ = range data.Planets {
562 <-barrier
563 }
564 work_done++
565 print(fmt.Sprintf("\r%3.0f%%", 100*work_done/work_units))
566 }
567 }
568 print("\n")
569 }
570
571 func FindBestState(data planet_data, dims []int, table []State) int {
572 addr := make([]int, NumDimensions)
573 addr[Edens] = *end_edens
574 addr[Cloaks] = dims[Cloaks] - 1
575 addr[BuyFighters] = dims[BuyFighters] - 1
576 addr[BuyShields] = dims[BuyShields] - 1
577 addr[Visit] = dims[Visit] - 1
578 // Fuel, Hold, UnusedCargo left at 0
579 max_index := -1
580 max_value := 0
581 for addr[Location] = 0; addr[Location] < dims[Location]; addr[Location]++ {
582 if len(end()) == 0 || end()[data.i2p[addr[Location]]] {
583 index := EncodeIndex(dims, addr)
584 if table[index].value > max_value {
585 max_value = table[index].value
586 max_index = index
587 }
588 }
589 }
590 return max_index
591 }
592
593 func Commas(n int) (s string) {
594 r := n % 1000
595 n /= 1000
596 for n > 0 {
597 s = fmt.Sprintf(",%03d", r) + s
598 r = n % 1000
599 n /= 1000
600 }
601 s = fmt.Sprint(r) + s
602 return
603 }
604
605 func DescribePath(data planet_data, dims []int, table []State, start int) (description []string) {
606 for index := start; index > 0 && table[index].from > 0; index = table[index].from {
607 var line string
608 addr := DecodeIndex(dims, index)
609 prev := DecodeIndex(dims, table[index].from)
610 if addr[Fuel] != prev[Fuel] {
611 from := data.i2p[prev[Location]]
612 to := data.i2p[addr[Location]]
613 line += fmt.Sprintf("Jump from %v to %v (%v hyper jump units)", from, to, prev[Fuel]-addr[Fuel])
614 }
615 if addr[Edens] == prev[Edens] - 1 {
616 from := data.i2p[prev[Location]]
617 to := data.i2p[addr[Location]]
618 line += fmt.Sprintf("Eden warp from %v to %v", from, to)
619 }
620 if addr[Hold] != prev[Hold] {
621 if addr[Hold] == 0 {
622 quantity := *hold - (prev[UnusedCargo] + prev[Edens] + prev[Cloaks])
623 line += fmt.Sprintf("Sell %v %v", quantity, data.i2c[prev[Hold]])
624 } else if prev[Hold] == 0 {
625 quantity := *hold - (addr[UnusedCargo] + addr[Edens] + addr[Cloaks])
626 line += fmt.Sprintf("Buy %v %v", quantity, data.i2c[addr[Hold]])
627 } else {
628 panic("Switched cargo?")
629 }
630
631 }
632 if addr[Cloaks] == 1 && prev[Cloaks] == 0 {
633 // TODO: Dump cloaks, convert from cargo?
634 line += "Buy a Cloak"
635 }
636 if addr[Edens] > prev[Edens] {
637 line += fmt.Sprint("Buy ", addr[Edens] - prev[Edens], " Eden Warp Units")
638 }
639 if addr[BuyShields] == 1 && prev[BuyShields] == 0 {
640 line += fmt.Sprint("Buy ", *batteries, " Shield Batterys")
641 }
642 if addr[BuyFighters] == 1 && prev[BuyFighters] == 0 {
643 line += fmt.Sprint("Buy ", *drones, " Fighter Drones")
644 }
645 if addr[Visit] != prev[Visit] {
646 // TODO: verify that the bit chat changed is addr[Location]
647 line += fmt.Sprint("Visit ", data.i2p[addr[Location]])
648 }
649 if line == "" {
650 line = fmt.Sprint(prev, " -> ", addr)
651 }
652 description = append(description, fmt.Sprintf("%13v ", Commas(table[index].value)) + line)
653 }
654 return
655 }
656
657 // (Example of a use case for generics in Go)
658 func IndexPlanets(m *map[string]Planet, start_at int) (map[string]int, []string) {
659 e2i := make(map[string]int, len(*m)+start_at)
660 i2e := make([]string, len(*m)+start_at)
661 i := start_at
662 for e := range *m {
663 e2i[e] = i
664 i2e[i] = e
665 i++
666 }
667 return e2i, i2e
668 }
669 func IndexCommodities(m *map[string]Commodity, start_at int) (map[string]int, []string) {
670 e2i := make(map[string]int, len(*m)+start_at)
671 i2e := make([]string, len(*m)+start_at)
672 i := start_at
673 for e := range *m {
674 e2i[e] = i
675 i2e[i] = e
676 i++
677 }
678 return e2i, i2e
679 }
680
681 func main() {
682 flag.Parse()
683 if *cpuprofile != "" {
684 f, err := os.Create(*cpuprofile)
685 if err != nil {
686 panic(err)
687 }
688 pprof.StartCPUProfile(f)
689 defer pprof.StopCPUProfile()
690 }
691 data := ReadData()
692 if *drone_price > 0 {
693 temp := data.Commodities["Fighter Drones"]
694 temp.BasePrice = *drone_price
695 data.Commodities["Fighter Drones"] = temp
696 }
697 if *battery_price > 0 {
698 temp := data.Commodities["Shield Batterys"]
699 temp.BasePrice = *battery_price
700 data.Commodities["Shield Batterys"] = temp
701 }
702 data.p2i, data.i2p = IndexPlanets(&data.Planets, 0)
703 data.c2i, data.i2c = IndexCommodities(&data.Commodities, 1)
704 dims := DimensionSizes(data)
705 table := InitializeStateTable(data, dims)
706 FillStateTable1(data, dims, table)
707 best := FindBestState(data, dims, table)
708 if best == -1 {
709 print("Cannot acheive success criteria\n")
710 } else {
711 description := DescribePath(data, dims, table, best)
712 for i := len(description) - 1; i >= 0; i-- {
713 fmt.Println(description[i])
714 }
715 }
716 }