Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Grid ¶
type Grid struct {
Goal int // The goal to reach by applying operations to the numbers
Numbers []int // The numbers to apply operations to
ValidOps []ops.Op // The valid operations to apply
IsValidCost func(int) bool // A function to validate the cost of the operation
}
A Grid represents the problem to solve
func (*Grid) AStar ¶
Runs the A* algorithm to find the path to the goal, if possible. The algorithm considers the next number in the array as the reference. The next states are built by combining the set of valid operations with the next number. The algorithm stops when the goal is reached or there are no more nodes to explore.
If `exhaustive` is false, the algorithm will try to find any path that yields the result. Otherwise, it will try to find the path that uses all the numbers in the array. The `cost` always refers the cumulative result of the operations. Depending on the operations available in the grid, it's possible to have multiple paths to the goal. But it's also possible that a path is unreachable from a certain state (e.g. the cost is greater than the goal and there are no "sub" operations). The `IsValidCost` function is used to discard states - thus optimize the search - by checking if the cost is valid. Simply returning `true` will make the algorithm to explore all the states, which could take longer.
type Node ¶
type Node struct {
// contains filtered or unexported fields
}
A node represents a possible state in the grid
type PathFinder ¶
type PathFinder struct {
// contains filtered or unexported fields
}
A PathFinder represents the possible states we can reach in the grid
func (PathFinder) EstimatedCost ¶
func (p PathFinder) EstimatedCost(g *Grid) int
EstimatedCost returns the estimated cost to reach the goal. The closer the number is to the end of the array, the lower the cost
func (PathFinder) Neighbors ¶
func (p PathFinder) Neighbors(g *Grid) []PathFinder
Neighbors returns the possible states we can reach from the current state
type PriorityQueue ¶
type PriorityQueue []*Node
A PriorityQueue implements heap.Interface and holds Nodes. The PriorityQueue is used to track open nodes by rank.
func (PriorityQueue) Len ¶
func (pq PriorityQueue) Len() int
func (PriorityQueue) Less ¶
func (pq PriorityQueue) Less(i, j int) bool
func (*PriorityQueue) Pop ¶
func (pq *PriorityQueue) Pop() interface{}
func (*PriorityQueue) Push ¶
func (pq *PriorityQueue) Push(x interface{})
func (PriorityQueue) Swap ¶
func (pq PriorityQueue) Swap(i, j int)
Source Files