aoc201617

Documentation

Index

• Variables
• func Run(key string)
• func RunBreadthFirst(maze *Maze, key string)
• func RunDepthFirst(maze *Maze, key string)
• type Dir
  • func GetOpenDirs(path string) (rtn []*Dir)
• type Maze
  • func (m *Maze) BreadthFirstSearch(paths []Path) *Path
  • func (m *Maze) DepthFirstSearch(key string, findAll bool) []string
  • func (m *Maze) DepthFirstSearchExt(pathCurrent string, x int, y int, exhaustive bool, pathAcc *[]string) bool
  • func (m *Maze) Move(x, y, xd, yd int) (int, int)
• type Path

Examples

• Run

Variables

var Dirs = []Dir{
	{"U", 0, -1},
	{"D", 0, 1},
	{"L", -1, 0},
	{"R", 1, 0},
}

Dirs defines the direction updates for each cardinal point;

Functions

func Run

func Run(key string)

Example

Run("pvhmgsws")

Output:

Breadth First
Shortest: (10) DRRDRLDURD
Depth First
Shortest: (10) DRRDRLDURD
Longest: (618) DRRDRLDURLLRURLDDULDULDURUUDRLRLRDULLRDUURDULDUDDURLRLLRLDRUULRLRLRDRULLRDUDDDUULURDRRLDDLLUDRURLRUURLDDUDLURDUULRDUDURDDLRLLUDURRLUDRULDRUDDLLLRLRUDRLRRUULRLLDURDLLRLRDUDLURURLDRURDLUDRDLUULDRDDLRUULRDUULRDLDLDRLUUURRRLDDULDLUURLRLRLDRDRLULURDDRUDURUDULLRLRDRUDDLRLLDLRURLDRLURDUUDLUDDLRUULRRULDLURRRLDRLUDLDLRLRLRDUUDDLRLUURDDRUDLURRLRULRDLLLRUURRDLDDULUURDLRLDDURUDURLDULUDLDUDUUDRUDRUDULRDDLLRURRLRDLLDULRURLDRURLUDULRLDRULDDLRDRURUDLRUULRDDLRLUDRLUDDUULRDUDLDUUDRULDRUDURLULRDDRULDLLRUDDUUDDURLULDURRDRLDULUDLRLDURULRRDRLLLDUUDURRDDLRULDUUDUURDDLRDUDUULDUDDUURLRURDLULDRDDUDUUDLUDLRUDDUULDRRLUUDDRRULDDURUDULURDDD

func RunBreadthFirst

func RunBreadthFirst(
	maze *Maze,
	key string,
)

RunBreadthFirst runs a breadth first search and reports the results.

key is the maze key specified in the problem.

func RunDepthFirst

func RunDepthFirst(
	maze *Maze,
	key string,
)

RunDepthFirst runs a depth first search and reports the results.//

key is the maze key specified in the problem.

Types

type Dir

type Dir struct {
	Path   string
	DX, DY int
}

Dir defines the direction updates for a cardinal point;

func GetOpenDirs

func GetOpenDirs(path string) (rtn []*Dir)

GetOpenDirs gets the open directions for path, based on the algorithm in the problem statement.

type Maze

type Maze struct {
	XSize, YSize   int
	XStart, YStart int
	XGoal, YGoal   int
}

Maze defines the structure of the maze. Since all the internal doors are computed based on the path, the internals of the maze need not be stored.

func (*Maze) BreadthFirstSearch

func (m *Maze) BreadthFirstSearch(
	paths []Path,
) *Path

BreadthFirstSearch runs a breadth first search.

paths is the list of paths (plus key) at the search front. Initially, this contains only the key specified in the problem.

func (*Maze) DepthFirstSearch

func (m *Maze) DepthFirstSearch(
	key string,
	findAll bool,
) []string

DepthFirstSearch runs a depth first search.

key is the maze key specified in the problem.

If findAll is true, all valid paths are returned. If findAll is false, only the first valid path is returned.

func (*Maze) DepthFirstSearchExt

func (m *Maze) DepthFirstSearchExt(
	pathCurrent string,
	x int,
	y int,
	exhaustive bool,
	pathAcc *[]string,
) bool

DepthFirstSearchExt runs a depth first search.

pathCurrent is the path to this point, including the key specified in the problem.

x and y are the current position. (Cheaper to pass than to re-compute from pathCurrent.)

If exhaustive is true, all valid paths are returned. If exhaustive is false, only the first valid path is returned.

pathAcc accumulates a list of valid paths.

func (*Maze) Move

func (m *Maze) Move(x, y, xd, yd int) (int, int)

Move adds xd and yd to x and y, and if valid, returns the updated (x, y) values. If invalid, it returns (-1, -1)

type Path

type Path struct {
	Path string
	X, Y int
}

Path is used mainly to cache X, Y values for breadth first search, and connect them to the Path.Path. This is cheaper than re-computing them from Path.Path.