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