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, prevent the memory manager
 164  * from allocating pages for these areas at all.
 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     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         BuyFighters         //   7     2  Errand: Buy fighter drones
 188         BuyShields          //   8     2  Errand: Buy shield batteries
 189         Visit               //   9  2**N  Visit: Stop by these N planets in the route
 190
 191         NumDimensions
 192 )
 193
 194 func bint(b bool) int {
 195         if b {
 196                 return 1
 197         }
 198         return 0
 199 }
 200
 201 func DimensionSizes(data planet_data) []int {
 202         eden_capacity := data.Commodities["Eden Warp Units"].Limit
 203         if *start_edens > eden_capacity {
 204                 eden_capacity = *start_edens
 205         }
 206         cloak_capacity := bint(*cloak)
 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)
 213         dims[Hold] = len(data.Commodities) + 1
 214         dims[BuyFighters] = bint(*drones > 0) + 1
 215         dims[BuyShields] = bint(*batteries > 0) + 1
 216         dims[Visit] = 1 << uint(len(visit()))
 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         }
 224         return dims
 225 }
 226
 227 func StateTableSize(dims []int) int {
 228         product := 1
 229         for _, size := range dims {
 230                 product *= size
 231         }
 232         return product
 233 }
 234
 235 type State struct {
 236         value, from int
 237 }
 238
 239 func EncodeIndex(dims, addr []int) int {
 240         index := addr[0]
 241         if addr[0] > dims[0] {
 242                 panic(0)
 243         }
 244         for i := 1; i < NumDimensions; i++ {
 245                 if addr[i] < 0 || addr[i] > dims[i] {
 246                         panic(i)
 247                 }
 248                 index = index*dims[i] + addr[i]
 249         }
 250         return index
 251 }
 252
 253 func DecodeIndex(dims []int, index int) []int {
 254         addr := make([]int, NumDimensions)
 255         for i := NumDimensions - 1; i > 0; i-- {
 256                 addr[i] = index % dims[i]
 257                 index /= dims[i]
 258         }
 259         addr[0] = index
 260         return addr
 261 }
 262
 263 func 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
 273 }
 274
 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.
 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.
 283  */
 284
 285 func 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
 293 func FillCellByArriving(data planet_data, dims []int, table []State, addr []int) {
 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 */
 299         if addr[Fuel]+2 < dims[Fuel] {
 300                 other[Fuel] = addr[Fuel] + 2
 301                 for other[Location] = 0; other[Location] < dims[Location]; other[Location]++ {
 302                         if data.Planets[data.i2p[addr[Location]]].BeaconOn {
 303                                 UpdateCell(table, my_index, EncodeIndex(dims, other), 0)
 304                         }
 305                 }
 306                 other[Location] = addr[Location]
 307                 other[Fuel] = addr[Fuel]
 308         }
 309
 310         /* Travel here via a hyper hole */
 311         if addr[Fuel]+1 < dims[Fuel] {
 312                 hole_index := (dims[Fuel] - 1) - (addr[Fuel] + 1)
 313                 if hole_index < len(flight_plan()) && addr[Location] == data.p2i[flight_plan()[hole_index]] {
 314                         other[Fuel] = addr[Fuel] + 1
 315                         for other[Location] = 0; other[Location] < dims[Location]; other[Location]++ {
 316                                 UpdateCell(table, my_index, EncodeIndex(dims, other), 0)
 317                         }
 318                         other[Location] = addr[Location]
 319                         other[Fuel] = addr[Fuel]
 320                 }
 321         }
 322
 323         /* Travel here via Eden Warp Unit */
 324         if addr[Edens]+1 < dims[Edens] && addr[UnusedCargo] > 1 {
 325                 _, available := data.Planets[data.i2p[addr[Location]]].RelativePrices["Eden Warp Units"]
 326                 if !available {
 327                         other[Edens] = addr[Edens] + 1
 328                         other[UnusedCargo] = addr[UnusedCargo] - 1
 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]
 333                         other[UnusedCargo] = addr[UnusedCargo]
 334                         other[Edens] = addr[Edens]
 335                 }
 336         }
 337 }
 338
 339 func FillCellBySelling(data planet_data, dims []int, table []State, addr []int) {
 340         if data.Planets[data.i2p[addr[Location]]].Private {
 341                 // Can't do commerce on private planets
 342                 return
 343         }
 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
 367                 absolute_price := float64(base_price) * float64(relative_price) / 100.0
 368                 sell_price := int(absolute_price * 0.9)
 369
 370                 for other[UnusedCargo] = 0; other[UnusedCargo] < dims[UnusedCargo]; other[UnusedCargo]++ {
 371
 372                         quantity := *hold - (other[UnusedCargo] + other[Cloaks] + other[Edens])
 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
 380 func FillCellByBuying(data planet_data, dims []int, table []State, addr []int) {
 381         if data.Planets[data.i2p[addr[Location]]].Private {
 382                 // Can't do commerce on private planets
 383                 return
 384         }
 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
 402         absolute_price := int(float64(base_price) * float64(relative_price) / 100.0)
 403         quantity := *hold - (addr[UnusedCargo] + addr[Cloaks] + addr[Edens])
 404         total_price := quantity * absolute_price
 405         other[Hold] = 0
 406         other[UnusedCargo] = 0
 407         UpdateCell(table, my_index, EncodeIndex(dims, other), -total_price)
 408         other[UnusedCargo] = addr[UnusedCargo]
 409         other[Hold] = addr[Hold]
 410 }
 411
 412 func FillCellByMisc(data planet_data, dims []int, table []State, addr []int) {
 413         my_index := EncodeIndex(dims, addr)
 414         other := make([]int, NumDimensions)
 415         copy(other, addr)
 416
 417         /* Buy a Device of Cloaking */
 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
 423                         if other[Hold] != 0 {
 424                                 other[UnusedCargo] = addr[UnusedCargo] + 1
 425                         }
 426                         UpdateCell(table, my_index, EncodeIndex(dims, other), -absolute_price)
 427                         other[UnusedCargo] = addr[UnusedCargo]
 428                         other[Cloaks] = addr[Cloaks]
 429                 }
 430         }
 431
 432         /* Silly: Dump a Device of Cloaking */
 433
 434         /* Buy Fighter Drones */
 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
 445         /* Buy Shield Batteries */
 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
 456         /* Visit this planet */
 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]
 465
 466 }
 467
 468 func 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
 494 func FillStateTable2Iteration(data planet_data, dims []int, table []State,
 495 addr []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.  */
 498         for addr[Hold] = 0; addr[Hold] < dims[Hold]; addr[Hold]++ {
 499                 for addr[Cloaks] = 0; addr[Cloaks] < dims[Cloaks]; addr[Cloaks]++ {
 500                         for addr[UnusedCargo] = 0; addr[UnusedCargo] < dims[UnusedCargo]; addr[UnusedCargo]++ {
 501                                 for addr[BuyFighters] = 0; addr[BuyFighters] < dims[BuyFighters]; addr[BuyFighters]++ {
 502                                         for addr[BuyShields] = 0; addr[BuyShields] < dims[BuyShields]; addr[BuyShields]++ {
 503                                                 for addr[Visit] = 0; addr[Visit] < dims[Visit]; addr[Visit]++ {
 504                                                         f(data, dims, table, addr)
 505                                                 }
 506                                         }
 507                                 }
 508                         }
 509                 }
 510         }
 511 }
 512
 513 func FillStateTable2(data planet_data, dims []int, table []State,
 514 addr []int, barrier chan<- bool) {
 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)
 519         FillStateTable2Iteration(data, dims, table, addr, FillCellByBuyingEdens)
 520         if barrier != nil {
 521                 barrier <- true
 522         }
 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  */
 542 func FillStateTable1(data planet_data, dims []int, table []State) {
 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-- {
 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                 }
 561                 for edens_remaining := eden_capacity; edens_remaining >= 0; edens_remaining-- {
 562                         /* Do the brunt of the work */
 563                         for planet := range data.Planets {
 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)
 569                         }
 570                         for _ = range data.Planets {
 571                                 <-barrier
 572                         }
 573                         work_done++
 574                         print(fmt.Sprintf("\r%3.0f%%", 100*work_done/work_units))
 575                 }
 576         }
 577         print("\n")
 578 }
 579
 580 func 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
 584         addr[BuyFighters] = dims[BuyFighters] - 1
 585         addr[BuyShields] = dims[BuyShields] - 1
 586         addr[Visit] = dims[Visit] - 1
 587         // Hold and UnusedCargo left at 0
 588         max_index := -1
 589         max_value := 0
 590         for addr[Fuel] = 0; addr[Fuel] < 2; addr[Fuel]++ {
 591                 for addr[Location] = 0; addr[Location] < dims[Location]; addr[Location]++ {
 592                         if len(end()) == 0 || end()[data.i2p[addr[Location]]] {
 593                                 index := EncodeIndex(dims, addr)
 594                                 if table[index].value > max_value {
 595                                         max_value = table[index].value
 596                                         max_index = index
 597                                 }
 598                         }
 599                 }
 600         }
 601         return max_index
 602 }
 603
 604 func Commas(n int) (s string) {
 605         r := n % 1000
 606         n /= 1000
 607         for n > 0 {
 608                 s = fmt.Sprintf(",%03d", r) + s
 609                 r = n % 1000
 610                 n /= 1000
 611         }
 612         s = fmt.Sprint(r) + s
 613         return
 614 }
 615
 616 func DescribePath(data planet_data, dims []int, table []State, start int) (description []string) {
 617         for index := start; index > 0 && table[index].from > 0; index = table[index].from {
 618                 var line string
 619                 addr := DecodeIndex(dims, index)
 620                 prev := DecodeIndex(dims, table[index].from)
 621                 if addr[Fuel] != prev[Fuel] {
 622                         from := data.i2p[prev[Location]]
 623                         to := data.i2p[addr[Location]]
 624                         line += fmt.Sprintf("Jump from %v to %v (%v hyper jump units)", from, to, prev[Fuel]-addr[Fuel])
 625                 }
 626                 if addr[Edens] == prev[Edens] - 1 {
 627                         from := data.i2p[prev[Location]]
 628                         to := data.i2p[addr[Location]]
 629                         line += fmt.Sprintf("Eden warp from %v to %v", from, to)
 630                 }
 631                 if addr[Hold] != prev[Hold] {
 632                         if addr[Hold] == 0 {
 633                                 quantity := *hold - (prev[UnusedCargo] + prev[Edens] + prev[Cloaks])
 634                                 line += fmt.Sprintf("Sell %v %v", quantity, data.i2c[prev[Hold]])
 635                         } else if prev[Hold] == 0 {
 636                                 quantity := *hold - (addr[UnusedCargo] + addr[Edens] + addr[Cloaks])
 637                                 line += fmt.Sprintf("Buy %v %v", quantity, data.i2c[addr[Hold]])
 638                         } else {
 639                                 panic("Switched cargo?")
 640                         }
 641
 642                 }
 643                 if addr[Cloaks] == 1 && prev[Cloaks] == 0 {
 644                         // TODO: Dump cloaks, convert from cargo?
 645                         line += "Buy a Cloak"
 646                 }
 647                 if addr[Edens] > prev[Edens] {
 648                         line += fmt.Sprint("Buy ", addr[Edens] - prev[Edens], " Eden Warp Units")
 649                 }
 650                 if addr[BuyShields] == 1 && prev[BuyShields] == 0 {
 651                         line += fmt.Sprint("Buy ", *batteries, " Shield Batterys")
 652                 }
 653                 if addr[BuyFighters] == 1 && prev[BuyFighters] == 0 {
 654                         line += fmt.Sprint("Buy ", *drones, " Fighter Drones")
 655                 }
 656                 if addr[Visit] != prev[Visit] {
 657                         // TODO: verify that the bit chat changed is addr[Location]
 658                         line += fmt.Sprint("Visit ", data.i2p[addr[Location]])
 659                 }
 660                 if line == "" {
 661                         line = fmt.Sprint(prev, " -> ", addr)
 662                 }
 663                 description = append(description, fmt.Sprintf("%13v ", Commas(table[index].value)) + line)
 664         }
 665         return
 666 }
 667
 668 // (Example of a use case for generics in Go)
 669 func IndexPlanets(m *map[string]Planet, 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 func IndexCommodities(m *map[string]Commodity, start_at int) (map[string]int, []string) {
 681         e2i := make(map[string]int, len(*m)+start_at)
 682         i2e := make([]string, len(*m)+start_at)
 683         i := start_at
 684         for e := range *m {
 685                 e2i[e] = i
 686                 i2e[i] = e
 687                 i++
 688         }
 689         return e2i, i2e
 690 }
 691
 692 func main() {
 693         flag.Parse()
 694         if *cpuprofile != "" {
 695                 f, err := os.Create(*cpuprofile)
 696                 if err != nil {
 697                         panic(err)
 698                 }
 699                 pprof.StartCPUProfile(f)
 700                 defer pprof.StopCPUProfile()
 701         }
 702         data := ReadData()
 703         if *drone_price > 0 {
 704                 temp := data.Commodities["Fighter Drones"]
 705                 temp.BasePrice = *drone_price
 706                 data.Commodities["Fighter Drones"] = temp
 707         }
 708         if *battery_price > 0 {
 709                 temp := data.Commodities["Shield Batterys"]
 710                 temp.BasePrice = *battery_price
 711                 data.Commodities["Shield Batterys"] = temp
 712         }
 713         data.p2i, data.i2p = IndexPlanets(&data.Planets, 0)
 714         data.c2i, data.i2c = IndexCommodities(&data.Commodities, 1)
 715         dims := DimensionSizes(data)
 716         table := InitializeStateTable(data, dims)
 717         FillStateTable1(data, dims, table)
 718         best := FindBestState(data, dims, table)
 719         if best == -1 {
 720                 print("Cannot acheive success criteria\n")
 721         } else {
 722                 description := DescribePath(data, dims, table, best)
 723                 for i := len(description) - 1; i >= 0; i-- {
 724                         fmt.Println(description[i])
 725                 }
 726         }
 727 }