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_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         Private bool
 114         /* Use relative prices rather than absolute prices because you
 115            can get relative prices without traveling to each planet. */
 116         RelativePrices map[string]int
 117 }
 118 type planet_data struct {
 119         Commodities map[string]Commodity
 120         Planets     map[string]Planet
 121         p2i, c2i    map[string]int // Generated; not read from file
 122         i2p, i2c    []string       // Generated; not read from file
 123 }
 124
 125 func ReadData() (data planet_data) {
 126         f, err := os.Open(*planet_data_file)
 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
 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.
 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, allows the memory manager
 164  * to swap out entire pages.
 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  *
 176  */
 177
 178 // The official list of dimensions:
 179 const (
 180         // Name                Num   Size  Description
 181         Edens        = iota //   1      3  # of Eden warp units (0 - 2 typically)
 182         Cloaks              //   2    1-2  # of Devices of Cloaking (0 or 1)
 183         UnusedCargo         //   3      4  # of unused cargo spaces (0 - 3 typically)
 184         Fuel                //   4     17  Hyper jump power left (0 - 16)
 185         Location            //   5     26  Location (which planet)
 186         Hold                //   6     15  Cargo bay contents (a *Commodity or nil)
 187         Traded              //   7      2  Traded yet?
 188         BuyFighters         //   8    1-2  Errand: Buy fighter drones
 189         BuyShields          //   9    1-2  Errand: Buy shield batteries
 190         Visit               //  10 1-2**N  Visit: Stop by these N planets in the route
 191
 192         NumDimensions
 193 )
 194
 195 func bint(b bool) int {
 196         if b {
 197                 return 1
 198         }
 199         return 0
 200 }
 201
 202 func DimensionSizes(data planet_data) []int {
 203         eden_capacity := data.Commodities["Eden Warp Units"].Limit
 204         if *start_edens > eden_capacity {
 205                 eden_capacity = *start_edens
 206         }
 207         cloak_capacity := bint(*cloak)
 208         dims := make([]int, NumDimensions)
 209         dims[Edens] = eden_capacity + 1
 210         dims[Cloaks] = cloak_capacity + 1
 211         dims[UnusedCargo] = eden_capacity + cloak_capacity + 1
 212         dims[Fuel] = *fuel + 1
 213         dims[Location] = len(data.Planets)
 214         dims[Hold] = len(data.Commodities) + 1
 215         dims[Traded] = 2
 216         dims[BuyFighters] = bint(*drones > 0) + 1
 217         dims[BuyShields] = bint(*batteries > 0) + 1
 218         dims[Visit] = 1 << uint(len(visit()))
 219
 220         // Remind myself to add a line above when adding new dimensions
 221         for i, dim := range dims {
 222                 if dim < 1 {
 223                         panic(i)
 224                 }
 225         }
 226         return dims
 227 }
 228
 229 func StateTableSize(dims []int) int {
 230         product := 1
 231         for _, size := range dims {
 232                 product *= size
 233         }
 234         return product
 235 }
 236
 237 type State struct {
 238         value, from int32
 239 }
 240
 241 const CELL_UNINITIALIZED =   -2147483647
 242 const CELL_BEING_EVALUATED = -2147483646
 243 const CELL_RUBISH =          -2147483645
 244
 245 func EncodeIndex(dims, addr []int) int32 {
 246         index := int32(addr[0])
 247         if addr[0] > dims[0] {
 248                 panic(0)
 249         }
 250         for i := 1; i < NumDimensions; i++ {
 251                 if addr[i] < 0 || addr[i] > dims[i] {
 252                         panic(i)
 253                 }
 254                 index = index*int32(dims[i]) + int32(addr[i])
 255         }
 256         return index
 257 }
 258
 259 func DecodeIndex(dims []int, index int32) []int {
 260         addr := make([]int, NumDimensions)
 261         for i := NumDimensions - 1; i > 0; i-- {
 262                 addr[i] = int(index) % dims[i]
 263                 index /= int32(dims[i])
 264         }
 265         addr[0] = int(index)
 266         return addr
 267 }
 268
 269 func CreateStateTable(data planet_data, dims []int) []State {
 270         table := make([]State, StateTableSize(dims))
 271         for i := range table {
 272                 table[i].value = CELL_UNINITIALIZED
 273         }
 274
 275         addr := make([]int, NumDimensions)
 276         addr[Fuel] = *fuel
 277         addr[Edens] = *start_edens
 278         addr[Location] = data.p2i[*start]
 279         addr[Traded] = 1
 280         table[EncodeIndex(dims, addr)].value = int32(*funds)
 281
 282         return table
 283 }
 284
 285 /* CellValue fills in the one cell at address addr by looking at all
 286  * the possible ways to reach this cell and selecting the best one. */
 287
 288 func Consider(data planet_data, dims []int, table []State, there []int, value_difference int, best_value *int32, best_source []int) {
 289         there_value := CellValue(data, dims, table, there)
 290         if value_difference < 0 && int32(-value_difference) > there_value {
 291                 /* Can't afford this transition */
 292                 return
 293         }
 294         possible_value := there_value + int32(value_difference)
 295         if possible_value > *best_value {
 296                 *best_value = possible_value
 297                 copy(best_source, there)
 298         }
 299 }
 300
 301 var cell_filled_count int
 302 func CellValue(data planet_data, dims []int, table []State, addr []int) int32 {
 303         my_index := EncodeIndex(dims, addr)
 304         if table[my_index].value == CELL_BEING_EVALUATED {
 305                 panic("Circular dependency")
 306         }
 307         if table[my_index].value != CELL_UNINITIALIZED {
 308                 return table[my_index].value
 309         }
 310         table[my_index].value = CELL_BEING_EVALUATED
 311
 312         best_value := int32(CELL_RUBISH)
 313         best_source := make([]int, NumDimensions)
 314         other := make([]int, NumDimensions)
 315         copy(other, addr)
 316         planet := data.i2p[addr[Location]]
 317
 318         /* Travel here */
 319         if addr[Traded] == 0 { /* Can't have traded immediately after traveling. */
 320                 other[Traded] = 1 /* Travel from states that have done trading. */
 321
 322                 /* Travel here via a 2-fuel unit jump */
 323                 if addr[Fuel]+2 < dims[Fuel] {
 324                         other[Fuel] = addr[Fuel] + 2
 325                         hole_index := (dims[Fuel] - 1) - (addr[Fuel] + 2)
 326                         if hole_index >= len(flight_plan()) || addr[Location] != data.p2i[flight_plan()[hole_index]] {
 327                                 for other[Location] = 0; other[Location] < dims[Location]; other[Location]++ {
 328                                         if data.Planets[data.i2p[addr[Location]]].BeaconOn {
 329                                                 Consider(data, dims, table, other, 0, &best_value, best_source)
 330                                         }
 331                                 }
 332                         }
 333                         other[Location] = addr[Location]
 334                         other[Fuel] = addr[Fuel]
 335                 }
 336
 337                 /* Travel here via a 1-fuel unit jump (a hyper hole) */
 338                 if addr[Fuel]+1 < dims[Fuel] {
 339                         hole_index := (dims[Fuel] - 1) - (addr[Fuel] + 1)
 340                         if hole_index < len(flight_plan()) && addr[Location] == data.p2i[flight_plan()[hole_index]] {
 341                                 other[Fuel] = addr[Fuel] + 1
 342                                 for other[Location] = 0; other[Location] < dims[Location]; other[Location]++ {
 343                                         Consider(data, dims, table, other, 0, &best_value, best_source)
 344                                 }
 345                                 other[Location] = addr[Location]
 346                                 other[Fuel] = addr[Fuel]
 347                         }
 348                 }
 349
 350                 /* Travel here via Eden Warp Unit */
 351                 if addr[Edens]+1 < dims[Edens] && addr[UnusedCargo] > 1 {
 352                         _, available := data.Planets[data.i2p[addr[Location]]].RelativePrices["Eden Warp Units"]
 353                         if !available {
 354                                 other[Edens] = addr[Edens] + 1
 355                                 if other[Hold] != 0 {
 356                                         other[UnusedCargo] = addr[UnusedCargo] - 1
 357                                 }
 358                                 for other[Location] = 0; other[Location] < dims[Location]; other[Location]++ {
 359                                         Consider(data, dims, table, other, 0, &best_value, best_source)
 360                                 }
 361                                 other[Location] = addr[Location]
 362                                 other[UnusedCargo] = addr[UnusedCargo]
 363                                 other[Edens] = addr[Edens]
 364                         }
 365                 }
 366                 other[Traded] = addr[Traded]
 367         }
 368
 369         /* Trade */
 370         if addr[Traded] == 1 {
 371                 other[Traded] = 0
 372
 373                 /* Consider not trading */
 374                 Consider(data, dims, table, other, 0, &best_value, best_source)
 375
 376                 if !data.Planets[data.i2p[addr[Location]]].Private {
 377
 378                         /* Sell */
 379                         if addr[Hold] == 0 && addr[UnusedCargo] == 0 {
 380                                 for other[Hold] = 0; other[Hold] < dims[Hold]; other[Hold]++ {
 381                                         commodity := data.i2c[other[Hold]]
 382                                         if !data.Commodities[commodity].CanSell {
 383                                                 continue
 384                                         }
 385                                         relative_price, available := data.Planets[planet].RelativePrices[commodity]
 386                                         if !available {
 387                                                 // TODO: Dump cargo
 388                                                 continue
 389                                         }
 390                                         base_price := data.Commodities[commodity].BasePrice
 391                                         absolute_price := float64(base_price) * float64(relative_price) / 100.0
 392                                         sell_price := int(absolute_price * 0.9)
 393
 394                                         for other[UnusedCargo] = 0; other[UnusedCargo] < dims[UnusedCargo]; other[UnusedCargo]++ {
 395                                                 quantity := *hold - (other[UnusedCargo] + other[Cloaks] + other[Edens])
 396                                                 sale_value := quantity * sell_price
 397                                                 Consider(data, dims, table, other, sale_value, &best_value, best_source)
 398                                         }
 399                                 }
 400                                 other[UnusedCargo] = addr[UnusedCargo]
 401                                 other[Hold] = addr[Hold]
 402                         }
 403
 404                         /* Buy */
 405                         other[Traded] = addr[Traded] /* Buy after selling */
 406                         if addr[Hold] != 0 {
 407                                 commodity := data.i2c[addr[Hold]]
 408                                 if data.Commodities[commodity].CanSell {
 409                                         relative_price, available := data.Planets[planet].RelativePrices[commodity]
 410                                         if available {
 411                                                 base_price := data.Commodities[commodity].BasePrice
 412                                                 absolute_price := int(float64(base_price) * float64(relative_price) / 100.0)
 413                                                 quantity := *hold - (addr[UnusedCargo] + addr[Cloaks] + addr[Edens])
 414                                                 total_price := quantity * absolute_price
 415                                                 other[Hold] = 0
 416                                                 other[UnusedCargo] = 0
 417                                                 Consider(data, dims, table, other, -total_price, &best_value, best_source)
 418                                                 other[UnusedCargo] = addr[UnusedCargo]
 419                                                 other[Hold] = addr[Hold]
 420                                         }
 421                                 }
 422                         }
 423                 }
 424         }
 425
 426         /* Buy a Device of Cloaking */
 427         if addr[Cloaks] == 1 && addr[UnusedCargo] < dims[UnusedCargo]-1 {
 428                 relative_price, available := data.Planets[data.i2p[addr[Location]]].RelativePrices["Device Of Cloakings"]
 429                 if available {
 430                         absolute_price := int(float64(data.Commodities["Device Of Cloakings"].BasePrice) * float64(relative_price) / 100.0)
 431                         other[Cloaks] = 0
 432                         if other[Hold] != 0 {
 433                                 other[UnusedCargo] = addr[UnusedCargo] + 1
 434                         }
 435                         Consider(data, dims, table, other, -absolute_price, &best_value, best_source)
 436                         other[UnusedCargo] = addr[UnusedCargo]
 437                         other[Cloaks] = addr[Cloaks]
 438                 }
 439         }
 440
 441         /* Buy Fighter Drones */
 442         if addr[BuyFighters] == 1 {
 443                 relative_price, available := data.Planets[data.i2p[addr[Location]]].RelativePrices["Fighter Drones"]
 444                 if available {
 445                         absolute_price := int(float64(data.Commodities["Fighter Drones"].BasePrice) * float64(relative_price) / 100.0)
 446                         other[BuyFighters] = 0
 447                         Consider(data, dims, table, other, -absolute_price * *drones, &best_value, best_source)
 448                         other[BuyFighters] = addr[BuyFighters]
 449                 }
 450         }
 451
 452         /* Buy Shield Batteries */
 453         if addr[BuyShields] == 1 {
 454                 relative_price, available := data.Planets[data.i2p[addr[Location]]].RelativePrices["Shield Batterys"]
 455                 if available {
 456                         absolute_price := int(float64(data.Commodities["Shield Batterys"].BasePrice) * float64(relative_price) / 100.0)
 457                         other[BuyShields] = 0
 458                         Consider(data, dims, table, other, -absolute_price * *batteries, &best_value, best_source)
 459                         other[BuyShields] = addr[BuyShields]
 460                 }
 461         }
 462
 463         /* Visit this planet */
 464         var i uint
 465         for i = 0; i < uint(len(visit())); i++ {
 466                 if addr[Visit] & (1 << i) != 0 && visit()[i] == data.i2p[addr[Location]] {
 467                         other[Visit] = addr[Visit] & ^(1 << i)
 468                         Consider(data, dims, table, other, 0, &best_value, best_source)
 469                 }
 470         }
 471         other[Visit] = addr[Visit]
 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                                         Consider(data, dims, table, other, -absolute_price * quantity, &best_value, best_source)
 486                                 }
 487                         }
 488                         other[Edens] = addr[Edens]
 489                         other[UnusedCargo] = addr[UnusedCargo]
 490                 }
 491         }
 492
 493         if table[my_index].value != CELL_BEING_EVALUATED {
 494                 panic(my_index)
 495         }
 496         table[my_index].value = best_value
 497         table[my_index].from = EncodeIndex(dims, best_source)
 498
 499         cell_filled_count ++
 500         if cell_filled_count & 0xff == 0 {
 501                 print(fmt.Sprintf("\r%3.1f%%", 100*float64(cell_filled_count)/float64(StateTableSize(dims))))
 502         }
 503
 504         return table[my_index].value
 505 }
 506
 507 func FindBestState(data planet_data, dims []int, table []State) int32 {
 508         addr := make([]int, NumDimensions)
 509         addr[Edens] = *end_edens
 510         addr[Cloaks] = dims[Cloaks] - 1
 511         addr[BuyFighters] = dims[BuyFighters] - 1
 512         addr[BuyShields] = dims[BuyShields] - 1
 513         addr[Visit] = dims[Visit] - 1
 514         addr[Traded] = 1
 515         // Hold and UnusedCargo left at 0
 516         max_index := int32(-1)
 517         max_value := int32(0)
 518         for addr[Fuel] = 0; addr[Fuel] < 2; addr[Fuel]++ {
 519                 for addr[Location] = 0; addr[Location] < dims[Location]; addr[Location]++ {
 520                         if len(end()) == 0 || end()[data.i2p[addr[Location]]] {
 521                                 index := EncodeIndex(dims, addr)
 522                                 value := CellValue(data, dims, table, addr)
 523                                 if value > max_value {
 524                                         max_value = value
 525                                         max_index = index
 526                                 }
 527                         }
 528                 }
 529         }
 530         return max_index
 531 }
 532
 533 func Commas(n int32) (s string) {
 534         r := n % 1000
 535         n /= 1000
 536         for n > 0 {
 537                 s = fmt.Sprintf(",%03d", r) + s
 538                 r = n % 1000
 539                 n /= 1000
 540         }
 541         s = fmt.Sprint(r) + s
 542         return
 543 }
 544
 545 func DescribePath(data planet_data, dims []int, table []State, start int32) (description []string) {
 546         for index := start; index > 0 && table[index].from > 0; index = table[index].from {
 547                 var line string
 548                 addr := DecodeIndex(dims, index)
 549                 prev := DecodeIndex(dims, table[index].from)
 550                 if addr[Fuel] != prev[Fuel] {
 551                         from := data.i2p[prev[Location]]
 552                         to := data.i2p[addr[Location]]
 553                         line += fmt.Sprintf("Jump from %v to %v (%v hyper jump units)", from, to, prev[Fuel]-addr[Fuel])
 554                 }
 555                 if addr[Edens] == prev[Edens] - 1 {
 556                         from := data.i2p[prev[Location]]
 557                         to := data.i2p[addr[Location]]
 558                         line += fmt.Sprintf("Eden warp from %v to %v", from, to)
 559                 }
 560                 if addr[Hold] != prev[Hold] {
 561                         if addr[Hold] == 0 {
 562                                 quantity := *hold - (prev[UnusedCargo] + prev[Edens] + prev[Cloaks])
 563                                 line += fmt.Sprintf("Sell %v %v", quantity, data.i2c[prev[Hold]])
 564                         } else if prev[Hold] == 0 {
 565                                 quantity := *hold - (addr[UnusedCargo] + addr[Edens] + addr[Cloaks])
 566                                 line += fmt.Sprintf("Buy %v %v", quantity, data.i2c[addr[Hold]])
 567                         } else {
 568                                 panic("Switched cargo?")
 569                         }
 570
 571                 }
 572                 if addr[Cloaks] == 1 && prev[Cloaks] == 0 {
 573                         // TODO: Dump cloaks, convert from cargo?
 574                         line += "Buy a Cloak"
 575                 }
 576                 if addr[Edens] > prev[Edens] {
 577                         line += fmt.Sprint("Buy ", addr[Edens] - prev[Edens], " Eden Warp Units")
 578                 }
 579                 if addr[BuyShields] == 1 && prev[BuyShields] == 0 {
 580                         line += fmt.Sprint("Buy ", *batteries, " Shield Batterys")
 581                 }
 582                 if addr[BuyFighters] == 1 && prev[BuyFighters] == 0 {
 583                         line += fmt.Sprint("Buy ", *drones, " Fighter Drones")
 584                 }
 585                 if addr[Visit] != prev[Visit] {
 586                         // TODO: verify that the bit chat changed is addr[Location]
 587                         line += fmt.Sprint("Visit ", data.i2p[addr[Location]])
 588                 }
 589                 if line == "" && addr[Hold] == prev[Hold] && addr[Traded] != prev[Traded] {
 590                         // The Traded dimension is for housekeeping.  It doesn't directly
 591                         // correspond to in-game actions, so don't report transitions.
 592                         continue
 593                 }
 594                 if line == "" {
 595                         line = fmt.Sprint(prev, " -> ", addr)
 596                 }
 597                 description = append(description, fmt.Sprintf("%13v ", Commas(table[index].value)) + line)
 598         }
 599         return
 600 }
 601
 602 // (Example of a use case for generics in Go)
 603 func IndexPlanets(m *map[string]Planet, start_at int) (map[string]int, []string) {
 604         e2i := make(map[string]int, len(*m)+start_at)
 605         i2e := make([]string, len(*m)+start_at)
 606         i := start_at
 607         for e := range *m {
 608                 e2i[e] = i
 609                 i2e[i] = e
 610                 i++
 611         }
 612         return e2i, i2e
 613 }
 614 func IndexCommodities(m *map[string]Commodity, start_at int) (map[string]int, []string) {
 615         e2i := make(map[string]int, len(*m)+start_at)
 616         i2e := make([]string, len(*m)+start_at)
 617         i := start_at
 618         for e := range *m {
 619                 e2i[e] = i
 620                 i2e[i] = e
 621                 i++
 622         }
 623         return e2i, i2e
 624 }
 625
 626 func main() {
 627         flag.Parse()
 628         if *cpuprofile != "" {
 629                 f, err := os.Create(*cpuprofile)
 630                 if err != nil {
 631                         panic(err)
 632                 }
 633                 pprof.StartCPUProfile(f)
 634                 defer pprof.StopCPUProfile()
 635         }
 636         data := ReadData()
 637         if *drone_price > 0 {
 638                 temp := data.Commodities["Fighter Drones"]
 639                 temp.BasePrice = *drone_price
 640                 data.Commodities["Fighter Drones"] = temp
 641         }
 642         if *battery_price > 0 {
 643                 temp := data.Commodities["Shield Batterys"]
 644                 temp.BasePrice = *battery_price
 645                 data.Commodities["Shield Batterys"] = temp
 646         }
 647         data.p2i, data.i2p = IndexPlanets(&data.Planets, 0)
 648         data.c2i, data.i2c = IndexCommodities(&data.Commodities, 1)
 649         dims := DimensionSizes(data)
 650         table := CreateStateTable(data, dims)
 651         best := FindBestState(data, dims, table)
 652         print("\n")
 653         if best == -1 {
 654                 print("Cannot acheive success criteria\n")
 655         } else {
 656                 description := DescribePath(data, dims, table, best)
 657                 for i := len(description) - 1; i >= 0; i-- {
 658                         fmt.Println(description[i])
 659                 }
 660         }
 661 }