Skip to content

Instantly share code, notes, and snippets.

@butzopower
Created February 13, 2010 06:09
Show Gist options
  • Save butzopower/303281 to your computer and use it in GitHub Desktop.
Save butzopower/303281 to your computer and use it in GitHub Desktop.
=== Note
=== This never revists a node
=== Would like to have it so it can loop around square groups
longestPaths(grid:Grid, goalNodes:Nodes, types:NodeTypes):
paths:Paths = []
for each type in types:
goals:Nodes = nodesForType(goalNodes, type)
while goals != []:
goal = pop(goals)
for each currentGoal in goals:
pathsForGoal:Paths = search(grid, goal, currentGoal, type, append([], goal), [])
path:Path = maxByLength(pathsForGoal)
paths:Paths = append(paths, path)
return paths
search(grid:Grid, currentNode:Node, goalNode:Node, type:NodeType, currentPath:Path, paths:Paths):
if currentNode = goalNode:
return append(paths, currentPath)
if typeOfNode(currentNode) != type:
return paths
above:Node = nodeAbove(grid, currentNode)
if !(contains(currentPath, above)):
paths = append(paths, search(grid, above, currentNode), type, append(currentPath, above),
currentPath, paths)
below:Node = nodeBelow(grid, currentNode)
if !(contains(currentPath, below)):
paths = append(paths, search(grid, below, currentNode), type, append(currentPath, below),
currentPath, paths)
left:Node = nodeLeft(grid, currentNode)
if !(contains(currentPath, left)):
paths = append(paths, search(grid, left, currentNode), type, append(currentPath, left),
currentPath, paths)
right:Node = nodeRight(grid, currentNode)
if !(contains(currentPath, right)):
paths = append(paths, search(grid, right, currentNode), type, append(currentPath, right),
currentPath, paths)
return paths
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment