astar

Documentation

Index

• Variables
• type Arcade
  • func (a *Arcade) AStar() Path
• type Button
  • func (b *Button) String() string
• type Location
  • func (l Location) Add(other Location) Location
• type Node
• type Path
  • func (p Path) Cost() (cost int)
  • func (p Path) Count() map[string]int
  • func (p Path) String() string
• type PathFinder
  • func (p PathFinder) EstimatedCost(a *Arcade) int
  • func (p PathFinder) Neighbors(a *Arcade) []PathFinder
• type PriorityQueue
  • func (pq PriorityQueue) Len() int
  • func (pq PriorityQueue) Less(i, j int) bool
  • func (pq *PriorityQueue) Pop() interface{}
  • func (pq *PriorityQueue) Push(x interface{})
  • func (pq PriorityQueue) Swap(i, j int)

Variables

var ORIGIN = Location{X: 0, Y: 0}

Types

type Arcade

type Arcade struct {
	Prize      Location
	Buttons    map[string]*Button
	MaxPresses int
}

func (*Arcade) AStar

func (a *Arcade) AStar() Path

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 Button

type Button struct {
	ID        string
	Increment Location
	Tokens    int
	// contains filtered or unexported fields
}

func (*Button) String

func (b *Button) String() string

type Location

type Location struct {
	X, Y int
}

func (Location) Add

func (l Location) Add(other Location) Location

type Node

type Node struct {
	// contains filtered or unexported fields
}

A node represents a possible state in the grid

type Path

type Path []*Node

A Path represents a sequence of operations to reach the goal

func (Path) Cost

func (p Path) Cost() (cost int)

func (Path) Count

func (p Path) Count() map[string]int

func (Path) String

func (p Path) String() string

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(a *Arcade) 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(a *Arcade) []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)