git.scottworley.com Git - planeteer/blob - 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_hold = flag.String("start_hold", "", "Start with a hold full of cargo")
  47
  48 var start_edens = flag.Int("start_edens", 0,
  49         "How many Eden Warp Units are you starting with?")
  50
  51 var end_edens = flag.Int("end_edens", 0,
  52         "How many Eden Warp Units would you like to keep (not use)?")
  53
  54 var cloak = flag.Bool("cloak", false,
  55         "Make sure to end with a Device of Cloaking")
  56
  57 var drones = flag.Int("drones", 0, "Buy this many Fighter Drones")
  58
  59 var batteries = flag.Int("batteries", 0, "Buy this many Shield Batterys")
  60
  61 var drone_price = flag.Int("drone_price", 0, "Today's Fighter Drone price")
  62
  63 var battery_price = flag.Int("battery_price", 0, "Today's Shield Battery price")
  64
  65 var visit_string = flag.String("visit", "",
  66         "A comma-separated list of planets to make sure to visit")
  67
  68 var cpuprofile = flag.String("cpuprofile", "", "write cpu profile to file")
  69
  70 var visit_cache []string
  71
  72 func visit() []string {
  73         if visit_cache == nil {
  74                 if *visit_string == "" {
  75                         return nil
  76                 }
  77                 visit_cache = strings.Split(*visit_string, ",")
  78         }
  79         return visit_cache
  80 }
  81
  82 var flight_plan_cache []string
  83
  84 func flight_plan() []string {
  85         if flight_plan_cache == nil {
  86                 if *flight_plan_string == "" {
  87                         return nil
  88                 }
  89                 flight_plan_cache = strings.Split(*flight_plan_string, ",")
  90         }
  91         return flight_plan_cache
  92 }
  93
  94 var end_cache map[string]bool
  95
  96 func end() map[string]bool {
  97         if end_cache == nil {
  98                 if *end_string == "" {
  99                         return nil
 100                 }
 101                 m := make(map[string]bool)
 102                 for _, p := range strings.Split(*end_string, ",") {
 103                         m[p] = true
 104                 }
 105                 end_cache = m
 106         }
 107         return end_cache
 108 }
 109
 110 type Commodity struct {
 111         BasePrice int
 112         CanSell   bool
 113         Limit     int
 114 }
 115 type Planet struct {
 116         BeaconOn bool
 117         Private  bool
 118         /* Use relative prices rather than absolute prices because you
 119            can get relative prices without traveling to each planet. */
 120         RelativePrices map[string]int
 121 }
 122 type planet_data struct {
 123         Commodities map[string]Commodity
 124         Planets     map[string]Planet
 125         p2i, c2i    map[string]int // Generated; not read from file
 126         i2p, i2c    []string       // Generated; not read from file
 127 }
 128
 129 func ReadData() (data planet_data) {
 130         f, err := os.Open(*planet_data_file)
 131         if err != nil {
 132                 panic(err)
 133         }
 134         defer f.Close()
 135         err = json.NewDecoder(f).Decode(&data)
 136         if err != nil {
 137                 panic(err)
 138         }
 139         return
 140 }
 141
 142 /* This program operates by filling in a state table representing the best
 143  * possible trips you could make; the ones that makes you the most money.
 144  * This is feasible because we don't look at all the possible trips.
 145  * We define a list of things that are germane to this game and then only
 146  * consider the best outcome in each possible game state.
 147  *
 148  * Each cell in the table represents a state in the game.  In each cell,
 149  * we track two things: 1. the most money you could possibly have while in
 150  * that state and 2. one possible way to get into that state with that
 151  * amount of money.
 152  *
 153  * A basic analysis can be done with a two-dimensional table: location and
 154  * fuel.  planeteer-1.0 used this two-dimensional table.  This version
 155  * adds features mostly by adding dimensions to this table.
 156  *
 157  * Note that the sizes of each dimension are data driven.  Many dimensions
 158  * collapse to one possible value (ie, disappear) if the corresponding
 159  * feature is not enabled.
 160  *
 161  * The order of the dimensions in the list of constants below determines
 162  * their layout in RAM.  The cargo-based 'dimensions' are not completely
 163  * independent -- some combinations are illegal and not used.  They are
 164  * handled as three dimensions rather than one for simplicity.  Placing
 165  * these dimensions first causes the unused cells in the table to be
 166  * grouped together in large blocks.  This keeps them from polluting
 167  * cache lines, and if they are large enough, allows the memory manager
 168  * to swap out entire pages.
 169  *
 170  * If the table gets too big to fit in RAM:
 171  *    * Combine the Edens, Cloaks, and UnusedCargo dimensions.  Of the
 172  *      24 combinations, only 15 are legal: a 38% savings.
 173  *    * Reduce the size of the Fuel dimension to 3.  We only ever look
 174  *      backwards 2 units, so just rotate the logical values through
 175  *      the same 3 physical addresses.  This is good for an 82% savings.
 176  *    * Reduce the size of the Edens dimension from 3 to 2, for the
 177  *      same reasons as Fuel above.  33% savings.
 178  *    * Buy more ram.  (Just sayin'.  It's cheaper than you think.)
 179  *
 180  */
 181
 182 // The official list of dimensions:
 183 const (
 184         // Name                Num   Size  Description
 185         Edens       = iota //   1      3  # of Eden warp units (0 - 2 typically)
 186         Cloaks             //   2    1-2  # of Devices of Cloaking (0 or 1)
 187         UnusedCargo        //   3      4  # of unused cargo spaces (0 - 3 typically)
 188         Fuel               //   4     17  Hyper jump power left (0 - 16)
 189         Location           //   5     26  Location (which planet)
 190         Hold               //   6     15  Cargo bay contents (a *Commodity or nil)
 191         Traded             //   7      2  Traded yet?
 192         BuyFighters        //   8    1-2  Errand: Buy fighter drones
 193         BuyShields         //   9    1-2  Errand: Buy shield batteries
 194         Visit              //  10 1-2**N  Visit: Stop by these N planets in the route
 195
 196         NumDimensions
 197 )
 198
 199 func bint(b bool) int {
 200         if b {
 201                 return 1
 202         }
 203         return 0
 204 }
 205
 206 func DimensionSizes(data planet_data) []int {
 207         eden_capacity := data.Commodities["Eden Warp Units"].Limit
 208         if *start_edens > eden_capacity {
 209                 eden_capacity = *start_edens
 210         }
 211         cloak_capacity := bint(*cloak)
 212         dims := make([]int, NumDimensions)
 213         dims[Edens] = eden_capacity + 1
 214         dims[Cloaks] = cloak_capacity + 1
 215         dims[UnusedCargo] = eden_capacity + cloak_capacity + 1
 216         dims[Fuel] = *fuel + 1
 217         dims[Location] = len(data.Planets)
 218         dims[Hold] = len(data.Commodities) + 1
 219         dims[Traded] = 2
 220         dims[BuyFighters] = bint(*drones > 0) + 1
 221         dims[BuyShields] = bint(*batteries > 0) + 1
 222         dims[Visit] = 1 << uint(len(visit()))
 223
 224         // Remind myself to add a line above when adding new dimensions
 225         for i, dim := range dims {
 226                 if dim < 1 {
 227                         panic(i)
 228                 }
 229         }
 230         return dims
 231 }
 232
 233 func StateTableSize(dims []int) int {
 234         product := 1
 235         for _, size := range dims {
 236                 product *= size
 237         }
 238         return product
 239 }
 240
 241 type State struct {
 242         value, from int32
 243 }
 244
 245 const (
 246         FROM_ROOT = -2147483647 + iota
 247         FROM_UNINITIALIZED
 248         VALUE_UNINITIALIZED
 249         VALUE_BEING_EVALUATED
 250         VALUE_RUBISH
 251 )
 252
 253 func EncodeIndex(dims, addr []int) int32 {
 254         index := addr[0]
 255         if addr[0] > dims[0] {
 256                 panic(0)
 257         }
 258         for i := 1; i < NumDimensions; i++ {
 259                 if addr[i] < 0 || addr[i] >= dims[i] {
 260                         panic(i)
 261                 }
 262                 index = index*dims[i] + addr[i]
 263         }
 264         return int32(index)
 265 }
 266
 267 func DecodeIndex(dims []int, index int32) []int {
 268         addr := make([]int, NumDimensions)
 269         for i := NumDimensions - 1; i > 0; i-- {
 270                 addr[i] = int(index) % dims[i]
 271                 index /= int32(dims[i])
 272         }
 273         addr[0] = int(index)
 274         return addr
 275 }
 276
 277 func CreateStateTable(data planet_data, dims []int) []State {
 278         table := make([]State, StateTableSize(dims))
 279         for i := range table {
 280                 table[i].value = VALUE_UNINITIALIZED
 281                 table[i].from = FROM_UNINITIALIZED
 282         }
 283
 284         addr := make([]int, NumDimensions)
 285         addr[Fuel] = *fuel
 286         addr[Edens] = *start_edens
 287         addr[Location] = data.p2i[*start]
 288         if *start_hold != "" {
 289                 addr[Hold] = data.c2i[*start_hold]
 290         }
 291         start_index := EncodeIndex(dims, addr)
 292         table[start_index].value = int32(*funds)
 293         table[start_index].from = FROM_ROOT
 294
 295         return table
 296 }
 297
 298 /* CellValue fills in the one cell at address addr by looking at all
 299  * the possible ways to reach this cell and selecting the best one. */
 300
 301 func Consider(data planet_data, dims []int, table []State, there []int, value_difference int, best_value *int32, best_source []int) {
 302         there_value := CellValue(data, dims, table, there)
 303         if value_difference < 0 && int32(-value_difference) > there_value {
 304                 /* Can't afford this transition */
 305                 return
 306         }
 307         possible_value := there_value + int32(value_difference)
 308         if possible_value > *best_value {
 309                 *best_value = possible_value
 310                 copy(best_source, there)
 311         }
 312 }
 313
 314 var cell_filled_count int
 315
 316 func CellValue(data planet_data, dims []int, table []State, addr []int) int32 {
 317         my_index := EncodeIndex(dims, addr)
 318         if table[my_index].value == VALUE_BEING_EVALUATED {
 319                 panic("Circular dependency")
 320         }
 321         if table[my_index].value != VALUE_UNINITIALIZED {
 322                 return table[my_index].value
 323         }
 324         table[my_index].value = VALUE_BEING_EVALUATED
 325
 326         best_value := int32(VALUE_RUBISH)
 327         best_source := make([]int, NumDimensions)
 328         other := make([]int, NumDimensions)
 329         copy(other, addr)
 330         planet := data.i2p[addr[Location]]
 331
 332         /* Travel here */
 333         if addr[Traded] == 0 { /* Can't have traded immediately after traveling. */
 334                 other[Traded] = 1 /* Travel from states that have done trading. */
 335
 336                 /* Travel here via a 2-fuel unit jump */
 337                 if addr[Fuel]+2 < dims[Fuel] {
 338                         other[Fuel] = addr[Fuel] + 2
 339                         hole_index := (dims[Fuel] - 1) - (addr[Fuel] + 2)
 340                         if hole_index >= len(flight_plan()) || addr[Location] != data.p2i[flight_plan()[hole_index]] {
 341                                 for other[Location] = 0; other[Location] < dims[Location]; other[Location]++ {
 342                                         if data.Planets[data.i2p[addr[Location]]].BeaconOn {
 343                                                 Consider(data, dims, table, other, 0, &best_value, best_source)
 344                                         }
 345                                 }
 346                         }
 347                         other[Location] = addr[Location]
 348                         other[Fuel] = addr[Fuel]
 349                 }
 350
 351                 /* Travel here via a 1-fuel unit jump (a hyper hole) */
 352                 if addr[Fuel]+1 < dims[Fuel] {
 353                         hole_index := (dims[Fuel] - 1) - (addr[Fuel] + 1)
 354                         if hole_index < len(flight_plan()) && addr[Location] == data.p2i[flight_plan()[hole_index]] {
 355                                 other[Fuel] = addr[Fuel] + 1
 356                                 for other[Location] = 0; other[Location] < dims[Location]; other[Location]++ {
 357                                         Consider(data, dims, table, other, 0, &best_value, best_source)
 358                                 }
 359                                 other[Location] = addr[Location]
 360                                 other[Fuel] = addr[Fuel]
 361                         }
 362                 }
 363
 364                 /* Travel here via Eden Warp Unit */
 365                 if addr[Edens]+1 < dims[Edens] && addr[UnusedCargo] > 0 {
 366                         _, available := data.Planets[data.i2p[addr[Location]]].RelativePrices["Eden Warp Units"]
 367                         if !available {
 368                                 other[Edens] = addr[Edens] + 1
 369                                 if other[Hold] != 0 {
 370                                         other[UnusedCargo] = addr[UnusedCargo] - 1
 371                                 }
 372                                 for other[Location] = 0; other[Location] < dims[Location]; other[Location]++ {
 373                                         Consider(data, dims, table, other, 0, &best_value, best_source)
 374                                 }
 375                                 other[Location] = addr[Location]
 376                                 other[UnusedCargo] = addr[UnusedCargo]
 377                                 other[Edens] = addr[Edens]
 378                         }
 379                 }
 380                 other[Traded] = addr[Traded]
 381         }
 382
 383         /* Trade */
 384         if addr[Traded] == 1 {
 385                 other[Traded] = 0
 386
 387                 /* Consider not trading */
 388                 Consider(data, dims, table, other, 0, &best_value, best_source)
 389
 390                 if !data.Planets[data.i2p[addr[Location]]].Private {
 391
 392                         /* Sell */
 393                         if addr[Hold] == 0 && addr[UnusedCargo] == 0 {
 394                                 for other[Hold] = 0; other[Hold] < dims[Hold]; other[Hold]++ {
 395                                         commodity := data.i2c[other[Hold]]
 396                                         if !data.Commodities[commodity].CanSell {
 397                                                 continue
 398                                         }
 399                                         relative_price, available := data.Planets[planet].RelativePrices[commodity]
 400                                         if !available {
 401                                                 // TODO: Dump cargo
 402                                                 continue
 403                                         }
 404                                         base_price := data.Commodities[commodity].BasePrice
 405                                         absolute_price := float64(base_price) * float64(relative_price) / 100.0
 406                                         sell_price := int(absolute_price * 0.9)
 407
 408                                         for other[UnusedCargo] = 0; other[UnusedCargo] < dims[UnusedCargo]; other[UnusedCargo]++ {
 409                                                 quantity := *hold - (other[UnusedCargo] + other[Cloaks] + other[Edens])
 410                                                 sale_value := quantity * sell_price
 411                                                 Consider(data, dims, table, other, sale_value, &best_value, best_source)
 412                                         }
 413                                 }
 414                                 other[UnusedCargo] = addr[UnusedCargo]
 415                                 other[Hold] = addr[Hold]
 416                         }
 417
 418                         /* Buy */
 419                         other[Traded] = addr[Traded] /* Buy after selling */
 420                         if addr[Hold] != 0 {
 421                                 commodity := data.i2c[addr[Hold]]
 422                                 if data.Commodities[commodity].CanSell {
 423                                         relative_price, available := data.Planets[planet].RelativePrices[commodity]
 424                                         if available {
 425                                                 base_price := data.Commodities[commodity].BasePrice
 426                                                 absolute_price := int(float64(base_price) * float64(relative_price) / 100.0)
 427                                                 quantity := *hold - (addr[UnusedCargo] + addr[Cloaks] + addr[Edens])
 428                                                 total_price := quantity * absolute_price
 429                                                 other[Hold] = 0
 430                                                 other[UnusedCargo] = 0
 431                                                 Consider(data, dims, table, other, -total_price, &best_value, best_source)
 432                                                 other[UnusedCargo] = addr[UnusedCargo]
 433                                                 other[Hold] = addr[Hold]
 434                                         }
 435                                 }
 436                         }
 437                 }
 438                 other[Traded] = addr[Traded]
 439         }
 440
 441         /* Buy a Device of Cloaking */
 442         if addr[Cloaks] == 1 && addr[UnusedCargo] < dims[UnusedCargo]-1 {
 443                 relative_price, available := data.Planets[data.i2p[addr[Location]]].RelativePrices["Device Of Cloakings"]
 444                 if available {
 445                         absolute_price := int(float64(data.Commodities["Device Of Cloakings"].BasePrice) * float64(relative_price) / 100.0)
 446                         other[Cloaks] = 0
 447                         if other[Hold] != 0 {
 448                                 other[UnusedCargo] = addr[UnusedCargo] + 1
 449                         }
 450                         Consider(data, dims, table, other, -absolute_price, &best_value, best_source)
 451                         other[UnusedCargo] = addr[UnusedCargo]
 452                         other[Cloaks] = addr[Cloaks]
 453                 }
 454         }
 455
 456         /* Buy Fighter Drones */
 457         if addr[BuyFighters] == 1 {
 458                 relative_price, available := data.Planets[data.i2p[addr[Location]]].RelativePrices["Fighter Drones"]
 459                 if available {
 460                         absolute_price := int(float64(data.Commodities["Fighter Drones"].BasePrice) * float64(relative_price) / 100.0)
 461                         other[BuyFighters] = 0
 462                         Consider(data, dims, table, other, -absolute_price**drones, &best_value, best_source)
 463                         other[BuyFighters] = addr[BuyFighters]
 464                 }
 465         }
 466
 467         /* Buy Shield Batteries */
 468         if addr[BuyShields] == 1 {
 469                 relative_price, available := data.Planets[data.i2p[addr[Location]]].RelativePrices["Shield Batterys"]
 470                 if available {
 471                         absolute_price := int(float64(data.Commodities["Shield Batterys"].BasePrice) * float64(relative_price) / 100.0)
 472                         other[BuyShields] = 0
 473                         Consider(data, dims, table, other, -absolute_price**batteries, &best_value, best_source)
 474                         other[BuyShields] = addr[BuyShields]
 475                 }
 476         }
 477
 478         /* Visit this planet */
 479         var i uint
 480         for i = 0; i < uint(len(visit())); i++ {
 481                 if addr[Visit]&(1<<i) != 0 && visit()[i] == data.i2p[addr[Location]] {
 482                         other[Visit] = addr[Visit] & ^(1 << i)
 483                         Consider(data, dims, table, other, 0, &best_value, best_source)
 484                 }
 485         }
 486         other[Visit] = addr[Visit]
 487
 488         /* Buy Eden warp units */
 489         eden_limit := data.Commodities["Eden Warp Units"].Limit
 490         if addr[Edens] > 0 && addr[Edens] <= eden_limit {
 491                 relative_price, available := data.Planets[data.i2p[addr[Location]]].RelativePrices["Eden Warp Units"]
 492                 if available {
 493                         absolute_price := int(float64(data.Commodities["Eden Warp Units"].BasePrice) * float64(relative_price) / 100.0)
 494                         for quantity := addr[Edens]; quantity > 0; quantity-- {
 495                                 other[Edens] = addr[Edens] - quantity
 496                                 if addr[Hold] != 0 {
 497                                         other[UnusedCargo] = addr[UnusedCargo] + quantity
 498                                 }
 499                                 if other[UnusedCargo] < dims[UnusedCargo] {
 500                                         Consider(data, dims, table, other, -absolute_price*quantity, &best_value, best_source)
 501                                 }
 502                         }
 503                         other[Edens] = addr[Edens]
 504                         other[UnusedCargo] = addr[UnusedCargo]
 505                 }
 506         }
 507
 508         // Check that we didn't lose track of any temporary modifications to other.
 509         for i := 0; i < NumDimensions; i++ {
 510                 if addr[i] != other[i] {
 511                         panic(i)
 512                 }
 513         }
 514
 515         // Sanity check: This cell was in state BEING_EVALUATED
 516         // the whole time that it was being evaluated.
 517         if table[my_index].value != VALUE_BEING_EVALUATED {
 518                 panic(my_index)
 519         }
 520
 521         // Record our findings
 522         table[my_index].value = best_value
 523         table[my_index].from = EncodeIndex(dims, best_source)
 524
 525         // UI: Progress bar
 526         cell_filled_count++
 527         if cell_filled_count&0xfff == 0 {
 528                 print(fmt.Sprintf("\r%3.1f%%", 100*float64(cell_filled_count)/float64(StateTableSize(dims))))
 529         }
 530
 531         return table[my_index].value
 532 }
 533
 534 func FindBestState(data planet_data, dims []int, table []State) int32 {
 535         addr := make([]int, NumDimensions)
 536         addr[Edens] = *end_edens
 537         addr[Cloaks] = dims[Cloaks] - 1
 538         addr[BuyFighters] = dims[BuyFighters] - 1
 539         addr[BuyShields] = dims[BuyShields] - 1
 540         addr[Visit] = dims[Visit] - 1
 541         addr[Traded] = 1
 542         addr[Hold] = 0
 543         addr[UnusedCargo] = 0
 544         max_index := int32(-1)
 545         max_value := int32(0)
 546         max_fuel := 1
 547         if *fuel == 0 {
 548                 max_fuel = 0
 549         }
 550         for addr[Fuel] = 0; addr[Fuel] <= max_fuel; addr[Fuel]++ {
 551                 for addr[Location] = 0; addr[Location] < dims[Location]; addr[Location]++ {
 552                         if len(end()) == 0 || end()[data.i2p[addr[Location]]] {
 553                                 index := EncodeIndex(dims, addr)
 554                                 value := CellValue(data, dims, table, addr)
 555                                 if value > max_value {
 556                                         max_value = value
 557                                         max_index = index
 558                                 }
 559                         }
 560                 }
 561         }
 562         return max_index
 563 }
 564
 565 func Commas(n int32) (s string) {
 566         r := n % 1000
 567         n /= 1000
 568         for n > 0 {
 569                 s = fmt.Sprintf(",%03d", r) + s
 570                 r = n % 1000
 571                 n /= 1000
 572         }
 573         s = fmt.Sprint(r) + s
 574         return
 575 }
 576
 577 func DescribePath(data planet_data, dims []int, table []State, start int32) (description []string) {
 578         for index := start; table[index].from > FROM_ROOT; index = table[index].from {
 579                 if table[index].from == FROM_UNINITIALIZED {
 580                         panic(index)
 581                 }
 582                 var line string
 583                 addr := DecodeIndex(dims, index)
 584                 prev := DecodeIndex(dims, table[index].from)
 585                 if addr[Fuel] != prev[Fuel] {
 586                         from := data.i2p[prev[Location]]
 587                         to := data.i2p[addr[Location]]
 588                         line += fmt.Sprintf("Jump from %v to %v (%v hyper jump units)", from, to, prev[Fuel]-addr[Fuel])
 589                 }
 590                 if addr[Edens] == prev[Edens]-1 {
 591                         from := data.i2p[prev[Location]]
 592                         to := data.i2p[addr[Location]]
 593                         line += fmt.Sprintf("Eden warp from %v to %v", from, to)
 594                 }
 595                 if addr[Hold] != prev[Hold] {
 596                         if addr[Hold] == 0 {
 597                                 quantity := *hold - (prev[UnusedCargo] + prev[Edens] + prev[Cloaks])
 598                                 line += fmt.Sprintf("Sell %v %v", quantity, data.i2c[prev[Hold]])
 599                         } else if prev[Hold] == 0 {
 600                                 quantity := *hold - (addr[UnusedCargo] + addr[Edens] + addr[Cloaks])
 601                                 line += fmt.Sprintf("Buy %v %v", quantity, data.i2c[addr[Hold]])
 602                         } else {
 603                                 panic("Switched cargo?")
 604                         }
 605
 606                 }
 607                 if addr[Cloaks] == 1 && prev[Cloaks] == 0 {
 608                         // TODO: Dump cloaks, convert from cargo?
 609                         line += "Buy a Cloak"
 610                 }
 611                 if addr[Edens] > prev[Edens] {
 612                         line += fmt.Sprint("Buy ", addr[Edens]-prev[Edens], " Eden Warp Units")
 613                 }
 614                 if addr[BuyShields] == 1 && prev[BuyShields] == 0 {
 615                         line += fmt.Sprint("Buy ", *batteries, " Shield Batterys")
 616                 }
 617                 if addr[BuyFighters] == 1 && prev[BuyFighters] == 0 {
 618                         line += fmt.Sprint("Buy ", *drones, " Fighter Drones")
 619                 }
 620                 if addr[Visit] != prev[Visit] {
 621                         // TODO: verify that the bit chat changed is addr[Location]
 622                         line += fmt.Sprint("Visit ", data.i2p[addr[Location]])
 623                 }
 624                 if line == "" && addr[Hold] == prev[Hold] && addr[Traded] != prev[Traded] {
 625                         // The Traded dimension is for housekeeping.  It doesn't directly
 626                         // correspond to in-game actions, so don't report transitions.
 627                         continue
 628                 }
 629                 if line == "" {
 630                         line = fmt.Sprint(prev, " -> ", addr)
 631                 }
 632                 description = append(description, fmt.Sprintf("%13v ", Commas(table[index].value))+line)
 633         }
 634         return
 635 }
 636
 637 // (Example of a use case for generics in Go)
 638 func IndexPlanets(m *map[string]Planet, start_at int) (map[string]int, []string) {
 639         e2i := make(map[string]int, len(*m)+start_at)
 640         i2e := make([]string, len(*m)+start_at)
 641         i := start_at
 642         for e := range *m {
 643                 e2i[e] = i
 644                 i2e[i] = e
 645                 i++
 646         }
 647         return e2i, i2e
 648 }
 649 func IndexCommodities(m *map[string]Commodity, start_at int) (map[string]int, []string) {
 650         e2i := make(map[string]int, len(*m)+start_at)
 651         i2e := make([]string, len(*m)+start_at)
 652         i := start_at
 653         for e := range *m {
 654                 e2i[e] = i
 655                 i2e[i] = e
 656                 i++
 657         }
 658         return e2i, i2e
 659 }
 660
 661 func main() {
 662         flag.Parse()
 663         if *start == "" || *funds == 0 {
 664                 print("--start and --funds are required.  --help for more\n")
 665                 return
 666         }
 667         if *cpuprofile != "" {
 668                 f, err := os.Create(*cpuprofile)
 669                 if err != nil {
 670                         panic(err)
 671                 }
 672                 pprof.StartCPUProfile(f)
 673                 defer pprof.StopCPUProfile()
 674         }
 675         data := ReadData()
 676         if *drone_price > 0 {
 677                 temp := data.Commodities["Fighter Drones"]
 678                 temp.BasePrice = *drone_price
 679                 data.Commodities["Fighter Drones"] = temp
 680         }
 681         if *battery_price > 0 {
 682                 temp := data.Commodities["Shield Batterys"]
 683                 temp.BasePrice = *battery_price
 684                 data.Commodities["Shield Batterys"] = temp
 685         }
 686         data.p2i, data.i2p = IndexPlanets(&data.Planets, 0)
 687         data.c2i, data.i2c = IndexCommodities(&data.Commodities, 1)
 688         dims := DimensionSizes(data)
 689         table := CreateStateTable(data, dims)
 690         best := FindBestState(data, dims, table)
 691         print("\n")
 692         if best == -1 {
 693                 print("Cannot acheive success criteria\n")
 694         } else {
 695                 description := DescribePath(data, dims, table, best)
 696                 for i := len(description) - 1; i >= 0; i-- {
 697                         fmt.Println(description[i])
 698                 }
 699         }
 700 }