package main
import "flag"
+import "fmt"
import "json"
import "os"
-import "fmt"
+import "strings"
+
+var start = flag.String("start", "",
+ "The planet to start at")
+
+var end = flag.String("end", "",
+ "A comma-separated list of planets to end at")
-var datafile = flag.String("planet_data_file", "planet-data",
+var planet_data_file = flag.String("planet_data_file", "planet-data",
"The file to read planet data from")
+var fuel = flag.Int("fuel", 16,
+ "Reactor units; How many non-Eden jumps we can make "+
+ "(but remember that deviating from the flight plan "+
+ "costs two units of fuel per jump)")
+
+var start_edens = flag.Int("start_edens", 0,
+ "How many Eden Warp Units are you starting with?")
+
+var end_edens = flag.Int("end_edens", 0,
+ "How many Eden Warp Units would you like to keep (not use)?")
+
+var cloak = flag.Bool("cloak", false,
+ "Make sure to end with a Device of Cloaking")
+
+var drones = flag.Int("drones", 0,
+ "Buy this many Fighter Drones")
+
+var batteries = flag.Int("batteries", 0,
+ "Buy this many Shield Batterys")
+
+var visit_string = flag.String("visit", "",
+ "A comma-separated list of planets to make sure to visit")
+
+func visit() []string {
+ return strings.Split(*visit_string, ",")
+}
+
type Commodity struct {
- Name string
BasePrice int
CanSell bool
Limit int
}
-
+type Planet struct {
+ BeaconOn bool
+ /* Use relative prices rather than absolute prices because you
+ can get relative prices without traveling to each planet. */
+ RelativePrices map[string]int
+}
type planet_data struct {
- Commodities []Commodity
- Planets []struct {
- Name string
- BeaconOn bool
- /* Use relative prices rather than absolute prices because you
- can get relative prices without traveling to each planet. */
- RelativePrices map [string] int
- }
+ Commodities map[string]Commodity
+ Planets map[string]Planet
+ pi, ci map[string]int // Generated; not read from file
}
func ReadData() (data planet_data) {
- f, err := os.Open(*datafile)
+ f, err := os.Open(*planet_data_file)
if err != nil {
panic(err)
}
return
}
-func TradeValue(data planet_data,
- from_index, to_index, commodity_index, quantity int) int {
+/* This program operates by filling in a state table representing the best
+ * possible trips you could make; the ones that makes you the most money.
+ * This is feasible because we don't look at all the possible trips.
+ * We define a list of things that are germane to this game and then only
+ * consider the best outcome in each possible game state.
+ *
+ * Each cell in the table represents a state in the game. In each cell,
+ * we track two things: 1. the most money you could possibly have while in
+ * that state and 2. one possible way to get into that state with that
+ * amount of money.
+ *
+ * A basic analysis can be done with a two-dimensional table: location and
+ * fuel. planeteer-1.0 used this two-dimensional table. This version
+ * adds features mostly by adding dimensions to this table.
+ *
+ * Note that the sizes of each dimension are data driven. Many dimensions
+ * collapse to one possible value (ie, disappear) if the corresponding
+ * feature is not enabled.
+ */
- commodity := &data.Commodities[commodity_index]
- if !commodity.CanSell {
- return 0
+// The official list of dimensions:
+const (
+ // Name Num Size Description
+ Edens = iota // 1 3 # of Eden warp units (0 - 2 typically)
+ Cloaks // 2 2 # of Devices of Cloaking (0 or 1)
+ UnusedCargo // 3 4 # of unused cargo spaces (0 - 3 typically)
+ Fuel // 4 17 Reactor power left (0 - 16)
+ Location // 5 26 Location (which planet)
+ Hold // 6 15 Cargo bay contents (a *Commodity or nil)
+ NeedFighters // 7 2 Errand: Buy fighter drones (needed or not)
+ NeedShields // 8 2 Errand: Buy shield batteries (needed or not)
+ Visit // 9 2**N Visit: Stop by these N planets in the route
+
+ NumDimensions
+)
+
+func bint(b bool) int {
+ if b {
+ return 1
}
+ return 0
+}
- from_planet := &data.Planets[from_index]
- from_relative_price, from_available := from_planet.RelativePrices[commodity.Name]
+func DimensionSizes(data planet_data) []int {
+ eden_capacity := data.Commodities["Eden Warp Units"].Limit
+ cloak_capacity := bint(*cloak)
+ dims := []int{
+ eden_capacity + 1,
+ cloak_capacity + 1,
+ eden_capacity + cloak_capacity + 1,
+ *fuel + 1,
+ len(data.Planets),
+ len(data.Commodities),
+ bint(*drones > 0) + 1,
+ bint(*batteries > 0) + 1,
+ 1 << uint(len(visit())),
+ }
+ if len(dims) != NumDimensions {
+ panic("Dimensionality mismatch")
+ }
+ return dims
+}
+
+func StateTableSize(dims []int) int {
+ sum := 0
+ for _, size := range dims {
+ sum += size
+ }
+ return sum
+}
+
+type State struct {
+ funds, from int
+}
+
+func NewStateTable(dims []int) []State {
+ return make([]State, StateTableSize(dims))
+}
+
+func EncodeIndex(dims, addr []int) int {
+ index := addr[0]
+ for i := 1; i < len(dims); i++ {
+ index = index*dims[i] + addr[i]
+ }
+ return index
+}
+
+func DecodeIndex(dims []int, index int) []int {
+ addr := make([]int, len(dims))
+ for i := len(dims) - 1; i > 0; i-- {
+ addr[i] = index % dims[i]
+ index /= dims[i]
+ }
+ addr[0] = index
+ return addr
+}
+
+/* What is the value of hauling 'commodity' from 'from' to 'to'?
+ * Take into account the available funds and the available cargo space. */
+func TradeValue(data planet_data,
+from, to Planet,
+commodity string,
+initial_funds, max_quantity int) int {
+ if !data.Commodities[commodity].CanSell {
+ return 0
+ }
+ from_relative_price, from_available := from.RelativePrices[commodity]
if !from_available {
return 0
}
-
- to_planet := &data.Planets[to_index]
- to_relative_price, to_available := to_planet.RelativePrices[commodity.Name]
+ to_relative_price, to_available := to.RelativePrices[commodity]
if !to_available {
return 0
}
- from_absolute_price := from_relative_price * commodity.BasePrice
- to_absolute_price := to_relative_price * commodity.BasePrice
+ base_price := data.Commodities[commodity].BasePrice
+ from_absolute_price := from_relative_price * base_price
+ to_absolute_price := to_relative_price * base_price
buy_price := from_absolute_price
sell_price := int(float64(to_absolute_price) * 0.9)
- return (sell_price - buy_price) * quantity
-
+ var can_afford int = initial_funds / buy_price
+ quantity := can_afford
+ if quantity > max_quantity {
+ quantity = max_quantity
+ }
+ return (sell_price - buy_price) * max_quantity
}
-func FindBestTrades(data planet_data) [][]*Commodity {
- best := make([][]*Commodity, len(data.Planets))
- for from_index := range data.Planets {
- best[from_index] = make([]*Commodity, len(data.Planets))
- for to_index := range data.Planets {
+func FindBestTrades(data planet_data) [][]string {
+ // TODO: We can't cache this because this can change based on available funds.
+ best := make([][]string, len(data.Planets))
+ for from := range data.Planets {
+ best[data.pi[from]] = make([]string, len(data.Planets))
+ for to := range data.Planets {
best_gain := 0
- for commodity_index := range data.Commodities {
- gain := TradeValue(data, from_index, to_index, commodity_index, 1)
+ price_list := data.Planets[from].RelativePrices
+ if len(data.Planets[to].RelativePrices) < len(data.Planets[from].RelativePrices) {
+ price_list = data.Planets[to].RelativePrices
+ }
+ for commodity := range price_list {
+ gain := TradeValue(data,
+ data.Planets[from],
+ data.Planets[to],
+ commodity,
+ 10000000,
+ 1)
if gain > best_gain {
- best[from_index][to_index] = &data.Commodities[commodity_index]
+ best[data.pi[from]][data.pi[to]] = commodity
gain = best_gain
}
}
return best
}
+// (Example of a use case for generics in Go)
+func IndexPlanets(m *map[string]Planet) map[string]int {
+ index := make(map[string]int, len(*m))
+ i := 0
+ for e := range *m {
+ index[e] = i
+ i++
+ }
+ return index
+}
+func IndexCommodities(m *map[string]Commodity) map[string]int {
+ index := make(map[string]int, len(*m))
+ i := 0
+ for e := range *m {
+ index[e] = i
+ i++
+ }
+ return index
+}
+
func main() {
flag.Parse()
data := ReadData()
+ data.pi = IndexPlanets(&data.Planets)
+ data.ci = IndexCommodities(&data.Commodities)
+ dims := DimensionSizes(data)
+ table := NewStateTable(dims)
+ table[0] = State{1, 1}
best_trades := FindBestTrades(data)
- for from_index, from_planet := range data.Planets {
- for to_index, to_planet := range data.Planets {
+
+ for from := range data.Planets {
+ for to := range data.Planets {
best_trade := "(nothing)"
- if best_trades[from_index][to_index] != nil {
- best_trade = best_trades[from_index][to_index].Name
+ if best_trades[data.pi[from]][data.pi[to]] != "" {
+ best_trade = best_trades[data.pi[from]][data.pi[to]]
}
- fmt.Printf("%s to %s: %s\n", from_planet.Name, to_planet.Name, best_trade)
+ fmt.Printf("%s to %s: %s\n", from, to, best_trade)
}
}
}
projects / planeteer / blobdiff