+}
+
+func FillStateTable2Iteration(data planet_data, dims []int, table []State,
+addr []int, f func(planet_data, []int, []State, []int)) {
+ /* TODO: Justify the safety of the combination of this dimension
+ * iteration and the various phases f. */
+ for addr[Hold] = 0; addr[Hold] < dims[Hold]; addr[Hold]++ {
+ for addr[Cloaks] = 0; addr[Cloaks] < dims[Cloaks]; addr[Cloaks]++ {
+ for addr[UnusedCargo] = 0; addr[UnusedCargo] < dims[UnusedCargo]; addr[UnusedCargo]++ {
+ for addr[BuyFighters] = 0; addr[BuyFighters] < dims[BuyFighters]; addr[BuyFighters]++ {
+ for addr[BuyShields] = 0; addr[BuyShields] < dims[BuyShields]; addr[BuyShields]++ {
+ for addr[Visit] = 0; addr[Visit] < dims[Visit]; addr[Visit]++ {
+ f(data, dims, table, addr)
+ }
+ }
+ }
+ }
+ }
+ }
+}
+
+func FillStateTable2(data planet_data, dims []int, table []State,
+addr []int, barrier chan<- bool) {
+ FillStateTable2Iteration(data, dims, table, addr, FillCellByArriving)
+ FillStateTable2Iteration(data, dims, table, addr, FillCellBySelling)
+ FillStateTable2Iteration(data, dims, table, addr, FillCellByBuying)
+ FillStateTable2Iteration(data, dims, table, addr, FillCellByMisc)
+ FillStateTable2Iteration(data, dims, table, addr, FillCellByBuyingEdens)
+ if barrier != nil {
+ barrier <- true
+ }
+}
+
+/* Filling the state table is a set of nested for loops NumDimensions deep.
+ * We split this into two procedures: 1 and 2. #1 is the outer, slowest-
+ * changing indexes. #1 fires off many calls to #2 that run in parallel.
+ * The order of the nesting of the dimensions, the order of iteration within
+ * each dimension, and where the 1 / 2 split is placed are carefully chosen
+ * to make this arrangement safe.
+ *
+ * Outermost two layers: Go from high-energy states (lots of fuel, edens) to
+ * low-energy state. These must be processed sequentially and in this order
+ * because you travel through high-energy states to get to the low-energy
+ * states.
+ *
+ * Third layer: Planet. This is a good layer to parallelize on. There's
+ * high enough cardinality that we don't have to mess with parallelizing
+ * multiple layers for good utilization (on 2011 machines). Each thread
+ * works on one planet's states and need not synchronize with peer threads.
+ */
+func FillStateTable1(data planet_data, dims []int, table []State) {
+ barrier := make(chan bool, len(data.Planets))
+ eden_capacity := data.Commodities["Eden Warp Units"].Limit
+ work_units := (float64(*fuel) + 1) * (float64(eden_capacity) + 1)
+ work_done := 0.0
+ for fuel_remaining := *fuel; fuel_remaining >= 0; fuel_remaining-- {
+ /* Make an Eden-buying pass (Eden vendors' energy gradient
+ * along the Edens dimension runs backwards) */
+ for edens_remaining := 0; edens_remaining <= eden_capacity; edens_remaining++ {
+ for planet := range data.Planets {
+ if _, available := data.Planets[planet].RelativePrices["Eden Warp Units"]; available {
+ addr := make([]int, len(dims))
+ addr[Edens] = edens_remaining
+ addr[Fuel] = fuel_remaining
+ addr[Location] = data.p2i[planet]
+ FillStateTable2(data, dims, table, addr, nil)
+ }
+ }
+ }
+ for edens_remaining := eden_capacity; edens_remaining >= 0; edens_remaining-- {
+ /* Do the brunt of the work */
+ for planet := range data.Planets {
+ addr := make([]int, len(dims))
+ addr[Edens] = edens_remaining
+ addr[Fuel] = fuel_remaining
+ addr[Location] = data.p2i[planet]
+ go FillStateTable2(data, dims, table, addr, barrier)
+ }
+ for _ = range data.Planets {
+ <-barrier
+ }
+ work_done++
+ print(fmt.Sprintf("\r%3.0f%%", 100*work_done/work_units))
+ }
+ }
+ print("\n")
+}
+
+func FindBestState(data planet_data, dims []int, table []State) int {
+ addr := make([]int, NumDimensions)
+ addr[Edens] = *end_edens
+ addr[Cloaks] = dims[Cloaks] - 1
+ addr[BuyFighters] = dims[BuyFighters] - 1
+ addr[BuyShields] = dims[BuyShields] - 1
+ addr[Visit] = dims[Visit] - 1
+ // Hold and UnusedCargo left at 0
+ max_index := -1
+ max_value := 0
+ for addr[Fuel] = 0; addr[Fuel] < 2; addr[Fuel]++ {
+ for addr[Location] = 0; addr[Location] < dims[Location]; addr[Location]++ {
+ if len(end()) == 0 || end()[data.i2p[addr[Location]]] {
+ index := EncodeIndex(dims, addr)
+ if table[index].value > max_value {
+ max_value = table[index].value
+ max_index = index
+ }
+ }
+ }
+ }
+ return max_index
+}
+
+func Commas(n int) (s string) {
+ r := n % 1000
+ n /= 1000
+ for n > 0 {
+ s = fmt.Sprintf(",%03d", r) + s
+ r = n % 1000
+ n /= 1000
+ }
+ s = fmt.Sprint(r) + s
+ return
+}
+
+func DescribePath(data planet_data, dims []int, table []State, start int) (description []string) {
+ for index := start; index > 0 && table[index].from > 0; index = table[index].from {
+ var line string
+ addr := DecodeIndex(dims, index)
+ prev := DecodeIndex(dims, table[index].from)
+ if addr[Fuel] != prev[Fuel] {
+ from := data.i2p[prev[Location]]
+ to := data.i2p[addr[Location]]
+ line += fmt.Sprintf("Jump from %v to %v (%v hyper jump units)", from, to, prev[Fuel]-addr[Fuel])
+ }
+ if addr[Edens] == prev[Edens] - 1 {
+ from := data.i2p[prev[Location]]
+ to := data.i2p[addr[Location]]
+ line += fmt.Sprintf("Eden warp from %v to %v", from, to)
+ }
+ if addr[Hold] != prev[Hold] {
+ if addr[Hold] == 0 {
+ quantity := *hold - (prev[UnusedCargo] + prev[Edens] + prev[Cloaks])
+ line += fmt.Sprintf("Sell %v %v", quantity, data.i2c[prev[Hold]])
+ } else if prev[Hold] == 0 {
+ quantity := *hold - (addr[UnusedCargo] + addr[Edens] + addr[Cloaks])
+ line += fmt.Sprintf("Buy %v %v", quantity, data.i2c[addr[Hold]])
+ } else {
+ panic("Switched cargo?")
+ }
+
+ }
+ if addr[Cloaks] == 1 && prev[Cloaks] == 0 {
+ // TODO: Dump cloaks, convert from cargo?
+ line += "Buy a Cloak"
+ }
+ if addr[Edens] > prev[Edens] {
+ line += fmt.Sprint("Buy ", addr[Edens] - prev[Edens], " Eden Warp Units")
+ }
+ if addr[BuyShields] == 1 && prev[BuyShields] == 0 {
+ line += fmt.Sprint("Buy ", *batteries, " Shield Batterys")
+ }
+ if addr[BuyFighters] == 1 && prev[BuyFighters] == 0 {
+ line += fmt.Sprint("Buy ", *drones, " Fighter Drones")
+ }
+ if addr[Visit] != prev[Visit] {
+ // TODO: verify that the bit chat changed is addr[Location]
+ line += fmt.Sprint("Visit ", data.i2p[addr[Location]])
+ }
+ if line == "" {
+ line = fmt.Sprint(prev, " -> ", addr)
+ }
+ description = append(description, fmt.Sprintf("%13v ", Commas(table[index].value)) + line)
+ }
+ return
+}
+
+// (Example of a use case for generics in Go)
+func IndexPlanets(m *map[string]Planet, start_at int) (map[string]int, []string) {
+ e2i := make(map[string]int, len(*m)+start_at)
+ i2e := make([]string, len(*m)+start_at)
+ i := start_at
+ for e := range *m {
+ e2i[e] = i
+ i2e[i] = e
+ i++
+ }
+ return e2i, i2e
+}
+func IndexCommodities(m *map[string]Commodity, start_at int) (map[string]int, []string) {
+ e2i := make(map[string]int, len(*m)+start_at)
+ i2e := make([]string, len(*m)+start_at)
+ i := start_at
+ for e := range *m {
+ e2i[e] = i
+ i2e[i] = e
+ i++
+ }
+ return e2i, i2e