DFS Go solution to Eschaton

main.go

package main

import (
	"encoding/json"
	"fmt"
	"io/ioutil"
	"os"
)

// RouteState represents the current state of a given route
type RouteState struct {
	parent       *RouteState
	time         int
	position     int
	velocity     int
	acceleration int
}

// Route generates a slice of r's route from its parents
func (r *RouteState) Route() []int {
	route := make([]int, r.time)
	for p := r; p != nil; p = p.parent {
		route[p.time-1] = p.acceleration
	}
	return route
}

// IsValid determines if r is allowed to exist in c
func (r *RouteState) IsValid(c *Chart) bool {
	pastBlast := r.time/c.TPerBlastMove <= r.position
	if r.position == 0 {
		return pastBlast
	}
	if r.position < 0 {
		return false
	}
	currentBelt := c.Asteroids[r.position-1]
	noAsteroid := (r.time+currentBelt.Offset)%currentBelt.TPerAsteroidCycle != 0
	return noAsteroid && pastBlast
}

// IsSolution determines whether r is a solution for c
func (r *RouteState) IsSolution(c *Chart) bool {
	return r.position > len(c.Asteroids)
}

// Next returns the next RouteState for a given acceleration
func (r *RouteState) Next(acceleration int) *RouteState {
	v := r.velocity + acceleration
	return &RouteState{
		parent:       r,
		time:         r.time + 1,
		position:     r.position + v,
		velocity:     v,
		acceleration: acceleration,
	}
}

// DepthFirstSearch searches the highest average velocity routes first
// in order to find a solution to the Chart c
// It returns the route of the first solution
func (r *RouteState) DepthFirstSearch(c *Chart) []int {
	if r.IsSolution(c) {
		return r.Route()
	}

	if !r.IsValid(c) {
		return nil
	}

	slice := []int{1, 0, -1}

	for _, a := range slice {
		solution := r.Next(a).DepthFirstSearch(c)
		if solution != nil {
			return solution
		}
	}
	return nil
}

// Chart is a mapping of the Eschaton json input
type Chart struct {
	Asteroids []struct {
		TPerAsteroidCycle int `json:"t_per_asteroid_cycle"`
		Offset            int `json:"offset"`
	} `json:"asteroids"`
	TPerBlastMove int `json:"t_per_blast_move"`
}

func processRoute(solutions chan []int, r *RouteState, c *Chart) {
	solution := r.DepthFirstSearch(c)
	if solution != nil {
		solutions <- solution
	}
}

func main() {
	file, e := ioutil.ReadFile("./path.json")
	if e != nil {
		fmt.Printf("File error: %v\n", e)
		os.Exit(1)
	}
	var chart Chart
	json.Unmarshal(file, &chart)

	root := RouteState{
		parent:       nil,
		time:         1,
		position:     1,
		velocity:     1,
		acceleration: 1,
	}

	r := []*RouteState{
		root.Next(1),
		root.Next(0),
		root.Next(-1),
	}

	solutions := make(chan []int)

	for _, route := range r {
		go processRoute(solutions, route, &chart)
	}

	fmt.Println(<-solutions)
}