X-Git-Url: http://git.scottworley.com/planeteer/blobdiff_plain/797391f853ed1af8da9f37d9367edf3e162203b7..370d198431389207cae2521ff186437eba3ef729:/planeteer.go diff --git a/planeteer.go b/planeteer.go index 6f6f7b7..e9f10c7 100644 --- a/planeteer.go +++ b/planeteer.go @@ -21,6 +21,7 @@ import "flag" import "fmt" import "json" import "os" +import "runtime/pprof" import "strings" var funds = flag.Int("funds", 0, @@ -30,15 +31,15 @@ var start = flag.String("start", "", "The planet to start at") var flight_plan_string = flag.String("flight_plan", "", - "Your hidey-holes for the day, comma-separated.") + "Your hyper-holes for the day, comma-separated.") -var end = flag.String("end", "", +var end_string = flag.String("end", "", "A comma-separated list of acceptable ending planets.") 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") +var fuel = flag.Int("fuel", 16, "Hyper Jump power left") var hold = flag.Int("hold", 300, "Size of your cargo hold") @@ -55,21 +56,51 @@ var drones = flag.Int("drones", 0, "Buy this many Fighter Drones") var batteries = flag.Int("batteries", 0, "Buy this many Shield Batterys") +var drone_price = flag.Int("drone_price", 0, "Today's Fighter Drone price") + +var battery_price = flag.Int("battery_price", 0, "Today's Shield Battery price") + var visit_string = flag.String("visit", "", "A comma-separated list of planets to make sure to visit") +var cpuprofile = flag.String("cpuprofile", "", "write cpu profile to file") + + +var visit_cache []string func visit() []string { - if *visit_string == "" { - return []string{} + if visit_cache == nil { + if *visit_string == "" { + return nil + } + visit_cache = strings.Split(*visit_string, ",") } - return strings.Split(*visit_string, ",") + return visit_cache } +var flight_plan_cache []string func flight_plan() []string { - if *flight_plan_string == "" { - return []string{} + if flight_plan_cache == nil { + if *flight_plan_string == "" { + return nil + } + flight_plan_cache = strings.Split(*flight_plan_string, ",") + } + return flight_plan_cache +} + +var end_cache map[string]bool +func end() map[string]bool { + if end_cache == nil { + if *end_string == "" { + return nil + } + m := make(map[string]bool) + for _, p := range strings.Split(*end_string, ",") { + m[p] = true + } + end_cache = m } - return strings.Split(*flight_plan_string, ",") + return end_cache } type Commodity struct { @@ -79,6 +110,7 @@ type Commodity struct { } type Planet struct { BeaconOn bool + Private bool /* Use relative prices rather than absolute prices because you can get relative prices without traveling to each planet. */ RelativePrices map[string]int @@ -149,11 +181,11 @@ const ( 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) + Fuel // 4 17 Hyper jump 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) + BuyFighters // 7 2 Errand: Buy fighter drones + BuyShields // 8 2 Errand: Buy shield batteries Visit // 9 2**N Visit: Stop by these N planets in the route NumDimensions @@ -179,8 +211,8 @@ func DimensionSizes(data planet_data) []int { dims[Fuel] = *fuel + 1 dims[Location] = len(data.Planets) dims[Hold] = len(data.Commodities) + 1 - dims[NeedFighters] = bint(*drones > 0) + 1 - dims[NeedShields] = bint(*batteries > 0) + 1 + dims[BuyFighters] = bint(*drones > 0) + 1 + dims[BuyShields] = bint(*batteries > 0) + 1 dims[Visit] = 1 << uint(len(visit())) // Remind myself to add a line above when adding new dimensions @@ -210,7 +242,7 @@ func EncodeIndex(dims, addr []int) int { panic(0) } for i := 1; i < NumDimensions; i++ { - if addr[i] > dims[i] { + if addr[i] < 0 || addr[i] > dims[i] { panic(i) } index = index*dims[i] + addr[i] @@ -267,35 +299,48 @@ func FillCellByArriving(data planet_data, dims []int, table []State, addr []int) if addr[Fuel]+2 < dims[Fuel] { other[Fuel] = addr[Fuel] + 2 for other[Location] = 0; other[Location] < dims[Location]; other[Location]++ { - UpdateCell(table, my_index, EncodeIndex(dims, other), 0) + if data.Planets[data.i2p[addr[Location]]].BeaconOn { + UpdateCell(table, my_index, EncodeIndex(dims, other), 0) + } } other[Location] = addr[Location] other[Fuel] = addr[Fuel] } - /* Travel here via a hidey hole */ + /* Travel here via a hyper hole */ if addr[Fuel]+1 < dims[Fuel] { hole_index := (dims[Fuel] - 1) - (addr[Fuel] + 1) - if hole_index < len(flight_plan()) { + if hole_index < len(flight_plan()) && addr[Location] == data.p2i[flight_plan()[hole_index]] { other[Fuel] = addr[Fuel] + 1 - other[Location] = data.p2i[flight_plan()[hole_index]] - UpdateCell(table, my_index, EncodeIndex(dims, other), 0) + for other[Location] = 0; other[Location] < dims[Location]; other[Location]++ { + UpdateCell(table, my_index, EncodeIndex(dims, other), 0) + } other[Location] = addr[Location] other[Fuel] = addr[Fuel] } } /* Travel here via Eden Warp Unit */ - for other[Edens] = addr[Edens] + 1; other[Edens] < dims[Edens]; other[Edens]++ { - for other[Location] = 0; other[Location] < dims[Location]; other[Location]++ { - UpdateCell(table, my_index, EncodeIndex(dims, other), 0) + if addr[Edens]+1 < dims[Edens] && addr[UnusedCargo] > 1 { + _, available := data.Planets[data.i2p[addr[Location]]].RelativePrices["Eden Warp Units"] + if !available { + other[Edens] = addr[Edens] + 1 + other[UnusedCargo] = addr[UnusedCargo] - 1 + for other[Location] = 0; other[Location] < dims[Location]; other[Location]++ { + UpdateCell(table, my_index, EncodeIndex(dims, other), 0) + } + other[Location] = addr[Location] + other[UnusedCargo] = addr[UnusedCargo] + other[Edens] = addr[Edens] } } - other[Location] = addr[Location] - other[Edens] = addr[Edens] } func FillCellBySelling(data planet_data, dims []int, table []State, addr []int) { + if data.Planets[data.i2p[addr[Location]]].Private { + // Can't do commerce on private planets + return + } if addr[Hold] > 0 { // Can't sell and still have cargo return @@ -333,6 +378,10 @@ func FillCellBySelling(data planet_data, dims []int, table []State, addr []int) } func FillCellByBuying(data planet_data, dims []int, table []State, addr []int) { + if data.Planets[data.i2p[addr[Location]]].Private { + // Can't do commerce on private planets + return + } if addr[Hold] == 0 { // Can't buy and then have nothing return @@ -364,23 +413,82 @@ func FillCellByMisc(data planet_data, dims []int, table []State, addr []int) { my_index := EncodeIndex(dims, addr) other := make([]int, NumDimensions) copy(other, addr) - /* Buy Eden warp units */ + /* Buy a Device of Cloaking */ if addr[Cloaks] == 1 && addr[UnusedCargo] < dims[UnusedCargo]-1 { relative_price, available := data.Planets[data.i2p[addr[Location]]].RelativePrices["Device Of Cloakings"] if available { absolute_price := int(float64(data.Commodities["Device Of Cloakings"].BasePrice) * float64(relative_price) / 100.0) other[Cloaks] = 0 - other[UnusedCargo] = addr[UnusedCargo] + 1 + if other[Hold] != 0 { + other[UnusedCargo] = addr[UnusedCargo] + 1 + } UpdateCell(table, my_index, EncodeIndex(dims, other), -absolute_price) other[UnusedCargo] = addr[UnusedCargo] other[Cloaks] = addr[Cloaks] } } + /* Silly: Dump a Device of Cloaking */ + /* Buy Fighter Drones */ + if addr[BuyFighters] == 1 { + relative_price, available := data.Planets[data.i2p[addr[Location]]].RelativePrices["Fighter Drones"] + if available { + absolute_price := int(float64(data.Commodities["Fighter Drones"].BasePrice) * float64(relative_price) / 100.0) + other[BuyFighters] = 0 + UpdateCell(table, my_index, EncodeIndex(dims, other), -absolute_price * *drones) + other[BuyFighters] = addr[BuyFighters] + } + } + /* Buy Shield Batteries */ + if addr[BuyShields] == 1 { + relative_price, available := data.Planets[data.i2p[addr[Location]]].RelativePrices["Shield Batterys"] + if available { + absolute_price := int(float64(data.Commodities["Shield Batterys"].BasePrice) * float64(relative_price) / 100.0) + other[BuyShields] = 0 + UpdateCell(table, my_index, EncodeIndex(dims, other), -absolute_price * *batteries) + other[BuyShields] = addr[BuyShields] + } + } + /* Visit this planet */ + var i uint + for i = 0; i < uint(len(visit())); i++ { + if addr[Visit] & (1 << i) != 0 && visit()[i] == data.i2p[addr[Location]] { + other[Visit] = addr[Visit] & ^(1 << i) + UpdateCell(table, my_index, EncodeIndex(dims, other), 0) + } + } + other[Visit] = addr[Visit] + +} + +func FillCellByBuyingEdens(data planet_data, dims []int, table []State, addr []int) { + my_index := EncodeIndex(dims, addr) + other := make([]int, NumDimensions) + copy(other, addr) + + /* Buy Eden warp units */ + eden_limit := data.Commodities["Eden Warp Units"].Limit + if addr[Edens] > 0 && addr[Edens] <= eden_limit { + relative_price, available := data.Planets[data.i2p[addr[Location]]].RelativePrices["Eden Warp Units"] + if available { + absolute_price := int(float64(data.Commodities["Eden Warp Units"].BasePrice) * float64(relative_price) / 100.0) + for quantity := addr[Edens]; quantity > 0; quantity-- { + other[Edens] = addr[Edens] - quantity + if addr[Hold] != 0 { + other[UnusedCargo] = addr[UnusedCargo] + quantity + } + if other[UnusedCargo] < dims[UnusedCargo] { + UpdateCell(table, my_index, EncodeIndex(dims, other), -absolute_price * quantity) + } + } + other[Edens] = addr[Edens] + other[UnusedCargo] = addr[UnusedCargo] + } + } } func FillStateTable2Iteration(data planet_data, dims []int, table []State, @@ -390,8 +498,8 @@ addr []int, f func(planet_data, []int, []State, []int)) { 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[NeedFighters] = 0; addr[NeedFighters] < dims[NeedFighters]; addr[NeedFighters]++ { - for addr[NeedShields] = 0; addr[NeedShields] < dims[NeedShields]; addr[NeedShields]++ { + 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) } @@ -403,16 +511,15 @@ addr []int, f func(planet_data, []int, []State, []int)) { } func FillStateTable2(data planet_data, dims []int, table []State, -fuel_remaining, edens_remaining int, planet string, barrier chan<- bool) { - addr := make([]int, len(dims)) - addr[Edens] = edens_remaining - addr[Fuel] = fuel_remaining - addr[Location] = data.p2i[planet] +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) - barrier <- true + FillStateTable2Iteration(data, dims, table, addr, FillCellByBuyingEdens) + if barrier != nil { + barrier <- true + } } /* Filling the state table is a set of nested for loops NumDimensions deep. @@ -438,10 +545,27 @@ func FillStateTable1(data planet_data, dims []int, table []State) { 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 { - go FillStateTable2(data, dims, table, fuel_remaining, - edens_remaining, planet, barrier) + 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 @@ -457,17 +581,19 @@ func FindBestState(data planet_data, dims []int, table []State) int { addr := make([]int, NumDimensions) addr[Edens] = *end_edens addr[Cloaks] = dims[Cloaks] - 1 - addr[NeedFighters] = dims[NeedFighters] - 1 - addr[NeedShields] = dims[NeedShields] - 1 + addr[BuyFighters] = dims[BuyFighters] - 1 + addr[BuyShields] = dims[BuyShields] - 1 addr[Visit] = dims[Visit] - 1 // Fuel, Hold, UnusedCargo left at 0 max_index := -1 max_value := 0 for addr[Location] = 0; addr[Location] < dims[Location]; addr[Location]++ { - index := EncodeIndex(dims, addr) - if table[index].value > max_value { - max_value = table[index].value - max_index = index + 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 @@ -487,33 +613,52 @@ func Commas(n int) (s string) { 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 { - line := fmt.Sprintf("%13v", Commas(table[index].value)) + var line string addr := DecodeIndex(dims, index) prev := DecodeIndex(dims, table[index].from) - if addr[Location] != prev[Location] { + if addr[Fuel] != prev[Fuel] { from := data.i2p[prev[Location]] to := data.i2p[addr[Location]] - if addr[Fuel] != prev[Fuel] { - line += fmt.Sprintf(" Jump from %v to %v (%v reactor units)", from, to, prev[Fuel]-addr[Fuel]) - } else if addr[Edens] != prev[Edens] { - line += fmt.Sprintf(" Eden warp from %v to %v", from, to) - } else { - panic("Traveling without fuel?") - } + 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]]) + 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]]) + line += fmt.Sprintf("Buy %v %v", quantity, data.i2c[addr[Hold]]) } else { panic("Switched cargo?") } } - description = append(description, line) + 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 } @@ -544,7 +689,25 @@ func IndexCommodities(m *map[string]Commodity, start_at int) (map[string]int, [] func main() { flag.Parse() + if *cpuprofile != "" { + f, err := os.Create(*cpuprofile) + if err != nil { + panic(err) + } + pprof.StartCPUProfile(f) + defer pprof.StopCPUProfile() + } data := ReadData() + if *drone_price > 0 { + temp := data.Commodities["Fighter Drones"] + temp.BasePrice = *drone_price + data.Commodities["Fighter Drones"] = temp + } + if *battery_price > 0 { + temp := data.Commodities["Shield Batterys"] + temp.BasePrice = *battery_price + data.Commodities["Shield Batterys"] = temp + } data.p2i, data.i2p = IndexPlanets(&data.Planets, 0) data.c2i, data.i2c = IndexCommodities(&data.Commodities, 1) dims := DimensionSizes(data) @@ -554,8 +717,6 @@ func main() { if best == -1 { print("Cannot acheive success criteria\n") } else { - fmt.Printf("Best state: %v (%v) with $%v\n", - best, DecodeIndex(dims, best), Commas(table[best].value)) description := DescribePath(data, dims, table, best) for i := len(description) - 1; i >= 0; i-- { fmt.Println(description[i])